Closed form probability random walk will hit k >=1 times in n steps

Question

I'm using Mathematica to try to solve https://quant.stackexchange.com/questions/24970 and came across what seems like a simple question: if you take a standard random walk of n steps, what is the formula for the probability you'll touch +k at least once. More generically, what's the probability distribution of a random walk of n steps.

I can compute this chance using a recursive formula:

 
c[n_,0] := 1 
c[0, k_] := 0 
c[n_,k_] := c[n,k] = 1/2*(c[n-1,k-1] + c[n-1,k+1]) 

but Mathematica won't RSolve it:

 
RSolve[{f[n,0] == 1, f[0,k] == 0, f[n,k] == 1/2*(f[n-1,k-1]+f[n-1,k+1])}, 
 f[n,k], {n,k}] 

returns unevaluated. I'm not too surprised, since Mathematica isn't that good with two variable recursion.

However, I'm convinced there's a "simple" formula here, or at least a good approximation for large n.

I did try a few different things to no avail:

• Trying to find a formula for specific values of n or k.

• Using Log to see if this was an exponential distribution of some sort.

• Comparing it to the right half of the normal distribution.

• Trying to find a formula for the interpolation, since the function itself is somewhat "juddery" (ie, f(x+1) = f(x) in many cases).

I'm convinced I can use Pascal's triangle (ie, the binomial theorem and Mathematica's Binomial function) to resolve this, but can't quite figure out how.

Answer 1

This is basically a reformulated problem of a random walk with absorbing boundary. If you place an absorbing boundary at $k$, your probability is complementary to the probability of being absorbed after $n$ steps. This does not have a recursion relation by itself, you need to also study where the walker is after $n$ steps (in order to know whether there's a chance of hitting the boundary in the next) and take the marginal of that distribution. This converts a seemingly 2-variate problem into a 3-variate one, which is even worse, so let's try and help Mathematica a bit first.

It helps greatly to imagine the absorbing boundary as a source of "negative probabilities" which cancel out exactly with the probability the walker arrives there after any particular number of steps. If we then let these probabilities propagate just as normal, they evolve into the corresponding modifications of the probability distribution of the unperturbed walk.

Even more interestingly, all one needs to do is to start another walker with a formal probability of $-1$ at the mirror image of the original starting position, reflected along the absorbing boundary. One then can work with the full line without the need to change the behaviour at $x=k$ in any way. Indeed, the probabilities of getting to $k$ at any time $t$ from the left and from the right cancel out, which is exactly what we want according to the above paragraph.

The total probability, only summed in the "positive half-plane" $x < k$, is then the probability that the walker hasn't reached $x=k$ up to the corresponding time. This can be expressed rather easily, $$p_t = \sum_{x=-t}^{k} 2^{-t} {t \choose \frac{t+x}2} - \sum_{x=-t}^{k} 2^{-t} {t \choose \frac{t+x-2k}2}$$ The first sum is simply the normal probability of finding a walker at $x ≤ k$ at time t. The second is the probability of finding another walker at the same time in the same region if we shift the initial position to $2k$. This is to be subtracted for the effect of the absorbing boundary. Importantly, in both sums, only terms $x$ for which $t-x$ is even are taken, other (which would result in noninteger terms in the binomial coefficients) are ignored.

The next obvious operation to simplify this formula is to change the summation index in the second sum from $x$ to $2k-x$ (this does not change parity so does not affect which $x$'s are taken), resulting in $$p_t = \sum_{x=-t}^{k} 2^{-t} {t \choose \frac{t+x}2} - \sum_{x=k}^{2k+t} 2^{-t} {t \choose \frac{t-x}2}.$$ The second summand can be changed to match the first without effect. Moreover, the second summation bound can be trimmed down to $t$ as any further terms are zero: $$p_t = \sum_{x=-t}^{k} 2^{-t} {t \choose \frac{t+x}2} - \sum_{x=k}^{t} 2^{-t} {t \choose \frac{t+x}2}.$$

The behaviour splits depending on whether $x=k$ belongs to the sum or not. If it does not, the sums do not have any overlapping terms. If it does, they overlap in $k$. Let us focus on the former case as it is slightly easier.

Therefore, let $k$ and $t$ be of different parity. Define $d = \lfloor(k+t)/2\rfloor$. After one more change of summation indices the formula becomes $$p_t = 2^{-t} \left( \sum_{y=0}^{d} {t \choose y} - \sum_{y=d+1}^{t} {t \choose y} \right).$$ Note that this almost looks like a binomial formula but one where a slice of the terms is taken with a negative sign. The familiar theorem does not apply in such cases, so here's where Mathematica comes in handy. Let's try

Sum[Binomial[t, y], {y, 0, d}]

(* 2^t - Binomial[t, 1 + d] Hypergeometric2F1[1, 1 + d - t, 2 + d, -1] *)

Voilà. The second sum is obviously just the complement to $2^t$, so the difference reads $$p_t = 2^{-t} \left( 2^t - 2 {t\choose d+1} {}_2F_1(1, d-t+1; d+2; -1) \right)$$ and the desired probability of hitting $k$ at least once is $$1 - p_t = 2^{1-t} {t \choose d+1} {}_2F_1(1, d-t+1; d+2; -1)$$

This formula does not work when the difference of $t$ and $k$ is even, that is, in times $t$ when the walker can actually reach the position $k$. But, instead of calculating a new formula, one just needs to realize that the probability can't change from such a $t$ to the next step. So, we can take $$1 - p_t = \begin{cases} 2^{1-t} {t \choose d+1} {}_2F_1(1, d-t+1; d+2; -1)\\ \quad \mathrm{where}\ d = \lfloor(k+t)/2\rfloor \quad\hfill \mbox{if $t-k$ odd,} \quad\\ 2^{-t} {t+1 \choose d+1} {}_2F_1(1, d-t; d+2; -1)\\ \quad \mathrm{where}\ d = (k+t)/2 \quad\hfill \mbox{if $t-k$ even.} \quad \end{cases}$$

The Mathematica function would be

c[k_, n_] := If[OddQ[n - k],
    With[{d = Floor[(n + k)/2]},
        2^(1 - n) Binomial[n, d + 1] Hypergeometric2F1[1, 1 + d - n, 2 + d, -1]],
    With[{d = (n + k)/2},
        2^(-n) Binomial[n + 1, d + 1] Hypergeometric2F1[1, d - n, 2 + d, -1]]]

To conclude and confirm let's compare the values predicted by it:

Table[c[k, n], {k, 1, 3}, {n, 0, 6}] // Column

(* {0, 1/2, 1/2, 5/8, 5/8, 11/16, 11/16}
   {0, 0, 1/4, 1/4, 3/8, 3/8, 29/64}
   {0, 0, 0, 1/8, 1/8, 7/32, 7/32} *)

with counting the trajectories of length $n$ appearing at least once at $k$ directly:

Table[
    Count[Accumulate /@ Tuples[{-1, 1}, n], {___, k, ___}]*1/2^n,
    {k, 1, 3}, {n, 0, 6}] // Column

(* {0, 1/2, 1/2, 5/8, 5/8, 11/16, 11/16}
   {0, 0, 1/4, 1/4, 3/8, 3/8, 29/64}
   {0, 0, 0, 1/8, 1/8, 7/32, 7/32} *)

Edit: By the way, the hypergeometrics reduce to a finite summation in both cases and cancel out nicely with their respective prefactors, leaving $$1 - p_t = \begin{cases} 2^{1-t} \sum_{n=0}^{t-d-1} {t \choose d+n+1} & \mbox{if $t-k$ odd,} \quad\\ 2^{-t} \sum_{n=0}^{t-d} {t+1 \choose d+n+1} & \mbox{if $t-k$ even.} \quad \end{cases}$$ with $d = \lfloor(k+t)/2\rfloor$. At the moment I'm not sure why but I'm certain there will be a very simple explanation. But often expressions with $_2F_1$ count better as a "closed form".