Rangkuman

Minggu 2

Definitions

State: possible value a random variable can take

In the case where we are measuring markov chain of whether it rains or not, the state space is $\{\text{it rains},\text{it doesn’t rain}\}$

• State vs sample

Absorbing state: State where the transition probability to itself is 1

All other transition probabilities for such state is 0, and it will ALWAYS transition to itself.

See Examples Gambling model

Process: The entire evolving random system, not just one observation at one time.

Markov chain: random variable at index n+1 is only dependent with the random variable at n, i.e., the previous “state”, and only on that previous state

state n+1 is depedent on n, and only n.

$$P\{X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\dots ,X_1=i_1,X_0=i_0\}=P_{ij}$$

Transition probability ($P_{ij}$): Probability of transitioning from state i to state j in one time step

Transition matrix $\mathbf{P}$: Full set of all $P_{ij}$ in matrix form.

$$\mathbf{P}=\Vert \begin{array}{cccc}{P}_{00}& P_{01}& P_{02}& \cdots \\ P_{10}& P_{11}& P_{12}& \cdots \\ ⋮& ⋮& ⋮& \\ P_{i0}& P_{i1}& P_{i2}& \cdots \\ ⋮& ⋮& ⋮& \end{array}\Vert$$

• Transition matrix example

Chapman-Kolmogorov: Transition probability to go from state i to j in n + m steps.

$P_{ij}^{(n+m)}={\sum }_k{P}_{ik}^{(n)}{P}_{kj}^{(m)}$

We say n + m steps to mathematically say we can decompose any multi-step transition into two parts.

Example:

• 5-step transition from rain to rain =
  • (2 steps to rain, then 3 steps rain→rain) +
  • (2 steps to sunny, then 3 steps sunny→rain)
• 7-step transition:
  • 1-step + 6-step
  • 2-step + 5-step
  • 3-step + 4-step
  • Whatever decomposition is convenient

The equation just formalizes: “to get somewhere in multiple steps, you must pass through some intermediate state.”

n-step Transition Matrix (${\mathbf{P}}^{(n)}$) : Probability that state i goes to j in n + m steps

By Chapman-Kolmogorov equation:

$${\mathbf{P}}^{(n+m)}={\mathbf{P}}^{(n)}+{\mathbf{P}}^{(m)}$$

Also ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$

State vs sample

A sample is a realized observation from a distribution - a concrete outcome you observe.

A state is a possible value the random variable can take - it exists whether or not you’ve observed it.

Example: Transition matrix

Consider state space whether it rains today (state 0) or will it be sunny (state 0).

Let the transition probabilities:

• $P_{00}=\alpha$: Probability it rains (0) today, then stay in rains (0) tomorrow
• $P_{10}=\beta$: Probability It’s sunny (1) today, then change to rains (0) tomorrow

The transition matrix is

$$\mathbf{P}=\Vert \begin{array}{cc}\alpha & 1-\alpha \\ \beta & 1-\beta \end{array}\Vert$$

Where

• $P_{01}=1-\alpha$: Probability it rains (0) today, then change to sunny (1) tomorrow
• $P_{11}=1-\beta$: Probability it’s sunny (1) today, then stay sunny tomorrow

Example: n-step transition matrix

Following from Example Transition matrix, let

$$\mathbf{P}=\Vert \begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\Vert$$

Using Chapman-Kolmogorov equation, we can compute the probability that if today is rains, then 4 days later it will be rains (${\mathbf{P}}_{00}^{(4)}$) as:

$$\begin{array}{rl}{\mathbf{P}}^{(4)}& ={\mathbf{P}}^4\\ & =\Vert \begin{array}{cc}0.5749& 0.4251\\ 0.5668& 0.4332\end{array}\Vert \end{array}$$

Thus, ${\mathbf{P}}_{00}^{(4)}=0.5749$

And,

• $P_{00}^{(4)}=0.5749$: If it rains today, probability it rains 4 days later is 57.49%
• $P_{01}^{(4)}=0.4251$: If it rains today, probability it’s sunny 4 days later is 42.51%
• $P_{10}^{(4)}=0.5668$: If it’s sunny today, probability it rains 4 days later is 56.68%
• $P_{11}^{(4)}=0.4332$: If it’s sunny today, probability it’s sunny 4 days later is 43.32%

Note: Each row sums to 1 (total probability from any starting state).

Examples: More complex n-step transition matrix

Urn Ball Replacement - Step-by-Step Illustration

Setup:

• Urn always has exactly 2 balls (red or blue)
• At each step: pick a ball, replace it with probability 0.8 same color, 0.2 opposite color
• Initial: both balls red (state 2)
• Find: P(5th ball selected is red)

State Space:

• State 0: 0 red balls (both blue)
• State 1: 1 red ball, 1 blue ball
• State 2: 2 red balls (both blue)

Understanding Transitions from State 2 (both red):

You pick a ball. Since both are red, you definitely pick red.

• With prob 0.8: replace with red → stay at 2 red balls (P_{22} = 0.8)
• With prob 0.2: replace with blue → now have 1 red, 1 blue (P_{21} = 0.2)
• P_{20} = 0 (impossible to go from 2 red to 0 red in one step)

Understanding Transitions from State 1 (1 red, 1 blue):

You pick a ball. Equal chance of picking red or blue (each prob 0.5).

Case 1: Pick red (prob 0.5)

• Replace with red (prob 0.8) → still 1R, 1B (state 1)
• Replace with blue (prob 0.2) → now 0R, 2B (state 0)

Case 2: Pick blue (prob 0.5)

• Replace with blue (prob 0.8) → still 1R, 1B (state 1)
• Replace with red (prob 0.2) → now 2R, 0B (state 2)

So:

• P_{10} = 0.5 × 0.2 = 0.1
• P_{11} = 0.5 × 0.8 + 0.5 × 0.8 = 0.8
• P_{12} = 0.5 × 0.2 = 0.1

Understanding Transitions from State 0 (both blue):

Symmetric to state 2:

• P_{00} = 0.8 (pick blue, replace with blue)
• P_{01} = 0.2 (pick blue, replace with red)
• P_{02} = 0

Transition Matrix: $\mathbf{P}=\left[\begin{array}{ccccccc}0.8& 0.2& 00.1& 0.8& 0.10& 0.2& 0.8\end{array}\right]$

Finding P(5th ball is red):

The 5th ball is red if at the moment of the 5th selection, we pick a red ball.

Starting at state 2 (both red initially), after 4 replacements we need the distribution over states, then calculate probability of picking red from each state.

Compute P^(4) starting from state 2, then:

• From state 0: prob of picking red = 0
• From state 1: prob of picking red = 0.5
• From state 2: prob of picking red = 1

P(5th ball red) = P^(4){20} × 0 + P^(4){21} × 0.5 + P^(4)_{22} × 1

Computing P^(4) using Chapman-Kolmogorov

We’ll compute P^(4) = P^(2) × P^(2), breaking the 4 steps into two 2-step segments.

Step 1: Compute P^(2) = P × P

$$\begin{array}{rl}{\mathbf{P}}^{(2)}& =\left[\begin{array}{ccc}0.8& 0.2& 0\\ 0.1& 0.8& 0.1\\ 0& 0.2& 0.8\end{array}\right]\times \left[\begin{array}{ccc}0.8& 0.2& 0\\ 0.1& 0.8& 0.1\\ 0& 0.2& 0.8\end{array}\right]\\ & =\left[\begin{array}{ccc}0.66& 0.32& 0.02\\ 0.16& 0.68& 0.16\\ 0.02& 0.32& 0.66\end{array}\right]\end{array}$$

Step 2: Compute P^(4) = P^(2) × P^(2)

$$\begin{array}{rl}{\mathbf{P}}^{(4)}& =\left[\begin{array}{ccc}0.66& 0.32& 0.02\\ 0.16& 0.68& 0.16\\ 0.02& 0.32& 0.66\end{array}\right]\times \left[\begin{array}{ccc}0.66& 0.32& 0.02\\ 0.16& 0.68& 0.16\\ 0.02& 0.32& 0.66\end{array}\right]\\ & =\left[\begin{array}{ccc}0.4872& 0.4352& 0.0776\\ 0.2176& 0.5648& 0.2176\\ 0.0776& 0.4352& 0.4872\end{array}\right]\end{array}$$

Final Answer:

$$\begin{array}{rl}P(\text{5th ball is red | start with 2 red})& =P_{20}^{(4)}(0)+P_{21}^{(4)}(0.5)+P_{22}^{(4)}(1)\\ & =0.0776(0)+0.4352(0.5)+0.4872(1)\\ & =0+0.2176+0.4872\\ & =0.7048(\text{or }70.48\%)\end{array}$$

Examples: Random walk model

A Markov chain whose state space is given by the integers i = 0, ±1, ±2, … is said to be a random walk if, for some number $0<p<1$,

$$P_{i,i+1}=p=1-P_{i,i-1},i=0,\pm 1,\dots$$

The preceding Markov chain is called a random walk for we may think of it as being a model for an individual walking on a straight line who at each point of time either takes one step to the right with probability p or one step to the left with probability $1–p$.

Examples: Gambling model

Consider a gambler who, at each play of the game, either wins $1 with probability $p$ or loses $1 with probability $1-p$. If we suppose that our gambler quits playing either when he goes broke or he attains a fortune of $N$, then the gambler’s fortune is a Markov chain having transition probabilities

$$\begin{array}{rl}{P}_{i,i+1}& =p=1-P_{i,i-1},i=1,2,\dots ,N-1,\\ P_{00}& =P_{NN}=1\end{array}$$

States 0 and $N$ are called absorbing states since once entered they are never left. Note that the preceding is a finite state random walk with absorbing barriers (states 0 and $N$).

Gambler’s Ruin Simulation

Parameters: p = 0.6 (win probability), N = 10 (target), starting fortune = $5

Simulation 1:

• Start: $5
• Game 1: P₅,₆ = 0.6 → Win → $6
• Game 2: P₆,₅ = 0.4 → Lose → $5
• Game 3: P₅,₆ = 0.6 → Win → $6
• Game 4: P₆,₇ = 0.6 → Win → $7
• Game 5: P₇,₆ = 0.4 → Lose → $6
• Game 6: P₆,₇ = 0.6 → Win → $7
• Game 7: P₇,₈ = 0.6 → Win → $8
• Game 8: P₈,₉ = 0.6 → Win → $9
• Game 9: P₉,₁₀ = 0.6 → Win → $10
• Game 10: P₁₀,₁₀ = 1.0 → Stay → $10 (absorbed)
• Result: Reached target in 9 games

Simulation 2:

• Start: $5
• Game 1: P₅,₄ = 0.4 → Lose → $4
• Game 2: P₄,₃ = 0.4 → Lose → $3
• Game 3: P₃,₂ = 0.4 → Lose → $2
• Game 4: P₂,₃ = 0.6 → Win → $3
• Game 5: P₃,₂ = 0.4 → Lose → $2
• Game 6: P₂,₁ = 0.4 → Lose → $1
• Game 7: P₁,₀ = 0.4 → Lose → $0
• Game 8: P₀,₀ = 1.0 → Stay → $0 (absorbed)
• Result: Went broke in 7 games

Transition probabilities:

• $P_{i,i+1}$ = p = 0.6 for i ∈ {1,2,…,9}
• $P_{i,i-1}$ = 1-p = 0.4 for i ∈ {1,2,…,9}
• P₀,₀ = 1 (absorbing)
• P₁₀,₁₀ = 1 (absorbing)

The transition matrix P is (N+1) × (N+1). For N=10:

$\mathbf{P}=\left[\begin{array}{ccccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0.4& 0& 0.6& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0.4& 0& 0.6& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0.4& 0& 0.6& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0.4& 0& 0.6& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0.4& 0& 0.6& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0.4& 0& 0.6& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0.4& 0& 0.6& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0.4& 0& 0.6& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0.4& 0& 0.6\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$

Where:

• Row i represents current state i (fortune = $i)
• Column j represents next state j
• States: 0, 1, 2, …, 10
• P₀,₀ = 1 (row 1: stay broke)
• P₁₀,₁₀ = 1 (row 11: stay at $10)
• For i ∈ {1,…,9}: P_{i,i-1} = 0.4, P_{i,i+1} = 0.6

Proof: Chapman-Kolmogorov Equation

$$\begin{array}{rl}{P}_{ij}^{n+m}& =P\{X_{n+m}=j|X_0=i\}\\ & =\sum _{k=0}^{\infty }P\{X_{n+m}=j,X_n=k|X_0=i\}\\ & =\sum _{k=0}^{\infty }P\{X_{n+m}=j|X_n=k,X_0=i\}P\{X_n=k|X_0=i\}\\ & =\sum _{k=0}^{\infty }{P}_{kj}^m{P}_{ik}^n\end{array}$$

Minggu 3

Classification of States

Accessible State

State $j$ is said to be accessible from state $i$ if $P_{ij}^n>0$ for some $n\ge 0$.

This means that starting from state $i$, it is possible to eventually enter state $j$.

If $j$ is not accessible from $i$, then:

$$P\{\text{ever enter }j\mid \text{start in }i\}=\sum _{n=0}^{\infty }{P}_{ij}^n=0$$

Communication

Two states $i$ and $j$ communicate if they are mutually accessible:

• $i\to j$ (accessible)
• $j\to i$ (accessible)

Notation: $i\leftrightarrow j$

Properties (equivalence relation):

1. Reflexive: $i\leftrightarrow i$ (since $P_{ii}^0=1$)
2. Symmetric: If $i\leftrightarrow j$, then $j\leftrightarrow i$
3. Transitive: If $i\leftrightarrow j$ and $j\leftrightarrow k$, then $i\leftrightarrow k$

Proof of transitivity: If $P_{ij}^n>0$ and $P_{jk}^m>0$, then by Chapman-Kolmogorov:

$$P_{ik}^{n+m}=\sum _r{P}_{ir}^n{P}_{rk}^m\ge P_{ij}^n{P}_{jk}^m>0$$

Communicating Classes

States that communicate form a class. Classes are either:

• Identical (same class), or
• Disjoint (no overlap)

The Markov chain is irreducible if there is only one class (all states communicate).

Recurrent vs Transient

Let $f_i$ = probability that, starting from state $i$, the process will ever return to state $i$.

• Recurrent: $f_i=1$ (will return with probability 1)
• Transient: $f_i<1$ (positive probability of never returning)

Key properties:

• If $i$ is recurrent: returns infinitely many times
• If $i$ is transient: number of visits to $i$ has geometric distribution with finite mean $1/(1-f_i)$
• State $i$ is recurrent iff expected number of time periods in state $i$ is infinite

Periodic vs Aperiodic

State $i$ has period $d$ if $P_{ii}^n=0$ unless $n$ is divisible by $d$, and $d$ is the greatest such integer.

• Periodic: period $d>1$
• Aperiodic: period $d=1$ (can return at irregular times)

Limiting Probability

Regular Transition Probability Matrix

A TPM $\mathbf{P}$ is regular if $P^k$ has all positive entries for some $k>0$.

Properties:

• If $P^k$ has no zero elements for some $k$, then $P^{k+n}$ will also have no zero elements for all $n\ge 1$
• A regular chain is necessarily irreducible and aperiodic

Limiting Distribution Theorem

For a regular TPM on finite state space, there exists a unique probability vector $\pi =({\pi }_0,{\pi }_1,\dots ,{\pi }_N)$ such that:

$$\underset{n\to \infty }{\lim }{P}_{ij}^n={\pi }_j\text{for all }i,j$$

The limiting distribution satisfies:

$$\pi =\pi \mathbf{P}\text{and}\sum _j{\pi }_j=1$$

Example: Social Class Problem

Given TPM:

$$\mathbf{P}=\left[\begin{array}{ccc}\frac{1}{2}& \frac{1}{2}& 0\\ \frac{1}{4}& \frac{1}{2}& \frac{1}{4}\\ 0& \frac{1}{2}& \frac{1}{2}\end{array}\right]$$

Solving $\pi =\pi \mathbf{P}$:

$$\begin{array}{rl}{\pi }_0& =\frac{1}{2}{\pi }_0+\frac{1}{4}{\pi }_1\\ {\pi }_1& =\frac{1}{2}{\pi }_0+\frac{1}{2}{\pi }_1+\frac{1}{2}{\pi }_2\\ {\pi }_2& =\frac{1}{4}{\pi }_1+\frac{1}{2}{\pi }_2\end{array}$$

With ${\pi }_0+{\pi }_1+{\pi }_2=1$, solving yields:

• ${\pi }_0=\frac{1}{13}\approx 0.0769$ (lower class)
• ${\pi }_1=\frac{8}{13}=0.6250$ (middle class)
• ${\pi }_2=\frac{5}{13}\approx 0.3846$ (upper class)

Long-run fractions: 7.69% lower, 62.50% middle, 29.81% upper.

First Step Analysis

Hitting Probability

For a Markov chain, define $T=\min \{n\ge 1:X_n=0\text{ or }2\}$ (first time hitting boundary).

The hitting probability $\pi =P\{X_T=0\mid X_0=1\}$ can be computed using first step analysis:

$$\begin{array}{rl}\pi & =P\{X_T=0\mid X_1=k\}\cdot P\{X_1=k\mid X_0=1\}\\ \pi & =\sum _{k}P\{X_T=0\mid X_1=k\}\cdot P_{1k}\end{array}$$

With boundary conditions:

• $P\{X_T=0\mid X_1=0\}=1$
• $P\{X_T=0\mid X_1=1\}=\pi$
• $P\{X_T=0\mid X_1=2\}=0$

Expected Time to Absorption

Let $\mu =E[T\mid X_0=1]$ be the expected time to reach an absorbing state.

Using first step analysis:

$$\mu =1+\sum _k{P}_{1k}\cdot {\mu }_k$$

where ${\mu }_k=E[T\mid X_1=k]$ with boundary conditions ${\mu }_0={\mu }_2=0$.

Rangkum

Sifat	Definisi
Accessible ($i\to j$)	$P_{ij}^n>0$ for some $n$
Communication ($i\leftrightarrow j$)	$i\to j$ and $j\to i$
Recurrent	$f_i=1$ (returns infinitely often)
Transient	$f_i<1$ (finite expected visits)
Periodic	Returns at regular intervals ($d>1$)
Aperiodic	Returns at irregular times ($d=1$)
Irreducible	All states communicate
Regular	$P^k$ has all positive entries for some $k$