Law of large numbers for stochastically chosen samples

Question

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.$$

Answer 1

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.

Answer 2

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.

Answer 3

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.