Skip to content
Get started

How noisy is an approximate counter?

An approximate counter stores a small integer XX, starting at X=0X=0. On each event it increments XX with probability 2−X2^{-X} (otherwise leaves it). After nn events it reports n^=2X−1\hat n=2^X-1, which is an unbiased estimate of nn. After n=100n=100 events, what is the standard deviation of n^\hat n? Give two decimals.

Show hints (2)+
  1. Given X=xX=x, what is the expected change of 2X2^X after one event? Of 4X4^X?
  2. E[4X]E[4^{X}] grows by 3E[2X]3E[2^{X}] per event, and E[2Xk]=k+1E[2^{X_k}]=k+1.

Answer

Reveal answer →

70.36 (± 0.05)

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions