Xnis the State That the System Is in at Time N

Chapter 16 Markov Chain

◎DEFINITION：

A Markov chain is a stochastic processsuch that

where

Pij is the probability that the process will make a transition into state j when it is currently in state i.

Xnis the state that the system is in at time n.

▲Markov property:

Given all the past states X0, X1,…,Xn ,the probability of any future state Xn+1 is independent of X0, X1,…,Xn-1(past states), and depends only on Xn(current state). That is, the future state is independent of past states given that we know the present state.

▲State transition diagram:

▲One-step transition matrix:

If does not depend on the time, then we have a homogeneous Markov chain.

The one-step transition probability matrix P is the matrix whose entry in the -th row and the -th column is such as

▲Stationary transition probability:

If ….., then the (one-step) transition probabilities are stationary.

That is, Pij does not change overtime.

▲Examples:

1. A Random Walk Model:

1. Weather Problem I :

If it rains today =>it will rain tomorrow with prob.

If it does not rain today =>it will rain tomorrow with prob.

Let state 0 = the state when it rains,

State 1 = the state when it does not rain and

= the state at time

Then, {, n=1,2,…}is a two-state Markov chain.

1. A Gambling Model : (random walk with barriers)

Each play i. wins $1 with prob. p

ii. losses $1 with prob. 1-p

Quit when the player broke or has $N

Note: States 0 and N are called absorbing states. (吸收狀態)

1. Weather Problem II : (Transforming a process into a Markov chain)

P{rain tomorrow | rain today, rain yesterday}=0.7

P{rain tomorrow | rain today, not rain yesterday}=0.5

P{rain tomorrow | not rain today, rain yesterday}=0.4

P{rain tomorrow | not rain today, not rain yesterday}=0.2

Note : If we let denote the state at time n, then, {,n=1,2,…}is not a Markov chain.

=>Define state RR: (Rain, Rain)

state RN: (Rain, Not Rain)

state NR: (Not Rain, Rain)

state NN: (Not Rain, Not Rain)

1. Inventory Example (p.16-2)

某相機店儲存某種可以每週訂貨之相機

Let= demand during the n-th week

and ( independently &identically distributed)

=number of cameras on hand now.

=number of cameras at the end of week 1…..

=number of cameras at the end of week n.

if no camera stock in stock, order 3 cameras.

Order policy: if any camera in stock, no order.

Sale lose : if .

Expression of : max{,

max{,

(1)Why is a Markov Chain?

(2) Describe its One-step Transition Matrix.

(3)State its transition diagram.

【Ex1_1】若某製造機器在每天開始於運作會有0.05 的機率會在這天之內故障。當故障時，此機器要隔天修理，並於當天結束時修好試辨識每天結束時之三個狀態，並建立ㄧ步移轉矩陣。

【Ex1_2】某電器行銷售某一型電熱器，根據過去銷售記錄得知每天需求機率如下表：

Dt / 0 / 1 / 2 / 3
pt / 0.3 / 0.4 / 0.2 / 0.1

又此電器行存用（s,S）的存貨政策（亦即：若存貨水準I≦S，則下訂單使得I=S），並設定s=0，S=3。狀態間的關係為：

Xt+1＝ Xt , Xt＞Dt

3 , Xt≦Dt

試求建立單階轉換機率矩陣。

【Ex1_3】若有一直銷員在A、B、C三個城市推銷化妝品，但他從不連續兩天在同一城市推銷。若他第一天在A城推銷，則第二天就到B城推銷。若他第一天在B城或C城推銷，則第二天他喜歡在A城推銷2倍於在另一城市，試求轉換機率矩陣。

▲N-step transition probability:

is the probability that a process is in state will be in state after transitions.

P(n) is then-step transition probability matrix whose entry in the-th row and the-th column is such as

P(1)=P is the one-step transition probability matrix.

▲Properties of

▲Chapman-Kolmogorov Equations:

(1)

(2)

▲Example:

1. Weather Problem I :

1. Weather Problem II:

Find the probability P{rain Thursday| rain Monday, rain Tuesday} = ?

【Ex2_1】假設若今天下雨，則明天下雨機率為，假設若今天晴天，則明天晴天機率為。

（1）建構這馬可夫鍵的（一步）轉移矩陣。

（2）試以and 表示各天氣狀態之穩態機率。

（3）試使用Chapman-Kolmogorov方程式求解(n步)轉移矩陣, 若, 。

【Ex2_2】在【Ex1_2】(p. 16_4)中，若某天早上有三台電熱器，則兩天後仍為三台的機率？又若某天早上有三台電熱器，則四天後仍為三台的機率？

【Ex2_3】假設某化妝品被兩家大廠商瓜分。若某人這次購買A品牌，則有70%的可能，下次她將會再購買A品牌。若某人這次購買B品牌，則有90%的可能，下次她將會再購買B品牌。

（1）如果某人目前是A品牌的購買者，則兩次後將購買B品牌的機率為何?

（2）如果某人目前是B品牌的購買者，則三次後將購買B品牌的機率為何?

【Ex2_4】奇易公司分成廠務、管理、業務三個部門，為培訓中階主管，半年輪調一次，但並無固定方式，可能一年後又調回原部門，其輪調情況如下：

-原來在業務部，下一個階段在業務及廠務部門的機會各半。

-原來在廠務部，下一個階段在廠務及管理部門的機會各半。

-原來在管理部，下一個階段有3/4的機會在業務部，1/4的機會在廠務部。

（1）試建構這馬可夫鍵的（一步）轉移矩陣。

（2）試問原來在業務部門，經過兩個階段後仍在業務部門的機率?

◎CLASSIFICATION OF STATES:

<def> Accessible (可達性)

A stateis said to be accessible from a stateif for some,

denoted by←or→

<def>

<def> Communicate (互通性)

If←or→, then andare said to communicate denoted by.

▲Example:

1.

2. Inventory Example

3. Gambling Example

<Properties> Communication is an equivalence relation, that is,

1.(reflexive). (反射性)

2. If ,then (symmetric). (對稱性)

3. If and ,then(transitive). (遞移性)

<def> Class(類別)

If ,then and are in the same class.

<def > Irreducible (不可約的)

A Markov chain is irreducible if there is only one class, that is,all the states communicate with each other.

<def> Recurrent (再生態)(重現狀態)

Let be the probability that starting in state ,the process will ever re-enter state .

If, then state is said to be recurrent.

Note: If state is recurrent, the process will re-enter state infinitely often.

<def>Transient (暫態)

If, then state is said to be transient.

Note: If stateis transient, the number of time periods that process will be in stateis a geometric random variable with parameter .

<def> Absorbing(吸態)

If , entering this state, the process will never leave this state again.

That is, if a stateis absorbing, then.

▲Example:

1. Gambling Example

2. Another Example

<def> Period

The periodof stateis the largest integer such that wheneveris

Not divisible by. That is , is the greatest common divisor of allsuch

that .

<def > class property

(1)All states in a class are either recurrent or transient.

(2)In a finite state Markov Chain, not all states can be transient.The process must be some state that are recurrent.

(3)All states in an irreducible finite state Markov Chain are recurrent.

<def> Aperiodic（無週期的）

A state with period 1 is said to be aperiodic.

▲Example:

<Corollary推論 Recurrency is a class property. That is,if and state is recurrent,

then state is recurrent also.

<Theorem定理 Periodicity is a class property.

=>if, then

=>if and are in the same class, then they have the same period.

<defErgodicState

A state is called ergodic if it is recurrent and aperiodic.

<def> ErgodicMarkov Chain

A Markov chain is called erdodic if it is irreducible and all states are ergodic.

【Ex3_1】Given the following one-step transition probability,

(i) Which states are transient? (ii) Which states are recurrent?

(iii) Which states are absorbing? (iv) Is this a Markov Chain?

【Ex3_2】考慮以下馬可夫鏈：

（1）哪些狀態為暫態? 哪些狀態為再生態? 哪些狀態為吸態?

（2）求各狀態之週期數?

（3）此馬可夫鏈是否為ergodic (Why)?

P1= / P2=

＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋

◎Long –Run Properties of Markov Chains

▲Steady-State (or Limiting) Probabilities: (n→∞)

<Theorem> For any irreducible, ergodic Markov chain, exists and is independent of . And letting or , thenis the unique non-negative solution which satisfies the following steady-state equations (穩態方程式)

or =P if =

<Corollary > If = be the steady-state probabilities for a finite state Markov Chain, then we have =P.

Note:

1.

As .

2. As, the limiting probability that the process will be in state is which i is independent of the initial state. (stationary)

3. As, is the long-run proportion of time that the process will be in state.

4. For an irreducible, recurrent, periodic Markov Chain, is interpreted as the long-run proportion of time that the process will be in state.

Matrix Formof Steady-State (or Limiting) Probabilities:

For =P(I-P)=0 or (I-P)=0 (whereis the transpose of ).

Note:

To have non-trivial solution, det(I-P)0 or det(I-P)0

Examples:

1. Another Example:

Let, find the Steady-State probabilities.

【Ex4_1】在【Ex1_3】(p. 16_4)中，試求在長期間，他在各城市A, B 與C城推銷之機率為何？

A / B / C
A / 0.7 / 0.2 / 0.1
B / 0.2 / 0.75 / 0.05
C / 0.1 / 0.1 / 0.8

【Ex4_2】西海岸某領先啤酒廠（標示為A）雇用一位OR分析師來分析其市場定位，這啤酒廠特別關切它的競爭對手（標示為B）。分析師相信顧客對品牌的變換可用三個狀態的馬可夫鏈來建立模式，狀態A及B分別代表顧客飲用前述兩個啤酒廠所生產的啤酒，狀態為C代表所有其它品牌的啤酒。每個月蒐集資料後，分析師依過去資料建立以下（一步）轉移矩陣表列於右，試求兩個主要啤酒廠的穩態市場佔有率為何？

【Ex4_3】某香皂公司專門銷售一種特殊型的洗澡香皂，其銷售量在兩個水準間波動---低水準及高水準，高低取決於兩個因素：（1）是否做促銷及（2）競爭對手是否有推出及促銷新產品。第二個因素非公司所能控制，但這公司嘗試決定自己應有的促銷策略。例如，行銷經理的提議是在銷售量低的時候做促銷，銷售量高時則不做促銷。若每季促銷成本為1.6百萬元，當某季做促銷時，下一季有高銷售量的機率為0.5或0.7，取決於該季銷售量是低還是高。而下一季有高銷售量的機率在不做促銷時則降為0.3或0.5。當銷售量高時，這公司每季的利潤（不含促銷成本）為5百萬，若銷售量低則為3百萬（以下皆以百萬為單位）。

（1）建構以下各種促銷策略的（一步）轉移矩陣：（i）皆做促銷（ii）依照行銷經理的策略。

（2）求解兩種策略的各別穩態機率。

＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋

▲Expected Average Cost per unit time

For an irreducible finite-state Markov chain, letCost incurred in state , where , then is a random variable which is independent of time n.

 Expected (long-run) average cost for the first n periods = .

Let , the long term Expected Average Cost =

(can be shown)

Inventory Example:

Let , find the expected (long-run) inventory cost.

＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋

◎First Passage Time

▲<def>First Passage Time from state state

= the number of transitions from state state for the first time

Note: If, then

= recurrent time for state

= the first passage time required to return to the initial state

Inventory Example:

If

Expected first passage time

Inventory Example:



1. Expected Recurrent Time =

Inventory Example:

【Ex5_1】

1. 某一馬可夫鏈有三個狀態，其一步轉移矩陣P 如下，試求每一狀態的期望再生時間(mii) 為何？

【Ex5_2】若某製造機器在每天開始於運作會有0.05 的機率會在這天之內故障。當故障時，此機器要隔天修理，並於當天結束時修好。

（1）試辨識每天結束時之三個狀態，並建立ㄧ步移轉矩陣。

（2）試求出當某機器完成修理後，到下一次故障之期望天數。

【Ex5_3】某製造商有一台機器，在每天開始運作，而有0.1的機率會在這一天之內故障, 當故障發生時，這機器要在隔天修理，而會在當天終了時修好。

(1)辨別每天終了時機器的三個狀態，然後建構(一步)轉移矩陣，將此機器狀態演進過程以一個馬可夫鏈來建立模式。

(2)求當修理完成後，這機器持續運轉到下一次故障的期望天數。

＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋

◎Absorbing States

▲<def> AbsorbingState(吸態)

If , entering this state, the process will never leave this state again.

That is, if a stateis absorbing, then.

▲Let state is an absorbingstate

the probability of absorption from . We have

.

where

if state is recurrent (another absorbing state),

Gambling Example:

Player A has $2, Player B has $2, bet $1 each time until one is broken

P(A wins) = 1/3, P(B wins) = 2/3

(1)Describe its One-step Transition Matrix.

(2)State its transition diagram. Which states are absorbing? Which states are recurrent?

(3)State the probability of losing and winning for Player A?

Another Example:

一家百貨公司將顧客帳單分為下列狀態:

State 0: Fully Paid

State 1: 1~30 days delay

State 2: 31~60 days delay

State 3: bad debts

Determine

(1)the probability of a 1~30 days delay customer which will lead up to a bad debt.

(2)the probability of a 31~60 days delay customer which will lead up to a bad debt.

【Ex6_1】

1 1/4 1/4 1/2 0

P＝ 2 1/3 1/3 0 1/3

3 0 0 1 0

4 0 0 0 1

試求（1）從分別由1與2開始，長時間以後停留在3的機率。

（2）從分別由1與2開始，長時間以後停留在4的機率。

【Ex6_2】某公司將其客戶的A/R情形分為四類：1.已付清 2.欠款一個月 3.欠款1至2個月 4.壞帳。因過去的記錄，該公司得以下的轉換矩陣：

1 1 0 0 0

P＝ 2 0.5 0.35 0.15 0

3 0.35 0.25 0 0.4

4 0 0 0 1

試問（1）欠款一個月內的A/R最後成為壞帳的機率。

（2）欠款一至兩個月內的A/R最後成為壞帳的機率。

【Ex6_3】某錄影機製造公司聲稱若錄影機在2年內故障提供完整的置換保證。基於編譯過的資料，公司知道只有2%的錄影機會在一年內故障，有5%的錄影機會在第一年倖存而在第二年內故障。這保證不包括已經置換過的錄影機。

(1) 建構錄影機的狀態演進過程的馬可夫鏈模式的（一步）轉移矩陣，其中包括產品置換保證及錄影機安然渡過保證期間的兩個吸收狀態。

(2) 求解這公司需要履行產品置換保證的機率。

【Ex6_4】Consider the following gambler’s ruin problem. A gamble bets $1 on each play of a game. Each time, he has a probability of of winning and probability of losing the dollar bet. He will continue to play until he goes broke or nets a fortune of dollars. Let denote the number of dollars possessed by the gambler after the nth play of the game. Then {} is a Markov chain. The gambler starts with dollars, where is a positive integer less than .

(1)(*) Construct the (one-step) transition matrix of the Markov chain and find out the classes of the Markov chain

(2)Let and . Please find out the probability of the gambler to lose the dollar bet if he starts with $1 and $2, respectively.

16-1