How Often Should You Beat Your Kids:    Torsten Sillke, Frankfurt/M, 2000-08-08
------------------------------------

Game: "Red Black" [Levasseur, 1988].

  Starting with a deck consisting of r red cards and b black cards (in 
  typical applications, r=b=26), the cards are turned up one at a time, each
  player at each stage predicting the color of the card which is about to 
  appear. 


Stategies:

  Black : Your guess is always Black.
  Red   : Your guess is always Red.
  Random: Throw a fair coin.
  Major : Predict the color, which is currently in the majority.
          In case of a tie select red.


Problems:

  A) Show that stategy Major has the maximal expectation of correct guesses.
     [Read, 1962][Levasseur, 1988]
  B) If you play Major and your kid Random. How often should you beat your
     kid? [Zagier, 1990]
     For k big this probability is p = (1 + 1/sqrt(2))/2 = 0.853553 
     The continued fraction of p = [0, 1, 5,_1,_4]. As [0, 1, 5, 1] = 6/7
     Don Zagier said: roughly speaking, one should beat one's kids 
     every day except Sunday.


Solution:

  Expectation:
    E(Red)    = r
    E(Black)  = b
    E(Random) = (r+b)/2
    E(Major)  = max(r,b) + ( E(diagonal point of a path (r,b) to (0,0)) - 1 )/2.

  Expectation: diagonal points
    E(diagonal point of a path (k,k) to (0,0)) = 4^k / Binomial(2k,k)
              --> sqrt(Pi*k) exp(1/(8k) + O(1/k^3))

  Countings Paths:
    Let P(x,y) be the set of left-down-pathes from (x,y) to (0,0).
    The number of this pathes is the well known Binomial coefficient.
    #P(k,k) = Binomial(2k,k) = [x^k] (1 - 4x)^(-1/2)
    With its generating function we call easily count the number
    of pathes weighted by their number of diagonal points [Levasseur, 1988].
    More generally we can weight with the Binomial of the number of diagonal points.
    This enables us to compute the moments for the number of diagonal points.
        _____
        \
        /____    Binomial(#{diagonal points of p} + m - 1, m)  
     p in P(k,k)
        _____
        \
   =    /____    #P(x0,x0) * #P(x1,x1) * ... * #P(x(m),x(m))
     x0,x1,..,x(m)  nonnegativ integers
     x0+x1+..+x(m)=k

   = [x^k] (1 - 4x)^(-(m+1)/2)

   = Binomial( -(m+1)/2, k ) * (-4)^k


 /---------
  Variance:
    4*sigma^2  =  4*k + 1 - ( 4^k / Binomial(2k,k) )^2  -->  (4-Pi)*k + 1 - Pi/4

  m-th Moment:
    E_{k+1}(X^m) = 2*Sum_{j=0}^{k} (Binomial(2k-j,k-j) - Binomial(2k-j,k-j-1)) * 2^j * (j+2)^m

  Probability for j additional matches:
    Prob(X_k=j) = (Binomial(2k-j,k-j) - Binomial(2k-j,k-j-1)) * 2^(j+1)
 ---------/

  Modal value:
    Maximal probability at j = floor(sqrt((k+1)/2)). If the sqrt is integral then at j-1 too.


References:

P. Diaconis;
   Statistical Problems in ESP-Research,
   Science 201 (1978) 131-136  (see also: Letters, Science 15.12.1978)

W. Feller;
   An Introduction to Probability Theory and its Applications, Vol 1,
   Wiley (1968), 3rd Edition
   (Chap. VI.8.Examples: Banach Matchbox problem, Table Tennis)

M. Gardner;
   Fractal Music, Hypercards and More Math. Recreations from SA Magazin,
   Freeman (1991) New York
   Chap. 14: Psychic Wonders and Probability
   (Robert Connelly's card game "Say Red")

A. Knopfmacher, H. Prodinger;
   A simple card guessing game revisited,
   The Electronic Journal of Combinatorics 8:2 (2001) #R13

D. E. Knuth;
   The Toilet Paper Problem,
   American Math. Monthly 91 (1984) 465-470

U. Krengel;
   Einfuehrung in die Wahrscheinlichkeitstheorie und Statistik,
   Vieweg (1991) 3te Auflage,
   (Chap. 6.5: Beispiel des Testens der Existenz von aussersinnlicher
    Wahrnehmung)

K. M. Levasseur;
   How to Beat Your Kids at Their Own Game,
   Math. Magazine 61:5 (1988) 301-305
   (Optimal Read-Black Strategy)

R. C. Read;
   Card Guessing with Information - a Problem in Probability,
   American Math. Monthly 69 (1962) 506-511

Z. Shan, E. T. H. Wang;
   The Gaps Between Consecutive Binomial Coefficients,
   Math. Magazine 63:2 (1990) 122-124
   (Theorem 2 gives the modal value for the red-black optimal strategy.
    d(n,k) = Binomial(n,k) - Binomial(n,k-1)
    d(n,k) is maximal for k = floor(t) if t is not integral,
    and for k = t and t-1 if t is integral.
    Where t = (n + 2 - sqrt(n+2))/2.)

H. S. Wilf;
   Some examples of combinatorial averaging,
   American Math. Monthly 92 (1985) 250-261

D. Zagier;
   How Often Should You Beat Your Kids,
   Math. Magazine 63:2 (1990) 89-92
   (Prob. Optimal beats Random Strategy, prob. to win is 1/2 + 1/sqrt(8)
    for k pairs for k big.)

--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/