Probability to cross an envelopp for 1D random walk?

Question

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.

Answer 1

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.

Here is the corrected Mathematica code, with correct results: