recursion

trading_interview_blog

Sometimes, in solving a problem, you’ll run into an infinite series, where each term is smaller than the previous in some way. This often happens in games with repetitive play, like this:

Q: Suppose you flip a coin until you see heads. How many flips do you expect to need?

$E(X) = 1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{8} + ...$

If you know the formula for evaluating that, great! If not, no worries, we can instead formulate this

recursively.

Think about what actually happens when you flip. You expend 1 flip, and then you’re in a situation where there’s a 1/2 chance you’re done (no more flips!), and a 1/2 chance you have to start all over again. If you have to reflip, you still expect the same number of flips as you did before this flip, because coin flips are independent of each other. When a process has the same distribution no matter what successes or failures you had earlier, we consider it memoryless, and often times it helps to think about it recursively.

This gives us: $E(flips)=1+\frac{1}{2} \times 0+\frac{1}{2} \times E(flips)$