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).


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


1 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:

enter image description here

  • $\begingroup$ I'm still "beginner" en mathematica; now I correct and it work ! Thank you again @Iosif Pinelis. $\endgroup$
    – Jonathan
    Commented Apr 7, 2021 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.