# Wald’s equation for dependent increments

A variant of Wald’s equation to use when the expected increment depends on the sum so far.

Wald’s equation applies to any sequence that, with each step, increases (or decreases) in expectation by a constant additive amount. What about sequences where the expected change with each step depends on the current value? For example, suppose Alice starts with coins. In each round , she flips each remaining coin and discards those that come up tails. She stops once all coins are discarded. What is the expected number of rounds?

# Wald’s for dependent increments

Lemma (Wald’s for dependent increments).

Consider a random sequence , where is a stopping time with finite expectation. Let be monotonic.

If for , and is increasing and is increasing, then

\begin{equation} \label{eqnLI} \textrm{E}[T] \, \ge \, \textrm{E}\left[\int _{X_0}^{X_ T} \frac{1}{\delta (z)} dz\right]. \end{equation}

If for , and is increasing and is decreasing, then

\begin{equation} \label{eqnGI} \textrm{E}[T] \, \le \, \textrm{E}\left[\int _{X_0}^{X_ T} \frac{1}{\delta (z)} dz\right]. \end{equation}

If for , and is decreasing and is decreasing, then

\begin{equation} \label{eqnLD} \textrm{E}[T] \, \ge \, \textrm{E}\left[\int _{X_ T}^{X_0} \frac{1}{\delta (z)} dz\right]. \end{equation}

If for , and is decreasing and is increasing, then

\begin{equation} \label{eqnGD} \textrm{E}[T] \, \le \, \textrm{E}\left[\int _{X_ T}^{X_0} \frac{1}{\delta (z)} dz\right]. \end{equation}

# Example

For Alice’s coin-flipping example above, let be the number of rounds; let be the number of coins left after rounds. With each round, each remaining coin is discarded with probability , so

$\textrm{E}[n_ t – n_{t+1} \, |\, n_ t ] ~ =~ \textstyle \frac{1}{2}\, n_ t ~ =~ \frac{1}{2}\, \lceil n_ t \rceil .$

(The ceiling will be useful below.) What does this tell us about ?

Take . Since is decreasing and is increasing, by \eqref{eqnGD} in the lemma, the expected number of rounds until all coins are discarded is at most

$\int _{n_ T}^{n_0} \frac{1}{\frac{1}{2}\lceil z\rceil \, dz} ~ =~ 2 \int _0^ n \frac{1}{\lceil z \rceil \, dz} ~ =~ 2\, {\rm H}(n),$

where is the th Harmonic number.

(Without the ceiling in , the lemma would only give bound !)

Exercise 1.

Alice throws balls one at a time randomly into bins. Show that the expected number of balls needed before all bins receive a ball is at most .

Exercise 2.

Starting with just 1 amoeba, at each time , each existing amoeba splits into two with probability 1/2. Show that the expected time before there are amoeba is at least .

# Proof of lemma

Proof.

We first prove \eqref{eqnLI}. Define random sequence by

Since is increasing,

By assumption , giving . This (by Wald’s equation) gives , implying the bound.

(Wald’s requires that the ’s are bounded from one side. Each is non-negative because is increasing and .)

This proves \eqref{eqnLI}. The proof of \eqref{eqnGI} is similar, but uses to get . Bounds \eqref{eqnLD} and \eqref{eqnGD} follow from \eqref{eqnLI} and \eqref{eqnGI} by the change of variables and . (Or redefine in the proof above and proceed similarly.)