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 some help, I tried to do: 


Let $S_n:=X_1+⋯+X_n$ (with $S_0:=0$), where $X_1,X_2$,… are iid Bernoulli random variables with parameter 1/2. 
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][1]


  [1]: https://i.sstatic.net/Pvqsl.png

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