# Law of large numbers for stochastically chosen samples

Let $X_t$ be a sequence of i.i.d. random variables with mean $\mu$. Then the law of large numbers states that $$\lim_{T \to \infty} \frac1T \sum_{t=1}^T X_t = \mu \quad a.s.$$

Now suppose that (in a game theoretic context) an agent can choose at every instant of time if she wants to observe $X_t$ or not. I want to prove that the average over the observations still converges to $\mu$.

In more details, the let $k_t=1$ denote that $X_t$ is observed, and $k_t=0$ that $X_t$ is not observed. To model that the agent's choice at time $t$ can depend only on past observations, I require $k_t$ to be measurable with respect to the $\sigma$-algebra $$\mathcal F_{t-1} := \sigma(k_1 X_1, \ldots, k_{t-1} X_{t-1}).$$ I define $$N_T:=\sum_{t=1}^T k_t, \quad Y_T:=\sum_{t=1}^T k_t X_t$$ and assume that $N_T \to \infty$ as $T \to \infty$. Now the question is if $$\lim_{T \to \infty} \frac{1}{N_T}Y_T = \mu.$$

• Perhaps I didn't understand the question, but isn't the sequence of chosen $X_t$'s also i.i.d.? – Ori Gurel-Gurevich Nov 9 '11 at 19:04

Using John's notation, and assuming $\{X_{\sigma(i)}\}$ are independent, then $X=(X_1,X_2,\ldots)$ has the same distribution as $X_\sigma=(X_{\sigma(1)},X_{\sigma(2)},\ldots)$. Let $f(X)=\limsup_{n\rightarrow\infty}(X_1+\cdots+X_n)/n$. Then $f(X_\sigma)=\limsup_{t\rightarrow\infty}Y_t/N_t$, and $\mathbb P[f(X_\sigma)=\mu]=\mathbb P[f(X)=\mu]=1$, and similarly for the liminf.

Wrong solution. See James' below. I'll just add that to show independence for say $X_{\sigma(1)},X_{\sigma(2)}$, $E(E(f(X_{\sigma(1)}) g(X_{\sigma(2)})|X_{\sigma(1)})) = E( f(X_{\sigma(1)}) E(g(X_{\sigma(2)}| X_{\sigma(1)}))$. It would suffice to show $E(g(X_{\sigma(2)})|X_\sigma(1)) = E(g(X_1))$. This can be done by conditioning on $\sigma(2) = j$ for $j > \sigma(1)$, and then sum over such $j$'s.

I think Ori's suggested approach is best. Let $\sigma(i)$ be the index of the $i$th k that is $1$. Then condition on $\sigma(1), \ldots, \sigma(N)$, $X_{\sigma(1)}, \ldots, X_{\sigma(N)}$ are iid. This you can easily check by computing $P(X_{\sigma(i} \in A_i)$ using tower property of conditioning.

So now you can just do a conditional LLN. By your assumption, for any $N$, $P(\sum_{j=1}^T k_j > N)$ with high probability, for sufficiently large $T$. So

$$P(\sum_{j=1}^T k_j X_j > c \sum_{j=1}^T k_j) < P(\sum_{i=1}^{\sigma^{-1}(T)} X_{\sigma(i)} > c \sigma^{-1}(T) | \sigma^{-1}(T) > N) + P(\sigma^{-1}(T) < N),$$

where $\sigma^{-1}(T)$ is the number of nonzero $k_j$'s for $j \le T$.

You can deal with the first component using Chebyshev by breaking it into an infinite sum conditioning on $\sigma^{-1}(T) = N+k$ for $k \in \mathbb{N}$, which are uniformly small; then apply Bayes' formula. The second piece is small as we discussed. The whole thing is then small.

Edit: the following earlier approach seems useless.

First of all assuming $X_j$'s are centered, your sequence $N_s := \sum_{t=1}^s k_t X_t$ is a Martingale because $E[ k_s X_s | \mathcal{F}_{s-1}] = 0$, where I let $\mathcal{F}_s$ be the sigma field generated by $X_1, \ldots, X_s, k_1, \ldots, k_s$. Thus $$var N_s = \sum_{j=1}^s E (k_j X_j)^2 = \sum_{j=1}^s E(k_j^2) E(X_j^2)$$ assuming $X_j$'s are centered, and using independence of $X_j$ with $k_j$. You should then be able to use Chebyshev as in the usual LLN to conclude.

• Thank you for your answer. I understand what you say. To use the Chebyshev inequality, I need to establish $var(Y_T/N_T) \to 0$. The problem with this is that $N_T$ now is a random variable, and that it is correlated with $Y_T$. Can you help me once more with this? PS: I sticked to my own notation in this comment, and I updated my question to make it more concise. – pharms Nov 9 '11 at 23:31
• See my updated solution above based on Ori's suggestion. – John Jiang Nov 10 '11 at 2:35
• No, that is not true. $X_{\sigma(1)},\ldots,X_\sigma(N)$ are not i.i.d given $\sigma(1),\ldots,\sigma(N)$. However, Ori Gurel-Gurevich's claim seems plausible to me. As an example for when your statement does not hold, consider conditioning on $\sigma(1)=1,\sigma(2)=2$. This implies $k_1=k_2=1$. Conditioning on $k_1$ does not have an influence because $k_1$ is deterministic. Conditioning on $k_2$ has no influence on the distribution of $X_2$, but it can have an influence on the distribution of $X_1$ because $k_2$ can be a function of $X_1$. – pharms Nov 10 '11 at 21:41

There is a continuous time version of this problem that sheds some more light on this. The discrete time result follows by choosing piecewise constant processes $k$.

It follows from [1, theorem 5.1] that $$\tag{1}\int_0^{S_t} k_s dN_s$$ is a Poisson process. Here $k$ is a process taking only the values 0 and 1 that is adapted to the natural filtration of $N$, $T$ is the finite time change (see ) given by $$T_t = \int_0^t k_s ds,$$ $S$ is the generalized inverse time change of $T$ given by $$S_t = \inf\ \{ s>0:T_s >t \} ,$$ and $N$ is a Poisson process with intensity $\lambda$. The result (1) has been proven earlier in [2, théorème 2'], but I find  more accessible.

It follows from the law of large numbers that $$\frac{1}{t} \int_0^{S_t} k_s dN_s \to \lambda \quad \text{a.s.}$$ Applying the time change $T$ then yields the desired formula $$\frac{1}{T_t} \int_0^{t} k_s dN_s \to \lambda \quad \text{a.s.}$$

Note: $k$ can not be replaced by a process with values in $\mathbb R$ without making additional assumptions on the integrator $N$. It has been shown in  that $N$ needs to be an $\alpha$ stable Levy process. The proof is much more instructive than  or . It is based on a property of the cumulant process $\mathcal K^N(k)$ of $N$ in the process $k$. One has $$\mathcal K^N(k)_t = \int_0^t \kappa(k_s) ds$$ for some function $\kappa$. The $\alpha$ stability of $N$ implies that $$\kappa(k x)=\lvert k\rvert^\alpha \kappa(x),\tag{2}$$ and this property is responsible for equation (1) to hold. Now it is obvious that (2) holds if $k$ takes only the values 0 and 1. Thus (1) is valid for all Levy processes.

 Kallenberg, Random time change and an integral representation for marked stopping times.

 Meyer, Démonstration simplifiée d’un théorème de Knight.

 Kobayashi, Stochastic Calculus for a Time-Changed Semimartingale.

 Kallsen and Shiryaev, Time Change Representations of Stochastic Integrals.