Section 11.3

First-Step Equations for Expectations

Expected durations or rewards of processes that restart or branch: the trapped miner, games that continue on some outcomes, coin-pair re-flipping, sums before stopping.

Toolkit

Use first-step (one-step conditioning) analysis: write the expected total as the cost/reward of the next step plus the probability-weighted expectation of continuing from the resulting state. For a process with state-independent restart probability $p$ and per-step cost $c$ ,

E = c + pE \implies E = \frac{c}{1-p}.

More generally, for a Markov chain on finitely many states, let $E_i$ be the expected remaining time (or reward) from state $i$ ; then

E_i = c_i + \sum_j P(i\to j)E_j,

a linear system solved by exploiting symmetry or absorbing states ( $E_{\text{absorbing}}=0$ ). Key facts: a success repeated independently with probability $p$ each trial gives a $\mathrm{Geom}(p)$ number of trials with mean $1/p$ ; operations that preserve a parity or other invariant restrict which states are reachable, collapsing the state space before solving.

Problems