Recursive Expectations in Sequential Experiments

Why Expectations Can Be Built One Stage at a Time

In a sequential experiment, the outcome at one stage can change what happens next. A trial might update a process from “no consecutive successes” to “one consecutive success”; a draw changes the composition of an urn; or an inspection result changes the cost and distribution of the next inspection. Rather than listing every possible full sequence, we can calculate the expectation by working backward from the final stage.

The key is to condition on the first outcome from the current state. Each possible outcome contributes its probability multiplied by the immediate reward plus the expected value of continuing from the state that outcome produces. This is the finite-stage expectation recursion. The conditional expectation principle behind it is familiar from earlier material; here the focus is how to set up and solve the recursion for an evolving experiment.

Setup and Backward Recursion

Definition: Consider a finite experiment with stages \(t=0,1,\ldots,T\). At stage \(t\), the experiment has a state \(S_t\) in a finite state space \(\mathcal S_t\). Given \(S_t=s\), an outcome \(Y_{t+1}\) is drawn from a finite set with probabilities \(q_t(y\mid s)\). The outcome produces a next state \(S_{t+1}=G_t(s,y)\) and an immediate reward \(r_t(s,y)\). Assume these probabilities and rules describe the conditional law given the entire history through stage \(t\): once \(S_t\) is known, earlier history does not further affect the next outcome. Let \(h(S_T)\) be a terminal reward. The total payoff is the sum of the stage rewards and terminal reward.

The state must contain enough information for the stated conditional-law assumption to hold. It need not record the entire past: it should record the parts of the past that affect future outcome probabilities, transitions, or rewards. Rewards may be negative, as with costs, and all quantities here are finite, so their expectations exist.

W=\sum_{t=0}^{T-1} r_t(S_t,Y_{t+1})+h(S_T).

For a state \(s\) at stage \(t\), define \(V_t(s)\) to be the expected total payoff from stage \(t\) onward, including the terminal reward. The recursion is

Theorem: Set \(V_T(s)=h(s)\). For \(t=T-1,T-2,\ldots,0\), define

V_t(s)=\sum_y q_t(y\mid s)\left[r_t(s,y)+V_{t+1}\bigl(G_t(s,y)\bigr)\right].

Then \(V_t(s)\) is the conditional expected payoff from stages \(t\) through \(T-1\), together with the terminal reward, given the current state \(S_t=s\). In particular, if the initial state is \(s_0\), then \(E[W]=V_0(s_0)\).

The sum is over the possible outcomes at stage \(t+1\). The term inside the brackets has two parts: the reward received now and the expected payoff from the next state. If an outcome can occur in several ways but produces the same next state, its outcomes can either be kept separate in the sum or combined by adding their probabilities.

Why the Recursion Is Valid

A direct proof works backward from the terminal stage. Write \(W_t\) for the payoff accumulated from stage \(t\) onward, including \(h(S_T)\). At the final stage, \(W_T=h(S_T)\), so the asserted conditional expectation is \(V_T(S_T)=h(S_T)\). Suppose the assertion holds at stage \(t+1\). Given \(S_t=s\), partition according to the possible values \(y\) of \(Y_{t+1}\). On the event \(Y_{t+1}=y\), the next state is \(G_t(s,y)\); the conditional-law assumption ensures the continuation expectation is \(V_{t+1}(G_t(s,y))\). Therefore,

\begin{aligned} E[W_t\mid S_t=s] &=\sum_y q_t(y\mid s)\, E\left[r_t(s,Y_{t+1})+W_{t+1}\mid S_t=s,\ Y_{t+1}=y\right]\\ &=\sum_y q_t(y\mid s)\left[r_t(s,y)+V_{t+1}\bigl(G_t(s,y)\bigr)\right]\\ &=V_t(s). \end{aligned}

The second equality uses that, after the outcome is fixed, the immediate reward and next state are fixed, and the expected continuation depends on the current state at stage \(t+1\). This proves the claim by backward induction. Taking expectation over the initial state gives \(E[W]=V_0(s_0)\) when that state is fixed. \(\square\)

The recursion also determines the answer uniquely: the terminal values are specified, and each earlier value is calculated from values at the next stage. No equation needs to be solved simultaneously with another at the same stage. This is why finite-stage calculations proceed backward, even though the experiment itself runs forward.

Choose the state.
Record the information that governs the next outcome, transition, and reward.

Set the terminal value.
Specify \(V_T(s)=h(s)\), including any terminal payoff or boundary condition.

Work backward.
For each state, sum the probability of each outcome times its immediate reward plus the value of the resulting state.

Evaluate the initial state.
The value at the actual starting state is the desired expected payoff.

Worked Examples

Worked Example: Attempts Until Success, With a Cap

An experiment makes independent attempts, each successful with probability \(p=0.3\). It stops at the first success or after four attempts, whichever comes first. Find the expected number of attempts made.

Let \(V_k\) be the expected number of additional attempts when \(k\) attempts remain. If \(k=0\), no more attempts are made, so \(V_0=0\). When \(k\geq 1\), one attempt is made immediately. With probability \(0.3\) it succeeds and the experiment stops; with probability \(0.7\) it fails and \(k-1\) attempts remain. Thus

V_k=1+0.7V_{k-1}.

Working backward gives \(V_1=1+0.7(0)=1\), \(V_2=1+0.7(1)=1.7\), \(V_3=1+0.7(1.7)=2.19\), and \(V_4=1+0.7(2.19)=2.533\). The expected number of attempts is therefore \(2.533\).

As a check, attempt \(j\) is made exactly when the first \(j-1\) attempts all fail. Its probability of being made is \(0.7^{j-1}\). Therefore the expected count is \(1+0.7+0.7^2+0.7^3=1+0.7+0.49+0.343=2.533\), agreeing with the recursion.

Worked Example: State-Dependent Rewards for Consecutive Successes

A fair coin is tossed three times. The state records the current run of consecutive heads, with states \(0,1,2\); state \(2\) means that two consecutive heads have already occurred and is absorbing. A head earns \(1\) when the current state is \(0\), and \(3\) when the current state is \(1\). A tail earns \(-1\) and resets the state to \(0\). Once state \(2\) is reached, subsequent tosses earn \(0\). At the end, a terminal bonus of \(4\) is paid if the process is in state \(2\), and \(0\) otherwise. Find the expected total payoff starting in state \(0\).

Let \(V_k(s)\) be the expected payoff with \(k\) tosses remaining and current state \(s\). At \(k=0\), only the terminal bonus remains:

V_0(0)=0,\qquad V_0(1)=0,\qquad V_0(2)=4.

With one toss remaining, from state \(0\) a head earns \(1\) and moves to state \(1\), while a tail earns \(-1\) and returns to state \(0\). Hence \(V_1(0)=\tfrac12(1+0)+\tfrac12(-1+0)=0\). From state \(1\), a head earns \(3\) and reaches state \(2\), while a tail earns \(-1\) and returns to state \(0\), so \(V_1(1)=\tfrac12(3+4)+\tfrac12(-1+0)=3\). State \(2\) remains absorbing and earns no further toss reward, giving \(V_1(2)=4\).

With two tosses remaining, the same outcome-by-outcome calculation gives

\begin{aligned} V_2(0)&=\tfrac12(1+V_1(1))+\tfrac12(-1+V_1(0)) =\tfrac12(4)+\tfrac12(-1)=1.5,\\ V_2(1)&=\tfrac12(3+V_1(2))+\tfrac12(-1+V_1(0)) =\tfrac12(7)+\tfrac12(-1)=3,\\ V_2(2)&=4. \end{aligned}

With three tosses remaining and initial state \(0\),

V_3(0)=\tfrac12(1+V_2(1))+\tfrac12(-1+V_2(0)) =\tfrac12(4)+\tfrac12(0.5)=2.25.

The expected total payoff is \(2.25\). The state matters because the reward from a head depends on the current run, and the future distribution of rewards depends on the state reached.

Worked Example: Drawing Without Replacement With a Terminal Bonus

An urn contains two red balls and one blue ball. The balls are drawn one at a time without replacement until the urn is empty. Each red ball pays \(3\), and the blue ball pays \(1\). In addition, a bonus of \(6\) is paid if the final ball drawn is red. Find the expected total payment.

Use the state \((r,b)\), the numbers of red and blue balls remaining. Define \(V(r,b)\) as the expected future payment. A red draw earns \(3\); if it is the last ball, it earns an additional \(6\). A blue draw earns \(1\). These state-dependent rewards give the boundary value \(V(0,0)=0\), and for nonempty urns the recursion is

V(r,b)=\frac{r}{r+b}\left(3+6\mathbf{1}_{\{r=1,\ b=0\}}+V(r-1,b)\right) +\frac{b}{r+b}\left(1+V(r,b-1)\right),

where a term with zero numerator is omitted, so the expression never calls for a state with a negative count. First, \(V(0,1)=1\), because the only ball is blue. Also \(V(1,0)=3+6=9\), because the only ball is red and earns the terminal bonus. From state \((1,1)\), each color is equally likely:

V(1,1)=\tfrac12(3+V(0,1))+\tfrac12(1+V(1,0)) =\tfrac12(4)+\tfrac12(10)=7.

From state \((2,0)\), both draws are red, and only the second is the last ball, so \(V(2,0)=3+9=12\). Initially, a red ball is drawn with probability \(2/3\) and a blue ball with probability \(1/3\). Therefore

V(2,1)=\tfrac23(3+V(1,1))+\tfrac13(1+V(2,0)) =\tfrac23(10)+\tfrac13(13)=11.

The answer also checks directly: the ordinary draw payments sum to \(3+3+1=7\) regardless of order, and the last ball is red with probability \(2/3\), giving expected bonus \(6(2/3)=4\). The total expectation is \(7+4=11\), matching the recursion.

Common Pitfall and Practical Uses

A common error is to average only the next state’s value and forget the reward earned on the transition. In the urn example, replacing \(3+V(r-1,b)\) by \(V(r-1,b)\) would omit the payment for a red draw. Another error is to use the same continuation value after distinct outcomes even when they lead to different states. The correct contribution from an outcome is its probability multiplied by both its immediate reward and the value of the state it creates.

A related modeling mistake is choosing a state that does not determine the future. For example, keeping only the total number of balls in the urn is insufficient: the chance of drawing red depends on how many red balls remain. The pair \((r,b)\) retains the information needed. Likewise, a streak process must record the current streak if future rewards depend on it.

Finite-stage expectation recursions are useful whenever an experiment evolves through a manageable set of states: capped repeated trials, sequential inspections, finite-horizon decision problems, and sampling schemes with changing composition. The method replaces enumeration of every complete outcome sequence with a calculation organized by stage and state. It is especially effective when many different histories lead to the same state, because those histories share the same continuation value.

Check Your Understanding

For each question, identify the state and the relevant conditional calculation before evaluating any numbers.

In the capped-attempt example, why is the probability of making the next attempt \(0.7\), rather than \(0.3\)?
A process has terminal value \(h(s)\) and one remaining stage. Write the recursion for its expected payoff when the next outcome has two possible values.
In the consecutive-heads example, why is it not enough to record only the number of tosses remaining?
For an urn with three red and two blue balls drawn without replacement, what state would be sufficient to calculate future expected payments?
In a finite-stage recursion, what changes if rewards are costs rather than gains? Explain how the recursion accommodates this.