context: Imagine we have an evolving bit sequence (ex: 001011...) where the probability to get 0 or 1 is 1/2. n is the lengh of my sequence (the number of bits)

I can make an analogy with random walk: let suppose that 0 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 1 in my sequence is greater than f(n)=n/2+sqrt(n) (if it's easier we can suppose an other generic function f(n))

My question is: What is the probability to stop for a given n (so it mean to violate my boundary for a certain n) knowing that I should not already stop before ? I cannot take any walk who arrived at a point because I must be sure, that i didn't already stop before. This is where I'm stuck.

I did: P(n & non-n)=(1-sum(P(j))*P(n | non-n)

Here it is the probability to stop at n AND do not stop before n: P(n & non-n) (1-sum(P(j)): here the sum go from j=1 to n-1. So it's the probability to DO NOT stop before n P(n | non-n): is the probability to stop at n knowing that I dind't stop before n. It's exactly this one that i would know.

Thank you for any helps, Jonathan

  • $\begingroup$ What kind of answer do you want to your question "What is the probability ..."? An obvious answer is tautological: This probability is what it is. Another obvious expression for this probability is given by an $n$-fold sum. $\endgroup$ Feb 26, 2021 at 18:42
  • $\begingroup$ I don't understand your comment. I think the question is clear: I would compute the probability to cross my boundary at a given n (ie to stop), but taking in account that before 'n', I had to do not cross my boundary already. $\endgroup$
    – Jonathan
    Mar 1, 2021 at 12:51
  • $\begingroup$ What do you mean by "compute the probability"? As I said, this probability can be obviously expressed as an $n$-fold sum, over the index set $\{0,1\}^n$. Specifically what (other) kind of expression do you want for this probability? $\endgroup$ Mar 1, 2021 at 16:46
  • $\begingroup$ I want an analytical form of the probability to be at a certain point (here above my boundary f(n) ). An expression giving to me the probability to be at a certain point for a given n. Here the key is, that I must take in account that before i shouldn't cross my boundary already (so i cannot take all path in count). According to this, I dont think I can use your method. If you know the answer please can you write it and explain. $\endgroup$
    – Jonathan
    Mar 8, 2021 at 9:40
  • 1
    $\begingroup$ The answer would depend on what you mean, exactly, by "an analytical form". The problem is that you keep using expressions such as "compute the probability" and "an analytical form" whose meaning is unclear. $\endgroup$ Mar 8, 2021 at 16:13

1 Answer 1


Let $S_n:=X_1+\dots+X_n$ (with $S_0:=0$), where $X_1,X_2,\dots$ are iid Bernoulli random variables with parameter $1/2$. Let then \begin{equation*} T:=\inf\{n\ge0\colon S_n>f(n)\}. \end{equation*} You are interested in $P(T=n)$.

We have \begin{align*} P(T=n)&=P(S_0\le f(0),\dots,S_{n-1}\le f(n-1),S_n>f(n)) \\ &=\frac1{2^n}\,\sum_{x_1=0}^1\dots\sum_{x_n=0}^1 I_n(x_1,\dots,x_n), \tag{$*$} \end{align*} where \begin{equation*} I_n(x_1,\dots,x_n):= 1(s_0\le f(0),\dots,s_{n-1}\le f(n-1),s_n>f(n)) \end{equation*} and $s_k:=x_1+\dots+x_k$ (with $s_0:=0$).

The $n$-fold sum in ($*$) provides an analytic expression for $P(T=n)$. However, this expression is rather complicated, and the calculation based on ($*$) requires an exponential in $n$ number of arithmetic operations.

It is much more effective to compute $P(T=n)$ recursively. First here, note that for natural $n$ \begin{equation*} P(T=n)=P_{n-1}-P_n,\tag{0} \end{equation*} where \begin{equation*} P_n:=P(T>n)=P(T\ge n+1). \end{equation*} In turn, \begin{equation*} P_n=\sum_{x=0}^{g(n)}p_{n,x},\tag{1} \end{equation*} where \begin{equation*} g(n):=\min(n,f(n)) \end{equation*} and \begin{equation*} p_{n,x}:=P(T>n,S_n=x). \end{equation*} For $n=1,2,\dots$ \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)) \\ &=P(T>n-1,S_{n-1}=x,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,X_n=0)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)P(X_n=0)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}+p_{n-1,x-1}}2\,1(x\le f(n)). \end{align*} Thus, we have a recursive difference scheme to determine $p_{n,x}$: for all $x=0,1,\dots$, \begin{equation*} p_{0,x}=1(x\le f(0),x=0) \end{equation*} and, for all $n=1,2,\dots$, \begin{align*} p_{n,x}=\frac{p_{n-1,x}+p_{n-1,x-1}}2\,1(x\le f(n)). \end{align*} So, to compute all nonzero values of $p_{n,x}$ for all $x=0,1,\dots$ by this scheme, we only need $O(\sum_{k=0}^n g(n))=O(n^2)$ arithmetic operations. Having computed the values of $p_{n,x}$, we use (0) and (1) to quickly finish the calculation of the probability of interest, $P_T(n):=P(T=n)$. This way, Mathematica computes $P_T(1),\dots,P_T(100)$ (for $f(n)\equiv n/2+\sqrt n$) in about 0.11 sec, and then $P_T(1),\dots,P_T(200)$ in about 0.37 sec:

enter image description here

In contrast, using formula ($*$), Mathematica takes about 0.56 sec to compute just $P_T(1),\dots,P_T(10)$ (for the same $f$) and about 3.2 sec to compute $P_T(1),\dots,P_T(12)$.

  • $\begingroup$ Thank you very much for your complete answer. I think I got it; I will try to do it again on my side. $\endgroup$
    – Jonathan
    Mar 15, 2021 at 19:43
  • $\begingroup$ Hello @Iosif Pinelis I made your alogrithm which work very nice. Then I was wondering, what happen if my random walk is bounded from both positive part and negative part. (an envelop where x must respect: -f(n)<x<f(n), so it mean now that S_(n-1)=x+1 or x-1). I implement this condition in your p_(n,x) expression and extend the sum in (1). But i found some negatif probabilities... An other point, I had the idea to show that the final probability (the sum of PT[n]) should be finite. I tried a convergence criterion but it seems not trivial. Do you have any ideas ? Thanks $\endgroup$
    – Jonathan
    Apr 6, 2021 at 8:45
  • $\begingroup$ @Jonathan : It is unclear from your comment what your walk now is or what your algorithm is. Anyhow, it is better to post additional questions in separate posts. $\endgroup$ Apr 6, 2021 at 13:20

Your Answer

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

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