# The number of distinct values taken by a sequence of partial sums of iid

I'm working on an old exam problem as follows:

Let $\{X_n\}_{n\in\mathbb{N}}$ be a sequence of i.i.d taking values in $\mathbb{Z}$. Define $S_0 :=0$ and $S_n:=X_1+X_2+...+X_n,$ and $\theta_n$ to be the number of distinct values taken by the sequence $S_0, S_1,...,S_n.$ Then for all $n\geq1$, $$P(\theta_n=\theta_{n-1}+1)=P(S_1\neq 0,S_2\neq 0,...,S_n\neq 0)$$ and $$lim_{n\rightarrow \infty}\frac{E(\theta_n)}{n}=P(S_k \neq0,k\geq1).$$

I'm confused since it seems like $\{\theta_n=\theta_{n-1}+1\}\neq\{S_1\neq 0,S_2\neq 0,...,S_n\neq 0\}$. Left hand side happens when $S_n$ arrives in a new location, which could still happens even when some $S_i=0.$ If my observation is true, how to see these two different events have the same probability? And how the achieve the second result by the first one? It looks like law of large numbers but it's not a expectation on the right hand side. Thanks for any help.

• Something is wrong here. For example if the variables take only the values 0,1 then the first probability is certainly not equal to what you've written, it's just the probability that $X_n$ is not zero. – Matt Samuel Jul 4 '15 at 22:23
• I assume the second has a $\forall$ as in is $\displaystyle \lim_{n\rightarrow \infty}\frac{E(\theta_n)}{n}= P(S_k \neq0, \forall k\geq1)$. It should certainly be possible to argue from the first expression that $P(S_k \neq0, \forall k\geq1)$ is a lower bound, and you might be able to go on and say the division by $n$ drives any difference to $0$ in the limit. – Henry Jul 5 '15 at 0:06
• @MattSamuel If the $X_i$ are only $0$ or $1$ then $S_i$ is non-negative and weakly increasing so $P(S_1\not =0 , S_2\not =0 , ... , S_n\not =0) =P(S_1\not =0)=P(X_1\not =0)$ which because $X_i$ is i.i.d. is equal to $P(X_n\not =0) = P(\theta_n=\theta_{n-1}+1)$. – Henry Jul 5 '15 at 7:34

$\theta_n=\theta_{n-1}+1$ when $S_n\not =S_{n-1}$ and $S_n\not =S_{n-2}$ and ... and $S_n\not =S_{1}$ and $S_n\not =S_{0}$,
so if $T_i=S_n-S_{n-i}$ then $\theta_n=\theta_{n-1}+1$ when $T_1\not =0$ and $T_2\not =0$ and ... and $T_{n-1}\not =0$ and $T_n\not =0$,
but the $T_i$ are just the partial sums of $X_n, X_{n-1}, X_{n-2}, \ldots$, which (because the $X_i$ are i.i.d.) have the same joint distribution as the $S_i$ which are the paritial sums of $X_1, X_{2}, X_{3}, \ldots$,
so $P(\theta_n=\theta_{n-1}+1)= P(T_1\not =0 , T_2\not =0 , ... , T_n\not =0) = P(S_1\not =0 , S_2\not =0 , ... , S_n\not =0)$.