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?

Click for background material…

Wald’s equation

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 $n$ th 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)$ .

Click for hint…

Define $n_t$ to be the number of empty bins after $t$ throws. Observe that, with each throw, each empty bin becomes non-empty with probability $1/n$ , so $\textrm{E}[n_t - n_{t+1} \, |\, n_t]$ is $n_t/n$ . Apply \eqref{eqnGD} from the lemma with $\delta (n_t) = \lceil n_t \rceil / 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)$ .

Click for hint…

Define $n_t$ to be the number of amoeba at time $t$ (so $n_0 = 1$ ). Observe that $\textrm{E}[n_{t+1} - n_{t} \, |\, n_t]$ is $1.5 n_t$ . Apply \eqref{eqnLI} from the lemma with $\delta (n_t) = 1.5\lceil n_t \rceil$ .

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.)

Bibliography

[1]	P. K. Lehre and C. Witt. General drift analysis with tail bounds. arXiv:1307.2559 [cs], July 2013.
[2]	P. K. Lehre and C. Witt. Concentrated hitting times of randomized search heuristics with variable drift. In H.-K. Ahn and C.-S. Shin, editors, Algorithms and Computation, number 8889 in Lecture Notes in Computer Science, pages 686–697. Springer International Publishing, Dec. 2014. DOI: 10.1007/978-3-319-13075-0_54.

Notes on algorithms

Lecture notes on algorithms

Wald’s equation for dependent increments

Wald’s for dependent increments

Example

Proof of lemma

Bibliography