I'm struggling with a problem I was asked by a friend a few days ago. It goes as follows:
You start at the origin. On the first iteration you walk right with probability $p$ and left with probability $q = 1 – p$. On each subsequent iteration you walk in the same direction as the previous iteration with probability $p$ and in the opposite direction with probability $q$. What is the probability that you return to the origin in $n$ steps or fewer?
The issue is that it's difficult to account for the Markov process in the calculation. Since I want something that works for arbitrary $n$, I can't use matrices.
Say $X_i$ is the the random variable such that on the $i$-th step
$$
X_i = \begin{cases} 1 &\text{if}\ i = 0\ \text{and went right}\\
-1 &\text{if}\ i = 0\ \text{and went left}\\
1 &\text{if}\ i > 0\ \text{and went in same direction}\\
-1 &\text{if}\ i > 0\ \text{and went in opposite direction.}\end{cases}
$$
Then the probability of returning to the origin is
\begin{align*}
P(\text{return})
&= q P(\text{return}|X_0 = -1) + p P(\text{return}|X_0 = 1)\\
&= P(\text{return}|X_0 = 1)\\
&= q + p P(\text{return}|X_1 = 1).
\end{align*}
I don't know where to go from here.
When constructing a Monte Carlo simulation, I first simulate $\left(X_i\right)_{i = 0}^{n-1}$. Then the cumulative product tells you whether you went left or right on the $i$-th step. From there, you can take the cumulative sum to find position. If that's ever 0, then you add to the count. It's not clear to me how one would map this onto a mathematically rigorous calculation.
This is my Python code.
import numpy as np
# Define n
n = 4
# Define p
p = 0.75
# Calculate q
q = 1 - p
# X can be either 1 or -1
vals = [1, -1]
# How many Monte Carlo simulations
sims = 10**6
# Whether same or opposite
X = np.random.choice(vals, size = (sims, n), replace = True, p = [p, q])
# Whether left or right
move = np.cumprod(X, axis = 1)
# Sum change to calculate position
position = np.cumsum(move, axis = 1)
# Which rows go through the origin
success = np.sum(position == 0, axis = 1) > 0
# Calculate fraction that go through the origin
solution = np.mean(success)
solution
Best Answer
An approach without using Markov chain.
To avoid double counting we will classify the paths by the number of the steps until the first return to the origin and by the number of direction changes. Observe that the former number must be even (the same number of steps in each direction) whereas the latter number must be odd.
Accordingly the probability of the first return to the origin at $2m$-th step after $2k-1$ direction changes can be written as: $$\begin{align} P_{mk}&=\underbrace{p\big[N(m-1,k)\,p^{2m-2-(2k-1)}q^{2k-1} \big]p}_\text{first step to the right}+\underbrace{q\big[N(m-1,k)\,p^{2m-2-(2k-1)}q^{2k-1} \big]p}_\text{first step to the left}\\ \\ &=N(m-1,k)\,p^{2m-2k}q^{2k-1},\tag1 \end{align}$$ where $$N(m,k)=\frac1k\binom m{k-1}\binom{m-1}{k-1}\tag2$$ is the Narayana number.
Finally the probability in question is: $$ \sum_{m=1}^{\left\lfloor\frac n2\right\rfloor}\sum_{k=1}^m P_{mk}.\tag3 $$