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?



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

  • $\begingroup$ @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$? $\endgroup$ – Mary May 5 '11 at 18:31
  • $\begingroup$ answered (the recursion ) $\endgroup$ – leonbloy May 5 '11 at 18:37
  • $\begingroup$ @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? $\endgroup$ – Mary May 5 '11 at 18:48
  • $\begingroup$ 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. $\endgroup$ – leonbloy May 5 '11 at 19:02
  • $\begingroup$ @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? $\endgroup$ – Mary May 5 '11 at 19:42

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.