5
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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)$ $\endgroup$
    – Shai Covo
    Oct 26, 2010 at 15:05
  • $\begingroup$ 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$. $\endgroup$ Oct 26, 2010 at 16:37
  • $\begingroup$ @ Shai : corrected the typo, thanks. $\endgroup$ Oct 27, 2010 at 8:23
  • $\begingroup$ @JBL : For $p=\frac{1}{3}$ I can show that the expectancy is greater than 1. $\endgroup$ Oct 27, 2010 at 8:24
  • $\begingroup$ OK. I meant that $S_n$ is integer-valued for all $n$, and so $S_N$ always takes positive integer values. $\endgroup$ Oct 27, 2010 at 17:04

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The $1/n$ term should be moved inside the sum. $\endgroup$
    – Shai Covo
    Oct 27, 2010 at 18:49
  • $\begingroup$ 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\}$. $\endgroup$
    – Shai Covo
    Oct 27, 2010 at 19:59
2
$\begingroup$

(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$.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Oct 29, 2010 at 15:50
  • $\begingroup$ @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! $\endgroup$
    – user6096
    Oct 29, 2010 at 15:54
  • $\begingroup$ @Louigi: You beat me! $\endgroup$
    – user6096
    Oct 29, 2010 at 15:54
  • $\begingroup$ @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. $\endgroup$
    – Did
    Oct 29, 2010 at 16:38

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.