If you flip a coin (head-tail) until you decide to stop and you want to maximize the ratio of heads to total flips, what is that expected ratio and your optimal strategy?
Thank you for your help.
| +9 | Natural Gas Analyst Path to Trader | 0 | 1d |
| +7 | RBC S&T 27' | 14 | 6h |
| +6 | CRE to S&T lateral opportunities | 4 | 9h |
| +6 | Exiting Sell Side FI Trading | 1 | 1d |
| +3 | S&T Outlook and Pivot from Buy Side | 1 | 8h |
Career Resources
Get instant access to lessons taught by experienced private equity pros and bulge bracket investment bankers including financial statement modeling, DCF, M&A, LBO, Comps and Excel Modeling.
Is it a fair coin? If so, this is pretty easy. Have you thought about it at all?
Yes, coin is fair but I don't think this is pretty easy, at least there are non trivial parts. Could you post your solution ?
If you get a heads on the first flip, obviously stop. If you get tails 1st, heads 2nd, stop. If you get 2 tails to start keep flipping until 0.5 ratio (or very close to it). Expected ratio of future flips is 0.5, so if you're above that you want to stop, and if you're below that you want to keep flipping (it will bring up your expected average). As an example, if you flip 3: 2 tails, 1 heads, your ratio is 0.33. Future flips are 0.5 so they will bring up your 0.33 average.
this is by no means an easy question but the solution is the same as the solution to the perpetual american put option. the solution above such that you ratio > 1/2 is definitely not the optimal solution and even if that were true, would you be able to derive the value of this given your strategy? the solution is state dependent on the total flips and the total number of heads till this point and it is markovian. given this, you should be able to derive a solution but i have not had the time to do it. hope this helps
http://www.ieor.berkeley.edu/~xinguo/papers/I.A.9.pdf
I'll state my strategy more explicitly and give an approximate expected value.
Flip if: # of Heads flipped so far = # of Tails flipped so far
50% of the time you will flip Heads the first time (Ratio = 1), and 50% of the time you will flip Tails.
1st Flip Heads (50%): Stop. Ratio = 1. 1st Flip Tails (50%): Continue Forever. Ratio = 0.5.
This makes Expected Ratio = 0.75. However, what if you flip tails, heads, heads? Then you would stop with a 0.67 Ratio, rather than flipping forever. This case happens 12.5% of the time. So,
1st Flip Heads (50%): Ratio = 1 Tails, Heads, Heads (12.5%): Ratio = 0.67 Everything Else (37.5%): Ratio = 0.5
This gives you an expected ratio of 0.77. As you keep doing this (3 heads, 2 tails 3% of time = Ratio 0.6, etc.), the solution is bound at ~0.78. Obviously, you could find out exact answer with some more advanced math than this trial and error method, but it appears 0.78 is about right.
@"woohoobaby" : Thanks for your answer, but I cannot figure out completely how is this connected to american put option, for example what is strike price of that option, is it 1/2 ? I didn't actually find a way how to apply that approach for solution to this problem...
@"derivstrader5" : Your solution is quite good, but the biggest problem for me was that advanced math at the end :). Unless I got something wrong, it seems that you have to count for every even number (2n) number of possible outcomes where you always have less or equal heads than tails and after 2n throws you have exact number of heads and tails, which is non-trivial, at least to me...
Actually, the math comes out to the following and I was bored at work so I proved it...
It turns out the answer is that you stop the second your ratio is greater than 1/2. Now, solving the expected value of this problem is key. So using @derivstrader5 scenario, 1st flip, if heads you stop. if tails you continue. On 2nd flip, in either scenario, you don't stop, so actually we deduce that the game ends only on an odd flip (why? think of this problem as the first stopping time such that the number of heads > number of tails. the first occurance can only on an odd number of flips).
Now let's say you are given that the game stopped on the 1st, 3rd, or 5th flip, how many heads do you have? In each respective case, you have 1,2, and 3 heads. Why? Because again, it is the first time such that the number of heads is greater than the number of tails.
Now, we have a closed form sum of the expected value which is:
Sum i=0 to infinity ( {[(1/2)^(i)]/C} * { (i+1)/(2i+1)} )
where C is a normalizing constant to normalize the distribution of the probability space of the length of the game. Solving the rest from here is trivial. Also, this game is very similar to a perpetual american put because if you think about it, you are exercising your option. In this game, it is actually a perpetual call option with a boundary with strike 0.
@"woohoobaby": Thank you for your response. I understand everything, expect what C actually means. By solving this, I got that we have C=1 when i =1, C=1/2 when i=2, and C=1/5 when i=3. Could you explain what C means and represents a bit more :)
Sorry, I just noticed a small mistake. The i in the exponent should be 2i+1. It should be,
Sum i=0 to infinity ( {[(1/2)^(2i+1)]/C} * { (i+1)/(2i+1)} )
and
C = Sum i=0 to infinity (1/2)^(2i+1)
The whole point of C is to just normalize the distribution so that the sum of the total probability space is 1.
Some posters here aren't quite correct; you stop the second your ratio is greater than .5, not equal to .5. To see why we can hope for a greater than .5 ratio is easy; at some point random walks will always diverge above the x-axis.
@"woohoobaby" : From your post it seems like C is equal 2/3 (a bit of calculations with geometric progressionss:)). It seems to me that you assumed that there is a probability [(1/2)^(2i+1)] that the game will stop after (2i+1)- flips, which isn't true in all cases. For example, when i=2 there is a probability 2/32 that the game will stop after (2*2+1=5)-flips, the possible desired results of tossing a coin are {TTHHH- first you get tail, then another tail and so on..., and THTHH}. Did I misunderstood your meaning of C?
Isn't this identical to "the country where people keep on having kids until they get a boy" questions or the gambler's ruin? Should the answer not be 0.5?
Aut qui error a facere hic dignissimos. Quo tempore eaque mollitia ex aut eligendi autem. Vitae molestiae fuga sint natus perferendis architecto. Blanditiis in autem possimus autem similique eum et.
See All Comments - 100% Free
WSO depends on everyone being able to pitch in when they know something. Unlock with your email and get bonus: 6 financial modeling lessons free ($199 value)
or Unlock with your social account...