⧼exchistory⧽
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 Example, define [math]f(i)[/math] to be the proportion of G genes in state [math]i[/math]. Show that [math]f[/math] is a harmonic function (see Exercise). Why does this show that the probability of being absorbed in state [math](\mbox{GG},\mbox{GG})[/math] is equal to the proportion of G genes in the starting state? (See Exercise.)

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 stepping stone model (Example) is an absorbing Markov chain. Assume that you are playing a game with red and green squares, in which your fortune at any time is equal to the proportion of red squares at that time. Give an argument to show that this is a fair game in the sense that your expected winning after each step is just what it was before this step. Hint: Show that for every possible outcome in which your fortune will decrease by one there is another outcome of exactly the same probability where it will increase by one.

Use this fact and the results of Exercise to show that the probability that a particular color wins out is equal to the proportion of squares that are initially of this color.

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]

Consider a random walker who moves on the integers 0, 1, ..., [math]N[/math], moving one step to the right with probability [math]p[/math] and one step to the left with probability [math]q = 1 - p[/math]. If the walker ever reaches 0 or [math]N[/math] he stays there. (This is the Gambler's Ruin problem of Exercise.)

If [math]p = q[/math] show that the function

[[math]] f(i) = i [[/math]]

is a harmonic function (see Exercise), and if [math]p \ne q[/math] then

[[math]] f(i) = \biggl(\frac {q}{p}\biggr)^i [[/math]]

is a harmonic function. Use this and the result of Exercise to show that the probability [math]b_{iN}[/math] of being absorbed in state [math]N[/math] starting in state [math]i[/math] is

[[math]] b_{iN} = \left \{ \matrix{ \frac iN, &\mbox{if}\,\, p = q, \cr \frac{({q \over p})^i - 1}{({q \over p})^{N} - 1}, & \mbox{if}\,\,p \ne q.\cr}\right. [[/math]]

For an alternative derivation of these results see Exercise.

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]

Complete the following alternate proof of Theorem. Let [math]s_i[/math] be a transient state and [math]s_j[/math] be an absorbing state. If we compute [math]b_{ij}[/math] in terms of the possibilities on the outcome of the first step, then we have the equation

[[math]] b_{ij} = p_{ij} + \sum_k p_{ik} b_{kj}\ , [[/math]]

where the summation is carried out over all transient states [math]s_k[/math]. Write this in matrix form, and derive from this equation the statement

[[math]] \mat{B} = \mat{N}\mat{R}\ . [[/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 Monte Carlo roulette (see Example), under option (c), there are six states ([math]S[/math], [math]W[/math], [math]L[/math], [math]E[/math], [math]P_1[/math], and [math]P_2[/math]). The reader is referred to Figure, which contains a tree for this option. Form a Markov chain for this option, and use the program AbsorbingChain to find the probabilities that you win, lose, or break even for a 1 franc bet on red. Using these probabilities, find the expected winnings for this bet. For a more general discussion of Markov chains applied to roulette, see the article of H. Sagan referred to in Example.

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]

We consider next a game called Penney-ante by its inventor W. Penney.[Notes 1] There are two players; the first player picks a pattern A of H's and T's, and then the second player, knowing the choice of the first player, picks a different pattern B.

We assume that neither pattern is a subpattern of the other pattern. A coin is tossed a sequence of times, and the player whose pattern comes up first is the winner. To analyze the game, we need to find the probability [math]p_A[/math] that pattern A will occur before pattern B and the probability

[math]p_B = 1- p_A[/math] that pattern B occurs before pattern A. To determine these probabilities we use the results of Exercise and Exercise. Here you were asked to show that, the expected time to reach a pattern B for the first time is,

[[math]] E(T^B) = BB\ , [[/math]]

and, starting with pattern A, the expected time to reach pattern B is

[[math]] E_A(T^B) = BB - AB\ . [[/math]]

  • Show that the odds that the first player will win are given by John Conway's formula[Notes 2]:
    [[math]] \frac{p_A}{1-p_A} = \frac{p_A}{p_B} = \frac{BB - BA}{AA - AB}\ . [[/math]]
    Hint: Explain why
    [[math]] E(T^B) = E(T^{A\ {\rm or}\ B}) + p_A E_A(T^B) [[/math]]
    and thus
    [[math]] BB = E(T^{A\ {\rm or}\ B}) + p_A (BB - AB)\ . [[/math]]
    Interchange A and B to find a similar equation involving the [math]p_B[/math]. Finally, note that
    [[math]] p_A + p_B = 1\ . [[/math]]
    Use these equations to solve for [math]p_A[/math] and [math]p_B[/math].
  • Assume that both players choose a pattern of the same length k. Show that, if [math]k = 2[/math], this is a fair game, but, if [math]k = 3[/math], the second player has an advantage no matter what choice the first player makes. (It has been shown that, for [math]k \geq 3[/math], if the first player chooses [math]a_1[/math], [math]a_2[/math], ..., [math]a_k[/math], then the optimal strategy for the second player is of the form [math]b[/math], [math]a_1[/math], ..., [math]a_{k - 1}[/math] where [math]b[/math] is the better of the two choices H or T.[Notes 3])

Notes

  1. W. Penney, “Problem: Penney-Ante,” Journal of Recreational Math, vol. 2 (1969), p. 241.
  2. M. Gardner, “Mathematical Games,” Scientific American, vol. 10 (1974), pp. 120--125.
  3. Guibas and Odlyzko, op. cit.