Question

Consider a model in which M balls are distributed between two bins, and at each time point one of the balls is chosen at random and is then removed from its bin and placed in the other one. Let Xn denote the number of balls in bin 1 after the nth switch and let m_n = E[Xn].

(a) Classify all the states of this chain as recurrent or transient (justify your answer!)

(b) Find E[X2|X0 = 2]

Answer 1

(a)

There will be M+1 states in this chain where Xn = 0, 1, 2, ..., M.

The ball from bin 1 or bin 2 will be selected with probability 1/2.

Thus, the transition probabilities are given as,

P(Xn+1 = k+1 | Xn = k) = 1/2 for k < M

P(Xn+1 = k-1 | Xn = k) = 1/2 for k 1

P(Xn+1 = k | Xn = k) = 1/2 for k = M if we assume that balls are not replaced if empty bin2 was selected.

P(Xn+1 = k | Xn = k) = 1/2 for k = 0   if we assume that balls are not replaced if empty bin1 was selected.

By looking at transition probabilities, every state is accessible from any other state, so this chain is irreducible. Therefore, every state is recurrent.

(b)

Assuming M 4,

P(X2 = 0 | X0 = 2] = Probability that bin 1 was selected twice to reduce number of balls in bin1 by 2 = (1/2) * (1/2) = 1/4

P(X2 = 2 | X0 = 2] = Probability that bin 1 was selected once and bin 2 was selected once in next 2 trials = (1/2) * (1/2) + (1/2) * (1/2) = 1/2

P(X2 = 4 | X0 = 2] = Probability that bin 2 was selected twice to increase number of balls in bin1 by 2 = (1/2) * (1/2) = 1/4

E[X2|X0 = 2] = (1/4) * 0 + (1/2) * 2 + (1/4) * 4 = 2