Random walk with 3 cases.

Question

Let the walking start be at $x=0$. With probability $p_1$ new $x=x+1$, with probability $p_2$: $x=x-1$ and with probability $1-p_1-p_2 \geq 0$ walking ends.

The question is what is the probability of ending on point $n$.

I've computed it numerically and getting something close to normal distribution with peak at zero, but with different dispersion on sides of $x=0$. How to get it analytically?

The provided answer seems ok, but I hope I can find some smooth function for it. Maybe with another type of solution.

Upd: my idea of solution.

$$P_{n+1} (x) = p_1 P_{n} (x-\delta x) + p_2 P_{n} (x + \delta x)$$ $$P_{n+1} (x) - P_{n} (x) = p_1 [P_n(x-\delta x) - P_n(x)] + p_2 [P_n(x+\delta x) - P_n(x)] - q\cdot P_{n}(x)$$ Dividing by $\delta n$ and $\delta x$ getting something like: $$\frac{\partial P(n,x)}{\partial n}= \frac{\delta x}{\delta n}\left[ (p_2 + p_1) \frac{\partial P(n,x)}{\partial x} - (1 - p_2 - p_1)\cdot P(n,x)\right]$$ Solving it leads to something like this: $$P(n,x) = Ae^{\frac{-q x}{p_1 + p_2}}(n + \frac{x}{p_1 + p_2})$$ I'm not sure yet if it means something.

Answer 1

We derive a closed formula and show the following is valid for $n\geq 0$ \begin{align*} \sum_{k=0}^\infty\binom{n+2k}{k}x^k&= \frac{1}{\sqrt{1-4x}} \left(\frac{1-\sqrt{1-4x}}{2x}\right)^n\tag{1}\\ \end{align*}

Note that \begin{align*} c(x)=\frac{1-\sqrt{1-4x}}{2x}=1+x+2x^2+5x^3+14x^4+\cdots \end{align*} is the generating function of the ubiquitous Catalan numbers. We use the coefficient of operator $[w^k]$ to denote the coefficient of $w^k$ in a series. This way we can write e.g. \begin{align*} [w^k](1+w)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^{\infty}\binom{n+2k}{k}x^k} &=\sum_{k=0}^\infty[w^{k}](1+w)^{n+2k}x^k\tag{2}\\ &=[w^0](1+w)^n\sum_{k=0}^\infty\left(\frac{x(1+w)^2}{w}\right)^k\tag{3}\\ &=[w^0]\frac{(1+w)^n}{1-\frac{x(1+w)^2}{w}}\tag{4}\\ &=-[w^{-1}]\frac{(1+w)^n}{x+(2x-1)w+xw^2}\\ &=-[w^{-1}]\frac{\left(1+w\right)^n}{x(w-w_0(x))(w-w_1(x))}\tag{5}\\ &=\frac{\left(1+w_0(x)\right)^n}{x(w_1(x)-w_0(x))}\tag{6}\\ &\color{blue}{=\frac{1}{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^n}\tag{7} \end{align*} and the claim (1) follows.

Comment:

• In (2) we apply the coefficient of operator.

• In (3) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [w^{p+q}]A(w)=[w^p]w^{-q}A(w) \end{align*}

• In (4) we apply the geometric series expansion.

• In (5) we represent the denominator with poles $w_0(x)$ and $w_1(x)$. \begin{align*} w_0(x)&=\frac{1-\sqrt{1-4x}}{2x}-1\tag{8}\\ w_1(x)&=\frac{1+\sqrt{1-4x}}{2x}-1\\ \end{align*}

• In (6) we calculate the residual of the simple pole at $w=w_0(x)$ using \begin{align*} \operatorname{res}_{w=a}f(w)=\lim_{w\to a}(w-a)f(w) \end{align*}

• In (7) we use the representation from (8).

Answer 2

First of all, it is easy to observe that the walking can only end after $n+2k$ steps, where $k \in \mathbb{N}$.

Now, let $P_k$ be the probability that we end after exactly $n+2k$ steps. Then:

$$P_k = \binom{n+2k}{k} p_1^{n+k}p_2^{k} (1-p_1 - p_2) $$

This is because in order to end the walk at exactly $n$, we need to spend (any) $k$ steps going "left" and (the remaining) $n+k$ steps going right. And after that we need to stop.

Thus, the total probability $P$ should be given by:

$$P = \sum\limits_{k=0}^{\infty}P_k = (1-p_1 - p_2)\sum\limits_{k=0}^{\infty}\binom{n+2k}{k} p_1^{n+k}p_2^{k}$$

Answer 3

Pellenthor's solution is probably the best you can obtain. You can simplify it just slightly more:

$$\begin{align} P^+(n) =&\; (1-p_1 - p_2)\cdot\sum\limits_{k=0}^{\infty}\binom{n+2k}{k} p_1^{n+k}p_2^{k}=\\ =&\; p_1^n\cdot(1-p_1 - p_2)\cdot\sum\limits_{k=0}^{\infty}\binom{n+2k}{k} (p_1p_2)^{k} =\\ =&\; p_1^n\cdot(1-p_1 - p_2)\cdot {_2F_1}\left(\frac{n+1}{2},\frac{n+2}{2};n+1;4p_1p_2 \right) \end{align}$$

where $_2F_1$ is the hypergeometric function (it is likely that the previous line looks more friendly!). Please note that this expression is valid for "destinations" on the right, i.e. for $n\gt 0$ (you might include here $n=0$, but I like to keep this case on its own). For "destinations" on the left replace every $n$ with $|n|$ and put $p_2^{|n|}$ at the beginning.

I've tested a couple of particular cases. For $p_1 = p_2 = 2/5$ (so $p_{stop}=1/5$) we have $$ \sum\limits_{n=-1}^{-\infty}P^-(n) \; + P(0) \; + \sum\limits_{n=1}^{\infty}P^+(n) = \frac{1}{3} \; + \; \frac{1}{3} \; + \; \frac{1}{3} = 1 $$ which respects symmetry and the correct sum to $1$. For $p_1=1/2$, $p_2=1/3$, $p_{stop}=1/6$: $$ \sum\limits_{n=-1}^{-\infty}P^-(n) \; + P(0) \; + \sum\limits_{n=1}^{\infty}P^+(n) = \frac{3-\sqrt{3}}{6} \; + \; \frac{\sqrt{3}}{6} \; + \; 0.5 = 1 $$ as expected unbalanced towards right. I don't think that anything better can be done. See the amazing answer from Markus Scheuer to see the closed form of the general term!