# Expectation of a random sum

Let $X_1, X_2, X_3,\dots$ be an i.i.d. sequence of random variables with finite mean. Write $S_n=X_1+X_2+\dots+X_n$.

Let $N$ be a non-negative integer-valued random variable with finite mean. $N$ may not be independent of the sequence $(X_i)$.

Is it necessarily the case that $S_N$ has finite mean?

Of course, it's true if $N$ is independent of the sequence $(X_i)$. Then $E(S_N)=E(N)E(X_1)$. It's still true if $N$ is a stopping time for the sequence $(X_i)$.

It's also true if the $X_i$ have finite variance. Then for any $c>E(X_i)$, the quantity $R_c=\sup(S_n-cn)$ has finite mean, and $E(S_N)\leq cE(N)+E(R_c)$.

-

Edit: I made it a bit clearer and simpler.

No. You start with noticing that there is no "linear" estimate for the mean of $S_N$ in terms of the mean of the sample $X$ under the assumption that the mean of $N$ is small. To this end just take $X$ be $0$ with probability $1-p$ and $A$ with probability $p$ so that $Ap$ is small. Now, once we have a sequence $X_i$ of independent copies of $X$, define $N$ to be $m$ if at least one of $X_1,\dots,X_m$ is not $0$ and $0$ otherwise. Then $ES_N= Apm$ and $EN\le m^2p$ and $EX=Ap$.

Now choose $A_j,p_j,m_j$ so that $\sum A_jp_j<+\infty$, $\sum A_jp_jm_j=+\infty$, $\sum m_j^2p_j<+\infty$. For instance, take $m_j=2^j$, $p_j=2^{-3j}$, $A_j=2^{2j}$.

Define the random samples $X^{(j)}$ and random interval lengths $N^{(j)}$ as above using $A_j,p_j,m_j$ in place of $A,p,m$. Put $X=\sum_j X^{(j)}$, $N=\sum_j N^{(j)}$. Then $EX$ and $EN$ are finite. Let $X_i$ be independent copies of $X$. We have $E\sum_1^N X_i\ge E\sum_j \sum_1^{N^{(j)}}X_i^{(j)}=\sum_j A_jp_jm_j=+\infty$.

-
I don't understand. Are your $X_i$ iid? If so, then what does the index $j$ refer to in the second-to-last sentence? –  Louigi Addario-Berry Feb 22 '11 at 19:50
I mean, you choose $X^{(j)}$ and $N^{(j)}$ the way I described (the $X^{(j)}$ are different samples, not the different copies of each sample) and then put $X=\sum_j X^{(j)}$ (that is just one sample which you use for making copies) and $N=\sum_j N^{(j)}$. –  fedja Feb 22 '11 at 20:04
Thanks fedja - nice argument. In fact, for any $\epsilon$ we can arrange it that $\sum A_j^{2-\epsilon} p_j<\infty$. I think this would give an example with a distribution $X$ satisfying $E X^{2-\epsilon}<\infty$. So it sounds like the finiteness of the variance (or something close to it) may actually be the relevant condition here. –  James Martin Feb 25 '11 at 10:13

Here's a counterexample.

Let $X$ be equal to $2^k k^{-2}$ with probability $2^{-k}$. The probability that among $n$ i.i.d. copies of $X$ we get at least one with value $2 ^ {2 \log n} (2 \log n)^{-2}= n^2 (2 \log n)^{-2}$ is about $n^{-1}$. Call this event $A_n$.

Thus, if we choose $N$ to be $2^{2k/3}$ with probability $2^{-k}$ such that the event $N=2^k$ is a subset of $A_{2^{2k/3}}$, we get that $S_N$ have infinite expectation. This should be quite easy to do since the events $A_n$ tend to be independent for far away $n$'s.

-

Assume $X_1$ has infinite variance and let $N$ denote the first time $n$ such that $S_n-cn=R_c$. By a result I do not manage to find a reference for but that you surely know, $R_c$ is not integrable hence $S_N$ is not either. To get an answer to your question, it would remain to prove that $N$ is integrable.

The probability that $N$ is not one of the $n$ first times of record should decrease geometrically hence if the time of a first record is integrable, conditionally on the fact that there is a positive record, we are done. I seem to remember that a random walk with a negative drift conditioned on hitting the positive halfline is a random walk based on different increments with a positive drift. One should be able to truncate them to get bounded increments still with a positive drift. Then the result becomes trivial. (Not sure this whole reasoning is watertight, though. If it is not, shoot.)

-
If $X_1$ has infinite variance we can arrange it so that $P(X_1 > n) \asymp 1/(n \log n (\log\log n)^2)$, say, and then the probability that one of $X_n,...,X_{2n}$ has value at least $2cn$, say, is of order $1/(\log n (\log\log n)^2)$. This doesn't quite shoot down the approach but it does show that $N$ need not decrease geometrically. –  Louigi Addario-Berry Feb 22 '11 at 19:16
@Louigi Surely this is me but how does this apply? –  Did Feb 22 '11 at 20:00
@Didier, do you mean how does my choice of distribution for $X_1$ apply to James' question? I'm not sure I understand your question. At any rate, I think you are probably right that N should be integrable in your construction, I was just trying to say that it can have a much heavier tail than geometric. –  Louigi Addario-Berry Feb 22 '11 at 20:53
@Louigi Call $q_n$ the probability that at least one $X_i$ for $i$ between $n$ and $2n$ is at least $2cn$. Call $p_n$ the probability that $N$ is not one of the first $n$ record times (of the random walk with steps distributed like $X_1-c$). I fail to see why a lower bound on $q_n$ implies a lower bound on $p_n$. (As an aside, note that $p_n$ thus defined is not the probability that $N\ge n+1$.) –  Did Feb 22 '11 at 21:20
@Didier, you're right, they're not related, I just wasn't reading what you wrote properly. Sorry! –  Louigi Addario-Berry Feb 22 '11 at 22:36