If me and a friend are playing a game and start with 10 marbles each. We flip a coin each round and each time it's a head he gives me a marble and each time it's tails I give him one. How many coin flips do we have to do on average before someone has all the marbles?
I tried to do the average by 10 * (1/2) ^10 + (11C1) * (1/2)^11 .... up to infinity by multiplying the probability of each time getting 10 more heads than my opponent gets tails. This doesn't make sense to me though: the answer seemed way off, and also the game wouldn't actually be able to end on 11 flips because it is an odd number. It also doesn't seem to consider the fact the game could end on an earlier round.
Any help with this question is much appreciated.
Answer for $N$ marbles: $N^2$
Proof: Let us denote by $$x_{k,l}\triangleq E[X|A=k,B=l]$$ the expected (mean) value of coin flips before someone has all the marbles given that player $A$ starts with $k$ marbles and player $B$ with $l$ marbles (notice that $x_{k,l}=x_{l,k}$ by symmetry).
I will show below that $x_{N,N}=N^2$.
To simplify the notation let us define $z_j\triangleq x_{2N-j,j}$ for $j=1,\ldots,N$.
Note that the variables $z_j$ satisfy the following system of equations written in matricial form (I can detail this part of the proof if necessary):
\begin{equation} \begin{bmatrix} z_N\\ z_{N-1}\\ z_{N-2}\\ z_{N-3}\\ \vdots\\ z_2\\ z_1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & & & & & 0\\ 1/2 & 0 & 1/2 & & & & \\ & 1/2 & 0 & 1/2 & & & \\ & & 1/2 & 0 & \ddots & & \\ & & &\ddots& \ddots & 1/2 & \\ & & & & 1/2 & 0 & 1/2\\ 0 & & & & & 1/2 & 0\\ \end{bmatrix} \begin{bmatrix} z_N\\ z_{N-1}\\ z_{N-2}\\ z_{N-3}\\ \vdots\\ z_2\\ z_1 \end{bmatrix} + \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ \vdots\\ 1\\ 1 \end{bmatrix} \end{equation}
Manipulating the expression above we get: \begin{equation} \begin{bmatrix} 1 & -1 & & & & & 0\\ -1/2 & 1 & -1/2 & & & & \\ & -1/2 & 1 & -1/2 & & & \\ & & -1/2 & 1 & \ddots & & \\ & & &\ddots& \ddots & -1/2 & \\ & & & & -1/2 & 1 & -1/2\\ 0 & & & & & -1/2 & 1\\ \end{bmatrix} \begin{bmatrix} z_N\\ z_{N-1}\\ z_{N-2}\\ z_{N-3}\\ \vdots\\ z_2\\ z_1 \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ \vdots\\ 1\\ 1 \end{bmatrix} \end{equation}
This is a linear system of equations with a tridiagonal coefficient matrix. It can be solved fairly easily (see for instance https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm). I give some details below.
Pivoting (starting at the lower right corner and moving up) we can eliminate the third diagonal of elements (the one to the right of the main diagonal): \begin{equation} \begin{bmatrix} 1/N & 0 & & & & & 0\\ -1/2 & b_{N-1} & 0 & & & & \\ & -1/2 & b_{N-2} & 0 & & & \\ & & -1/2 & b_{N-3} & \ddots & & \\ & & &\ddots& \ddots & 0 & \\ & & & & -1/2 & b_2 & 0\\ 0 & & & & & -1/2 & b_1\\ \end{bmatrix} \begin{bmatrix} z_N\\ z_{N-1}\\ z_{N-2}\\ z_{N-3}\\ \vdots\\ z_2\\ z_1 \end{bmatrix} = \begin{bmatrix} N\\ d_{N-1}\\ d_{N-2}\\ d_{N-3}\\ \vdots\\ d_2\\ d_1 \end{bmatrix} \end{equation} where $b_i\triangleq\dfrac{1+i}{2i}$ and $d_i\triangleq\dfrac{1+i}{2}$ for $i=1,\ldots,N-1$.
We conclude from the first line that $x_{N,N}=z_{N}=N^2$, as we wanted to show.