exercise:3f7aeef1b5: Difference between revisions

From Stochiki
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> (from K. Levasseur<ref group="Notes" >K. Levasseur, “How to Beat Your Kids at Their Own Game,” ''Mathematics Magazine'' vol. 61, no. 5 (December, 1988), pp. 301-305.</ref>) A parent and his child play the following game. A deck of <math>2n</m...")
 
No edit summary
 
Line 47: Line 47:
\frac 12 + \frac 1{2\sqrt 2}\ .
\frac 12 + \frac 1{2\sqrt 2}\ .
</math>
</math>
\item
Prove that
<math display="block">
u^{(2)}_{2n} = \frac 1{4^{2n}} \sum_{k = 0}^n \frac {(2n)!}{k!k!(n-k)!(n-k)!}\ ,
</math>
and
<math display="block">
u^{(3)}_{2n} = \frac 1{6^{2n}} \sum_{j,k} \frac {(2n)!}{j!j!k!k!(n-j-k)!(n-j-k)!}\ ,
</math>
where the last sum extends over all non-negative <math>j</math> and <math>k</math> with <math>j+k \le n</math>.  Also show
that this last expression may be rewritten as
<math display="block">
\frac 1{2^{2n}}{{2n}\choose n} \sum_{j,k}
\biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr)^2\ .
</math>
\item
Prove that if <math>n \ge 0</math>, then
<math display="block">
\sum_{k = 0}^n {n \choose k}^2 = {{2n} \choose n}\ .
</math>
'' Hint'': Write the sum as
<math display="block">
\sum_{k = 0}^n {n \choose k}{n \choose {n-k}}
</math>
and explain why this is a coefficient in the product
<math display="block">
(1 + x)^n (1 + x)^n\ .
</math>
Use this, together with [[guide:Ff217e6881#exer 12.1.11 |Exercise]], to show that
<math display="block">
u^{(2)}_{2n} = \frac 1{4^{2n}}{{2n}\choose n}\sum_{k = 0}^n {n \choose k}^2 =
\frac 1 {4^{2n}} {{2n}\choose n}^2\ .
</math>
\item
Using Stirling's Formula, prove that
<math display="block">
{{2n}\choose n} \sim \frac {2^{2n}}{\sqrt {\pi n}}\ .
</math>
\item
Prove that
<math display="block">
\sum_{j,k}
\biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr) = 1\ ,
</math>
where the sum extends over all non-negative <math>j</math> and <math>k</math> such that <math>j + k \le n</math>.  '' Hint'':
Count how many ways one can place <math>n</math> labelled balls in 3 labelled urns.
\item
Using the result proved for the random walk in <math>{\mathbf R}^3</math> in [[guide:Ff217e6881#exam 12.1.0.6 |Example]],
explain why the probability of an eventual return in <math>{\mathbf R}^n</math> is strictly less than one,
for all <math>n \ge 3</math>.  '' Hint'': Consider a random walk in <math>{\mathbf R}^n</math> and disregard all but
the first three coordinates of the particle's position.


'''Notes'''
'''Notes'''


{{Reflist|group=Notes}}
{{Reflist|group=Notes}}

Latest revision as of 00:38, 15 June 2024

[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

(from K. Levasseur[Notes 1]) A parent and his child play the following game. A deck of [math]2n[/math] cards, [math]n[/math] red and [math]n[/math] black, is shuffled. The cards are turned up one at a time. Before each card is turned up, the parent and the child guess whether it will be red or black. Whoever makes more correct guesses wins the game. The child is assumed to guess each color with the same probability, so she will have a score of [math]n[/math], on average. The parent keeps track of how many cards of each color have already been turned up. If more black cards, say, than red cards remain in the deck, then the parent will guess black, while if an equal number of each color remain, then the parent guesses each color with probability 1/2. What is the expected number of correct guesses that will be made by the parent? Hint: Each of the [math]{{2n}\choose n}[/math] possible orderings of red and black cards corresponds to a random walk of length [math]2n[/math] that returns to the origin at time [math]2n[/math]. Show that between each pair of successive equalizations, the parent will be right exactly once more than he will be wrong. Explain why this means that the average number of correct guesses by the parent is greater than [math]n[/math] by exactly one-half the average number of equalizations. Now define the random variable [math]X_i[/math] to be 1 if there is an equalization at time [math]2i[/math], and 0 otherwise. Then, among all relevant paths, we have

[[math]] E(X_i) = P(X_i = 1) = \frac{{{2n-2i}\choose{n-i}}{{2i}\choose{i}}}{{{2n}\choose{n}}}\ . [[/math]]

Thus, the expected number of equalizations equals

[[math]] E\biggl(\sum_{i = 1}^n X_i\biggr) = \frac 1{{{2n}\choose{n}}}\sum_{i = 1}^n {{2n-2i}\choose{n-i}}{{2i}\choose{i}}\ . [[/math]]

One can now use generating functions to find the value of the sum.


It should be noted that in a game such as this, a more interesting question than the one asked above is what is the probability that the parent wins the game? For this game, this question was answered by D. Zagier.[Notes 2] He showed that the probability of winning is asymptotic (for large [math]n[/math]) to the quantity

[[math]] \frac 12 + \frac 1{2\sqrt 2}\ . [[/math]]

Notes

  1. K. Levasseur, “How to Beat Your Kids at Their Own Game,” Mathematics Magazine vol. 61, no. 5 (December, 1988), pp. 301-305.
  2. D. Zagier, “How Often Should You Beat Your Kids?” Mathematics Magazine vol. 63, no.\ 2 (April 1990), pp. 89-92.
Retrieved from "http://www.stochiki.com/w/index.php?title=exercise:3f7aeef1b5&oldid=10329"