$\DeclareMathOperator{\p}{P}$ $\DeclareMathOperator{\P}{P}$ $\DeclareMathOperator{\c}{^C}$ $\DeclareMathOperator{\or}{ or}$ $\DeclareMathOperator{\and}{ and}$ $\DeclareMathOperator{\var}{Var}$ $\DeclareMathOperator{\Var}{Var}$ $\DeclareMathOperator{\Std}{Std}$ $\DeclareMathOperator{\E}{E}$ $\DeclareMathOperator{\std}{Std}$ $\DeclareMathOperator{\Ber}{Bern}$ $\DeclareMathOperator{\Bin}{Bin}$ $\DeclareMathOperator{\Poi}{Poi}$ $\DeclareMathOperator{\Uni}{Uni}$ $\DeclareMathOperator{\Geo}{Geo}$ $\DeclareMathOperator{\NegBin}{NegBin}$ $\DeclareMathOperator{\Beta}{Beta}$ $\DeclareMathOperator{\Exp}{Exp}$ $\DeclareMathOperator{\N}{N}$ $\DeclareMathOperator{\R}{\mathbb{R}}$ $\DeclareMathOperator*{\argmax}{arg\,max}$ $\newcommand{\d}{\, d}$

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*}