Approximate Counting

What if you wanted a counter that could count up to the number of atoms in the universe, but you wanted to store the counter in 8 bits? You could use the amazing probabilistic algorithm described below! In this example we are going to show that the expected return value of stochastic_counter(4), where count is called four times, is in fact equal to four.

def stochastic_counter(true_count):
   n = -1
   for i in range(true_count):
       n += count(n) 
   return 2 ** n  # 2^n, aka 2 to the power of n
 
def count(n):
   # To return 1 you need n heads. Always returns 1 if n is <= 0
   for i in range(n):
       if not coin_flip():
           return 0
   return 1
 
def coin_flip():
   # returns true 50% of the time
   return random.random() < 0.5

Let $X$ be a random variable for the value of $n$ at the end of \texttt{stochastic\_counter(4)}. Note that $X$ is not a binomial because the probabilities of each outcome change.

Let $R$ be the return value of the function. $R = 2^X$ which is a function of $X$. Use the law of unconscious statistician $$E[R] = \sum_{x} 2^x \cdot P(X=x)$$ We can compute each of the probabilities $P(X=x)$ separately. Note that the first two calls to count will always return 1. Let $H_i$ be the event that the $i$th call returns 1. Let $T_i$ be the event that the $i$th call returns 0. $X$ can't be less than 1 because the first two calls to count always return 1. $P(X=1) = P(T_3,T_4)$ \\ $P(X=2) = P(H_3,T_4) + P(T_3,H_4)$ \\ $P(X=3) = P(H_3, H_4)$

At the point of the third call to count, $n = 1$. If $H_3$ then $n=2$ for the fourth call and the loop runs twice. \begin{align*} P(H_3,T_4) &= P(H_3) \cdot P(T_4|H_3) \\ &= \frac{1}{2} \cdot ( \frac{1}{2} + \frac{1}{4}) \end{align*} \begin{align*} P(H_3,H_4) &= P(H_3) \cdot P(H_4|H_3) \\ &= \frac{1}{2} \cdot \frac{1}{2} \end{align*}

If $T_3$ then $n=1$ for the fourth call. \begin{align*} P(T_3,H_4) &= P(T_3) \cdot P(H_4|T_3) \\ &= \frac{1}{2} \cdot \frac{1}{2} \end{align*} \begin{align*} P(T_3,T_4) &= P(T_3) \cdot P(T_4|T_3) \\ &= \frac{1}{2} \cdot \frac{1}{2} \end{align*} Plug everything in: \begin{align*} E[R] &= \sum_{x=1}^3 2^x \cdot P(X=x) \\ &= 2 \cdot \frac{1}{4} + 4\cdot \frac{5}{8} + 8\cdot \frac{1}{8}\\ &= 4 \end{align*}