1D random walk with variable probability

Question

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!

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.