I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

1. Initial: $X=0$

2. For each item in the stream, increment $X$ with probability $\frac{1}{2^X}$.

3. Output: $2^X-1$.

It is said that $\mathbb{E}[2^X-1]=m$, where $X_m$ is the value of $X$ after seeing $m$ items.

How to show that $\mathbb{E}[2^X-1]=m$? Any help would be greatly appreciated.

Let us denote by $X_n$ the value of $X$ after reading $n$ elements, and let $Y_n = 2^{X_n}$. We have $Y_0 = 1$ and $Y_{n+1}$ equals $2Y_n$ with probability $1/Y_n$, and $Y_n$ otherwise. Therefore $$\mathbb{E}[Y_{n+1}|Y_n] = Y_n + \frac{Y_n}{Y_n} = Y_n + 1,$$ which together with $Y_0 = 1$ implies that $\mathbb{E}[Y_n] = n + 1$.
More generally, we can estimate all moments of $Y_n$ in this way. We have $$\mathbb{E}[Y_{n+1}^k|Y_n^k] = Y_n^k + \frac{(2^k-1)Y_n^k}{Y_n} = Y_n^k + (2^k-1) Y_n^{k-1},$$ and so $Y_0^k = 1$ implies that $$\mathbb{E}[Y_n^k] = 1 + (2^k-1) \sum_{m=0}^{n-1} \mathbb{E}[Y_n^{k-1}].$$ As an example, $$\mathbb{E}[Y_n^2] = 1 + 3 \sum_{m=0}^{n-1} (m+1) = 1 + 3 \frac{n(n+1)}{2}.$$ Therefore the variance of the estimator $Y_n-1$ is $$\mathbb{V}[Y_n-1] = \mathbb{V}[Y_n] = \mathbb{E}[Y_n^2] - \mathbb{E}[Y_n]^2 = 1 + 3 \frac{n(n+1)}{2} - (n+1)^2 = \frac{n(n-1)}{2}.$$ More generally, induction shows that $\mathbb{E}[Y_n^k] = \Theta(n^k)$, and with some effort we can even calculate the leading constant: $$\mathbb{E}[Y_n^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell} n^k + O(n^{k-1}).$$ In particular, if we denote $Z_n = (Y_n-1)/n$ then $Z_n \to Z$, where $$\mathbb{E}[Z^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell}.$$ For more on $Z$, see Theorem 7 in Ph. Robert, On the asymptotic behavior of some algorithms.
• Hi Yuval, thank you very much. I still have one question. Why $\mathbb{E}[Y_{n+1}|Y_n]=Y_n + \frac{Y_n}{Y_n}$? – Jianrong Li Jul 4 '18 at 19:12
We can use induction to prove the theorem. Let $X_n$ be the value of $X$ after $n$ events. If $n=0$, then $X_0=0$ and $2^{X_0}=1=0+1=n+1$. The result is true.
Suppose that $\mathbb{E}[2^{X_{n-1}}]=(n-1)+1=n$. We will prove that $\mathbb{E}[2^{X_n}]=n+1$.