First-step analysis: Definition & Examples

First-step analysis solves a random waiting or hitting problem by conditioning on the next outcome and expressing what remains as the same problem from a new state. It turns “will a risk boundary be reached, and how long will that take?” into equations for probabilities or expected times.

The key is choosing a state that preserves the information needed for the future. For a time-homogeneous Markov chain, knowing the next state lets the calculation restart with the same transition rules. This is recursive conditioning, rather than an assumption that successive states are independent.

One chain, two questions

Consider a fictional risk score taking values $0,1,2,3$ . From an interior state it moves up or down by one, each with probability $1/2$ . Stop on reaching either boundary. State $0$ is the lower boundary; state $3$ is the upper target. Start at $1$ .

There are two distinct questions:

What is the probability of reaching $3$ before $0$ ?
How many steps, on average, pass before reaching either boundary?

This small chain is adapted from Example 3.2 in Richard Weber’s Cambridge notes. The score and probabilities are stipulated: the example explains a calculation, rather than estimating a trading strategy’s ruin risk. A step has no calendar duration unless the model supplies one.

Four-state toy random walk: states 0 and 3 stop the process, while states 1 and 2 move left or right with probability one half. The chance of reaching 3 first is one third from 1 and two thirds from 2. Mean time to either boundary is two steps from both interior states.

The same transitions produce two different recursions. Expected time includes the step taken now; success probability does not.

Write $u_i$ for the success probability starting at $i$ . The boundary values are $u_0=0$ and $u_3=1$ . Conditioning on the first move gives

u_1=\tfrac12u_0+\tfrac12u_2=\tfrac12u_2, \qquad u_2=\tfrac12u_1+\tfrac12u_3=\tfrac12u_1+\tfrac12.

Substitution yields $u_1=\tfrac14u_1+\tfrac14$ , hence $u_1=1/3$ and $u_2=2/3$ . The one-step chance of moving upward is $1/2$ , but the eventual success probability from $1$ is $1/3$ : a first upward move still leaves the possibility of returning and failing.

Now let

T=\inf\{n\ge0:X_n\in\{0,3\}\}

and

t_i=\mathbb{E}[T\mid X_0=i]

. This is a hitting time. Starting on a boundary means

T=0

. At an interior state, spend one step and then average the remaining wait:

t_1=1+\tfrac12t_2, \qquad t_2=1+\tfrac12t_1.

Thus

t_1=1+\tfrac12(1+\tfrac12t_1)

, so

t_1=t_2=2

steps. Omitting the

1

would erase elapsed time. Adding it to the probability equations would mix incompatible quantities. The general expected-time recursion and its derivation through conditional expectation are described in Berkeley’s CS70 notes, “Hitting Time”.

The reusable equations—and their limits

For disjoint stopping sets $A$ (failure) and $B$ (success), let $p_{ij}$ be the transition probability from $i$ to $j$ . Outside the stopping sets,

u_i=\sum_j p_{ij}u_j, \qquad u_i=0\ (i\in A),\quad u_i=1\ (i\in B).

For the mean steps to reach $A\cup B$ ,

t_i=1+\sum_j p_{ij}t_j, \qquad t_i=0\ (i\in A\cup B).

Boundary conditions are part of the problem. “Time until success” differs from “time until either outcome”: paths that fail can make the former infinite. In a finite chain where every non-boundary state can reach a stopping boundary, absorption occurs almost surely with finite mean, and these boundary-value systems have unique solutions.

Outside that setting, check finiteness before rearranging expected-time equations as ordinary finite algebra. A positive chance of never hitting the target makes its unconditional mean hitting time infinite; even almost-sure hitting need not imply a finite mean in an infinite state space. The nonnegative solution may require a minimality condition. See Auckland’s STATS 325 notes, §8.12.

Also check that the state is sufficient. A trigger requiring consecutive losses needs the current loss-run length; today’s profit alone may lose that history. If transitions change over time, include time in the state or index the unknowns by time.

For a fuller boundary calculation, Gambler’s Ruin and First Passage Times extends these equations to arbitrary starting fortune and unequal up/down probabilities. Its public preview is available; the full lesson requires membership.

Practice: a step that leaves you where you started

A hypothetical review is pending. At each step it remains pending with probability $0.2$ , clears with probability $0.5$ , or fails with probability $0.3$ , using the same rules after every pending result. Clear and failed are stopping states. Starting pending, find the probability of eventual clearance and the mean steps to either outcome.

Answer. With

h

the clearance probability,

h=0.5+0.2h

, so

h=5/8=0.625

. With

m

the mean wait,

m=1+0.2m

, so

m=5/4=1.25

steps. A pending-to-pending move consumes a step even though the state does not change. The immediate clearance probability

0.5

excludes later attempts.

Sources

Richard Weber, Markov Chains, §§3.1–3.3: recursive conditioning, the four-state walk adapted above, and minimal nonnegative hitting-probability solutions.
UC Berkeley CS70, Markov Chains, “Hitting Time” and “Probability of A before B”: first-step equations for mean waits and competing boundaries.
Ruth Fewster, STATS 325, Chapter 8, §8.12: expected hitting times, infinite values and minimal nonnegative solutions.

One chain, two questions

The reusable equations—and their limits

Practice: a step that leaves you where you started

Sources

Related terms

Conditional expectation

Hitting time

Markov chain