Rangkuman

Lecture material is stored at directory “2 Personal/files/College/Semester 6/Model Stokastik 1”.

Minggu 1

Review: Probability and Random Variables

• Random Variable: A variable that takes on its values by chance.
• Discrete RV: Takes on a finite or countable set of values. Described by Probability Mass Function (PMF) $p(x)=P\{X=x\}$.
• Continuous RV: Takes on a continuum of values. Described by Probability Density Function (PDF) $f(x)$ where $P\{a\le X\le b\}={\int }_a^{b}f(x)dx$.
• Distribution Function (CDF): $F(x)=P\{X\le x\}$.
• Mean (Expectation): $E[X]=\sum xp(x)$ or $\int xf(x)dx$.
• Variance: $Var[X]=E[X^2]-(E[X]{)}^2$.

Review: Conditional Probability and Expectation

• Conditional Probability: $P\{A|B\}=\frac{P\{A\cap B\}}{P\{B\}}$ for $P\{B\}>0$.
• Law of Total Probability: $P\{A\}={\sum }_{i}P\{A|B_i\}P\{B_i\}$ for a partition $\{B_i\}$.
• Conditional Expectation: Discrete: $E[X|Y=y]=\sum xP\{X=x|Y=y\}$. Continuous: $E[X|Y=y]=\int x{f}_{X|Y}(x|y)dx$.
• Law of Iterative Expectations: $E[X]=E[E[X|Y]]$.

Definition: Classification of Stochastic Processes

A stochastic process $\{X(t),t\in T\}$ is classified by its state space ($S$) and its index set ($T$):

1. Discrete-time, Discrete state space: $T=\{0,1,2,...\}$, $S=\{0,1,2,...\}$. Example: Markov Chain.
2. Continuous-time, Discrete state space: $T=[0,\infty )$, $S=\{0,1,2,...\}$. Example: Poisson Process.
3. Discrete-time, Continuous state space: $T=\{0,1,2,...\}$, $S=\mathbb{R}$.
4. Continuous-time, Continuous state space: $T=[0,\infty )$, $S=\mathbb{R}$. Example: Brownian Motion.

Minggu 2

Definition: Stochastic process

A stochastic process $\{X(t),t\in T\}$ is a collection of random variables $X(t)$ indexed by $t$.

• Process: Depends on time
• Stochastic: Probabilistic
• Stochastic Process: Sequence (implies ordering) of random variables indexed by time

Definition: State

Values of stochastic process $X(t)$ is referred to as states of the process

About State vs Sample

• State: A possible value the random variable can take - it exists whether or not you’ve observed it.
• Sample: A realized observation from a distribution - a concrete outcome you observe.

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}\}$

• About State vs Sample

Definition: Markov property

Let $\{X_t\}$ : Stochastic process

Markov Property is the property that, given the value of $X_t$ the values of $X_s$ for $s>t$ are not influenced by the values of $X_u$, $u<t$

That is, the probability of any particular future behavior of the process, when its current state is known exactly, is not altered by additional knowledge concerning its past behavior.

Definition: Markov process

A Markov Process $\{X_t\}$ is a stochastic process with the markov property

Definition: 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

Definition: Process

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

Definition: Discrete-time Markov chain

Random variable at index n+1 is only dependent with the random variable at n

A state depends on the previous “state”, and only on that previous state

$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}$

Tip

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

Definition: Transition probability

Suppose that the (conditional) probability of $X_{n+1}$ being in state $j$ given that $X_n$ is in state $i$ is constant over time, i.e., $P_{ij}=P(X_{n+1}=j\mid X_n=i),\text{for all }n.$ Then $P_{ij}$ is called the one-step transition probability

Tip

Probability of transitioning from state i to state j in one time step

Definition: Transition probability matrix (TPM)

Full set of all $P_{ij}$ in matrix form.

$P_{ij}$ is transition probability from state i to j

Often abbreviated to TPM

$$\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

Interpretation:

• $P_{12}$ is probability of transitioning from state 1 to state 2 in one step (Transition probability)
• $P_{34}$ transition probability from state 3 to 4
• $P_{55}$ transition probability from state 5 to 5

Procedure: Proving a Valid TPM

1. All entries $P_{ij}\ge 0$
2. Each row sums to 1: ${\sum }_j{P}_{ij}=1$ for all $i$

Definition: Chapman-Kolmogorov

Transition probability to go from state i to j in n + m steps.

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

where $N$ is number of all states

See proof

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

We can then “recurse” it by breaking the n steps to k + l step, and so forth.

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.”

Definition: n-step Transition Matrix

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$ (see proof)

Proof: n-step Transition Matrix Identity

Theorem: For any $n\ge 1$, the n-step Transition Matrix ${\mathbf{P}}^{(n)}$ is the $n$-th power of the Transition matrix $\mathbf{P}$, i.e., ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$.

Proof by Induction:

1. Base Case ($n=1$): By definition of Transition probability, $P_{ij}^{(1)}$ is the probability of transitioning from state $i$ to $j$ in one step, which is $P_{ij}$. Thus, ${\mathbf{P}}^{(1)}={\mathbf{P}}^1$.

2. Inductive Hypothesis: Assume ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ holds for some $n\ge 1$.

3. Inductive Step: Consider ${\mathbf{P}}^{(n+1)}$. By the Chapman-Kolmogorov equation with $m=1$: $P_{ij}^{(n+1)}={\sum }_k{P}_{ik}^{(n)}{P}_{kj}^{(1)}$ Substituting $P_{kj}^{(1)}=P_{kj}$ and using the inductive hypothesis $P_{ik}^{(n)}=({\mathbf{P}}^n{)}_{ik}$: $P_{ij}^{(n+1)}={\sum }_k({\mathbf{P}}^n{)}_{ik}{P}_{kj}$ The right-hand side corresponds to the entry in row $i$ and column $j$ of the matrix product ${\mathbf{P}}^n\cdot \mathbf{P}$. Therefore, ${\mathbf{P}}^{(n+1)}={\mathbf{P}}^n\cdot \mathbf{P}={\mathbf{P}}^{n+1}$.

By induction, the identity holds for all $n\ge 1$.

About 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 1).

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 red)

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}$$

Definition: Random Walk Markov Chain

A Random Walk is a Markov chain whose state space is given by the integers $i=0,\pm 1,\pm 2,\dots$ where at each point of time the process either moves:

• One step to the right with probability $p$
• One step to the left with probability $1-p=q$

$P_{i,i+1}=p,P_{i,i-1}=1-p$ where $0<p<1$.

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

Definition: 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$$

Definition: 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$$

Definition: Communicating Classes

States that communicate form a class. Classes are either:

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

Definition: Irreducible

The Markov chain is irreducible if there is only one communicating class (all states are communicative).

Definition: Recurrent vs Transient

Transient: Will eventually leave and never come back

Recurrent: Will always come back, no matter how many times it leaves

Notice that unlike transition probability, this talks about whether or not state will return back to itself in the future.

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

Definition: Period, Periodic, Aperiodic

the GCD of all steps $n$ at which it is possible to return to state $i$.

The period of state $i$ is defined as:

$d(i)=\gcd \{n\ge 1:P_{ii}^{(n)}>0\}$

• Periodic: period $d>1$ — returns are confined to multiples of $d$
• Aperiodic: period $d=1$ — no such rhythm, can return at irregular times

About aperiodic vs periodic state

Everyday illustrations of Periodic and Aperiodic states:

Periodic State

A state $i$ has period $d>1$ if you can only return to that state in a number of steps ($n$) that is a multiple of $d$ (i.e., $n$ is divisible by $d$).

Everyday Example: A Pendulum or a Swing

Imagine a child on a swing. Let’s define the State as “The swing is at the highest point on the right side.”

• If the swing is at the highest point now (Step 0), it must swing down to the middle, then to the left, then back to the middle, before returning to the right.
• It takes exactly 2 full “ticks” of the movement to return to that specific spot.
• You can only be in that state at Step 2, Step 4, Step 6, etc.
• Because you can never be in that state at Step 1, 3, or 5, the state is Periodic with a period of $d=2$.

Aperiodic State

A state is aperiodic if its period $d=1$. This means you can return to the state at irregular times, and there is no fixed “rhythm” or multiple you must follow.

Everyday Example: Checking Your Phone for Notifications

Imagine the State is “You are looking at your phone screen.”

• You look at your phone now (Step 0).
• You might look at it again 1 minute later ($n=1$).
• Or you might wait and look at it 5 minutes later ($n=5$).
• Or 12 minutes later ($n=12$).
• Because it is possible to return to the state in just 1 step ($n=1$), the greatest common divisor of all possible return times is 1.
• There is no “rule” saying you can only check every 3 minutes; you can return to this state whenever you like. Therefore, it is Aperiodic.

Cheatsheet: State Classification

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$

Example: Transient state

When an absorbing state occurs, it’s absorbed there forever and never goes to other states, which makes the other states “transient”.

Note that the transient definition only talks about the probability of a state returning to itself, without mentioning about “absorbing”. absorbing states are just one scenario that produces it.

Other example is if states $\{2,3,5,6,7\}$ and $\{1,4,8\}$ are two disjoint communicating classes, neither is necessarily transient just from that alone.

Transience depends on whether you can escape the class. If from class $\{1,4,8\}$ there is a positive probability of transitioning into $\{2,3,5,6,7\}$ but not vice versa, then $\{1,4,8\}$ is transient — because once you leave, you never return.

Definition: Limiting Probability

For a Markov chain $\{X_n,n\ge 0\}$, the limiting probability ${\pi }_j$ of state $j$ represents the long-run probability that the process will be in state $j$, independent of the initial state $i$. ${\pi }_j={\lim }_{n\to \infty }{P}_{ij}^n$

where $P_{ij}^n$ is the n-step transition probability from state $i$ to state $j$.

The limiting probability is related to the mean recurrence time ${\mu }_{jj}$ (expected time to return to state $j$ starting from $j$) by: ${\pi }_j=\frac{1}{{\mu }_{jj}}$

Definition: Regular Transition Probability Matrix

A TPM $\mathbf{P}$ is regular if:

1. For every pair $i,j$, there is a path $k_1,k_2,\dots ,k_r$ for which $P_{i{k}_1}{P}_{k_1{k}_2}\dots P_{k_{r}j}>0$;
2. There is at least one state $i$ for which $P_{ii}>0$.

Equivalently, $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 (see proof)

Condition 2 ensures the chain is aperiodic.

Without it, a chain could be irreducible (condition 1 satisfied) but still periodic — meaning it cycles through states in a fixed pattern and never settles into a stationary distribution. A self-loop $P_{ii}>0$ forces the chain to be able to “stay” at a state, breaking any fixed cycle and guaranteeing period 1.

Together, irreducible + aperiodic = regular = guaranteed convergence to a unique stationary distribution regardless of initial state.

Theorem: Limiting Distribution Theorem

Let $\mathbf{P}$ : Transition probability matrix (TPM) on finite state space

Then

$$\begin{array}{c}\exists \pi =({\pi }_0,{\pi }_1,\dots ,{\pi }_N)\\ \ni \\ {\pi }_j=\underset{n\to \infty }{\lim }{P}_{ij}^{(n)},\forall i,j\end{array}$$

The limiting distribution satisfies: $\pi =\pi \mathbf{P}\text{and}{\sum }_j{\pi }_j=1$

Definition: Stationary Distribution

A probability vector $\pi =({\pi }_0,{\pi }_1,\dots )$ is a stationary distribution if it satisfies: $\pi =\pi \mathbf{P}\text{and}{\sum }_j{\pi }_j=1$ If the initial state $X_0$ is chosen according to $\pi$, then the probability of being in state $j$ at any time $n$ is also ${\pi }_j$ (i.e., $P(X_n=j)={\pi }_j$ for all $n$).

Definition: Ergodic State

A state is ergodic if it is both positive recurrent (expected return time is finite) and aperiodic (period $d=1$).

• In a finite irreducible Markov chain, all states are positive recurrent.
• If the chain is also aperiodic, all states are ergodic.
• For an irreducible ergodic Markov chain, the limiting distribution always exists and is equal to the unique stationary distribution.
• The limiting distribution, when it exists, is always a stationary distribution. However, a stationary distribution may exist without a limiting distribution (e.g., a periodic chain can have a stationary distribution but no limiting distribution).

About positive recurrent state

Positive recurrent

I imagine a scenario of “closed” communicative state.

So in Markov chain 0→1→2→0, then ${\mu }_{00}=3$, because we expect that if we start from 0 to eventually return back to 0 in 3 steps.

The example above is “deterministic”. When there are other possible states each state can take, then it’s “probabilistic”, and we deal with the notion of expectation of the time to take to go back to 0.

Null recurrent

Random walks on $\mathbb{Z}$ causes ${\mu }_{ii}=\infty$. The way I see it is we can be ANYWHERE at $\mathbb{Z}$, which is $(-\infty ,\infty )$, which means it is possible to “return” to state $i$, but the expected time is basically infinite, since we could’ve traversed anywhere also.

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 & =\pi \mathbf{P}\\ \left[\begin{array}{ccc}{\pi }_1& {\pi }_2& {\pi }_3\end{array}\right]& =\left[\begin{array}{ccc}{\pi }_1& {\pi }_2& {\pi }_3\end{array}\right]\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]\\ & =\left[\begin{array}{ccc}\frac{1}{2}{\pi }_1+\frac{1}{4}{\pi }_2+0& \frac{1}{2}{\pi }_1+\frac{1}{2}{\pi }_2+\frac{1}{2}{\pi }_3& 0+\frac{1}{4}{\pi }_2+\frac{1}{2}{\pi }_3\end{array}\right]\end{array}$$

Matching components:

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

• From equation 1: $\frac{1}{2}{\pi }_1=\frac{1}{4}{\pi }_2\Rightarrow {\pi }_2=2{\pi }_1$
• From equation 3: $\frac{1}{2}{\pi }_3=\frac{1}{4}{\pi }_2\Rightarrow {\pi }_3=\frac{1}{2}{\pi }_2={\pi }_1$
• Substituting into ${\pi }_1+{\pi }_2+{\pi }_3=1$:

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

• Subtituting to ${\pi }_2$ and ${\pi }_3$ we obtain:

${\pi }_2=\frac{1}{2},{\pi }_3=\frac{1}{4}$

Comparison: Limiting vs. Hitting Probability

Although both often use the notation $\pi$ in lecture slides, they represent fundamentally different concepts:

Feature	Limiting Probability ${\pi }_j$	Hitting Probability ${\pi }_i(j)$
Question	”In the long run, what % (proportion) of time is spent in state $j$?"	"Starting at state $i$, what is the chance I ever reach state $j$?”
System State	Describes steady state (long-run).	Describes the fate of a single path.
Dependence	Independent of starting state.	Heavily depends on starting state $i$.
Matrix Math	Left-multiplication: $\pi =\pi \mathbf{P}$	Right-multiplication: $u=\mathbf{P}u$
Indices	Summing over columns: ${\pi }_j={\sum }_k{\pi }_k{P}_{kj}$	Summing over rows: ${\pi }_i={\sum }_k{P}_{ik}{\pi }_k$
Boundaries	No boundaries; requires $\sum {\pi }_j=1$.	Requires boundaries (Target=1, Other Absorbing=0).

TIP

• Use Limiting Probability when asked for “Long-run proportion” or “Steady state”.
• Use Hitting Probability (via First Step Analysis) when asked for “Probability of reaching/absorption” or “Chance of winning”.

Procedure: First Step Analysis

First Step Analysis (FSA) allows you to calculate specific properties of a Markov Chain, such as the probability of reaching a target state or the time until absorption, by analyzing the very first transition.

Prerequisites

• A defined Transition Probability Matrix (TPM).
• Clear identification of target states (hitting boundaries) and absorbing states.

Calculating hitting probabilities

Use this procedure to determine the probability that a process starting in state $i$ will eventually hit a specific target state $j$.

1. Identify boundary conditions. Set:
   • ${\mu }_{\text{target}}=1$
   • ${\mu }_{\text{others \& absorbing}}=0$
2. Formulate equations for transient states. For each state $i$ that is not a boundary or absorbing state, express the hitting probability ${\pi }_i$ as a weighted sum of the probabilities from its possible next states: ${\pi }_i={\sum }_k{P}_{ik}\cdot {\pi }_k$
3. Solve the linear system. Solve the resulting set of equations for all unknown ${\pi }_i$ values.

Outcome: You will obtain the exact probability of the process ever entering the target state $j$.

Calculating expected time to absorption

Use this procedure to find the average number of steps required to reach any absorbing state from a starting state $i$.

1. Set boundary conditions. For all absorbing states, the expected time to absorption is 0 (${\mu }_{\text{absorbed}}=0$).
2. Formulate equations for transient states. For each transient state $i$, add 1 (representing the current step) to the expected time remaining from all possible next states $k$: ${\mu }_i=1+{\sum }_k{P}_{ik}\cdot {\mu }_k$
3. Solve the linear system. Solve the resulting equations to find the expected time ${\mu }_i$ for each state.

Outcome: You will determine the mean number of transitions until the process terminates in an absorbing state.

Example: First Step Analysis - Gambler’s Ruin

Using the scenario from Examples Gambling model, consider a gambler with $N=3$ and win probability $p=0.4$ (lose probability $q=0.6$).

We want to find the probability of reaching the target ($3$) starting from state $1$.

Hitting probability

Let ${\pi }_i$ be the probability of hitting state $3$ starting from state $i$.

• Boundary Conditions: ${\pi }_3=1$ (Target reached), ${\pi }_0=0$ (Broke).

• Equations for Transient States:

  • ${\pi }_1=0.4{\pi }_2+0.6{\pi }_0⟹{\pi }_1=0.4{\pi }_2$
  • ${\pi }_2=0.4{\pi }_3+0.6{\pi }_1⟹{\pi }_2=0.4(1)+0.6{\pi }_1$

• Solution:

  ${\pi }_1=0.4(0.4+0.6{\pi }_1)=0.16+0.24{\pi }_1$

  $0.76{\pi }_1=0.16⟹{\pi }_1\approx 0.2105$

Expected time to absorption

Let ${\mu }_i$ be the expected number of steps until reaching state $i$.

• Boundary Conditions: ${\mu }_0=0,{\mu }_3=0$

• Equations:

  • ${\mu }_1=1+0.4{\mu }_2+0.6{\mu }_0⟹{\mu }_1=1+0.4{\mu }_2$
  • ${\mu }_2=1+0.4{\mu }_3+0.6{\mu }_1⟹{\mu }_2=1+0.6{\mu }_1$

• Solution:

  ${\mu }_1=1+0.4(1+0.6{\mu }_1)=1+0.4+0.24{\mu }_1$

  $0.76{\mu }_1=1.4⟹{\mu }_1\approx 1.8421$ steps.

Proof: Regular chain is necessarily irreducible and aperiodic

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

This means that after $k$ steps, there is a non-zero probability of moving from any state $i$ to any state $j$.

1. Proof of Irreducibility

Definition: A chain is irreducible if all states communicate ($i\leftrightarrow j$). This means for any two states $i$ and $j$, it is possible to go from $i$ to $j$ and from $j$ to $i$.

Proof:

1. By the definition of a regular chain, there exists some $k$ such that $({\mathbf{P}}^k{)}_{ij}>0$ for all $i,j$.
2. Since $({\mathbf{P}}^k{)}_{ij}>0$, state $j$ is accessible from state $i$ ($i\to j$).
3. Similarly, since $({\mathbf{P}}^k{)}_{ji}>0$, state $i$ is accessible from state $j$ ($j\to i$).
4. Because every state can reach every other state, they all belong to the same communicating class.
5. Conclusion: The chain is irreducible.

2. Proof of Aperiodicity

Definition: A state $i$ is aperiodic if its period $d(i)=1$. The period is the Greatest Common Divisor (GCD) of all $n$ such that $({\mathbf{P}}^n{)}_{ii}>0$.

Proof:

1. In a regular chain, we know $({\mathbf{P}}^k{)}_{ii}>0$ for all states $i$. This means $k$ is one possible time the process can return to state $i$.
2. Your notes mention: “If ${\mathbf{P}}^k$ has no zero elements… then ${\mathbf{P}}^{k+n}$ will also have no zero elements for all $n\ge 1$.”
   • Why? Because ${\mathbf{P}}^{k+1}=\mathbf{P}\cdot {\mathbf{P}}^k$. To get from $i$ to $j$ in $k+1$ steps, you just need to take one step to any intermediate state $m$, and then take $k$ steps to $j$. Since ${\mathbf{P}}^k$ is all positive, and you must be able to go somewhere in one step, a path always exists.
3. This implies that if $({\mathbf{P}}^k{)}_{ii}>0$, then $({\mathbf{P}}^{k+1}{)}_{ii}>0$ as well.
4. The period $d(i)$ must be a common divisor of $k$ and $k+1$.
5. The only positive integer that divides two consecutive integers ($k$ and $k+1$) is 1.
6. Conclusion: $d(i)=1$ for all states, so the chain is aperiodic.

Summary

• Irreducible because “all positive entries” means you can get anywhere from anywhere.
• Aperiodic because “all positive entries” means you can return to a state at any time $n\ge k$, breaking any fixed “rhythm” or period.

Minggu 4

Definition: Mean Time Spent in Transient States

For a finite Markov chain, let $T=\{1,2,\dots ,t\}$ be the set of transient states. The Transition matrix restricted to transient states is $\mathbf{Q}$ (or ${\mathbf{P}}_T$).

The matrix $\mathbf{\mu }$ contains the expected number of time periods spent in transient state $j$ given starting in transient state $i$: $\mathbf{\mu }=(\mathbf{I}-\mathbf{Q}{)}^{-1}$

Properties:

• ${\mu }_{ij}$ (or ${\mu }_i(j)$): Expected number of visits to state $j$ starting from $i$.
• $\mathbf{I}$: Identity matrix of size $t$.

About relation of matrix mu and absorption time

In relation of the mean time matrix $\mathbf{\mu }$ (Definition Mean Time Spent in Transient States) to the expected time to absorption ${\mu }_i$ (Expected time to absorption): ${\mu }_i={\sum }_j{\mathbf{\mu }}_{ij}$

Essentially,

• ${\mu }_i$ is a single value (or vector element) representing total time until any absorption.
• $\mathbf{\mu }$ is a matrix containing detailed information about visits to each transient state $j$ before absorption.

Definition: Hitting Probability (Transient)

The probability that the Markov chain ever enters transient state $j$ given that it starts in transient state $i$ is ${\pi }_i(j)$:

$${\pi }_i(j)=\frac{{\mu }_{ij}-{\delta }_{ij}}{{\mu }_{jj}}$$

where ${\delta }_{ij}=1$ if $i=j$ and $0$ otherwise.

Example: Gambler’s Ruin (Matrix Analysis)

For $N=7,p=0.4$ (lose prob $0.6$), starting with 3 units:

• ${\mu }_{3,5}=0.9228$ (Expected time at 5 units)
• ${\mu }_{3,2}=2.3677$ (Expected time at 2 units)
• Probability of ever hitting 1: ${\pi }_3(1)={\mu }_{3,1}/{\mu }_{1,1}=1.4206/1.6149=0.8797$

Minggu 5

Definition: Branching Processes

A population model where each individual produces $j$ offspring with probability $P_j$.

$X_n$ is the size of the $n$-th generation.

Moment	Formula
Mean offspring	$\mu ={\sum }_{j=0}^{\infty }j{P}_j$
Expected size at gen $n$	$E[X_n]={\mu }^n$
Variance at gen $n$	$\text{Var}(X_n)={\sigma }^2{\mu }^{n-1}\frac{1-{\mu }^n}{1-\mu }$

Definition: Extinction Probability (${\pi }_0$)

Let $\mu =E[{\xi }_i]$ — the expected number of offspring per individual, i.e. the mean of the offspring distribution $P_j$.

• If $\mu \le 1$: ${\pi }_0=1$ (certain extinction, unless $P_1=1$).
• If $\mu >1$: ${\pi }_0$ is the smallest positive solution to:

${\pi }_0={\sum }_{j=0}^{\infty }{\pi }_0^j{P}_j$

Where:

• ${\pi }_0$ (left side) — the extinction probability we’re solving for
• $j$ — number of offspring a single individual produces
• $P_j$ — probability of producing exactly $j$ offspring
• ${\pi }_0^j$ (right side) — probability that all $j$ offspring lines eventually go extinct (each offspring independently has extinction probability ${\pi }_0$, and there are $j$ of them)

The right side sums over all possible offspring counts: probability of having $j$ offspring × probability all $j$ lineages die out. This is a self-consistency equation — ${\pi }_0$ appears on both sides because extinction of the whole population requires extinction of every sub-lineage.

Definition: Time Reversible Markov Chains

A stationary Markov chain is time reversible if it satisfies the detailed balance equation

${\pi }_i{P}_{ij}={\pi }_j{P}_{ji},\forall i,j$

Tip

${\pi }_i$ is the long-run/“overall” proportion/probability of time spent in state $i$. $P_{ij}$ is the transition probability from $i$ to $j$ in one time step.

$P_{ij}$ alone = probability of going $i\to j$ given you’re already in $i$.

${\pi }_i{P}_{ij}$ = probability of going $i\to j$ unconditionally, accounting for how often you’re even in $i$ to begin with.

Detailed balance says this frequency is equal in both directions.

Essentially, the rate at which the process goes from $i\to j$ is equal to the rate from $j\to i$.

Theorem: Kolmogorov’s Criterion

A chain is time reversible iff for any cycle of states $i\to i_1\to \cdots \to i_k\to i$, the product of transition probabilities is the same in both directions:

$$P_{i,i_1}{P}_{i_1,i_2}\dots P_{i_k,i}=P_{i,i_k}{P}_{i_k,i_{k-1}}\dots P_{i_1,i}$$

Examples

• Random Walk on Graphs (with symmetric weights $w_{ij}=w_{ji}$): $P_{ij}=\frac{w_{ij}}{\sum w_{ik}}$ is time reversible.
• Ehrenfest Urn: State $i$ (number of balls in Urn 1) is time reversible with ${\pi }_i=\left(\genfrac{}{}{0ex}{}{M}{i}\right)(\frac{1}{2}{)}^M$.
• One-closer rule: Reordering rule that is time reversible, unlike move-to-front.

Definition: Markov Chain Monte Carlo (MCMC)

Method to sample from a distribution $\pi$ by constructing a time reversible Markov chain.

Metropolis-Hastings Algorithm:

1. Propose jump from $i$ to $j$ with $q_{ij}$.
2. Accept with probability ${\alpha }_{ij}=\min \left(1,\frac{{\pi }_j{q}_{ji}}{{\pi }_i{q}_{ij}}\right)$.

Minggu 6

Definition: Counting Process

A stochastic process $\{N(t),t\ge 0\}$ is a counting process if $N(t)$ represents the total number of “events” that occur by time $t$.

Properties:

• $N(t)\ge 0$
• $N(t)$ is integer valued
• If $s<t$, then $N(s)\le N(t)$
• $N(t)-N(s)$ equals the number of events in $(s,t]$

About Independent and Stationary Increments

• Independent increments: Numbers of events in disjoint time intervals are independent
• Stationary increments: Distribution of number of events in any interval depends only on the length of the interval (not the starting point)

Not all counting processes possess both properties.

Definition: Poisson Distribution

A random variable $X$ has Poisson distribution with parameter $\mu >0$ if: $P(X=k)=\frac{e^{-\mu }{\mu }^k}{k!},k=0,1,2,\dots$

MGF: $\varphi (t)=e^{\mu (e^t-1)}$

Theorem: Sum of Poisson Random Variables

If $X\sim \text{Po}(\mu )$ and $Y\sim \text{Po}(\nu )$ are independent, then $X+Y\sim \text{Po}(\mu +\nu )$.

Theorem: Poisson-Binomial Distribution

Let $N\sim \text{Po}(\mu )$ and conditional on $N=n$, let $M|N=n\sim \text{Bin}(n,p)$. Then $M$ (unconditional on $N$) is Poisson distributed with parameter $\mu p$.

About Axioms of Poisson Distribution

For a process occurring with rate $\lambda$, let $X(t)$ be the number of occurrences in $[0,t]$. For infinitesimal $h$:

1. $P(\text{1 event in }[t,t+h])=\lambda h+o(h)$
2. $P(\text{0 events in }[t,t+h])=1-\lambda h+o(h)$
3. $P(\ge 2\text{ events in }[t,t+h])=o(h)$

Where $f(h)=o(h)$ means ${\lim }_{h\to 0}\frac{f(h)}{h}=0$.

Definition: Poisson Process

A counting process $\{N(t),t\ge 0\}$ is a Poisson process of rate $\lambda >0$ if:

1. $N(0)=0$
2. Independent increments
3. $P(N(t+h)-N(t)=1)=\lambda h+o(h)$
4. $P(N(t+h)-N(t)\ge 2)=o(h)$

Equivalently: $N(t+s)-N(s)\sim \text{Po}(\lambda t)$ for all $s,t\ge 0$.

About Properties of Poisson Process

1. $N(t)\sim \text{Po}(\lambda t)$
2. Time of first event $T_1\sim \text{Exp}(\lambda )$
3. Inter-arrival times $T_n$ (time between $(n-1)$-th and $n$-th event) are i.i.d. $\text{Exp}(\lambda )$
4. Waiting time $W_n$ (time until $n$-th event) $\sim \text{Gamma}(n,\lambda )$

Definition: Inter-arrival Times

The sequence $\{T_n,n=1,2,\dots \}$ where $T_n$ is the elapsed time between the $(n-1)$-th and $n$-th event. For Poisson process: $T_n\stackrel{\text{i.i.d.}}{\sim }\text{Exp}(\lambda )$.

This follows from the memoryless property — the process “restarts” probabilistically at each event.

Definition: Waiting Times

$W_n={\sum }_{i=1}^n{T}_i$ is the time of occurrence of the $n$-th event. For Poisson process: $W_n\sim \text{Gamma}(n,\lambda )$ with PDF: $f_{W_n}(t)=\lambda e^{-\lambda t}\frac{(\lambda t{)}^{n-1}}{(n-1)!},t\ge 0$

Relationship: $N(t)\ge n⟺W_n\le t$.

Theorem: Conditional Distribution of Arrival Times

Given $N(t)=n$, the $n$ arrival times $S_1,\dots ,S_n$ have the same distribution as the order statistics of $n$ i.i.d. $\text{Uniform}(0,t)$ random variables.

Joint density: $f(s_1,\dots ,s_n|N(t)=n)=\frac{n!}{t^n}$ for $0<s_1<\cdots <s_n<t$.

Paraphrased: given $n$ events occurred in $(0,t)$, the event times are distributed independently and uniformly over $(0,t)$ (as unordered variables).

Definition: Type I and Type II Events (Thinning)

Given Poisson process $\{N(t),t\ge 0\}$ of rate $\lambda$. Each event is classified as type I with probability $p$ or type II with probability $1-p$, independently. Let $N_1(t)$ and $N_2(t)$ count type I and II events.

Theorem: Thinning

Thinning a Poisson process with probability $p$ yields a Poisson process with rate $\lambda p$.

Theorem: Independence of Thinned Processes

$N_1(t)\sim \text{Po}(\lambda pt)$ and $N_2(t)\sim \text{Po}(\lambda (1-p)t)$ are independent Poisson processes.

Generalizes to $k$ types: if events are classified into $k$ types with probabilities $p_1,\dots ,p_k$, then the $k$ resulting processes are independent Poisson processes with rates $\lambda p_i$.

Definition: Exponential Distribution

A continuous random variable $X$ has exponential distribution with parameter $\lambda >0$ if: $f(x)=\lambda e^{-\lambda x},x\ge 0$ $F(x)=1-e^{-\lambda x},x\ge 0$

• Mean: $E[X]=\frac{1}{\lambda }$
• Variance: $\text{Var}(X)=\frac{1}{{\lambda }^2}$
• MGF: $\varphi (t)=\frac{\lambda }{\lambda -t}$ for $t<\lambda$

About Memoryless Property

$P(X>s+t\mid X>t)=P(X>s)$ for all $s,t\ge 0$.

The exponential distribution is the only continuous distribution with this property. An item that has survived $t$ hours is “as good as new” — the remaining lifetime has the same distribution as the original.

About Failure Rate Function

$r(t)=\frac{f(t)}{1-F(t)}$ represents the conditional probability density that a $t$-year-old item will fail.

For exponential: $r(t)=\lambda$ (constant). The failure rate function uniquely determines the distribution.

Definition: Hyperexponential Random Variable

A mixture of exponentials: $X=X_T$ where $P(T=j)=P_j$ and $X_j\sim \text{Exp}({\lambda }_j)$.

CDF: $1-F(t)={\sum }_{i=1}^n{P}_i{e}^{-{\lambda }_{i}t}$

Failure rate: $r(t)={\sum }_{j=1}^n{\lambda }_{j}P(T=j\mid X>t)$

As $t\to \infty$, $r(t)\to {\min }_i{\lambda }_i$ (converges to the slowest-failing type).

Definition: Hypoexponential Random Variable

Sum of independent exponentials with distinct rates: $S={\sum }_{i=1}^n{X}_i$ where $X_i\sim \text{Exp}({\lambda }_i)$, ${\lambda }_i\ne {\lambda }_j$.

PDF: $f_S(t)={\sum }_{i=1}^n{C}_{i,n}{\lambda }_i{e}^{-{\lambda }_{i}t}$ where $C_{i,n}={\prod }_{j\ne i}\frac{{\lambda }_j}{{\lambda }_j-{\lambda }_i}$

Tail: $P(S>t)={\sum }_{i=1}^n{C}_{i,n}{e}^{-{\lambda }_{i}t}$

As $t\to \infty$, remaining lifetime ≈ exponential with rate ${\min }_i{\lambda }_i$.

Definition: Coxian Random Variable

$Y={\sum }_{j=1}^N{X}_j$ where $N$ is random and $X_j\sim \text{Exp}({\lambda }_j)$. Arises when an item goes through stages and may quit after each stage with probability $r(n)$.

Definition: Nonhomogeneous Poisson Process

A counting process $\{N(t),t\ge 0\}$ with intensity function $\lambda (t)$ where:

1. $N(0)=0$
2. Independent increments
3. $P(N(t+h)-N(t)=1)=\lambda (t)h+o(h)$
4. $P(N(t+h)-N(t)\ge 2)=o(h)$

Then $N(t)\sim \text{Po}(m(t))$ where $m(t)={\int }_0^t\lambda (s)ds$ (mean value function).

Definition: Compound Poisson Process

$X(t)={\sum }_{i=1}^{N(t)}{Y}_i$ where $\{N(t)\}$ is Poisson with rate $\lambda$ and $Y_i$ are i.i.d. random variables independent of $N(t)$.

• $E[X(t)]=\lambda t\cdot E[Y_i]$
• $\text{Var}(X(t))=\lambda t\cdot E[Y_i^2]$

Cheatsheet: Poisson Process Summary

Concept	Formula
$N(t)$ distribution	$\text{Po}(\lambda t)$
Inter-arrival times $T_n$	i.i.d. $\text{Exp}(\lambda )$
Waiting time $W_n$	$\text{Gamma}(n,\lambda )$
Given $N(t)=n$	Arrival times = order statistics of $n$ uniform$(0,t)$
Thinning (prob $p$)	Independent Poisson with rate $\lambda p$
Nonhomogeneous $N(t)$	$\text{Po}\left({\int }_0^t\lambda (s)ds\right)$

Example: Exponential Random Variables and Expected Discounted Returns

Example: Time Spent in a Bank

Example: Automobile Accident Damage

Example: Commodity Ordering

Example: Analyzing Greedy Algorithms for the Assignment Problem

Example: Cells in the Body

Example: Customers in Line

Example: Function o(h)

Example: Immigrants into a Territory

Example: Nonnegative Offers

Example: System with Classified Individuals

Example: The Coupon Collecting Problem

Example: An Infinite Server Queue

Example: Minimizing the Number of Encounters

Example: Tracking the Number of HIV Infections

Example: Insurance Claims

Example: An Optimization Example

Minggu 7

Definition: Mixed Poisson Process

Example: Nonhomogeneous Poisson Process — Demand of a Facility

Example: Bugs in Operating Time

Example: Siegbert Hot Dog Stand

Example: The Output Process of an Infinite Server Poisson Queue

Example: Families Migrate to an Area

Example: Busy Periods in Single-Server Poisson Arrival Queues

Lemma 4.1

Lemma 4.2

Lemma 4.3

Minggu 8

Definition: Conditional Poisson Process

Example: Gamma Density

Example: Insurance Company Policyholders

Rangkum

Sifat	Definisi
Ergodic State	Positive Recurrent + Aperiodic
Stationary Distribution	$\pi =\pi \mathbf{P}$ and $\sum {\pi }_j=1$
$\mathbf{\mu }=(\mathbf{I}-\mathbf{Q}{)}^{-1}$	Expected time spent in transient states
${\pi }_i(j)=\frac{{\mu }_{ij}-{\delta }_{ij}}{{\mu }_{jj}}$	Probability of ever hitting state $j$ from $i$
${\pi }_0=\sum {\pi }_0^j{P}_j$	Extinction probability for branching processes
${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$	Detailed Balance (Time Reversible)
$N(t)\sim \text{Po}(\lambda t)$	Poisson Process
$T_n\stackrel{\text{i.i.d.}}{\sim }\text{Exp}(\lambda )$	Inter-arrival times
$W_n\sim \text{Gamma}(n,\lambda )$	Waiting times
$N_1,N_2$ independent	Thinning with probabilities $p,1-p$