Waiting for Two Consecutive Successes

Turn a Pattern into a Stopped-Martingale Calculation

Waiting for two consecutive successes is not the same as waiting for two successes in total: a failure erases the progress made by a single success. A useful way to handle this dependence is to count successes and adjacent successful pairs up to the stopping time. Two martingales give the expectations of those counts, and together they determine the expected waiting time.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_n)_{n\ge1}$ be independent Bernoulli random variables with $\mathbb{P}(X_n=1)=p$ and $\mathbb{P}(X_n=0)=1-p$, where $0<p\le1$. Thus $X_n=1$ records a success on trial $n$. Let $\mathcal{F}_n=\sigma(X_1,\ldots,X_n)$, with $\mathcal{F}_0=\{\varnothing,\Omega\}$. Define the waiting time for the first two consecutive successes by

T=\inf\{n\ge2:X_{n-1}=1,\ X_n=1\}.

A random time $T$ is a stopping time for $(\mathcal{F}_n)$ if $\{T\le n\}\in\mathcal{F}_n$ for each $n$. Here this event means that at least one adjacent successful pair has appeared by trial $n$, so it is determined by $X_1,\ldots,X_n$; hence $T$ is a stopping time.

Theorem: For independent Bernoulli trials with success probability $0<p\le1$, the time $T$ is finite almost surely, has finite expectation, and $$ \mathbb{E}[T]=\frac{1+p}{p^2}. $$

Why Optional Stopping Is Valid Here

Before using a martingale at $T$, verify that $T$ is integrable. Examine the disjoint pairs of trials $(1,2),(3,4),\ldots,(2m-1,2m)$. If any of the first $m$ pairs consists of two successes, then $T\le2m$. These pairs are independent, and each is two successes with probability $p^2$. Therefore

\mathbb{P}(T>2m)\le(1-p^2)^m.

For a nonnegative integer-valued random variable, $\mathbb{E}[T]=\sum_{n\ge0}\mathbb{P}(T>n)$, with the equality also valid when the expectation is infinite. Grouping the terms for $n=2m$ and $n=2m+1$, and using $\mathbb{P}(T>2m+1)\le\mathbb{P}(T>2m)$, gives

\mathbb{E}[T]\le 2\sum_{m\ge0}(1-p^2)^m=\frac{2}{p^2}<\infty.

In particular, $T<\infty$ almost surely. This argument also covers $p=1$: the first disjoint pair is successful, so $T=2$.

Stopping-sum fact: Suppose $D_k$ is $\mathcal{F}_k$-measurable, $\mathbb{E}[D_k\mid\mathcal{F}_{k-1}]=0$, and $|D_k|\le C$ for a finite constant $C$. If $T$ is a stopping time and $\mathbb{E}[T]<\infty$, then $$ \mathbb{E}\left[\sum_{k=1}^{T}D_k\right]=0. $$

Proof. The event $\{T\ge k\}$ is in $\mathcal{F}_{k-1}$, since it says that stopping has not occurred by time $k-1$. Thus $\mathbf{1}_{\{T\ge k\}}D_k$ has expectation zero: conditioning on $\mathcal{F}_{k-1}$ gives $\mathbf{1}_{\{T\ge k\}}\mathbb{E}[D_k\mid\mathcal{F}_{k-1}]=0$. Also, $\sum_{k\ge1}\mathbb{E}[|\mathbf{1}_{\{T\ge k\}}D_k|]\le C\sum_{k\ge1}\mathbb{P}(T\ge k)=C\mathbb{E}[T]<\infty$. The sum is therefore integrable, and expectations can be interchanged with the sum. Every term has expectation zero, so the stopped sum has expectation zero. $\square$

Two Counts Determine the Waiting Time

For $n\ge0$, with an empty sum understood to be zero, define

M_n=\sum_{k=1}^{n}(X_k-p), \qquad N_n=\sum_{k=2}^{n}X_{k-1}(X_k-p).

Both are martingales for $(\mathcal{F}_n)$. For $M_n$, the increment $X_k-p$ has conditional expectation zero given $\mathcal{F}_{k-1}$, by independence and $\mathbb{E}[X_k]=p$. For $N_n$, the factor $X_{k-1}$ is already known at time $k-1$, so the increment $X_{k-1}(X_k-p)$ also has conditional expectation zero. Each increment has absolute value at most $1$. The stopping-sum fact applies to both, because $\mathbb{E}[T]<\infty$.

Apply it first to $M_n$. Writing out the stopped sum and taking expectations yields

0=\mathbb{E}\left[\sum_{k=1}^{T}(X_k-p)\right] =\mathbb{E}\left[\sum_{k=1}^{T}X_k\right]-p\mathbb{E}[T].

Thus the expected number of successes up to and including trial $T$ is $p\mathbb{E}[T]$. Apply the fact next to $N_n$. By the definition of $T$, exactly one adjacent pair of successes occurs among trials $1,\ldots,T$: it is the pair ending at $T$. Consequently, $\sum_{k=2}^{T}X_{k-1}X_k=1$, while $\sum_{k=2}^{T}X_{k-1}=\sum_{i=1}^{T-1}X_i$. Hence

0=\mathbb{E}\left[\sum_{k=2}^{T}X_{k-1}(X_k-p)\right] =1-p\mathbb{E}\left[\sum_{i=1}^{T-1}X_i\right].

It follows that the expected number of successes strictly before trial $T$ is $1/p$. Since $X_T=1$, the total number of successes through trial $T$ is one more, so its expectation is $1+1/p$. Equating this with $p\mathbb{E}[T]$, obtained from the first martingale, proves the theorem:

p\mathbb{E}[T]=1+\frac{1}{p}, \qquad \mathbb{E}[T]=\frac{1+p}{p^2}.

This proof uses optional stopping only in a form justified by integrability and bounded increments. It does not infer that a martingale stopped at an arbitrary unbounded random time preserves its expectation; the stopping-time condition and the integrable bound are doing essential work.

Worked Example: Success Probability One Third

Suppose each independent trial succeeds with probability $p=\tfrac13$. The probability of two successes in any specified disjoint pair is $p^2=\tfrac19$, so the preceding geometric-tail bound gives $\mathbb{E}[T]\le2/(1/9)=18$; in particular, the integrability condition holds. The martingale calculation gives

\mathbb{E}[T]=\frac{1+\tfrac13}{(\tfrac13)^2} =\frac{\tfrac43}{\tfrac19} =\frac43\cdot9=12.

Check the two expected counts that led to the answer. The expected number of successes before the terminal pair is $1/p=3$; including the final success at time $T$, the expected total is $3+1=4$. The first martingale says this total is $p\mathbb{E}[T]=\tfrac13\cdot12=4$, as required.

Worked Example: The Fair-Coin Calculation

For a fair coin, $p=\tfrac12$. The expected number of successes before the final pair is $1/p=2$, and the final trial adds one more success. The first stopped martingale therefore gives $\tfrac12\mathbb{E}[T]=3$, so

\mathbb{E}[T]=6.

A betting interpretation checks the terminal accounting. At each trial $k$, a new bettor enters with one unit and bets on two consecutive successes, stopping after two bets. With fair odds, a bettor who wins the first bet has two units to bet on the second. The wealth after $r$ consecutive successes is $2^r$; after a failure it is zero. Conditional on the information before a trial, each active bettor’s expected wealth after the trial equals the wealth before it. A new bettor’s expected wealth after the first bet is $\tfrac12\cdot2+\tfrac12\cdot0=1$. Thus the total wealth of all bettors who have entered by time $n$, minus the $n$ units they initially invested, is a martingale. While play continues, only the new bettor and at most one bettor awaiting a second result can have nonzero wealth, so its increments are bounded. Since $\mathbb{E}[T]<\infty$, the stopping-sum argument just proved gives expected terminal net profit zero.

At time $T$, the bettor who entered at $T-1$ has won twice and has four units. The bettor who entered at $T$ has won the first bet and has two units. Each of the $T-2$ earlier bettors has had two trials but did not win two consecutive successes, so has zero units. The aggregate terminal wealth is $4+2=6$, against $T$ units invested; the net profit is $6-T$. Its expectation is zero, giving $\mathbb{E}[T]=6$, in agreement with the indicator-sum calculation.

Worked Example: A Biased Coin with Success Probability Two Thirds

Let $p=\tfrac23$. A state description records the current run of consecutive successes: state $0$ means there is no current success run, state $1$ means the most recent trial was a success, and state $2$ means the target pair has occurred. In the order $0,1,2$, the transition matrix is

P= \begin{bmatrix} \tfrac13&\tfrac23&0\\ \tfrac13&0&\tfrac23\\ 0&0&1 \end{bmatrix}.

The first row sums to $\tfrac13+\tfrac23+0=1$, the second to $\tfrac13+0+\tfrac23=1$, and the third to $0+0+1=1$. Let $e_0,e_1$ be the expected remaining number of trials from states $0,1$. Conditioning on the next trial gives

e_0=1+\tfrac13e_0+\tfrac23e_1, \qquad e_1=1+\tfrac13e_0+\tfrac23\cdot0.

The first equation rearranges to $e_0=\tfrac32+e_1$. The second gives $e_1=1+\tfrac13e_0$. Substitution yields $e_0=\tfrac32+1+\tfrac13e_0$, hence $\tfrac23e_0=\tfrac52$, $e_0=\tfrac{15}{4}$, and $e_1=1+\tfrac13\cdot\tfrac{15}{4}=\tfrac94$. Check both equations: $1+\tfrac13\cdot\tfrac{15}{4}+\tfrac23\cdot\tfrac94=1+\tfrac54+\tfrac32=\tfrac{15}{4}$; and $1+\tfrac13\cdot\tfrac{15}{4}=\tfrac94$. The general formula independently gives $(1+\tfrac23)/(\tfrac23)^2=\tfrac53\cdot\tfrac94=\tfrac{15}{4}$, matching the expected time from state $0$.

Common Accounting Pitfall

In the fair-coin betting calculation, omitting the bettor who enters at time $T$ gives the expression $4-1-(T-2)$: four units from the successful bettor, minus that bettor’s one-unit initial stake, and minus one unit for each of the $T-2$ earlier losing bettors. Taking expectations and setting this incomplete expression to zero gives $0=4-1-(\mathbb{E}[T]-2)=5-\mathbb{E}[T]$, or the incorrect answer $\mathbb{E}[T]=5$. The missing bettor entered at time $T$, won the first bet, and has net profit $2-1=1$. Including that profit gives the correct expected terminal-profit identity

0=4-1-(\mathbb{E}[T]-2)+1=6-\mathbb{E}[T], \qquad \mathbb{E}[T]=6.

The zero here is an expectation of the terminal net profit, not a pathwise identity: on a particular run the total net profit is $6-T$, which need not be zero. The stopped-martingale justification is what permits setting its expectation to zero. In the indicator-sum method, the corresponding detail is to include the terminal success $X_T=1$ when converting the count before $T$ into the count through $T$.

Check Your Understanding

Use the definitions and stopped-sum identities above to answer these questions.

For success probability $p=\tfrac14$, compute $\mathbb{E}[T]$ and the expected number of successes strictly before $T$.
Why is $\{T\ge k\}$ measurable with respect to $\mathcal{F}_{k-1}$, and why is that useful when taking the expectation of a stopped sum?
In the fair-coin betting accounting, what is the terminal wealth of the bettor who entered at time $T$, and why must that bettor be included?
Which step in the proof establishes that optional stopping is valid for these martingales at $T$?
What goes wrong with the formula $(1+p)/p^2$ at $p=0$, and what is the waiting time in that case?

Waiting for Two Consecutive Successes

What You'll Learn