Calculating $P(X_n\ge 0)$, for $n = 1, 2, 3, 4$ in a random walk

Question

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.

Answer 1

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)$

Answer 2

$\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$$