⧼exchistory⧽
15 exercise(s) shown, 0 hidden
SORT:
BBy Bot
Jun 09'24
[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]

Using the Binomial Theorem, show that

[[math]] {1\over{\sqrt {1 - 4x}}} = \sum_{m = 0}^\infty {2m \choose m} x^m\ . [[/math]]

What is the interval of convergence of this power series?

BBy Bot
Jun 09'24
[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]
  • Show that for [math]m \ge 1[/math],
    [[math]] f_{2m} = u_{2m-2} - u_{2m}\ . [[/math]]
  • Using part (a), find a closed-form expression for the sum
    [[math]] f_2 + f_4 + \cdots + f_{2m}\ . [[/math]]
  • Using part (b), show that
    [[math]] \sum_{m = 1}^\infty f_{2m} = 1\ . [[/math]]
    (One can also obtain this statement from the fact that
    [[math]] F(x) = 1 - (1-x)^{1/2}\ .) [[/math]]
  • Using parts (a) and (b), show that the probability of no equalization in the first [math]2m[/math] outcomes equals the probability of an equalization at time [math]2m[/math].
BBy Bot
Jun 09'24
[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]

Using the notation of Example, show that

[[math]] |E_{2k}| = f_{2k} 2^{2m}\ . [[/math]]

BBy Bot
Jun 09'24
[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]

Using Stirling's Formula, show that

[[math]] u_{2m} \sim {1\over{\sqrt {\pi m}}}\ . [[/math]]

BBy Bot
Jun 09'24
[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]

A lead change in a random walk occurs at time

[math]2k[/math] if [math]S_{2k-1}[/math] and [math]S_{2k+1}[/math] are of opposite sign.

  • Give a rigorous argument which proves that among all walks of length [math]2m[/math] that have an equalization at time [math]2k[/math], exactly half have a lead change at time [math]2k[/math].
  • Deduce that the total number of lead changes among all walks of length [math]2m[/math] equals
    [[math]] {1\over 2}(g_{2m} - u_{2m})\ . [[/math]]
  • Find an asymptotic expression for the average number of lead changes in a random walk of length [math]2m[/math].
BBy Bot
Jun 09'24
[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]
  • Show that the probability that a random walk of length [math]2m[/math] has a last return to the origin at time [math]2k[/math], where [math]0 \le k \le m[/math], equals
    [[math]] {{{2k}\choose k}{{2m-2k}\choose {m-k}}\over{2^{2m}}} = u_{2k}u_{2m - 2k}\ . [[/math]]
    (The case [math]k = 0[/math] consists of all paths that do not return to the origin at any positive time.) Hint: A path whose last return to the origin occurs at time [math]2k[/math] consists of two paths glued together, one path of which is of length [math]2k[/math] and which begins and ends at the origin, and the other path of which is of length [math]2m - 2k[/math] and which begins at the origin but never returns to the origin. Both types of paths can be counted using quantities which appear in this section.
  • Using part (a), show that if [math]m[/math] is odd, the probability that a walk of length [math]2m[/math] has no equalization in the last [math]m[/math] outcomes is equal to [math]1/2[/math], regardless of the value of [math]m[/math]. Hint: The answer to part a) is symmetric in [math]k[/math] and [math]m-k[/math].
BBy Bot
Jun 09'24

Show that the probability of no equalization in a walk of length [math]2m[/math] equals [math]u_{2m}[/math].

BBy Bot
Jun 09'24
[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]

Show that

[[math]] P(S_1 \ge 0,\ S_2 \ge 0,\ \ldots,\ S_{2m} \ge 0) = u_{2m}\ . [[/math]]

Hint: First explain why

[[math]] \begin{eqnarray*} &&P(S_1 \gt 0,\ S_2 \gt 0,\ \ldots,\ S_{2m} \gt 0) \\ && \;\;\;\;\;\;\;\;\;\;\;\;\; = {1\over 2}P(S_1 \ne 0,\ S_2 \ne 0,\ \ldots,\ S_{2m} \ne 0) \ . \end{eqnarray*} [[/math]]

Then use Exercise, together with the observation that if no equalization occurs in the first [math]2m[/math] outcomes, then the path goes through the point [math](1,1)[/math] and remains on or above the horizontal line [math]x = 1[/math].

BBy Bot
Jun 09'24
[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]

In Feller,[Notes 1] one finds the

following theorem: Let [math]M_n[/math] be the random variable which gives the maximum value of [math]S_k[/math], for [math]1 \le k \le n[/math]. Define

[[math]] p_{n, r} = {n\choose {{n+r}\over{2}}}2^{-n}\ . [[/math]]

If [math]r \ge 0[/math], then

[[math]] P(M_n = r) = \left \{ \begin{array}{ll} p_{n, r}\,,&\mbox{if $r \equiv n\, (\mbox{mod}\ 2)$}, \\ p_{n, r+1}\,,&\mbox{if $r \not\equiv n\,(\mbox{mod}\ 2)$}. \end{array} \right. [[/math]]

  • Using this theorem, show that
    [[math]] E(M_{2m}) = {1\over{2^{2m}}}\sum_{k = 1}^m (4k-1){2m \choose m+k}\ , [[/math]]
    and if [math]n = 2m+1[/math], then
    [[math]] E(M_{2m+1}) = {1\over {2^{2m+1}}} \sum_{k = 0}^m (4k+1){2m+1\choose m+k+1}\ . [[/math]]
  • For [math]m \ge 1[/math], define
    [[math]] r_m = \sum_{k = 1}^m k {2m\choose m+k} [[/math]]
    and
    [[math]] s_m = \sum_{k = 1}^m k {2m+1\choose m+k+1}\ . [[/math]]
    By using the identity
    [[math]] {n\choose k} = {n-1\choose k-1} + {n-1\choose k}\ , [[/math]]
    show that
    [[math]] s_m = 2r_m - {1\over 2}\biggl(2^{2m} - {2m \choose m}\biggr) [[/math]]
    and
    [[math]] r_m = 2s_{m-1} + {1\over 2}2^{2m-1}\ , [[/math]]
    if [math]m \ge 2[/math].
  • Define the generating functions
    [[math]] R(x) = \sum_{k = 1}^\infty r_k x^k [[/math]]
    and
    [[math]] S(x) = \sum_{k = 1}^\infty s_k x^k\ . [[/math]]
    Show that
    [[math]] S(x) = 2 R(x) - {1\over 2}\biggl({1\over{1- 4x}}\biggr) + {1\over 2}\biggl(\sqrt{1-4x}\biggr) [[/math]]
    and
    [[math]] R(x) = 2xS(x) + x\biggl({1\over{1-4x}}\biggr)\ . [[/math]]
  • Show that
    [[math]] R(x) = {x\over{(1-4x)^{3/2}}}\ , [[/math]]
    and
    [[math]] S(x) = {1\over 2}\biggl({1\over{(1- 4x)^{3/2}}}\biggr) - {1\over 2}\biggl({1\over{1- 4x}}\biggr)\ . [[/math]]
  • Show that
    [[math]] r_m = m{2m-1\choose m-1}\ , [[/math]]
    and
    [[math]] s_m = {1\over 2}(m+1){2m+1\choose m} - {1\over 2}(2^{2m})\ . [[/math]]
  • Show that
    [[math]] E(M_{2m}) = {m\over{2^{2m-1}}}{2m\choose m} + {1\over{2^{2m+1}}}{2m\choose m} - {1\over 2}\ , [[/math]]
    and
    [[math]] E(M_{2m+1}) = {{m+1}\over{2^{2m+1}}}{2m+2\choose m+1} - {1\over 2}\ . [[/math]]
    The reader should compare these formulas with the expression for \linebreak [math]g_{2m}/2^{(2m)}[/math] in Example \ref{exam 12.1.1}.

Notes

  1. W. Feller, Introduction to Probability Theory and its Applications, vol. I, 3rd ed. (New York: John Wiley \& Sons, 1968).
BBy Bot
Jun 09'24
[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.