CS 70 Su23: Lecture 24 (6B)

Markov Chains II: hitting time, probability of state A before state B

A quick recap

Markov chain (it’s a directed graph), defined by:

• States (nodes)
• Transition probabilities (edges)
• self-edges are allowed
• it’s probability, so all the outgoing edges have to add to 1
• do all incoming edges have to add to 1?¹
• Initial probabilities (how likely you are to start at each state)

Markov chains are amnesic: the transition probabilities only depend on the current state

Hitting time

Given a starting state in a Markov Chain, what is the expected number of steps (transitions) until we reach some other state?

Suppose that:

• Pr[A→B] = 1
• Pr[B→C] = 1

If we start at A, how many steps, on average, will it take to get to C?

• 2 steps

First-step equations

Random variables are our friend. Let’s define:

• T_AB = the number of steps it takes to go from state A to state B

If you only care about one of the states, you can simplify this (for example):

• T_A = the number of steps it takes to go from A to C
• this is useful shorthand if your markov chain has a clear “end state”

We are interested in computing E[T_A], for some state A (to reach C).

You will also see this as a function (the notes uses β):

• T(A) = the expected number of steps to reach state C from state A
• Note: this is an expectation! Be careful when reading to double check what the variable represents

First-step equations

What is T(C)?

• E[T_CC] = 0 (you’re already there!)

Example 1: first-step equations (with numbers)

What is T(A)?

• T(A) = 1 + ⅕T(A) + ⅘T(B)

What is T(B)?

• T(B) = 1 + ½T(A) + ½T(C)

⅕

7/10

3/10

½

Example 1: first-step equations (with numbers)

T(A) = 1 + ⅕T(A) + ⅘T(B)

T(B) = 1 + ½T(A) + ½T(C)

= 1+ ½T(A)

T(A) = 1 + ⅕T(A) + ⅘(1 + ½T(A))

= 1 + ⅕T(A) + ⅘ + ⅖T(A)

= 9/5 + ⅗T(A)

⅖T(A) = 9/5

T(A) = 9/2

First-step equations

In general, the expected number of steps to state Y from state X is:

• T_Y(X) = 1 + ∑_Z Pr[X→Z] · T_Y(Z)
• T_Y(Y) = 0

In other words, we have to go somewhere, and with some probability, we end up at a different state, which takes some expected number of steps to get to state Y (if you start when you want to go, it takes 0 steps to get there).

(again, if Y is implied, you can omit it)

Example 2: more numbers

We want to reach state 1. What is T₁(2)?

T(2) = 1 + ⅓T(1) + ⅔T(3)

= 1 + ⅔T(3)

T(3) = 1 + ½T(1) + ½T(3)

= 1 + ½T(3)

T(3) = 2

T(2) = 7/3

Example 3: Geometric… again

How can we represent a geometric distribution as a Markov Chain?

T(0) = 1 + pT(1) + (1 - p)T(0)

= 1 + T(0) - pT(0)

pT(0) = 1

T(0) = 1/p

​

Example 4: Geometric… again (again)

Now what if we want to flip until we get 2 heads in a row?

Example 4: Geometric… again (again)

​

T(0) = 1+ pT(1) + (1 - p)T(0)

T(1) = 1+ pT(2) + (1 - p)T(0)

= 1 + T(0) - pT(0)

T(0) = 1 + p(1 + T(0) - pT(0)) + (1 - p)T(0)

T(0) = 1 + p + pT(0) - p²T(0) + T(0) - pT(0)

T(0) = (1 + p)/p²

Return time

We start at state X. What is the expected number of steps until we return to state X?

• R_X = 1 + ∑_Z Pr[X→Z] · T_X(Z)

In other words, we have to go somewhere, and with some probability, we end up at a different state, which takes some expected number of steps to get to state 1.

Example 5: the numbers from before

We start in state 1. What is R₁?

R₁ = 1 + ¼ T(1) + ½T(2) + ¼T(3)

= 1 + 0 + ½ · 7/3 + ¼ · 2

= 6/6 + 7/6 + 3/6

= 16/6

= 8/3

Probability of state A before state B

Given a starting state, what is the probability we reach some state before some other state?

Suppose that:

• Pr[A→B] = 1
• Pr[B→C] = 1

If we start at A, what is the probability of reaching C before B?

• 0

Probability of state A before state B

Let P(X) = the probability that you reach state A before state B from state X (for some specified states A and B).

• This is, again, a function (the notes uses α)
• If you want to be very precise, you can use subscripts for clarity
• Example: P_CB(X) = probability if reaching C before B, starting from X

Example 6: probability of C before B

Returning to our example:

Let’s say we are interested in whether we visit C before B.

What is P(C)?

• 1

What is P(B)?

• 0

Example 6: probability of C before B

Returning to our example:

What is P(A)?

P(A) = Pr[A→A] · P(A)

+ Pr[A→B] · P(B)

+ Pr[A→C] · P(C)

= Pr[A→A] · P(A)

+ Pr[A→C] · P(C)

Probability of state A before state B

In general, the probability of reaching state A before state B, starting from state X, is:

• P_AB(X) = ∑_Y Pr[X→Y] · P_AB(Y)
• P_AB(A) = 1
• P_AB(B) = 0

(again, if A and B are implied, you can omit them)

Example 7: gamble responsibly

You are playing a game where you flip a coin with probability p. If it lands heads, you win $1. Otherwise, you lose $1. The game ends when you have $0. What is the probability that you earn $N before you run out of money?

Let’s write out the equations:

• P(0) = 0
• P(N) = 1
• P(n) = p · P(n + 1) + (1 - p) · P(n - 1), for 0 < n < N

With the magic of algebra, we have P(n) = (1 - ((1 - p)/p)ⁿ) / (1 - ((1 - p)/p)^N)