Math 311

Class 10

Example 4.12

In a sequence of independent coin flips, let \(N\) denote the number of flips until there are 3 consecutive heads.

  • Find \(\operatorname{P}(N \le 8)\)
  • Find \(\operatorname{P}(N = 8)\)

States:

0: Either we just started or we just flipped a tail

1: We just flipped a head, either as a first flip, or after a tail

2: Second head in a row

3: Either we just flipped the third head in a row, or we had 3 heads in a row in the past.

Example 4.12 cont.

 

 

\[\Large\quad\mathbf{P} = \begin{bmatrix} .5 & .5 & 0 & 0 \\ .5 & 0 & .5 & 0 \\ .5 & 0 & 0 & .5 \\ 0 & 0 & 0 & \color{red}{1} \end{bmatrix}\]

Example 4.12 calculations

P = [
    .5 .5 0 0
    .5 0 .5 0
    .5 0 0 .5
    0 0 0 1
]
4×4 Matrix{Float64}:
 0.5  0.5  0.0  0.0
 0.5  0.0  0.5  0.0
 0.5  0.0  0.0  0.5
 0.0  0.0  0.0  1.0
P^8
4×4 Matrix{Float64}:
 0.316406  0.171875  0.09375    0.417969
 0.265625  0.144531  0.078125   0.511719
 0.171875  0.09375   0.0507812  0.683594
 0.0       0.0       0.0        1.0
P^7
4×4 Matrix{Float64}:
 0.34375   0.1875    0.101562   0.367188
 0.289062  0.15625   0.0859375  0.46875
 0.1875    0.101562  0.0546875  0.65625
 0.0       0.0       0.0        1.0

Example 4.13 (modified)

Given a Markov Chain with states 1, 2, 3, 4, and 5, with some transition probabilities

  • \(P_{11} = .3\)
  • \(P_{12} = .3\)
  • \(P_{21} = .1\)
  • \(P_{22} = .2\)

Starting at state 1, what is the probability that the first time you enter a state greater than 2 is on step 4?

Random communication

You have 5 stations, a message sent from each station will end up at any of the stations with the following probabilities:

\[\mathbf{P} = \begin{bmatrix} .1 & .2 & .5 & 0 & .2 \\ .3 & 0 & .7 & 0 & 0 \\ .6 & .1 & .3 & 0 & 0 \\ 0 & 0 & 0 & .6 & .4 \\ 0 & 0 & 0 & .3 & .7 \end{bmatrix}\]

Accessible states

Definition: State \(j\) is accessible from state \(i\) if \(P^n_{ij} > 0\) for some \(n\).

Definition: States \(i\) and \(j\) communicate (denoted \(i \leftrightarrow j\)) if \(i\) is accessible from \(j\) and \(j\) is accessible from \(i\).

  • \(i \leftrightarrow i\) (reflexivity)
  • If \(i \leftrightarrow j\) then \(j \leftrightarrow i\) (symmetry)
  • If \(i \leftrightarrow j\) and \(j \leftrightarrow k\) then \(i \leftrightarrow k\) (transitivity)

\({}\leftrightarrow{}\) is an equivalence relation on the set of all states.

It splits the set of states into equivalence classes

Example

\[\mathbf{P} = \begin{bmatrix} .1 & .2 & .5 & 0 & .2 \\ .3 & 0 & .7 & 0 & 0 \\ .6 & .1 & .3 & 0 & 0 \\ 0 & 0 & 0 & .6 & .4 \\ 0 & 0 & 0 & .3 & .7 \end{bmatrix}\]

Examples

  • Weather model
  • Gambling model
  • Distributing balls to urns