Why is this coin - turning probability trouble unresolved?

You play a video game turning a reasonable coin. You might stop after any kind of test, whereupon you are paid in bucks the percent of heads turned. So if on the first test you turn a head, you need to stop and also gain \$ 100. due to the fact that you have 100% heads. If you turn a tail after that a head, you can either stop and also gain \$ 50,. or continue, wishing the proportion will certainly go beyond 1/ 2. This 2nd approach transcends.

A paper by Medina and also Zeilberger (arXiv:0907.0032v2 [math.PR]) claims that it is an unresolved. trouble to establish if it is far better to proceed or stop after you have actually turned 5 heads in 8 tests: approve \$ 62.50 or wish for even more. It is very easy to imitate this trouble and also it is clear. from also minimal speculative information that it is far better to proceed (probably greater than 70% opportunity you'll boost over \$ 62.50 _ rt:

My inquiry is primarily: Why is this hard to confirm? Probably it is not that hard. to draw up an expression for the assumption of going beyond 5/ 8 in regards to the collective binomial distribution.

( 5 Dec 2013 ). A paper on this subject was simply released:

Olle Häggström, Johan Wästlund. " Rigorous computer system evaluation of the Chow - Robbins video game." (pre - journal arXiv link). The American Mathematical Monthly , Vol. 120, No. 10, December 2013. (Jstor link). From the Abstract:

" In certain, we validate that with 5 heads and also 3 tails, quiting is optimum."

2019-05-18 21:53:35
Source Share
Answers: 2

I approve Qiaochu is solution "Have you attempted in fact doing that?" I did attempt currently, and also currently I can value the challenge.: -) The paper I pointed out describes an additional by Chow and also Robbins from 1965 that has an attractive solution, much more clear than the cummulative binomials with which I battled. Allow me clarify it, due to the fact that it is actually trendy.

For the all-natural approach I stated in the remarks (and also resembled by Raynos),. allow $f(n,h,t)$ be the anticipated payback. if you start with $h$ heads and also $t$ tails, and also allow the video game proceed no greater than $n$ more tests. After that there is a very easy recursive solution for $f$:. $$f(n,h,t) = \max \left( \frac{1}{2} f(n,h+1,t) + \frac{1}{2} f(n,h,t+1) , h/(h+t) \right) $$. due to the fact that you have an equivalent opportunity of raising to $h+1$ heads or to $t+1$ tails on the next. turn if you proceed, and also you get the existing proportion if you stop. Currently, when $h+t=n$, you require to make a "border" presumption. Thinking the regulation of. lots for huge $n$ brings about the practical value $\max ( 1/2, h/n )$ in this instance. So currently all you require to do is fill in the table for all $h$ and also $t$ values approximately $n=h+t$. The actual solution is the restriction when $n \rightarrow \infty$, yet making use of huge $n$ estimates this restriction.

After the Medina and also Zeilberger paper was launched, actually nearly 3 weeks earlier,. a really mindful estimation making use of the above recursive solution was made by Julian Wiseman and also reported on this web page. The verdict is to me impressive: "Choosing to proceed decreases the anticipated payback [from 0.625 ] to 0.62361957757.". This is still not an evidence, yet the "solution" is currently recognized. So my "it is clear from also minimal speculative information that" was entirely incorrect! I am happy to pick up from my blunder.

2019-05-21 16:59:18

This appears to be connected to Gittins Indices. Gittins Indices are a means of addressing these sort of optimum quiting troubles for some courses of troubles, and also primarily offer you a means of stabilizing just how much you are anticipated to obtain provided your existing expertise and also just how much extra you can obtain by taking the chance of getting even more details concerning the procedure (or probability of turning heads, etc).


2019-05-21 16:27:12