# A Question about probability and games

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.

-
(a) is often called a Polya urn and is easy to prove by induction as each position has equal probability – Henry Oct 20 '11 at 0:13
Should that be $A(n,k)$ in (2) (or else $|\{\pi\in S_n:\pi\text{ has }m\text{ runs}\}|$)? – Brian M. Scott Oct 20 '11 at 0:16
yes I will fix it – Alex M Oct 20 '11 at 1:04

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.

-
For what it's worth, the $A(n,k)$ are the Eulerian numbers. – Mike Spivey Oct 20 '11 at 4:46
@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 isn’t a bad quick starting point for someone who’s not run into them before.) – Brian M. Scott Oct 20 '11 at 5:12
+1, by the way. – Mike Spivey Oct 20 '11 at 5:39

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.

-
This does give a nice non-inductive solution for game $A$, though. – Brian M. Scott Oct 21 '11 at 12:46