JEST TCS 2025 | Section A (MCQ) | Question: 15

Question

Starting with $x_0 = 0$, suppose you do the following:, at the $n^{th}$ stepyou flip a fair coin: if it is heads then $x_n := x_{n-1} + 1$ and if it is tails then $x_n := x_{n-1} - 1$ for $n \geq 1.$ Let $p_n(m)$ be the probability that $x_n = m$ . Consider the following statements for $n \geq 1.$

1. $p_{2n}(0) = p_{2n-1}(1)$.
2. $p_{2n}(0) = \frac{p_{2n-1}(1) + p_{2n-1}(-1)}{2}$.
3. $p_{2n-1}(0) = 0$.
4. $p_{2n}(0) > p_{2n+1}(1)$.

Which of the following choices is true?

• A. Only i., ii. and iii. are true.
• B. The statements i., ii., iii., and iv. are true.
• C. Only i., and ii. are true.
• D. Only i. is true. 

Answer 1

We start at position \(x_0 = 0\).
At each step, a fair coin is flipped:
Heads (\(H\)): move right → \(x_{i} = x_{i-1} + 1\)
Tails (\(T\)): move left → \(x_{i} = x_{i-1} - 1\)

Let \(k\) be the number of heads in \(n\) steps.  
Then, the number of tails is \(n - k\).  
So the total distance from initial position is:
\[
x_n = (+1) \cdot k + (-1) \cdot (n - k) = 2k - n.
\]

Now, to reach position \(m\) after \(n\) steps:
\[
2k - n = m \Rightarrow k = \frac{n + m}{2}.
\]
This has to be an integer; otherwise, we cannot reach position \(m\) at step \(n\), so in that case \(p_n(m) = 0\).

Otherwise, the probability is going to be:
\[
p_n(m) = \binom{n}{\frac{n + m}{2}} \left(\frac{1}{2}\right)^n.
\]

This is because (out of \(n\)) we can choose exactly \(\frac{n + m}{2}\) steps to be heads , and each step has equal probability (either a head or a tail).

 

---

 

\({\text{Statement (i): } p_{2n}(0) = p_{2n-1}(1)}\)

For \(p_{2n}(0)\):  

To be at position 0 after \(2n\) steps, we need \(k = \frac{2n + 0}{2} = n\) heads.  
So:
  \[
  p_{2n}(0) = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n} = \frac{\binom{2n}{n}}{4^n}.
  \]

For \(p_{2n-1}(1)\):  
To be at position 1 after \(2n-1\) steps, we need \(k = \frac{2n - 1 + 1}{2} = n\) heads.  
So:
\[
  p_{2n-1}(1) = \binom{2n-1}{n} \left(\frac{1}{2}\right)^{2n-1} 
  = \frac{\binom{2n-1}{n}}{2^{2n-1}} = \frac{\binom{2n-1}{n} \cdot 2}{4^n}.
  \]

we can deduce this:
\[
\binom{2n}{n} = 2 \cdot \binom{2n - 1}{n}.
\]

So:
\[
p_{2n}(0) = \ p_{2n-1}(1).
\]

Therefore, statement (i) is \(\boxed{\text{true}}\)

---

\({\text{Statement (ii): } p_{2n}(0) = \frac{p_{2n-1}(1) + p_{2n-1}(-1)}{2}}\)

We have already calculated \(LHS\):
\[
p_{2n}(0) = \binom{2n}{n} \cdot \left(\frac{1}{2}\right)^{2n} = \frac{\binom{2n}{n}}{4^n}.
\]

Now compute \(p_{2n-1}(1)\) :

To be at position 1 after \(2n - 1\) steps: we need \(k = \frac{(2n-1) + 1}{2} = n\) heads.
So:
\[
p_{2n-1}(1) = \binom{2n - 1}{n} \cdot \left( \frac{1}{2} \right)^{2n - 1}.
\]

Similarly,
\[
p_{2n-1}(-1) = \binom{2n - 1}{\frac{2n - 1 + (-1)}{2}} \cdot \left(\frac{1}{2}\right)^{2n-1}
= \binom{2n - 1}{n - 1} \cdot \frac{1}{2^{2n - 1}}.
\]

So the RHS becomes:
\[
\frac{p_{2n-1}(1) + p_{2n-1}(-1)}{2}
= \frac{1}{2} \cdot \left( \binom{2n - 1}{n} + \binom{2n - 1}{n - 1} \right) \cdot \frac{1}{2^{2n - 1}}.
\]

we know that:
\[
\binom{2n - 1}{n} + \binom{2n - 1}{n - 1} = \binom{2n}{n},
\]

we get:
\[
\frac{p_{2n-1}(1) + p_{2n-1}(-1)}{2}
= \frac{1}{2} \cdot \binom{2n}{n} \cdot \frac{1}{2^{2n - 1}}
= \frac{\binom{2n}{n}}{2 \cdot 2^{2n - 1}}
= \frac{\binom{2n}{n}}{2^{2n}} = \frac{\binom{2n}{n}}{4^n}.
\]

This matches \(LHS\), so statement (ii) is \(\boxed{\text{true}}\).

 

---

\({\text{Statement (iii): } p_{2n-1}(0) = 0}\)

To be at position 0 after \(2n - 1\) steps: we need \(k = \frac{(2n-1) + 0}{2} =\frac{2n - 1}{2}\) heads.
\[
p_{2n - 1}(0) = \binom{2n - 1}{\frac{2n - 1}{2}} \cdot \left( \frac{1}{2} \right)^{2n - 1}
\]
but \(k = \frac{2n - 1}{2} \notin \mathbb{Z}\),

so it is undefined, and thus the probability is zero.

Therefore, statement (iii) is \(\boxed{\text{true}}\)

 

 

---

 

\({\text{Statement (iv): } p_{2n}(0) > p_{2n+1}(1)}\)
 

we have already calculated:

\[
p_{2n}(0) = \frac{\binom{2n}{n}}{4^n}
\]

 

For  \(p_{2n+1}(1)\)

To be at position 1 after \(2n+1\) steps, we need \(k = \frac{(2n+1) + 1}{2} = n+1\) heads.  

Then,
\[
p_{2n+1}(1) = \binom{2n+1}{n+1} \cdot \left( \frac{1}{2} \right)^{2n + 1}
= \frac{\binom{2n+1}{n+1}}{2^{2n + 1}}
\]

 

we can easily verify that:
\[
p_{2n}(0) > p_{2n+1}(1)
\]

Therefore, statement (iv) is \(\boxed{\text{true}}\)