How can I model the following problem by a random walk:

Consider that at time $t=0$ Mike has $M$ dollars. He receives a dollar at each of the times $R_1, R_1+ R_2, R_1+R_2+R_3,\cdots$, where $R_i$s are independent random variables according to probability density function (pdf) $p_1(x)$, and spends a dollar at times $S_1, S_1+ S_2, S_1+S_2+S_3,\cdots$, where $S_i$s are independent random variables according to pdf $p_2(x)$. If he has to spend a dollar but he doesn't have any money, he borrows that.

Question: What is the probability that he doesn't borrow money, from the beginning until the time that he spends the $k^{th}$ dollar?

If I model this by a random walk, then I will have to find the survival probability which may be already in the literature. Let's try model this problem by a random walk: Mike starts at point $x=M$, when he receives a dollar he goes to $x-1$, and when he spends a dollar he goes to $x+1$. But, the probability that Mike goes to left or right depends on $x$. What should I do?

I am wondering if you have faced similar problem and know how I should deal with it. I appreciate any helps regarding that including useful references. Of course, a full answer is the best!

  • 3
    $\begingroup$ This doesn't appear to be a random walk--not in the standard sense of the term. It concerns two independent point processes with waiting times given by two continuous distributions with PDFs $p_1$ and $p_2$. $\endgroup$
    – whuber
    Nov 12, 2016 at 23:40
  • 1
    $\begingroup$ @whuber Then, any idea how I can solve it? If it is not random walk, anything similar in the literature? $\endgroup$
    – Sus20200
    Nov 12, 2016 at 23:45

1 Answer 1


It's important to know whether the probability distributions $P_1$ and $P_2$ are markovian (i.e., memoryless) or not. If they are markovian, then just like whuber said, you can model it as follows: the random walk goes left (towards bankruptcy) w.p. $p=Pr(X_1 > X_2)$ with $X_1 \sim P_1, X_2 \sim P_2$. This will define a (biased) random walk with probability $p$ and you can look into the book

Feller: An introduction to probability theory and its applications

for an analysis of hitting bankruptcy (this is called gambler's ruin). From this you should also be able to calculate the expected time this happens, supposing that $p\geq 1/2$ (otherwise it's infinity).

If they are not markovian, meaning for every time step you have a time-dependent probability, then you might be want to look into martingales and Azuma's inequality, which won't give tight results, but at least something.

  • $\begingroup$ Hi, thank you. That was helpful. I am more interested in the general case. $\endgroup$
    – Sus20200
    Sep 2, 2018 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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