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?


1 Answer 1


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<k,\dots,W_{t-1}<k,W_t=k,W_n=j) \\ &=\sum_{t=1}^n P(W_1<k,\dots,W_{t-1}<k,W_t=k,W_n-W_t=j-k) \\ &=\sum_{t=1}^n P(W_1<k,\dots,W_{t-1}<k,W_t=k)P(W_n-W_t=j-k) \\ &=\sum_{t=1}^n P(W_1<k,\dots,W_{t-1}<k,W_t=k)P(W_n-W_t=k-j) \\ &=\sum_{t=1}^n P(W_1<k,\dots,W_{t-1}<k,W_t=k,W_n-W_t=k-j) \\ &=\sum_{t=1}^n P(W_1<k,\dots,W_{t-1}<k,W_t=k,W_n=2k-j) \\ &=\sum_{t=1}^n P(\tau_k=t,W_n=2k-j) \\ &=P(\tau_k\le n,W_n=2k-j) \\ &=P(W_n=2k-j), \end{aligned} \end{equation*} 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<b}e^{hj}P(W_n=j) \\ &=\sum_{(n-b)/2<i\le(n-a)/2}e^{h(2i-n)}P(B_n=i) \\ &=\sum_{(n-b)/2<i\le(n-a)/2}e^{h(2i-n)}\binom ni 2^{-n} \\ &=\cosh^n h\,\sum_{(n-b)/2<i\le(n-a)/2}\binom ni p_h^i(1-p_h)^{n-i} \\ &=\cosh^n h\,\big(F_{n,p_h}((n-a)/2)-F_{n,p_h}((n-b)/2)\big). \end{aligned} \end{equation*} 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$

  • $\begingroup$ Thank you a lot for your detailed answer! $\endgroup$
    – Ddzin
    Oct 29, 2023 at 19:26

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.