Coin Exchange (Part II)

Let $p_{k}$ be the probability that Alison has $k$ coins after $n$ turns. We can see that $A(n)=\sum_{i=0}^{1000} ip_{i}$ .

If Alison has $k$ coins, she has a $\frac{1000-k}{1000}$ chance of gaining a coin and a $\frac{k}{1000}$ chance of losing one next turn. Therefore, her expected net gain each turn would be $\frac{1000-2k}{1000}$ .

$A(n+1)=A(n)+\sum_{i=0}^{1000} \frac{1000-2i}{1000}p_{i}=A(n)+\sum_{i=0}^{1000} p_{i}-\frac{2}{1000}(\sum_{i=0}^{1000} ip_{i})=A(n)+1-\frac{1}{500}A(n)=\frac{499}{500}A(n)+1$

Solve with the initial condition $A(0)=1$ , and we get $A(n)=1+\frac{499}{500}A(n-1)=1+\frac{499}{500}+(\frac{499}{500})^{2}A(n-2)=...=\sum_{i=0}^{n}(\frac{499}{500})^{i}=\frac{1-(\frac{499}{500})^{n+1}}{1-\frac{499}{500}}=500(1-(\frac{499}{500})^{n+1})$

When $n=30$ , $A(n)=30.08773$ , so the answer is $\boxed{3008773}$ .