Problem 11477
(American Mathematical Monthly, Vol.117, January 2010) Proposed by A. Gonzalez (Spain) and J. H. Nieto (Venezuela).
Several boxes sit in a row, numbered from 0 on the left to n on the right. A frog hops from box to box, starting at time 0 in box 0. If at time t, the frog is in box k, it hops one box to the left with probabilityk/n and one box to the right with probability 1 − k/n. Let pi(k) be the prob- ability that the frog launches its(t+1)th hop from box k. Find limi→∞p2i(k) and limi→∞p2i+1(k).
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
This process can be described as a finite Markov chain with states {0, 1, 2, . . . , n} (the boxes), with a transition matrix P such that
pk,k+1= 1 − k/n, pk,k−1= k/n and pk,j= 0 otherwise.
Starting from an even-numbered state, the process can be in even-numbered states only in an even number of steps, and in an odd-numbered state in an odd number of steps. Hence the even and odd states form two cyclic classes. Let Qebe the restriction of P2to the even-numbered state. It is easy to see that this transition matrix is regular (i. e. some power of the matrix has all nonzero entries) and therefore there exists a unique invariant probability vector ue(i. e. ueQe= ue) such that
n→∞lim veQne = ue
for any probability vectors ve. Similarly, letting Qo be the restriction of P2 to the odd-numbered state then there exists a unique invariant probability vector uosuch that
n→∞lim voQno = uo
for any probability vectors vo. This implies that the limits qe(n, k) := limi→∞p2i(k) and qo(n, k) :=
limi→∞p2i+1(k) exist and, since the initial state is 0, they are the components of two unique prob- ability vectors such that: qe(n, k) = 0 for k odd, qo(n, k) = 0 for k even, and they satisfy the equations
qo(n, k) =
1 −k − 1 n
qe(n, k − 1) + k + 1
n qe(n, k + 1), qe(n, k) =
1 −k − 1 n
qo(n, k − 1) +k + 1
n qo(n, k + 1).
(notice that qe(n, k) = qe(n, k) = 0 for k 6∈ {0, 1, . . . , n}). Finally, we can easily verify that
qe(n, k) = 1 2n−1
n k
[k is even] and qo(n, k) = 1 2n−1
n k
[k is odd].
In factPn k=0
n
k[k is even] = Pnk=0 nk[k is odd] = 2n−1and
1 −k − 1 n
n k − 1
+k + 1
n
n k + 1
=
n k − 1
−n − 1 k − 2
+n − 1 k
=n − 1 k − 1
+n − 1 k
=n k
.
