# Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in $\lbrace -1, \frac{1-p}{p} \rbrace$ and $P(X_k=-1)=1-p$ (so that $X_k$ has mean $0$). Let $S_n=X_1+X_2+ \ldots +X_n$ for $n\geq 1$ and let $N$ denote the smallest integer such that $S_{N} > 0$ (it is well known that $N$ exists almost surely). What is the expectation of $S_{N}$ ?

If $p$ is of the form $1-\frac{1}{k}$ where $k$ is an integer, it is easily seen that $S_{N}$ is constant and equal to $\frac{1}{k-1}$.

Update 10/26/2010: In general, $S_N$ can only take a finite number of values, so the expectation is finite, as noted in the comments below. It seems that the distribution of $S_N$ should be computable using some simple algebra, but I was unable to do this. The finite-set of values property allows one however to compute $E(S_N)$ to a reasonable acurracy for a given $p$. For $p=\frac{1}{3}$, the expectation is larger than 1 and does not seem to be rational.

-
There is an obvious typo: if $p$ is of the form $1−1/k$ where $k$ is an integer, then $S_N$ is equal to $1/(k−1)$ – Shai Covo Oct 26 '10 at 15:05
JBL: In the case $p = 1/3$, $X_k$ is $-1$ with probability $2/3$ and $2$ with probability $1/3$. So $S_n$ is positive-integer-valued for all $n$. In particular $S_N$ only takes the values $1$ or $2$, and therefore has expectation at least $1$. – Michael Lugo Oct 26 '10 at 16:37
@ Shai : corrected the typo, thanks. – Ewan Delanoy Oct 27 '10 at 8:23
@JBL : For $p=\frac{1}{3}$ I can show that the expectancy is greater than 1. – Ewan Delanoy Oct 27 '10 at 8:24
OK. I meant that $S_n$ is integer-valued for all $n$, and so $S_N$ always takes positive integer values. – Michael Lugo Oct 27 '10 at 17:04

You are looking for the "mean ladder height" of a random walk. There is a (not very tractable) formula due to Spitzer that gives the answer:

$$E(S_N)={\sigma\over\sqrt{2}} \exp\left$$\sum_{n=1}^\infty {1\over n}(P(S_n<0)-1/2)\right$$$$

Here $\sigma^2$ is the variance of the jump distribution. Maybe it would be possible to work this out in your special case.

[1] Chow, Yuan S. On Spitzer's formula for the moment of ladder variables. Statist. Sinica 7 no. 1, 1997, 149–156.

[2] Spitzer, Frank A Tauberian theorem and its probability interpretation. Trans. Amer. Math. Soc. 94, 1960, 150–169.

-
The $1/n$ term should be moved inside the sum. – Shai Covo Oct 27 '10 at 18:49
Quite right! Thanks. – Byron Schmuland Oct 27 '10 at 19:11
Note, however, that the above formula for $E(S_N)$ corresponds to $N=\inf\{n \geq 1: S_n \geq 0\}$, whereas in our case $N=\inf\{n \geq 1: S_n > 0\}$. – Shai Covo Oct 27 '10 at 19:59
Thanks, I hadn't noticed that. – Byron Schmuland Oct 27 '10 at 20:02

(EDITED, to comply with quite accurate objections by Louigi and Byron)

Assume that with full probability $X_k$ is either $-1$ or a random positive integer (this includes the setting of the question when $p=1/(k+1)$ with $k$ a positive integer but note that $X_k$ may take more than one positive integer values). Then, Wiener-Hopf factorization formula becomes simple enough to compute the distribution of $S_N$.

More precisely, let $N$ denote the first time $n\ge1$ such that $S_n>0$ (as in the OP's post) and let $M$ denote the first time $n\ge1$ such that $S_n\le 0$ (note the "lower than or equal to"). In the centered and bounded case the OP is interested in, $N$ and $M$ are both almost surely finite and Wiener-Hopf formula reads $$(1-E(e^{iuS_N}))(1-E(e^{iuS_M}))=1-E(e^{iuX}),$$ for every real number $u$ and every $X$ distributed as the steps $X_k$. Here, $S_M=-1$ on $[X_1=-1]$ and $S_M=0$ on $[X_1>0]$. This yields $$q(1-e^{-iu})E(e^{iuS_N})=E(e^{iuX};X>0)-p,$$ with $q=P[X=-1]$ and $p=1-q=P[X>0]$. This provides the full distribution of $S_N$ and, differentiating both sides at $u=0$, the expectation of $S_N$. The end result is $$E(S_N)=E(X+X^2;X>0)/(2q).$$ If $X=-1$ or $X=k$ with $k$ a positive integer, then $[X > 0]=[X=k]$ and $p=1/(k+1)$, and one sees that $S_N$ is uniformly distributed on the integers from $1$ to $k$ and that $E(S_N)=(k+1)/2$.

-
This would be right except that it is not necessarily true that $S_M=0$ on the event $X_1 > 0$. If $p=2/3$, for example, then $X$ takes values $-1$ and $1/2$, So $S_M$ can take the value $-1/2$. – Louigi Addario-Berry Oct 29 '10 at 15:50
@Didier: Why does $S_M=0$ on $X_1>0$? When $p=1/3$, you could jump once to the right, then once left, and find yourself at -1/2. This is the first time that the process is $\leq 0$. However, I'm still hopeful that the Wiener-Hopf approach may lead to a solution! – Byron Schmuland Oct 29 '10 at 15:54
@Louigi: You beat me! – Byron Schmuland Oct 29 '10 at 15:54
@Louigi, Byron: Argh... You are right, of course; the argument works only if the upward steps are integer valued. Sorry, I shall modify the answer. – Did Oct 29 '10 at 16:38