-

# You begin with \$100. You flip a fair coin. Heads, you get 1\$. Tails, your money gets inversed (i.e. first tails, your money is now 1/100). What is the expected value after 7 flips? (hint: recursion)

Répondre

## Réponses aux questions d'entretien

7 réponse(s)

5

You're on the right path, but I think I have a slightly more intuitive way of looking at it: As the person before me mentioned it's much easier to simplify this problem by finding the probability that you end near 100. There are two ways to end near 100, you either already have 100 and flip heads, or you have 100 and flip tails twice in a row, everything else will give you a messy fraction. Let's see how this plays out: Flip 0: you have one 100. Flip 1: the 100 becomes 101, you still have one. Flip 2: the 101 becomes 102, the 100 from flip 0 has now flipped back and gave us 100, now we have two. Flip 3: the 102 becomes 103, the 100 becomes 101, and the 101 from flip 1 flipped back and gave us 101, now we have three. A familiar pattern is emerging. You can add the number of 100s from the turn before and the number of 100s from two turns before (the flip backs) to determine how many 100s you have now. The sequence will goes 1, 1, 2, 3, 5, 8, 13, 21. Fibonacci! It's not a perfect answer, but for aesthetic purposes i will go with 21/128.

Joe le

1

@the one before me (again) Aren't the bounds 107 (highest) and 1/106(lowest)?

Utilisateur anonyme le

1

@ones after: no yes and yes. 49 is incorrect. The correct divisor is 2^7. That was my mistake. As for the second question, I was being pretty fast and loose with my rounding. The point is only that there is a similar probability of both values near 0 and near 100, so the value ought to be between. I believe I messed up the 49

Python rules le

0

I don't see a closed solution, but I get 18.26083027739004 from numerical calculation. This is not an integer divided by 49 or 128.

Utilisateur anonyme le

0

@the one before me 49 is the number of options?

Utilisateur anonyme le

0

47.701. Got this by writhing python program to simulate every solution in the tree and divide by number of options. Each has same probability, so it's just 2337.38 / 49. If you think about it, it should be between 107 and 1, since those are roughly the bounds

Python rules le

1

The Expected value on the 7th flip is: E(X_7) = .5(E(X_6) +1) + .5(1/E(X_6)). In general, E(X_k) = .5(E(X_k-1) +1) + .5(1/E(X_k-1)). Rearranged, this becomes: E(X_k) = [E(X_k-1)^2 + E(X_k-1) + 1]/(2*E(X_k-1)) Using this equation we can plug in 100 to get the expected value of 1 flip, then plug that answer back in to get the expected value of 2 flips etc. The answer I got for the 7th flip is about 1.63. An interesting followup question is whether the expected value converges as the number of flips goes to infinity. I believe the answer is yes and you get it by solving: X = [X^2 + X + 1]/(2*X) We get (1+6^.5)/2 or about 1.72. This looks to be about where we were at after 7 flips.

Archai le

## Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.