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 n coins. In each round t=1,2,\ldots ,T, 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 X=X_0, X_1, \ldots , X_ T, where T is a stopping time with finite expectation. Let \delta :{\mathbb R}\rightarrow {\mathbb R}_+ be monotonic.

If \textrm{E}[X_{t+1} – X_{t} \, |\, X_ t ] ~ \le ~ \delta (X_ t) for t\lt T, and X is increasing and \delta 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 \textrm{E}[X_{t+1} – X_{t} \, |\, X_ t ] ~ \ge ~ \delta (X_ t) for t\lt T, and X is increasing and \delta 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 \textrm{E}[X_ t – X_{t+1} \, |\, X_ t ] ~ \le ~ \delta (X_ t) for t\lt T, and X is decreasing and \delta 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 \textrm{E}[X_ t – X_{t+1} \, |\, X_ t ] ~ \ge ~ \delta (X_ t) for t\lt T, and X is decreasing and \delta 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 T be the number of rounds; let n_ t be the number of coins left after t rounds. With each round, each remaining coin is discarded with probability 1/2, 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 \textrm{E}[T]?

Take \delta (n_ t) = \frac{1}{2}\lceil n_ t\rceil . Since n_ t is decreasing and \delta is increasing, by \eqref{eqnGD} in the lemma, the expected number of rounds until all n 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 {\rm H}(n) = 1+\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} is the nth Harmonic number.

(Without the ceiling in \delta (n_ t), the lemma would only give bound 2\ln (n/0) = \infty !)

Exercise 1.

Alice throws balls one at a time randomly into n bins. Show that the expected number of balls needed before all bins receive a ball is at most n\, {\rm H}(n).

Exercise 2.

Starting with just 1 amoeba, at each time t=1,2,\ldots , each existing amoeba splits into two with probability 1/2. Show that the expected time before there are n amoeba is at least 1.5\, {\rm H}(n).

Proof of lemma

Proof.

We first prove \eqref{eqnLI}. Define random sequence D_1, D_2,\ldots , D_ T by \displaystyle D_ t ~ =~ \int _{X_{t-1}}^{X_{t}} \frac{1}{\delta (z)}\, dz.

Since \delta is increasing, D_ t ~ \le ~ (X_{t} – X_{t-1})/\delta (X_{t-1}).

By assumption \textrm{E}[X_{t}-X_{t-1}\, |\, X_{t-1}] \le \delta (X_{t-1}), giving \textrm{E}[D_ t \, |\, T \ge t] \le 1. This (by Wald’s equation) gives \textrm{E}[\sum _{t=1}^ T D_ t] \le \textrm{E}[T], implying the bound.

(Wald’s requires that the D_ t’s are bounded from one side. Each D_ t is non-negative because X is increasing and \delta (z)\ge 0.)

This proves \eqref{eqnLI}. The proof of \eqref{eqnGI} is similar, but uses D_ t \ge (X_ t-X_{t-1})/\delta (X_{t-1}) to get \textrm{E}[D_ t \, |\, T \ge t] \ge 1. Bounds \eqref{eqnLD} and \eqref{eqnGD} follow from \eqref{eqnLI} and \eqref{eqnGI} by the change of variables X’_ t = -X_ t and \delta ’(z) = \delta (-z). (Or redefine D_ t = \int _{X_{t}}^{X_{t-1}} 1/\delta (z)\, dz in the proof above and proceed similarly.)