Coin Exchange (Part I)

We can see that $A(0)=2$ and $A(1)=\frac{1}{3} \times3 +\frac{2}{3} \times1=\frac{5}{3}$ , and can define $A(n)$ recursively.

If Alison has $r$ coins after $x$ turns where $x≤n-2$ and $r=1$ or $2$ , she has a $\frac{2}{3}$ chance of having $3-p$ coins and $\frac{1}{3}$ chance of having $0$ (if $p=1$ ) or $3$ (if $p=2$ ) coins after one turn. In the latter case, she will have a $\frac{1}{3}$ chance of having $p$ coins again after the $(x+2)^{th}$ turn. This means that $A(x)=\frac{2}{3}(3-A(x-1))+\frac{1}{3}A(x-2)$ . Note that $(x-1)$ and $(x-2)$ were used instead of $(x+1)$ and $(x+2)$ because the $(x+1)^{th}$ turn is one turn closer to turn $n$ than the $x^{th}$ turn. The above expression simplifies to $A(x)=2-\frac{2}{3}A(x-1)+\frac{1}{3}A(x-2)$ .

If Alison has $s$ coins after $x$ turns, where $s=0$ or $3$ , she will certainty have $1$ or $2$ coins respectively after one turn. Therefore, after the $(x+2)^{th}$ turn, she will have a $\frac{1}{3}$ chance of having $s$ coins again and $\frac{2}{3}$ chance of having $2$ or $1$ coins respectively—this means that there is a probability of $\frac{2}{3}$ that the number of coins she has after the $(x+1)^{th}$ turn and that after the $(x+2)^{th}$ turn sum up to $3$ . In this case, we also arrive at the conclusion that $A(x)=\frac{2}{3}(3-A(x-1))+\frac{1}{3}A(x-2)$ , meaning that $A(x)=2-\frac{2}{3}A(x-1)+\frac{1}{3}A(x-2)$ no matter how many coins Alison has after $x$ turns.

Solving the recurrence relation with the initial conditions stated above, we get $A(n)=\frac{3}{2}+\frac{1}{2\times3^{n}}$ . Therefore, $\lim_{n \to \infty} A(n)=\frac{3}{2}$ and $\sum_{i=1}^{\infty} (A(i)-\lim_{n \to \infty} A(n))=\sum_{i=1}^{\infty} \frac{1}{2\times3^{i}}=\frac{1}{2} \times \frac{1}{2}=\frac{1}{4}$ , giving the answer of $\boxed{5}$ .

If Alison has a coins and Bob has 3-a coins after (n-1) turns then:

A(n) = $\frac{a}{3}$ $\times$ (a-1) + $\frac{3-a}{3}$ $\times$ (a+1)= probability of losing a coin times no. of coins after change + probability of gaining a coin times no. of coins after change

a = A(n-1) by definition

After a bit of rearrangement: A(n) = 1 + $\frac{A(n-1)}{3}$

as n gets larger, A(n) tends to 1.5 as it is the only stable equilibrium since:

if A(n)=1.5 then A(n+1) = 1.5

if A(n)>1.5 then A(n+1)<A(n)

if A(n)<1.5 then A(n+1)>A(n)

let S = $\sum_{i=1}^∞$ A(i) - 1.5

then $\frac{S}{3}$ = $\sum_{i=1}^∞$ $\frac{A(i)}{3}$ - 0.5 = $\sum_{i=2}^∞$ A(i) - 1.5 using the recurrence relationship

S = $\frac{S}{3}$ + $\frac{1}{6}$

S = $\frac{1}{4}$