# A probability question

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!

-
This related problem uses dice, so is a case where $X$ can take the values 1,2,3,4,5 or 6: math.stackexchange.com/questions/12433/… –  Byron Schmuland Nov 9 '11 at 16:51

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

-
@leonbloy: Thanks! How about when $P(X_n) = p_1, P(X_n=2)=p_2, P(X_n=3)=1-p_1-p_2$? –  Mary May 5 '11 at 18:31
answered (the recursion ) –  leonbloy May 5 '11 at 18:37
@leonbloy: Thanks! I think the case for 3 values are different from for 2 values. You now consider two events: reaching z-1 and reaching z-2. But the two events are not exclusive, because reaching z-2 can then reaching z-1. So Is $a_z = (p_2 + p_3) (1- a_{z-1}) + p_3 (1 - a_{z-2})$ not right? –  Mary May 5 '11 at 18:48
You are right in suspecting about the 3 values solution, but I think it's right nevertheless. The process can "jump" the value 'z' by three posible "jumps" (mutually exclusive) - I'm summing over those three cases. –  leonbloy May 5 '11 at 19:02
@leonbloy: Could you explain more on "The process can 'jump' the value 'z' by three posible 'jumps' (mutually exclusive) - I'm summing over those three cases"? You used the law of total expectation to consider several events, which requires these events to be exclusive, doesn't it? –  Mary May 5 '11 at 19:42
show 1 more comment

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.

-