Rigorous computer analysis of the Chow-Robbins game

2012/01/03 by Olle Häggström, Häggström, Olle, Johan Wästlund +1
Computer Science · Mathematics · #60G40 #62L15 #91A60 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.GT #math.PR #msc:60G40 #msc:62L15 #msc:91A60

paper · pdf · doi:10.48550/arxiv.1201.0626

10 pages

arxiv created 2012/01/03 · arxiv updated 2012/01/04

Abstract

Flip a coin repeatedly, and stop whenever you want. Your payoff is the proportion of heads, and you wish to maximize this payoff in expectation. This so-called Chow-Robbins game is amenable to computer analysis, but while simple-minded number crunching can show that it is best to continue in a given position, establishing rigorously that stopping is optimal seems at first sight to require "backward induction from infinity". We establish a simple upper bound on the expected payoff in a given position, allowing efficient and rigorous computer analysis of positions early in the game. In particular we confirm that with 5 heads and 3 tails, stopping is optimal.

Related

• Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle
• On the Sn/n-Problem
• An Experimental Mathematics Perspective on the Old, and still Open, Question of When To Stop?
• A Class of Mean-Field Games with Optimal Stopping and its Inverse Problem
• On maximizing the number of heads when you need to set aside at least one coin every round