0

Ten people are attending a party in a two-room apartment and, initially, it is equally likely that all ten are in room A or that nine are in room A and one in room B. This is no ordinary party: every minute, one person is chosen uniformly at random (independently of whatever happened in the past), and they must move into the other room (i.e. if they were in room A they move to B, and vice-versa).

For example, suppose we're in the 50% of cases where everyone is initially in room A. At the end of the first minute someone will be chosen and will walk into room B, leaving nine people in room A. At the end of the second minute, with probability 9/10 someone in room A will be selected (in which case they'd go join the person in room B, or, with probability 1/10, the person in room B will return to room A, restoring the initial configuration.

We're interested in the probability that the group is evenly split between rooms A and B (i.e. 5 people in each) after N minutes. What does that probability converge to as N goes to infinity?

Himanshu Agarwal
  • 19
  • 2

1 Answers1

1

For nonnegative integer $n$ and $k\in\left\{ 0,1,2,3,4,5\right\} $ let $p_{n,k}$ denote the probability that after $n$ minutes there are $k$ persons in room that does not contain more persons than other room.

Then we are interested in sequence $\left(p_{n,5}\right)_{n}$.

We find the following equalities:

  • $2p_{0,0}=1=2p_{0,1}$ and $p_{0,2}=p_{0,3}=p_{0,4}=p_{0,5}=0$

And for every $n$:

  • $10p_{n+1,0}=p_{n,1}$
  • $10p_{n+1,1}=10p_{n,0}+2p_{n,2}$
  • $10p_{n+1,2}=9p_{n,1}+3p_{n,3}$
  • $10p_{n+1,3}=8p_{n,2}+4p_{n,4}$
  • $10p_{n+1,4}=7p_{n,3}+10p_{n,5}$
  • $10p_{n+1,5}=6p_{n,4}$

Preassuming that for every $k$ limit $p_{k}:=\lim_{n\to\infty}p_{n,k}$ exists we find:

  • $p_{0}+p_{1}+p_{2}+p_{3}+p_{4}+p_{5}=1$
  • $10p_{0}=p_{1}$
  • $10p_{1}=10p_{0}+2p_{2}$
  • $10p_{2}=9p_{1}+3p_{3}$
  • $10p_{3}=8p_{2}+4p_{4}$
  • $10p_{4}=7p_{3}+10p_{5}$
  • $10p_{5}=6p_{4}$

This can be solved (do it yourself) and leads to: $$p_{5}=\frac{126}{512}=\frac{63}{256}=0.24609375$$

drhab
  • 151,093