1
$\begingroup$

First some definitions:

1) A Run in a permutation is a maximal increasing subsequence of the one line form.

2) $A(n,k):=|\{\pi\in S_n:\pi\;\mathrm{has}\;k\;\mathrm{runs}\}|$

Now the problem is: we have two games A and B, played by Ann and Bob. They each start with one dollar and in each round exactly one of them will win an extra dollar from the bank. When Ann has $a$ dollars and Bob has $b$ dollars then the probability that Ann wins the next dollar is $\frac{a}{a+b}$ when the play A, whereas it is $\frac{b}{a+b}$ in the game B. After $n$ rounds of either game both Ann and Bob have somewhere between 1 dollar and $n+1$ dollars and their fortunes add up to $n+2$ dollars.

a) After $n$ rounds of A prove that the probability that Ann has $k$ dollars is $\frac{1}{n+1}$.

b) After $n$ round of B prove that the probability that Ann has $k$ dollars is $\frac{A(n+1,k)}{(n+1)!}$.

Could you help me solve this problem? I will be glad also with only some hints.

  • 0
    yes I will fix it2011-10-20

2 Answers 2

3

I’ll leave (a) to you: with the suggestion to do it by induction on $n$, it really is pretty easy, especially after you’ve seen an inductive proof of (b).

Problem (b) can also be done by induction. Let $p(n,k)$ be the probability that Ann has $k$ dollars after $n$ plays. In order to have $k$ dollars after $n$ plays, she must either have had $k$ dollars after $n-1$ plays and lost on the $n$-th play, or have had $k-1$ dollars after $n-1$ plays and won on the $n$-th play. If she has $k$ dollars after $n-1$ plays, her probability of losing on the $n$-th play is $\frac{k}{n+1}$. If she has $k-1$ dollars after $n-1$ plays, Bob has $n+2-k$ dollars, so her probability of winning on the $n$-th play is $\frac{n+2-k}{n+1}$. It follows that $\begin{align*} p(n,k) &= p(n-1,k)\frac{k}{n+1}+p(n-1,k-1)\frac{n+2-k}{n+1}\\ &= \frac1{n+1}\left(kp(n-1,k)+(n+2-k)p(n-1,k-1)\right) \end{align*}$ for $1\le k\le n$. The initial conditions for the recurrence are clearly $p(0,1)=1$ and $p(n,0)=0$ for all $n\ge 0$.

Now consider the numbers $A(n,k)$. It’s easy to see that $A(n,1)=A(n,n)=1$ for all $n>0$. Now consider $A(n+1,k)$. A permutation of $[n+1]$ with $k$ runs can be obtained in two ways from a permutation of $[n]$.

  1. We can start with a permutation of $[n]$ that has $k$ runs and insert $n+1$ at the end of one of these runs; each of the $A(n,k)$ permutations of $[n]$ with $k$ runs gives rise in this way to $k$ permutations of $[n+1]$ with $k$ runs.
  2. We can start with a permutation of $[n]$ that has $k-1$ runs and insert $n+1$ in any of the $n+1-(k-1)=n+2-k$ positions that are not at the end of a run; each of the $A(n,k-1)$ permutations of $[n-1]$ with $k-1$ runs gives rise in this way to $n+2-k$ permutations of $[n+1]$ with $k$ runs.

It follows that $A(n+1,k)=kA(n,k)+(n+2-k)A(n,k-1)\;.$ Thus, if $p(n-1,k)=\frac{A(n,k)}{n!}$ and $p(n-1,k-1)=\frac{A(n,k-1)}{n!}$, then $\begin{align*} p(n,k) &= \frac1{n+1}\left(k\frac{A(n,k)}{n!}+(n+2-k)\frac{A(n,k-1)}{n!}\right)\\ &= \frac{A(n+1,k)}{(n+1)!}, \end{align*}$ and all that remains is to check the boundary conditions.

  • 0
    @Mike: Thanks; I should have mentioned that. Offset by $1$, as I recall: $A(n,k) = \left\langle\matrix{n\\k-1}\right\rangle$. (The [Wikipedia article](http://en.wikipedia.org/wiki/Eulerian_number) isn’t a bad quick starting point for someone who’s not run into them before.)2011-10-20
1

Game A is equivalent to generating an ordering of $n+1$ coins numbered from $0$ to $n$ by a random Insertion Sort process. Start out with coin $0$ and at step $i$ place coin $i$ at one of the $i+1$ possible positions relative to the previous coins, each position having probability $\frac{1}{i+1}$ of being chosen. This generates a uniform random permutation of the $n+1$ coins.

Ann gets the coins to the left of $0$ plus one free coin; Bob gets the coins to the right of $0$ plus one free coin. All possible positions of $0$ are equally likely and this implies a uniform distribution on the $n+1$ possible divisions of the number of coins.

Game B is the same process with Ann receiving the coins that terminate a run, and Bob the other coins plus one free coin. Given the interpretation of game A this is only a restatement of the known answer and does not explain why it is true.

  • 0
    This does give a nice non-inductive solution for game $A$, though.2011-10-21