This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes to improve my numerical estimate. One would be easy for a statistician; one requires something more subtle.
Toss a coin repeatedly until you say “stop”, when you score the proportion of tosses that are heads = $h / (h+t)$. So if the first toss is a head, stop and score 1, the maximum. If tosses are tail-head-head-head, then stop and score ¾ (the optimal strategy after tail-head-head is to toss again, with expected value ≈ 0.6694 > ⅔).
Obviously one could, at any time, undertake to keep tossing until $h=t$, which happens eventually with probability one.
So a simple strategy would be to stop if the first toss is a head, otherwise to toss repeatedly until $h=t$. So the value of the game must be ≥ 0.75.
Numerically one can get a lower bound for the value of the game by building an $n$×$n$ spreadsheet, with $h=t=0$ in the top left, tails increasing to the right and heads increasing down. Cells are then filled with $=Max( h/(h+t), Avg(↓,→), ½ )$. This is choosing the best of stopping now and scoring $h/(h+t)$, tossing once more with half chance of a head and half chance of a tail, and tossing forever (relevant only on the boundary). Obviously stopping is disallowed with $h+t=0$.
And if the spreadsheet size is 1024×1024 the value of this constrained game is an edge more than 0.79272249. Obviously doubling the size of the spreadsheet would increase the value of the game, and doubling again increases it again, though by only 0.602× as much. This ratio varies little over large increases in $n$. So one can estimate the value at the limit as the current estimate, plus the most recent difference divided by one less than the reciprocal of the ratio.
(Diagrams and data at jdawiseman.com.)
This leads to the first question, the easy statistical one.
Easy statistical question
Currently I’m estimating the value at the limit using only three spreadsheet sizes, and these in geometric progression. Surely it is possible to get a better estimate, and some sense of ±error around that, using all the data at once. Presumably one should model the value of the restricted game as being something like 0.79295350640 – 0.036659 × ($n$ ^ –0.7311766), with constants to be better estimated. My guess is that this would be done with a fitting, giving greater weight to larger $n$. So, using all the data at once, what is the best estimate of the constant term and its error bounds?
A continuous game that approximates the estimate at the discrete game’s boundary
My approach uses backward induction from a boundary, the value at the boundary being deemed to be the better of stop = $h/(h+t)$ and toss forever = $½$. A better estimate at the boundary is likely to improve the speed of convergence quite dramatically.
Return to the unconstrained game, so on the spreadsheet of infinite size. For each $t$ there is some $h[t]$, such that one would stop with $h ≥ h[t]$, and continue otherwise. Let’s have a value of the not-yet-defined continuous game, $EV[h,t]$, of which I know some of the properties.
• ∃ EV[h,t] continuous $∀ h≥0, t≥0$.
• ∃ $h[t] ≥ t$ such that $h≥h[t] ⇒ EV[h,t]=h/(h+t)$.
• $h < h[t] ⇒ ∂EV[h,t]/∂h = –∂EV[h,t]/∂t$. This is the analogue of the “Avg(↓,→)” from the discrete game.
• For fixed $h$, $t→∞ ⇒ EV[h,t]→½$.
• Then $h[t]$ is chosen to maximise $EV[0,t']$ for some $t'≥0$.
• Any other sensible properties.
Hard ill-defined continuous game-theoretic question
Define a continuous version of the Chow & Robbins game, with known analytic solution, that can be used as the boundary approximation in the computation of the value of the discrete game.
