# 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 [3]) 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 [1] 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 [4] that $N$ needs to be an $\alpha$ stable Levy process. The proof is much more instructive than [1] or [2]. 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.

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

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

[3] Kobayashi, Stochastic Calculus for a Time-Changed Semimartingale.

[4] Kallsen and Shiryaev, Time Change Representations of Stochastic Integrals.

-