# Probability to cross an envelopp for 1D random walk?

Imagine we have an evolving sequence composed of 1 and -1 (ex: -1-11-111...) where the probability to get -1 or 1 is 1/2. n is the lengh of my sequence.

I can make an analogy with random walk: let suppose that -1 mean "go down" and 1 mean "go up", I can plot a random walk where x-axis is "n" (like a time).

Condition: My sequence can stop (do not evolve anymore) if the sum of my sequence is greater than $$f(n)=\frac{n}{2}+n^\frac{1}{k}$$ or smaller than $$-f(n)=-\frac{n}{2}-n^\frac{1}{k}$$ where $$k\in N$$ (it means that my walk must be evolve inside my boundaries, f(n) and -f(n))

Thanks to this answer, I tried to do:

Let $$S_n:=X_1+⋯+X_n$$ (with $$S_0:=0$$), where $$X_1,X_2$$,… are iid Rademacher random variables. Let then define $$T:=\inf[n≥0:S_n>f(n) | S_n<-f(n)]$$

I want to compute the probability to cross my boundary for a given (either from above above or from below):

$$P(T=n)=P_{n−1}−P_n$$ where $$P_n:=P(T>n)=P(T≥n+1)$$ (ie the probability to stop after n)

then we can "count" all the differents possibilities of my random walk for a given n.

$$\begin{equation*} P_n=\sum_{x=max(-n,-(f(n))}^{min(n,f(n))}p_{n,x},\tag{1} \end{equation*}$$

where $$\begin{equation*} p_{n,x}:=P(T>n,S_n=x). \end{equation*}$$ (ie the probability to stop after n and being at $$S_n=x$$)

\begin{align*} p_{n,x}&=\sum_{y=0}^\infty P(T>n-1,S_{n-1}=y,S_n=x)1(|x|\le f(n))1(|y|\le f(n-1)) \\ &=P(T>n-1,S_{n-1}=x+1,S_n=x)1(|x|\le f(n)) \\ &+P(T>n-1,S_{n-1}=x-1,S_n=x)1(|x|\le f(n)) \\ &=P(T>n-1,S_{n-1}=x+1,X_n=-1)1(|x|\le f(n)) \\ &+P(T>n-1,S_{n-1}=x-1,X_n=1)1(|x|\le f(n)) \\ &=P(T>n-1,S_{n-1}=x+1)P(X_n=-1)1(|x|\le f(n)) \\ &+P(T>n-1,S_{n-1}=x-1)P(X_n=1)1(|x|\le f(n)) \\ &=\frac{p_{n-1,x+1}+p_{n-1,x-1}}2\,1(|x|\le f(n)). \end{align*}

and $$\begin{equation*} p_{0,x}=1(|x|\le f(0),x=0) \end{equation*}$$

So for all n=1,2,...

\begin{align*} p_{n,x}=\frac{p_{n-1,x+1}+p_{n-1,x-1}}2\,1(|x|\le f(n)). \end{align*}

Then injecting this in (1) and plug it in $$P(T=n)$$ we have our probability.

If tried to compute this recursive process on mathematica. So for an envelopp $$f(n)=\frac{n}{2}+n^\frac{1}{2}$$ and $$-f(n)$$, but it give me 1 with some negative probabilities... which is obviously wrong (Cf. image).

Mathematica_randomwalk_image

If someone has any ideas where could be the mistake, I would be very thankfull.

This is a problem, not with the mathematics, but with Mathematica. The values of $$x$$ over which Mathematica sums the values of $$p_{n,x}$$ in the sum $$\begin{equation*} \sum_{x=\max(-n,-f(n))}^{\min(n,f(n))}p_{n,x},\tag{1} \end{equation*}$$ are of the form $$x_n,x_n+1,\dots$$, where $$x_n:=\max(-n,-f(n))$$. So, when $$x_n$$ is not an integer, Mathematica gets the value $$0$$ for this sum. 