Estimating reaching probabilities of a simple random walk I'm currently reading the paper "Simple Random Walk" from Sven Erick Alm.
Nearly everything  is clear, except for the one inequality.
A simple random walk started at $0$, with probability $p$ of going up ($+1$) and $q=1-p$ of going down ($-1$). He defined $P_k(n)$ as the probability to reach $x=k$ in the first $n$ steps and claims that conditioning on the first step gives
$$
P_1(n) = p + qP_2(n-1) \le p+qP_1^2(n-1).
$$
I am having problem with the inequality on the RHS. Is there an easy explanation for it?
I tried to prove it rigorously using induction, but so far I didn't get satisfying results.
 A: We want to show $P_2(n-1) \le P_1(n-1)^2$, or in other words $P(\text{random walk hits $2$ in $n-1$ steps}) \le P(\text{random walk hits $1$ in $n-1$ steps})^2$.
Let $\tau$ be the first time the random walk $X$ hits $1$, and define $\hat X$ to be a random walk started at $1$ at time $\tau$ (basically thinking of restarting our random walk when it hits $1$ the first time).  The strong Markov property implies $X$ is independent of $\hat X$.  Then \begin{align*}P(\text{$X$ hits $2$ in $n-1$ steps}) &= P(\text{$X$ hits $1$ in $\tau$ steps and $\hat X$ hits $1$ in $n-1-\tau$ steps}) \\
&= P(\text{$X$ hits $1$ in $\tau$ steps}) P(\text{$\hat X$ hits $1$ in $n-1-\tau$ steps}) \\
&\le P(\text{$X$ hits $1$ in $n-1$ steps}) P(\text{$\hat X$ hits $1$ in $n-1$ steps}) \\
&= P(\text{$X$ hits $1$ in $n-1$ steps})^2 \\
&= P_1(n-1)^2.
\end{align*}
That's not a rigorous proof or anything, but that's the basic idea: to hit $2$ in $n-1$ steps, you have to independently hit $1$ twice in less than $n-1$ steps.  You can make this rigorous by being a little more careful about how you define $\hat X$.
