2010/02/09 by Vittorio Addona, Stan Wagon, Addona, Vittorio +3 · 1 citation
Mathematics · #05A15 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05A15
paper · pdf · doi:10.48550/arxiv.1002.1763
arxiv created 2010/08/05 · arxiv updated 2015/03/13
Suppose Alice has a coin with heads probability q and Bob has one with heads probability p>q. Now each of them will toss their coin n times, and Alice will win iff she gets more heads than Bob does. Evidently the game favors Bob, but for the given p,q, what is the choice of n that maximizes Alice's chances of winning? The problem of determining the optimal N first appeared in \citewa. We show that there is an essentially unique value N(q,p) of n that maximizes the probability f(n) that the weak coin will win, and it satisfies (1)/(2(p-q))-\frac12≤ N(q,p)≤ \fracmax(1-p,q)p-q. The analysis uses the multivariate form of Zeilberger's algorithm to find an indicator function Jn(q,p) such that J>0 iff n<N(q,p) followed by a close study of this function, which is a linear combination of two Legendre polynomials. An integration-based algorithm is given for computing N(q,p).