# Generating function of the stopped simple random walk

Let $$\varepsilon_i$$ be independent random variables such that $$\mathbb{P}(\varepsilon_i = \pm 1)= 1/2$$ and denote $$W_n = \sum_{i=1}^{n}\varepsilon_i$$. That is, $$W_n$$ is the simple random walk on $$\mathbb{Z}$$ started at $$0$$. Denote by $$\tau_k$$ the hitting time of $$k\in \mathbb{N}$$ (the smallest time $$t$$ when $$W_t=x$$). I am interested in the simple random walk that is stopped if it hits $$k$$. So let us define $$S_n = \sum_{i=1}^{\min(\tau_k, n)}\varepsilon_{i}.$$

Question. Does the generating function $$f_h(t)=\mathbb{E}e^{hS_n}$$ have a simple analytical expression and maybe it is known?

Take any positive integers $$n$$ and $$k$$. Then
$$\begin{equation*} Ee^{hS_n}=E\exp\{hW_{\min(n,\tau_k)}\}=s_1+s_2, \tag{1}\label{1} \end{equation*}$$ where $$\begin{equation*} s_1:=Ee^{hS_n}1(\tau_k\le n)=e^{hk}P(\tau_k\le n), \tag{2}\label{2} \end{equation*}$$ $$\begin{equation*} s_2:=Ee^{hW_n}1(\tau_k>n) =\sum_{j=-n}^{k-1}e^{hj}P(\tau_k>n,W_n=j). \tag{3}\label{3} \end{equation*}$$

By the reflection principle, for each integer $$j\le k$$ $$\begin{equation*} P(\tau_k\le n,W_n=j)=P(W_n=2k-j) \tag{4}\label{4} \end{equation*}$$ (see details on this below), so that $$\begin{equation*} P(\tau_k>n,W_n=j)=P(W_n=j)-P(W_n=2k-j) \tag{5}\label{5} \end{equation*}$$ and \begin{equation*} \begin{aligned} P(\tau_k\le n)&=P(\tau_k\le n,W_n\le k)+P(\tau_k\le n,W_n>k) \\ &=\sum_{j\le k}P(\tau_k\le n,W_n=j)+P(W_n>k) \\ &=\sum_{j\le k}P(W_n=2k-j)+P(W_n>k) \\ &=P(W_n\ge k)+P(W_n>k). \end{aligned} \tag{6}\label{6} \end{equation*}

By \eqref{1}, \eqref{2}, the definition of $$s_2$$ in \eqref{3}, \eqref{6}, the latter equality in \eqref{3}, and \eqref{5}, \begin{equation*} \begin{aligned} Ee^{hS_n}&=e^{hk}P(\tau_k\le n)+Ee^{hW_n}1(\tau_k>n) \\ &=e^{hk}(P(W_n\ge k)+P(W_n>k)) \\ &+\sum_{j=-n}^{k-1}e^{hj}(P(W_n=j)-P(W_n=2k-j)). \end{aligned} \tag{7}\label{7} \end{equation*}

The latter expression can be re-expressed in terms of the c.d.f.'s of the binomial distributions with parameters $$n,\dfrac12$$ and with parameters $$n,\dfrac{e^{2h}}{e^{2h}+1}$$ (see details below), and hence in terms of the incomplete beta function (see e.g. this comment).

Details on \eqref{4}: For each integer $$j\le k$$ \begin{equation*} \begin{aligned} &P(\tau_k\le n,W_n=j) \\ &=\sum_{t=1}^n P(\tau_k=t,W_n=j) \\ &=\sum_{t=1}^n P(W_1 since $$2k-j\ge k$$. $$\quad\Box$$

Details on re-expressing the latter expression in \eqref{7} in terms of the c.d.f.'s of the binomial distributions with parameters $$n,\dfrac12$$ and with parameters $$n,\dfrac{e^{2h}}{e^{2h}+1}$$: Note that $$W_n=2B_n-n$$, where $$B_n$$ a random variable with the binomial distribution with parameters $$n,1/2$$. Let $$F_{n,p}$$ denote the c.d.f. of the binomial distribution with parameters $$n,p$$. Then $$\begin{equation*} P(W_n\ge k)=P(W_n>k-1)=P(B_n>(n+k-1)/2)=1-F_{n,1/2}((n+k-1)/2) \end{equation*}$$ and hence/similarly $$\begin{equation*} P(W_n>k)=1-F_{n,1/2}((n+k)/2). \end{equation*}$$ Also, for $$p_h:=\dfrac{e^{2h}}{e^{2h}+1}$$ and any real $$a$$ and $$b$$ such that $$a\le b$$, \begin{equation*} \begin{aligned} &\sum_{a\le j So, \begin{equation*} \begin{aligned} \sum_{j=-n}^{k-1}e^{hj}P(W_n=j) =\cosh^n h\,\big(1-F_{n,p_h}((n-k)/2)\big) \end{aligned} \end{equation*} and \begin{equation*} \begin{aligned} &\sum_{j=-n}^{k-1}e^{hj}P(W_n=2k-j) \\ &=\sum_{i=k+1}^{2k+n}e^{h(2k-i)}P(W_n=i) \\ &=\sum_{i=k+1}^n e^{h(2k-i)}P(W_n=i) \\ &=\sum_{i=k+1}^n e^{h(2k-i)}P(W_n=-i) \\ &=e^{2kh}\sum_{j=-n}^{-k-1} e^{hj}P(W_n=j) \\ &=e^{2kh}\cosh^n h\,\big(1-F_{n,p_h}((n+k)/2)\big). \end{aligned} \end{equation*} So, in view of \eqref{7}, indeed we can express $$Ee^{hS_n}$$ in terms of the c.d.f.'s of the binomial distributions with parameters $$n,\dfrac12$$ and with parameters $$n,p_h=\dfrac{e^{2h}}{e^{2h}+1}$$. $$\quad\Box$$

• Thank you a lot for your detailed answer! Oct 29, 2023 at 19:26