TIFR CSE 2022 | Part A | Question: 15

Question

Fix $n \geq 4$. Suppose there is a particle that moves randomly on the number line, but never leaves the set $\{1,2, \ldots, n\}$. The initial probability distribution of the particle is $\pi$ i.e., the probability that particle is in location $i$ is given by $\pi(i)$. In the first step, if the particle is at position $i$, it moves to one of the positions in $\{1,2, \ldots, i\}$ with uniform distribution; in the second step, if the particle is in location $j$, then it moves to one of the locations in $\{j, j+1, \ldots, n\}$ with uniform distribution. Suppose after two steps, the final distribution of the particle is uniform. What is the initial distribution $\pi?$ 

• A. $\pi$ is not unique
• B. $\pi$ is uniform
• C. $\pi(i)$ is non-zero for all even $i$ and zero otherwise
• D. $\pi(1)=1$ and $\pi(i)=0$ for $i \neq 1$
• E. $\pi(n)=1$ and $\pi(i)=0$ for $i \neq n$

Comments

https://gateoverflow.in/333105/tifr-cse-2020-part-a-question-4

Answer 1

(1)  $\pi$ is the initial distribution of particle being at location $i$.

$\implies \pi(1) + \pi(2) + \pi(3) + … + \pi(n) = 1$

(2) (First Step) When particle is in location $i$, it can move to any position in {$1,2,…,i$} with uniform probability ie probability of particle going to location $k$ is $\frac{1}{i}$ where $k \le i$.

(3) (Second Step) When particle is in location $k$ after first step, it can move to any position in {$k,k+1,…,n$} with uniform probability ie probability of particle going to location $j$ is $\frac{1}{n-k+1}$ where $j \ge k$.

As given, after completing both steps, the final distribution of particle is uniform in {$1,2,…,n$} with probability that particle is in location $j$ is $\pi’(j) = \frac{1}{n}$.

$\therefore \pi’(1) = \frac{1}{n}$

Now, the probability in terms of $\pi(i)$ of particle being at location $1$ is given by – 

$\pi’(1) = \pi(1) * \frac{1}{1} * \frac{1}{n} + \pi(2) * \frac{1}{2} * \frac{1}{n} + \pi(3) * \frac{1}{3} * \frac{1}{n} + … + \pi(n) * \frac{1}{n} * \frac{1}{n}$

$\implies \frac{1}{n} = \pi(1) * \frac{1}{1} * \frac{1}{n} + \pi(2) * \frac{1}{2} * \frac{1}{n} + \pi(3) * \frac{1}{3} * \frac{1}{n} + … + \pi(n) * \frac{1}{n} * \frac{1}{n}$

$\implies 1 = \pi(1) * \frac{1}{1} + \pi(2) * \frac{1}{2} + \pi(3) * \frac{1}{3}  + … + \pi(n) * \frac{1}{n}$

$\therefore \pi(1) + \pi(2) + \pi(3) + … + \pi(n) = \pi(1) * \frac{1}{1} + \pi(2) * \frac{1}{2} + \pi(3) * \frac{1}{3}  + … + \pi(n) * \frac{1}{n}$

$\implies \pi(2) + \pi(3) + … + \pi(n) =  \frac{\pi(2) }{2} + \frac{\pi(3)}{3}  + … + \frac{\pi(n)}{n}$

This is only possible when $\pi(2) = \pi(3) = … = \pi(n) = 0$

$\implies \pi(1) = 1 \text{ and } \pi(i) = 0, \forall i \neq 1$

Answer :- D.