4
$\begingroup$

Suppose $X_1, X_2, ...,$ are IID random variables with $P(X_n=1)=p$ and $P(X_n=2)=1-p$. Let $S_n=\sum_{i=1}^n X_i$.

I was wondering how to find $P(S_n \neq z, \forall n \in \mathbb{N})$ for some particular natural number $z$?

How about the case when $P(X_n=1) = p_1, P(X_n=2)=p_2, P(X_n=3)=1-p_1-p_2$?

Does this problem belong to some kind of problems of random process?

Thanks!

  • 0
    This related problem uses dice, so is a case where $X$ can take the values 1,2,3,4,5 or 6: http://math.stackexchange.com/questions/12433/probability-of-dice-sum-just-greater-than-100/12553#125532011-11-09

2 Answers 2

4

This is similar to a asymmetric random walk, but the general theory does not help in your case.

Lets call $A_z$ the event that the process $S_n$ does reach the value $z$ for some $n$.

The complementary event $\bar{A_z}$ can only happen if $S_n$ reaches the previous value ($z-1$) and then it jumps by two ($X$ takes the value 2 for the next try).

That is

$P(\bar{A_z}) = P(\bar{A_z} | A_{z-1}) P(A_{z-1}) $

Then, calling $a_z = P(\bar{a_z})$ (the probability we are interested in ), and $q=1-p$ (probability of a two-sized jump) we get the recursion

$a_z = q \; \left[ 1 - a_{z-1} \right] $

with the initial condition $a(0) = 0$

The explicit solution is

$\displaystyle a(z) = q \frac{1 -(-q)^{z}}{1+q} $

ADDED: If $X(n)$ can take 3 values instead of 2, with probs $p_1,p_2,p_3$ the reasoning is similar. There are 3 possible cases and the recursion is

$a_z = (p_2 + p_3) (1- a_{z-1}) + p_3 (1 - a_{z-2})$

  • 0
    Yes, I'm summing over those three cases. The three posibles jumps (from z-1 , length 2; from z_1 , length 3; from z_2 , length 3) are three mutually exclusive events (call them J1 J2 J3) that divide the super-event "the process jumped over the value z". The probability of each event is thus computed, as a joint probability (eg J1 = process reaches z-1 AND x takes value 2), which is expressed as a conditional2011-05-05
5

Here's another approach, which may be more sophisticated than the asker wanted, but is a bit slicker.

Let $T = \inf\{n : S_n \ge z\}$. Note $S_T$ is either $z$ or $z+1$, and if $S_T = z+1$ then $z$ is never reached. So we are seeking $P(S_T = z+1)$. Call this value $q_z$ for short.

$T$ is a stopping time, so we'll use optional stopping on an exponential martingale. We seek $\theta$ such that $Y_n := \theta^{S_n}$ is a martingale; this will happen iff $E[\theta^{X_n}] = p \theta + (1-p) \theta^2 = 1$. The solutions of this equation are $\theta = 1$ (not useful) and $\theta = -1/(1-p)$. One easily sees that ${Y_{n \wedge T}}$ is bounded, so by the optional stopping theorem we have $ 1 = E[Y_0] = E[Y_T] = (1-q_z) \theta^z + q_z\theta^{z+1}.$ Taking $\theta = -1/(1-p)$ and solving for $q_z$ gives the result.

Incidentally, I "borrowed" a variant of this problem to use on an exam.