0

I'm having a hard time trying to compute the limiting distribution of this problem

Problem

In a kindergarten, $n$ boys and $n$ girls are standing in a circle playing a game. The children are spaced evenly around the circle and alternate between boys and girls. Initially, a ball is given to a child chosen uniformly at random. At each second, the ball will be passed according to the following rules:

  • If a girl has the ball, she will either pass it to the child on her left or the child on her right, with equal probabilities.
  • If a boy has the ball, he will either throw it up into the air and catch it himself, or throw it to the child diametrically opposite him in the circle, with equal probabilities.

(a) Consider the probability of a particular child having the ball at $t$ seconds. Does this have a limit as $t$ goes to infinity? If so, compute that limit. If not, explain why. Hint. Beware of the parity of $n$.

(b) Suppose we change the rules so that when a boy has the ball, he always throws it to the child diametrically opposite him. What would be the answer to part (a)?

My attempt:

a) The limiting distribution does exists because it is an irreducible aperiodic markov chain. I am not sure how do I find the limiting distribution. Intuitively it looks like in the long run, if the child is a boy then it will have a probability of 1 getting the ball as t -> $\infty$

b) There will not be a limiting distribution as the ball will keep travelling and will not converge.

Am I on the right track?

codelearner
  • 253

1 Answers1

1

So first off your answer to b is just nonsense; the ball stays in motion but that doesn't say anything about the evolution of the distribution of its motion, besides that a point mass at a particular child isn't stationary.

Moving on, the first thing you need to pay attention to is the warning about the parity of $n$. This decides whether boys face boys or boys face girls, which has a huge impact on the dynamics; in one case the chain is irreducible and aperiodic and in the other case it isn't. You'll need to think a little bit about the case where the chain isn't irreducible and aperiodic, because in this case the limiting behavior of the distribution depends on the initial condition.

Now the main thing you need to do in order to shrink the problem is to realize that all the boys are equivalent and all the girls are equivalent. So it suffices to look at a small value of $n$ (of each parity) in order to determine the probability that the current holder is a boy and the probability that the current holder is a girl, then just divide each of those by $n$ to finish.

Ian
  • 101,645