Law of large numbers with one dependency: $\frac{1}{n}\sum_{i=1}^n g(X,Y_i)$

Question

Let $\{Y_i\}_{i=1}^{\infty}$ be a sequence of independent and identically distributed (i.i.d.) random variables. Let $X$ be another random variable (possibly dependent on $\{Y_i\}_{i=1}^{\infty}$). Let $g:\mathbb{R}^2\rightarrow\mathbb{R}$ be a measurable function. Assume that $E[g(x,Y_1)]$ is well defined and finite for all $x \in \mathbb{R}$.

I would like to know when there exists a deterministic function $f$ such that
$$ \lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n g(X, Y_i) = f(X) \quad \mbox{with prob 1} $$ I am particularly interested in the candidate function $f(x) = E[g(x, Y_1)]$.

I have been able to prove the result for the case when $X$ is discrete (see below). I am interested in results and/or counter-examples for more general cases.

---

Context: This question is a refinement of the question here: Strong law of large numbers for function of random vector: can we apply it for a component only?

In that link, I was able to prove the result always holds for $f(x)=E[g(x,Y_1)]$ when $X$ takes values in a finite or countably infinite set.

Answer 1

Fran's comment conjectures it is true for $g$ a simple function. Here is a counter-example. In fact, it can fail even if $g$ is binary-valued.

---

Let $A$ be a subset of positive integers such that the following limit does not exist: $$ \lim_{n\rightarrow\infty} \frac{1}{n} \sum_{i=1}^n 1_{\{i \in A\}} $$ where $1_{\{i \in A\}}$ is an indicator function that is $1$ if $i \in A$, and 0 else.

Define $\{Y_i\}_{i=1}^{\infty}$ i.i.d. and uniformly distributed over $[0,1)$. Express each $Y_i$ in its unique binary expansion (that does not contain an infinite tail of 1s): $$Y_i = \sum_{j=1}^{\infty} B_{ij}2^{-j} = 0.B_{i1} B_{i2} B_{i3}...$$ Then $(B_{ij})_{i,j=1}^{\infty}$ are i.i.d. and equally likely to be 0 or 1. We can arrange these in a 2-d grid:

The $(B_{ij})$ grid:

\begin{align} B_{11} \: B_{12} \: B_{13} \: B_{14} \quad \leftrightarrow & \quad V_1 \: V_3 \: V_6 \: \cdots \\ B_{21} \: B_{22} \: B_{23} \: B_{24} \quad \leftrightarrow & \quad V_2 \: V_5 \: \cdots \\ B_{31} \: B_{32} \: B_{33} \: B_{34} \quad \leftrightarrow& \quad V_4 \: \cdots \end{align} Now use the "diagonal" method to list them as $\{V_1, V_2, V_3, ...\}$ where $$V_1=B_{11}, V_2=B_{21}, V_3=B_{12}, V_4 = B_{31}, V_5 = B_{22}, V_6 = B_{13}, ...$$ and so on. Further, any real number $x \in [0,1)$ can be written as a "1-d expansion": $$x=0.x_1x_2x_3x_4...$$ and this can be rearranged as a "2-d expansion":

The 2-d expansion of $x$:

\begin{align} &x_1 \: x_3 \: x_6 \: \cdots \\\ &x_2 \: x_5 \: \cdots \\ &x_4 \: \cdots \end{align} Now define the random variable $X$ as follows: $$ X = \sum_{k=1}^{\infty} V_k 2^{-k} = 0.V_1 V_2 V_3... = 0.B_{11}B_{21}B_{12}...$$ Since $\{V_k\}_{k=1}^{\infty}$ is i.i.d. binary and equally likely to be either 0 or 1, $X$ is uniformly distributed over $[0,1)$. Yet, given $X$, we obtain information about the entire $\{Y_i\}$ sequence. This is done by forming the 2-d expansion of $X$, as shown in the above picture of the 2-d grid for $(B_{ij})$, and noting that each $Y_i$ value is formed by taking its binary expansion as row $i$ from that grid. Since $\{Y_i\}_{i=1}^{\infty}$ are i.i.d. uniform over $[0,1)$, with probability 1 all $Y_i$ values are different. So we can define a function $g$ that, given $X$ and $Y_i$, extracts the index $i$.

Specifically define the binary-valued function $g:[0,1)^2 \rightarrow \{0,1\}$ as follows:

• Define $g(x,y) = 0$ if the 1-d expansion of $y$ does not appear on any row of the 2-d expansion of $x$, or if it appears on multiple rows of the 2-d expansion of $x$.

• Define $g(x,y) = 1_{\{i \in A\}}$ if the 1-d expansion of $y$ appears on row $i$ of the 2-d expansion of $x$, and if it appears on no rows other than $i$.

Now for any $x\in [0,1)$ we have $E[g(x,Y_1)]=0$ since, with prob 1, the 1-d expansion of $Y_1$ does not appear on any row of the 2-d expansion of $x$. On the other hand, by construction we know that the 1-d expansion of $Y_i$ is on row $i$ of the 2-d expansion of $X$. Since all $Y_i$ values are distinct with probability 1, with probability 1 all rows of the 2-d expansion of $X$ are distinct, and so (with probability 1):
$$g(X, Y_i) = 1_{\{i \in A\}} \quad \forall i \in \{1, 2, 3, ...\} $$ Hence, with probability 1, for all positive integers $n$ we have:
$$ \frac{1}{n}\sum_{i=1}^n g(X,Y_i) = \frac{1}{n}\sum_{i=1}^n 1_{\{i \in A\}} $$ and, by our assumption on the set $A$, this limit as $n\rightarrow\infty$ does not exist!

---

(Edit) Measurability of $g$

Notice that the $g$ function is indeed measurable: Fix a positive integer $m$ and fix $b \in \{0,1\}$. Observe that the set of all $x=0.x_1x_2x_3... \in [0,1)$ such that $x_m=b$ is a finite union of intervals. For example, the set of all $x \in [0, 1)$ such that $x_2=1$ is equal to $$ [1/4,1/2) \cup [3/4, 1) $$

Fix $j$ as a positive integer, fix a set of indices $m_1, m_2, ..., m_j$, and fix a binary string $(b_1,b_2,..., b_j)$. Then the set of all $x=0.x_1x_2x_3... \in [0,1)$ such that $x_{m_1}=b_1, x_{m_2}=b_2, ..., x_{m_j}=b_j$ is the intersection of finite unions of intervals and so is itself a finite union of intervals. For example, the set of all $x \in [0,1)$ such that the first three digits of row 1 in the 2-d expansion of $x$ are "011" is equal to the set of all $x=0.x_1x_2x_3... \in [0,1)$ such that $x_1=0, x_3=1, x_6=1$ (see the picture of the 2-d expansion of $x$ above, where it is clear that $x_1, x_3, x_6$ are the first 3 bits of the first row), and this is a finite union of intervals.

So fix $i,j$ positive integers. There are $2^j$ binary strings of length $j$, enumerate them and index them by $k \in \{1, 2, ..., 2^j\}$. Let $B_{ijk}$ be the set of all $(x,y) \in [0,1)^2$ such that the 1-d expansion of $y$ has the first $j$ bits equal to the $k$th binary string, and the row $i$ of the 2-d expansion of $x$ has the first $j$ bits also equal to the $k$th binary string. The set $B_{ijk}$ is the Cartesion product $C_{ijk}\times D_{ijk}$ where $C_{ijk}$ is a finite union of intervals on the $x$-axis, and $D_{ijk}$ is a single interval of the $y$ axis. So $B_{ijk}$ is a union of rectangles and hence measurable. Define $$ B_{ij} = \cup_{k=1}^{2^j} B_{ijk}$$ and note that $B_{ij}$ is measureable. By taking unions, intersections, and complements with the (measurable) $B_{ij}$ sets we can form the set $\{(x,y) \in [0,1)^2 : g(x,y)=1\}$, as shown in the comment below, and so $g$ is measurable.

Answer 2

Here is a sufficient condition that follows from the discrete case.

---

Let $\mathcal{X}\subseteq \mathbb{R}$ and $\mathcal{Y}\subseteq \mathbb{R}$ be sets such that $X \in \mathcal{X}$ and $Y_1 \in \mathcal{Y}$. Recall that $\{Y_i\}_{i=1}^{\infty}$ is i.i.d. and $X$ is possibly dependent on $\{Y_i\}_{i=1}^{\infty}$. Define $f(x) = E[g(x,Y_1)]$ for all $x \in \mathbb{R}$. Define Property * as follows:

Property *:

$$ \lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n g(X,Y_i) = f(X) \quad \mbox{ with prob 1} $$

Claim 1:

Property * holds whenever $\mathcal{X}$ is a finite or countably infinite set.

Proof: See answer here: Strong law of large numbers for function of random vector: can we apply it for a component only?

$\Box$

Claim 2:

Property * holds if $g$ satisfies the following “piecewise uniform continuity” property: For each $\epsilon>0$ there is a sequence of disjoint intervals $\{I_i^{(\epsilon)}\}_{i=1}^{\infty}$, each interval $I_i^{(\epsilon)}$ having a finite size (some intervals possibly being "degenerate" by consisting of a single point), such that $\mathcal{X} \subseteq \cup_{i=1}^{\infty} I_i^{(\epsilon)}$ and for all $i \in \{1, 2, 3, \ldots\}$ and all $a,b \in I_i^{(\epsilon)}$ we have: $$ |g(a, y) - g(b,y)|\leq \epsilon \quad \forall y \in \mathcal{Y} $$

Proof: Fix $\epsilon>0$. Then $X \in \cup_{i=1}^{\infty}I_i^{(\epsilon)}$ and there is a unique index $i(X)$ such that $X \in I_{i(X)}^{(\epsilon)}$. Define $X_{\epsilon}$ as the discrete random variable that is equal to the midpoint of $I_{i(X)}^{(\epsilon)}$. Then for all realizations of $X, \{Y_i\}$ we have: $$ |g(X_{\epsilon}, Y_k) - g(X, Y_k)| \leq \epsilon \quad \forall k \in \{1, 2, 3, …\}$$ Since $X_{\epsilon}$ is discrete, by Claim 1 we know $$ \lim_{n\rightarrow\infty} \frac{1}{n} \sum_{i=1}^ng(X_{\epsilon}, Y_i) = f(X_{\epsilon}) \quad \mbox{ with prob 1} $$ For all $n$ we have \begin{align} \left|\frac{1}{n}\sum_{i=1}^n g(X,Y_i)-f(X)\right|&\leq \underbrace{\left|\frac{1}{n}\sum_{i=1}^n[g(X,Y_i)-g(X_{\epsilon},Y_i)]\right|}_{\leq \epsilon} \\ &\quad +\left|\frac{1}{n}\sum_{i=1}^n g(X_{\epsilon},Y_i) - f(X_{\epsilon})\right|\\ &\quad + \underbrace{\left|f(X_{\epsilon})-f(X)\right|}_{\leq \epsilon} \end{align} Taking a limit gives, with probability 1: $$ \limsup_{n\rightarrow\infty} \left|\frac{1}{n}\sum_{i=1}^n g(X,Y_i)-f(X)\right| \leq 2\epsilon $$ The above holds for all $\epsilon>0$, and the result follows. $\Box$

Claim 3:

The assumptions of Claim 2 hold whenever $\mathcal{Y}$ is a compact subset of $\mathbb{R}$ and $g:\mathbb{R}\times \mathcal{Y}\rightarrow \mathbb{R}$ is continuous.

Proof: Write $\mathbb{R} = \cup_{i=-\infty}^{\infty} [i, i+1]$. The function $g$ restricted to the compact domain $[i, i+1]\times \mathcal{Y}$ is continuous over this compact domain, and hence uniformly continuous over this compact domain. Hence, it is uniformly continuous over each interval of the union of disjoint intervals $\cup_{i=-\infty}^{\infty} [i, i+1)$. $\Box$