How noisy is an approximate counter?
An approximate counter stores a small integer , starting at . On each event it increments with probability (otherwise leaves it). After events it reports , which is an unbiased estimate of . After events, what is the standard deviation of ? Give two decimals.
Show hints (2)+
- Given , what is the expected change of after one event? Of ?
- grows by per event, and .
Answer
Reveal answer →Final 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