Maths Olympiad Prep

Track / Stage 7 / 251 of 300 #1651 of 1964

Problem 1651

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.6 Find the answer

A particle performing a random walk on the integer points of the semi-axis x0x \ge 0 moves a distance 11 to the right with probability aa, and to the left with probability bb, and stands still in the remaining cases (if x=0x = 0, it stands still instead of moving to the left). Determine the steady-state probability distribution, and also the expectation of xx and x2x^2 over a long time, if the particle starts at the point 00.

The source for this one didn't record the answer, so there is nothing to check what you type against. Work it on paper and mark yourself against the solution below.

Official solution

1. Define the problem and the Markov Chain:
- The particle performs a random walk on the integer points of the semi-axis x0 x \ge 0 .
- The transition probabilities are:
- Moves to the right (from x x to x+1 x+1 ) with probability a a .
- Moves to the left (from x x to x1 x-1 ) with probability b b , but if x=0 x = 0 , it stands still.
- Stands still with the remaining probability 1ab 1 - a - b .

2. Steady-state probability distribution:
- Let π(k)\pi(k) be the steady-state probability of being at position k k .
- For k1 k \ge 1 , the balance equations are:
π(k)a=bπ(k+1) \pi(k) a = b \pi(k+1)
- For k=0 k = 0 , the balance equation is:
π(0)=π(0)(1a)+bπ(1) \pi(0) = \pi(0) (1 - a) + b \pi(1)
- From the first balance equation, we can express π(k+1)\pi(k+1) in terms of π(k)\pi(k):
π(k+1)=abπ(k) \pi(k+1) = \frac{a}{b} \pi(k)
- By iterating this relationship, we get:
π(k)=(ab)kπ(0) \pi(k) = \left(\frac{a}{b}\right)^k \pi(0)
- To find π(0)\pi(0), we use the normalization condition:
k=0π(k)=1 \sum_{k=0}^{\infty} \pi(k) = 1
π(0)k=0(ab)k=1 \pi(0) \sum_{k=0}^{\infty} \left(\frac{a}{b}\right)^k = 1
- The series k=0(ab)k\sum_{k=0}^{\infty} \left(\frac{a}{b}\right)^k converges if ab<1\frac{a}{b} < 1, which implies a<b a < b :
k=0(ab)k=11ab=bba \sum_{k=0}^{\infty} \left(\frac{a}{b}\right)^k = \frac{1}{1 - \frac{a}{b}} = \frac{b}{b - a}
- Therefore:
π(0)bba=1    π(0)=bab \pi(0) \cdot \frac{b}{b - a} = 1 \implies \pi(0) = \frac{b - a}{b}
- The steady-state distribution is:
π(k)=(ab)kbab \pi(k) = \left(\frac{a}{b}\right)^k \frac{b - a}{b}

3. **Expectation of x x :**
- The expectation E[x] E[x] is given by:
E[x]=k=0kπ(k) E[x] = \sum_{k=0}^{\infty} k \pi(k)
E[x]=k=0k(ab)kbab E[x] = \sum_{k=0}^{\infty} k \left(\frac{a}{b}\right)^k \frac{b - a}{b}
- Using the formula for the sum of an infinite series:
k=0krk=r(1r)2forr<1 \sum_{k=0}^{\infty} k r^k = \frac{r}{(1 - r)^2} \quad \text{for} \quad |r| < 1
- Here, r=ab r = \frac{a}{b} :
E[x]=babab(1ab)2=babab(bab)2=aba E[x] = \frac{b - a}{b} \cdot \frac{\frac{a}{b}}{\left(1 - \frac{a}{b}\right)^2} = \frac{b - a}{b} \cdot \frac{\frac{a}{b}}{\left(\frac{b - a}{b}\right)^2} = \frac{a}{b - a}

4. **Expectation of x2 x^2 :**
- The expectation E[x2] E[x^2] is given by:
E[x2]=k=0k2π(k) E[x^2] = \sum_{k=0}^{\infty} k^2 \pi(k)
E[x2]=k=0k2(ab)kbab E[x^2] = \sum_{k=0}^{\infty} k^2 \left(\frac{a}{b}\right)^k \frac{b - a}{b}
- Using the formula for the sum of an infinite series:
k=0k2rk=r(1+r)(1r)3forr<1 \sum_{k=0}^{\infty} k^2 r^k = \frac{r(1 + r)}{(1 - r)^3} \quad \text{for} \quad |r| < 1
- Here, r=ab r = \frac{a}{b} :
E[x2]=babab(1+ab)(1ab)3=babab(b+ab)(bab)3 E[x^2] = \frac{b - a}{b} \cdot \frac{\frac{a}{b} \left(1 + \frac{a}{b}\right)}{\left(1 - \frac{a}{b}\right)^3} = \frac{b - a}{b} \cdot \frac{\frac{a}{b} \left(\frac{b + a}{b}\right)}{\left(\frac{b - a}{b}\right)^3}
E[x2]=a(b+a)(ba)2 E[x^2] = \frac{a(b + a)}{(b - a)^2}

The final answer is:

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.