Calculating $P(X_n\ge 0)$, for $n = 1, 2, 3, 4$ in a random walk Let us take a random walk as follows, $$X_0 = 0;\ X_n = \sum_{i=1}^{n} e_i$$
where,
$$
e_n=
\begin{cases} 
+1 \text{ with probability } p; \\
-1 \text{ with probability } q;
\end{cases}
$$
and all $e_n$ are independent variables, so I have to calculate
$$ \mathbb{P}(X_n\ge0,\forall\ n = 1,2,3,4 )$$
I know the standard results regarding random walks but I am drawing blanks here.
 A: The following binary tree shows all possible ways that we can have the event $X_n \geq 0,\;\forall{n}\in\{1,2,3,4\}$

Number of ways favorable to the event = number of possible paths from the root node to a leaf node in the tree = number of leaf nodes in the tree = 6, with the total probability $P(X_n \geq 0)$ summing up to $p^4 + p^3q + p^2qp + p^2q^2 + pqp^2 + pqpq=p^2(p^2+3pq+2q^2)$
A: $\forall i \in \{1, \ldots, n\}, \dfrac{e_i + 1}{2}$ is a Benoulli distribution of parameter $p$ then :
$$Y = \sum_{i = 1}^n \dfrac{e_i + 1}{2} = \dfrac{X_n + n}{2}$$
is a binomial distribution of parameter $(n, p)$.
we deduce that :
$$p(X_n \geq 0) = p (Y \geq \frac{n}{2}) = \sum_{k \geq \frac{n}{2}}^n \binom{n}{k} p^k q^{n - k}$$

*

* For $n = 1$ :
$$p(X_1 \geq 0) = \binom{1}{1} p q^{1 - 1} = p$$

* For $n = 2$ :
$$p(X_2 \geq 0) = \sum_{k = 1}^2 \binom{2}{k} p^k q^{2 - k} = 2 p q + p^2$$

* For $n = 3$ :
$$p(X_3 \geq 0) = \sum_{k = 2}^3 \binom{3}{k} p^k q^{3 - k} = 3 p^2 q + p^3$$

* For $n = 4$ :
$$p(X_4 \geq 0) = \sum_{k = 2}^4 \binom{4}{k} p^k q^{4 - k} = 6 p^2 q^2 + 4 p^3 q + p^4$$
