Let $(X_n)_{n\in\mathbb{N}}$ be i.i.d. random variables taking values in the set of natural number $\mathbb{N}$. Assume that $\mathbb{P}(X_1=i)=p_i>0$ for $i\in\mathbb{N}$. Let $D_n$ denote the carinality of the set $\{X_1,X_2,...,X_n\}$. Prove $(i)$, $D_n\rightarrow\infty$ a.s.; $(ii)$, $D_n/n\rightarrow 0$ in probability. Can one strengthen $(ii)$ to a.s. convergence?

Answer on (i):

$\left\{ D_{n}\rightarrow\infty\right\} ^{c}=\bigcup_{k=1}^{\infty}\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} $ so that $P\left(\left\{ D_{n}\rightarrow\infty\right\} ^{c}\right)\leq\sum_{k=1}^{\infty}P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)$.

For a fixed $k$ we find $P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)\leq P\left(\bigcap_{n=1}^{m}\left\{ X_{n}\leq k\right\} \right)=\left(p_{1}+\cdots+p_{k}\right)^{m}$ for any $m$.

Here $p_{1}+\cdots+p_{k}<1$ so $m\rightarrow\infty$ makes clear that $P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)=0$.

Actually the second convergence can be almost surely

Fix $\epsilon >0$. Let $\tau$ be the first moment when the total probability of elements in $D_n$ is greater than $1 - \frac{\epsilon}{2}$. By the fact that every element will eventually fall into $D_n$, we know $\tau$ is finite almost surely. To strictly prove it, begin with the element with biggest probability, then that with second biggest probability etc.

By the strong law of large number $\limsup\dfrac{D_n - D_\tau}{n - \tau} < \dfrac{\epsilon}{2} $, since after $\tau$, for each step the probability that $D_n$ increase by 1 is less than $\dfrac{\epsilon}{2}$

The above limit is also limsup of $\dfrac{D_n}{n}$.

My question: Why strong law of large number can be applied to $\limsup\dfrac{D_n - D_\tau}{n - \tau} < \dfrac{\epsilon}{2} $?? I don't understand.


For every $n$, consider the random set $Y_n=\mathbb N\setminus\{X_k\mid k\leqslant n\}$, then $Y_{\tau+k-1}\subseteq Y_{\tau}$ for every $k\geqslant1$, hence, for every $n\geqslant\tau$, $$D_n-D_\tau=\sum_{k=1}^{n-\tau}\mathbf 1_{X_{\tau+k}\in Y_{\tau+k-1}}\leqslant\sum_{k=1}^{n-\tau}U_k^\tau,\qquad U_k^\tau=\mathbf 1_{X_{\tau+k}\in Y_\tau}.$$ Conditionally on $Y_\tau$, the sequence $$\left(U_k^\tau\right)_{k\geqslant1}$$ is i.i.d. Bernoulli with probability of success $p(Y_\tau)$ where, for every $B\subseteq\mathbb N$, $p(B)=\sum\limits_{i\in B}p_i$. Thus, by the strong law of large numbers conditionally on $Y_\tau$, one has, almost surely, $$\limsup_{n\to\infty}\frac{D_n-D_\tau}{n-\tau}\leqslant\lim_{n\to\infty}\frac1{n-\tau}\sum_{k=1}^{n-\tau}U^\tau_k=\lim_{n\to\infty}\frac1n\sum_{k=1}^{n-\tau}U^\tau_k=p(Y_\tau).$$ Finally, note that, by definition of $\tau$, $p(Y_\tau)\leqslant\frac12\epsilon$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.