1
$\begingroup$

I've been stuck on this expected value question for some time now, for some reason:

Suppose we have two bins. Bin A has $k$ balls and Bin B has $n-k$ balls. For each step, we randomly pick a ball from one of the bins (so each ball has a $1/n$ chance of being selected each time) and move it to the other bin. What is the expected number of steps required until there are $k$ balls in Bin A again?

As for my work, I let $E_i$ be the expected number of steps required until there are $k$ balls in Bin A, if we started out with $i$ balls in Bin A. Then I found that $$E_i=\frac inE_{i-1}+\frac{n-i}nE_{i+1}+1$$ for $i$ for $1\le i\le n-1$. For $0$ and $n$, I found that \begin{align*}E_0&=E_1+1\\E_n&=E_{n-1}+1.\end{align*} When I tried to solve this system of equations, I got some really ugly constants that I couldn't figure out how to simplify. In particular, I found that \begin{align*}E_1&=E_2+\frac{n+1}{n-1}\\E_2&=E_3+\frac{n^2+n+2}{(n-1)(n-2)}\\E_3&=E_4+\frac{n^3+5n+6}{(n-1)(n-2)(n-3)}.\end{align*} I feel like this might not be the right approach, so feel free to suggest something completely different. Thanks!

Edit: I've edited my initial conditions, but I still can't get it to work out.

$\endgroup$
  • 1
    $\begingroup$ Your initial conditions are wrong. $E_0=1+E_1$, for instance. The ball must be chosen from the full bin. $\endgroup$ – saulspatz Jul 22 at 16:18
  • $\begingroup$ @saulspatz Apparently, I copied in the incorrect initial conditions, but I was actually using the correct ones. Still not sure how to do this :( $\endgroup$ – boink Jul 22 at 16:59
  • 2
    $\begingroup$ You need to work $k$ into the picture. For $i=k\pm1$, one of the terms $E_{i-1}$ or $E_{i+1}$ in your recurrence should be replaced by $1$. $\endgroup$ – Steve Kass Jul 22 at 17:11
  • $\begingroup$ @SteveKass Okay, that makes sense to me. I'm sorry, but I don't quite see how that solves the problem, since all that happens is I have split this problem into two (smaller) problems, where the endpoints are $0$ and $k-1$ (or $k+1$ and $n$), rather than $0$ and $n$. If someone could explain this, that'd be brilliant! Thanks :) $\endgroup$ – boink Jul 22 at 17:41
  • $\begingroup$ I posted what I think are the right recurrence relations as an answer, as it's too long for a comment. $\endgroup$ – Steve Kass Jul 22 at 19:18
1
$\begingroup$

Your recursion is only right is we define $E_i$ such that $E_k=0$ (hence, not the expected time to get $k$ balls again, but to simply get $k$ balls). Then the recursion is indeed

$$ E_i=\frac inE_{i-1}+\frac{n-i}nE_{i+1}+1 \hskip{1cm} i\ne k, \; 0\le i\le n \tag 1$$ with $E_i=0$ if $i=k$ or $i<0$ or $i>n$.

Once we have $E_i$, the required expected time is $F_k=\frac knE_{k-1}+\frac{n-k}nE_{k+1}+1$.

The linear system $(1)$ has $n$ variables and $n$ equations, it can be solved numerically (for example, writing the system in matricial form). But I'm not sure about a symbolic solution.

Alternatively, and perhaps a little more elegant, this can modelled as a Markov chain with $n+1$ states, and the expected time between visits can be obtained from its limiting distribution. Again, this is easy... numerically.


Update: this is an Ehrenfest model. The following is adapted/copied from here.

Let $C_{i, j}$ be the expected time to get from $i$ balls to $j$ balls in the first bin, with $C_{i,i}=0$

Then, for $0<i<n$

$$ C_{i,n}=\frac{i}{n} C_{i-1,n}+\frac{n-i}{n} C_{i+1,n}+1 \tag 2$$

(like eq. $(1)$ , a little more general). Or

$$ n(C_{i,n}-C_{i+1,n} - 1 ) =i( C_{i-1,n}-C_{i+1,n} )\tag 3$$

But we also know, by linearity of expectation

$$ C_{i,n}=C_{i,i+1} +C_{i+1,i+2} + \cdots + C_{n-1,n} \tag4$$

Putting both eqs together:

$$ n (C_{i,i+1} -1)=i(C_{i-1,i} +C_{i,i+1}) \implies A_i(n-i)=i A_{i-1} +n\tag{5}$$ where $A_i=C_{i,i+1}$. With the initial condition $A_0=1$ this is solved by

$$A_i=\frac{\sum_{t=0}^{i}\binom{n}{t}}{\binom{n-1}{i}} \tag6$$

By simmetry of the bins, $$B_i \triangleq C_{i,i-1} = C_{n-i,n-i+1}=A_{n-i}\tag 7$$

Finally our desired expected time is

$$F_k = 1 + \frac{k}{n}A_{k-1} + \frac{n-k}{n}B_{k+1}=1 + \frac{k}{n}A_{k-1} + \frac{n-k}{n}A_{n-k-1}\tag8$$

...which, operating, gives $$F_k=\frac{2^n}{\binom{n}{k}} \tag9$$

This result is surprisingly (embarrasingly) simple, so perhaps I messed up something or either there should be a much simpler derivation... (Granted, this derivation solves a more general problem: it gives the expected time from any values of the start and end ocuppancy values)


Update 2: I wrote the result above and I saw this: if we regard this as a Markov Chain, but with the $2^n$ states corresponding to which (labeled) balls are in bin $A$, then the chain is reversible (the matrix is doubly stochastic) and hence the states are equiprobable in the equilibrium distribution, with $p=1/2^{n}$ each. Then the $n+1$ macro states composed of those states having $k$ balls have total probability $\binom{n}{k}/2^n$, and the mean recurrence time is $2^n/\binom{n}{k}$

$\endgroup$
0
$\begingroup$

[Not a full answer, but too long for a comment.]

The correct recursion for this problem is a little different than yours, which doesn’t account for actually reaching the goal of $k$ balls in the bin.

Let $E(i)$ be the expected number of steps needed to reach $k$ balls in bin A for the first time in the future, if there are currently $i$ balls in bin A and $n-i$ balls in bin B.

For $i$ equal to $0$ or $n$:

\begin{equation} E(0) = \begin{cases} 1+E(1) & \mbox{ if } k\neq1 \\ 1 & \mbox{ if } k=1 \end{cases} \end{equation}

\begin{equation} E(n) = \begin{cases} 1+E(n-1) & \mbox{ if } k\neq n-1 \\ 1 & \mbox{ if } k=n-1 \end{cases} \end{equation}

For $0< i < n$,

\begin{equation} E(i) = \begin{cases} \frac in E(i-1)+\frac{n-i}nE(i+1)+1 & \mbox{ if } k\notin\{i-1,i+1\} \\ \frac in +\frac{n-i}n(1+E(i+1)) & \mbox{ if } k=i-1 \\ \frac{n-i}n +\frac in(1+E(i-1)) & \mbox{ if } k=i+1 \end{cases} \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.