First Step Analysis

Procedure

First Step Analysis (FSA) allows calculating 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:

   • ${\pi }_{\text{target}}=1$
   • ${\pi }_{\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: ${\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.

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.

Example

See First Step Analysis - Gambler’s Ruin Example.

Related

• Hitting Probability (Transient)
• Mean Time Spent in Transient States
• Limiting vs Hitting Probability