2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Jianrong Li Jul 4 '18 at 19:12
  • $\begingroup$ Take it as an exercise. If the formula confuses you, try computing the expectation from first principles. $\endgroup$ – Yuval Filmus Jul 4 '18 at 19:40
1
$\begingroup$

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

We have \begin{align} \mathbb{E}[2^{X_n}] & = \sum_i 2^i Pr[X_n=i] \\ & = \sum_i 2^i( Pr[X_n=X_{n-1}+1 \text{ and } X_{n-1} = i-1 ] + Pr[X_n=X_{n-1} \text{ and } X_{n-1}=i] ) \\ & = \sum_i 2^i( \frac{1}{2^{i-1}} Pr[ X_{n-1} = i-1 ] + (1-\frac{1}{2^i}) Pr[ X_{n-1}=i] ) \\ & = \sum_i 2 Pr[ X_{n-1} = i-1 ] + \sum_i 2^i Pr[ X_{n-1} = i ] - \sum_i Pr[ X_{n-1} = i ] \\ & = \sum_i 2^i Pr[ X_{n-1} = i ] + \sum_i Pr[ X_{n-1} = i ] \\ & = \sum_i 2^i Pr[ X_{n-1} = i ] + 1 \\ & = n+1. \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.