Find the expected value of the sum of numbers without knowing them

Question

There are 100 notes on the table and a real number is written on every note. It is known that the sum of all numbers written on all notes is $0$. On every step, we choose one note uniformly from all the notes.

Let $S_n$ be the sum of all numbers written on the first $n$ notes chosen.

Find the expected of value of $S_n$:

A. While returning every note chosen back to the table. $(n=1,2,\dots)$.

B. Without returning. $(n=1,2,\dots,100)$.

My attempt:

A. I think, since every note can be summed many times, that $\mathbb{E}(S_n)$ depends on the numbers written on the notes.

B. Since every note can be summed one time only, that $\mathbb{E}(S_n)$ is $0$.

Answer 1

Label the notes with $j=1,2,\dots,100$ and let $r_j$ denote the number written on note $j$.

For $i=1,2,\dots,100$ let $X_i$ denote the number written on the $i$-th chosen note.

Then $S_n=X_1+\cdots+ X_n$ so that by linearity of expecation we find that $\mathbb ES_n=\sum_{i=1}^n\mathbb EX_i$.

A)

The $X_i$ all have the same distribution, so that $\mathbb EX_i$ does not depend on $i$.

This leads to $\mathbb ES_n=n\mathbb EX_1$.

Further $\mathbb EX_1=\frac1{100}\sum_{j=1}^{100}r_j=0$, so we conclude that $\mathbb ES_n=0$.

B)

For $i,j=1,2,\dots,100$ let $B_{i,j}$ take value $1$ if by the $i$-th choice note $j$ is chosen and value $0$ otherwise.

Observe that the $B_{i,j}$ are equidistributive with $\mathbb EB_{i,j}=\mathbb EB_{1,1}=\frac1{100}$

Then $S_n=\sum_{i=1}^n\sum_{j=1}^{100}r_jB_{i,j}$ so that $\mathbb ES_n=\sum_{i=1}^n\sum_{j=1}^{100}r_j\mathbb EB_{i,j}=\frac{n}{100}\sum_{j=1}^{100}r_j=0$.

Answer 2

I believe $\ {\mathbb E}\left(S_n\right) = 0\ $ in both cases, regardless of what numbers are written on the notes. The key observations are:

• $\ S_n = \sum_{i=1}^n X_i\ $, where $\ X_i\ $ is the number on the $\ i^{\small\mathrm{th}}\ $ note chosen.
• $\ X_i\ $ is uniformly distributed over the numbers written on the notes, so $\ {\mathbb E}\left(X_i\right) = \frac{\sum_{j=0}^{100} \nu_j}{100}\ = 0\ $, where $\ \nu_j\ $ is the number written on the $\ j^{\small\mathrm{th}}\ $ note. The indexing of the numbers $\ \nu_j\ $ with the index $\ j\ $ here is just some convenient way of referring to the numbers on the notes, and isn't related in any way to the order in which the notes are chosen.
• $\ {\mathbb E}\left(S_n\right) = \sum_{i=1}^n {\mathbb E}\left(X_i\right)\ .$

In regard to the second of the above points, while it is true that in case B the random variables $\ X_i\ $ are no longer independent as they are in case A, this does not affect their unconditional distribution, which is what you need to use to calculate their (unconditional) expected values.