Let $(X_i)_{i \geq 1}$ be i.i.d. random variables.. The strong law of large numbers ensures that for each $t$, the empirical cdf $\hat{F_n}\left(t\right)=\frac{1}{N}\sum_{i=1}^{N}\mathbb{1}_{X_i\leq t}$ converges almost surely to $P\left(X \leq t\right)$.
Now, let $w_i$ be deterministic weights. Can we say anything about the convergence of $\sum_{i=1}^{N}\frac{w_i}{\sum_{i=1}^{N}w_i}\mathbb{1}_{X_i\leq t}$ ?
If we can, what happens when the weights are not deterministic anymore, and $w_i$ is a function of $X_i$ ?
Best Answer
Yes, you can simply apply the strong law of large numbers to both the numerator and denominator (assuming all the necessary assumptions are satisfied). More specifically, in the setting where $w_i \equiv w(X_i)$, and denoting $q$ the distribution according to which each $X_1,\ldots,X_N$ is distributed : $$\begin{align*} \hat F_N^w(t) := \frac{\sum_{i=1}^N w(X_i) \mathbf 1\{X_i\le t\}}{\sum_{i=1}^N w(X_i)} &= \frac{\frac{1}{N}\sum_{i=1}^N w(X_i) \mathbf 1\{X_i\le t\}}{\frac{1}{N}\sum_{i=1}^N w(X_i)}\\ &\stackrel{N\to\infty}{\longrightarrow} \frac{E_q[w(X_1)\mathbf 1\{X_1\le t\}]}{E_q[w(X_1)]} \tag1 \end{align*} $$
Now, unless $w(X_1)$ is independent of $\mathbf 1\{X_1\le t\}$ (which more or less means that $w$ is constant), it seems like there is not much we can say.
There is a very important setting in which we can however prove that $(1)$ is equal to $P(X_1\le t)$ : that is in the framework of Importance Sampling, in which this type of quantities is extremely common : the problem is to estimate $E[f(X)] := \int f(x) p(x) dx $ where we do not have access to $p$, the pdf of $X$ (or maybe we do but it's expensive/difficult to sample from $p$, or maybe we only know $p$ up to a hard-to-compute constant). In our case, the function $f$ we want to integrate is $f := \mathbf 1\{\cdot \le t\}$.
The idea is thus to let $q$ be a distribution which we can easily sample from, and define the weight function $w : x\mapsto p(x)/q(x)$. We then create an i.i.d. sample $X_1,\ldots,X_n\sim q$ and define the estimator $\hat F_N^w(t)$ as above, it can be shown that $\hat F^w_N(t)$ converges almost surely to $P(X_1\le t)$. To prove it, it is enough to show that $(1)$ is equal to $P(X_1\le t)$, so let's develop :
$$\begin{align*} \frac{E_q[w(X_1)\mathbf 1\{X_1\le t\}]}{E_q[w(X_1)]} &= \frac{\int w(x) \mathbf 1\{x\le t\}q(x)dx}{\int w(x) q(x) dx}\\ &= \frac{\int \frac{p(x) q(x)}{q(x)} \mathbf 1\{x\le t\}dx}{\int \frac{p(x) q(x)}{q(x)} dx}\\ &= \frac{\int p(x)\mathbf 1\{x\le t\}dx}{\int p(x) dx}\\ &=\frac{\int p(x)\mathbf 1\{x\le t\}dx}{1}\\ &= P(X\le t) \end{align*} $$
As desired.
Note that in the above computation, $X\sim p$ while $X_1\sim q$ ! If $q=p$ then we simply recover the unweighted estimator $\hat F_n$. If you want to read more about this, you should Google "normalized importance sampling", you will find many great references on the subject.