How to lose as little as possible

Vittorio Addona, Stan Wagon, Herb Wilf


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? 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(pq) − 1/2⌋ ≤ N(q, p) ≤ ⌈max(1 − pq)/(pq)⌉. 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).


Legendre polynomials, symbolic summation, probability

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications