## Remark to Q 3.22

This forum is for discussing our interview question book. If you want the answer to a follow-up question or to dispute the solutions, this is the place to ask.

### Remark to Q 3.22

In the solution to question 3.22 seems like we still need to prove that the probability of the ant getting from positions n=1,2,3 to position n=0 equals 1. In other words that the expected time for the ant to get from positions n=1,2,3 to position n=0 is finite.
For example, lets consider this formula: f(0) = f(1) + 1. By definition of expectation: f(0) = sum(i)(t_i * p(w_00i)) = sum(j)[(t_j + 1) * p(w_10j)], where w_00i (w_10j) is an ith (jth) path to get from position 0 (1) to position 0 and takes time t_i (t_j). Thus f(0) = sum(j)(t_j * p(w_10j)) + 1 * sum(j) p(w_10j) = f(1) + 1 * sum(j) p(w_10j). So f(0) equals f(1) + 1 only when sum(j) p(w_10j) = 1. How can we prove it?
Let P_i0 denote a probability of getting to position 0 starting from position i = 1,2,3. Then starting from position 1 the ant travels to position 0 with probability 1/3 and to position 2 with probability 2/3 which gives: P_10 = 1/3 + 2/3 * P_20. Same way P_20 = 2/3 * P_10 + 1/3 * P_30 and P_30 = P_20 because from position 3 the ant can travel only to position 2. Solving these equations gives P_10 = P_20 = P_30 = 1, which was needed to prove.
tns

Posts: 4
Joined: Thu Apr 06, 2017 2:27 pm