Stopping Probabilities for Random Walk with Drift

Question

[EDIT] After the comments and answer I understood that my formation of the problem is incorrect. However I'm still interested in a stochastic solution to the original riddle. Please skip to the "Background" part of this question. And thanks for setting a bounty on this question!!

Let $X_1,X_2,...$ be independent and identically distributed random variable. $X_i = 2$ or $X_i=-1$ each with 50% probability. And let $S_n = X_1+\cdots+ X_n$ be the associated random walk. So we can think of this as a random walk with drift $\mu = 0.5$ and step-length = $1.5$

For a given constant $m$, suppose we define a stopping rule to stop when $S_n \leq -m$ or $S_n \geq K$. How do we find $K$, such that the probability of stopping at $S_n \geq K$ is equal to the probability of stopping at $S_n \leq -m$?

When there is no drift the solution is trivial $K = m$. I suspect this little modification should be a classical problem in stochastic process too?

The solution is apparently $K \sim O(m^2)$, but I'm looking for a stochastic explanation. see the background below.

Background: I found this riddle and its solution. I reproduce the riddle here:

At a pivotal moment in an epic battle between the living and the dead, the Night King, head of the army of the dead, raises all the fallen (formerly) living soldiers to join his ranks. This ability obviously presents a huge military advantage, but how big an advantage exactly?

Forget the Battle of Winterfell and model our battle as follows. Each army lines up single file, facing the other army. One soldier steps forward from each line and the pair duels — half the time the living soldier wins, half the time the dead soldier wins. If the living soldier wins, he goes to the back of his army’s line, and the dead soldier is out (the living army uses dragonglass weapons, so the dead soldier is dead forever this time). If the dead soldier wins, he goes to the back of their army’s line, but this time the (formerly) living soldier joins him there. (Reanimation is instantaneous for this Night King.) The battle continues until one army is entirely eliminated.

What starting sizes of the armies, living and dead, give each army a 50-50 chance of winning?

So we can think of this riddle as above problem. Let $m$ be the size of dead army. Let $S_i$ be (current difference in army sizes - initial difference of army sizes). For each step $S_i$ increments by either −1 or 2. If $S_n=−m$, that means comparing to the initial state, the dead army is down by $−m$, the battle ended. If $S_n=K$, that means comparing to the initial state, the dead army is up by $K$, the battle ended. The solution is apparently $K \sim O(m^2)$. The combinatorial argument is nice, but the paper offers no stochastic explanation, which I am truly curious about.

I am fine with an approximation solution. So if we replace $X_i$ with a normal random variable with non-zero mean is fine to me too, if that helps with the estimation. But I think for a large enough $n$ this probably doesn't matter anyways.

Answer 1

If you take $K=+\infty$ and $m=some\ large\ number$, then it is more likely to go right ad infinum then to finally hit $-m$. From the central limit theorem one can deduce that on step $n$ with high probability we will be somewhere within the range $\mu n \pm c\sqrt n$, where $c$ is a constant depending on our desired confidence with which we want to make such a statement (and it also includes that $1.5$ coefficient). And $\mu n$ asymptotically grows faster than $c\sqrt n$ independently of the value of $c$, so from some point $n$ this range is never hitting negative zone.

Therefore, for large enough $m$ there is simply no such $K$. And for small $m$ I suspect you can't really find this in any better way than with Monte-Carlo simulation.

Answer 2

The probability of hitting $-m$ before surpassing $K$ converges to the probability of ever hitting $-m$, as $K$ increases to $+\infty$. If the latter probability is $>1/2$, then the probability of being at $-m$ at the stopping time can be made equal to $1/2$ by choosing $K>0$ sufficiently large. Whether the probability of ever hitting $-m$ is $>1/2$ depends on $m$ because of the right-ward drift.

One could get some sense of the magnitudes involved by considering the analogous problem for a Brownian motion with drift $\mu=0.5$ and diffusion coefficient $\sigma = 1.5$ (for which there are known (and googlable) formulas for the hitting probabilities). In this instance the probability of ever hitting $-m$ is $\exp(-4m/9)$ so $m<(9/4)\log 2$ is needed for the choice of $K$ to be possible, and then $K= -(9/4)\log(2-\exp(4m/9))>0$.

Answer 3

This is too long for a comment, but the problem you formulated is not equivalent to the problem in the background material. The interpretation is supposed to be that $X_i=+2$ means that a dead soldier won a duel, and $X_i=-1$ means a living soldier won. You then say that $S_n=K$ means that the dead army has won. However, if the dead army initially wins $K/2$ battles in a row, then you will have $S_{n}=2(K/2)=K$, but the dead army would not have won yet.

Here is a correct formulation. Suppose there are initially $K$ living soldiers and $m$ dead ones. Let $Y_1,Y_2,\dots$ be i.i.d. and equal to $-1$ or ${\bf +1}$ with equal probability; the event $Y_i=+1$ represents a dead soldier winning a duel, and $Y_i=-1$ means a living soldier won (note the random walk is now symmetric).

Let $T_n=Y_1+\dots+Y_n$. Notice that $(n+T_n)/2$ is the number of dead soldier wins, and $(n-T_n)/2)$ is the number of living soldier wins. Now, we see that:

• When $(n+T_n)/2=K$, then the dead soldiers have won $K$ duels, so they won the battle. That is, the winning condition for the dead soldiers is $T_n= 2K-n$. Whereas you had the "target value" as a constant $K$, the target value should change over time.

• When $T_n=-m$, then the living soldiers have reduced the dead army by $m$, so the living soldiers have won (This part is the same as your setup).

Now, I do not think there is a good "stochastic" reason why $K\sim m^2$ produces a fair fight. I do know a good reason, but it has to do with carefully analyzing the walks in the 2D plane defined by the above random process, and using the reflection principle cleverly. Unfortunately, the same reflection principle argument does not work if you approximate the discrete walk by a Brownian motion, so the argument cannot be "stochastic" alone, it needs tricky combinatorics.