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/