Return to Question

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

The answer below is very insightful. I have some clarifying questions, as I am not an expert of martingales, which I list below.

Step 1: for each $b \in B$, the formula $$M_n(b) := \sum_{k=1}^n\frac{1}{k}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ defines a square-integrable martingale. That is $$ E(M_n(b)^2)<\infty\quad \forall n\in \mathbb{N}. $$

Q1: How do I show that?

Step 2: This martingale has orthogonal increments. That is $$ E\Big((M_{m_2}(b)-M_{n_2}(b))(M_{m_1}(b)-M_{n_1}(b))\Big| ? \Big )=0 $$

Q2: Is Step 2 just a property of square-integrable martingales? Has this property a name or a specific reference? What should I condition on the expectation?

Step 3: This martingale is bounded in $L^2(P)$. That is, $$ \sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $$ since $$E\Big[\frac{1}{k^2}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)^2\Big] \le \frac{1}{4k^2}.$$

Q3: Isn't Step 3 a simple consequence of Step 1? That is, if $E(M_n(b)^2)<\infty$ $\forall n\in \mathbb{N}$, then $\sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $.

Step 4: By Steps 1-3, $M_n(b)$ converges almost surely (to what?) and in $L^2(P)$.

Q4: What is the name of the theorem applied here? Any specific reference?

Step 5: We deduce that the averages
$$\frac{S_n(b)}{n} := \frac{1}{n}\sum_{k=1}^n \big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ converge almost surely to $0$, by Cesàro lemma since $$\frac{S_n(b)}{n} = \frac{1}{n}\sum_{k=1}^n k(M_n(b)-M_{n-1}(b)) = \frac{1}{n}\Big(nM_n(b) - \sum_{k=0}^{n-1}M_k(b)\Big).$$

Step 6: As a result, the averages $\frac{S_n(b)}{n}$ and $\frac{1}{n}\sum_{k=1}^n P[a_k = b|a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to \infty$, which belong to the same interval.

Q6: How can I conclude this from Step 5? And, from here, how does the statement that I want to prove hold? Does $x_N(b)$ have actually a limit point?

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

The answer below is very insightful. I have some clarifying questions, as I am not an expert of martingales, which I list below.

Step 1: for each $b \in B$, the formula $$M_n(b) := \sum_{k=1}^n\frac{1}{k}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ defines a square-integrable martingale. That is $$ E(M_n(b)^2)<\infty\quad \forall n\in \mathbb{N}. $$

Q1: How do I show that?

Step 2: This martingale has orthogonal increments. That is $$ E\Big((M_{m_2}(b)-M_{n_2}(b))(M_{m_1}(b)-M_{n_1}(b))\Big| ? \Big )=0 $$

Q2: Is Step 2 just a property of square-integrable martingales? Has this property a name or a specific reference? What should I condition on the expectation?

Step 3: This martingale is bounded in $L^2(P)$. That is, $$ \sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $$ since $$E\Big[\frac{1}{k^2}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)^2\Big] \le \frac{1}{4k^2}.$$

Q3: Isn't Step 3 a simple consequence of Step 1? That is, if $E(M_n(b)^2)<\infty$ $\forall n\in \mathbb{N}$, then $\sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $.

Step 4: By Steps 1-3, $M_n(b)$ converges almost surely (to what?) and in $L^2(P)$.

Q4: What is the name of the theorem applied here? Any specific reference?

Step 5: We deduce that the averages
$$\frac{S_n(b)}{n} := \frac{1}{n}\sum_{k=1}^n \big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ converge almost surely to $0$, by Cesàro lemma since $$\frac{S_n(b)}{n} = \frac{1}{n}\sum_{k=1}^n k(M_n(b)-M_{n-1}(b)) = \frac{1}{n}\Big(nM_n(b) - \sum_{k=0}^{n-1}M_k(b)\Big).$$

Step 6: As a result, the averages $\frac{S_n(b)}{n}$ and $\frac{1}{n}\sum_{k=1}^n P[a_k = b|a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to \infty$, which belong to $[R_l(b),R_u(b)]$

Q6: How can I conclude this from Step 5? And, from here, how does the statement that I want to prove hold? Does $x_N(b)$ have actually a limit point?

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

The answer below is very insightful. I have some clarifying questions, as I am not an expert of martingales, which I list below.

Step 1: for each $b \in B$, the formula $$M_n(b) := \sum_{k=1}^n\frac{1}{k}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ defines a square-integrable martingale. That is $$ E(M_n(b)^2)<\infty\quad \forall n\in \mathbb{N}. $$

Q1: How do I show that?

Step 2: This martingale has orthogonal increments. That is $$ E\Big((M_{m_2}(b)-M_{n_2}(b))(M_{m_1}(b)-M_{n_1}(b))\Big| ? \Big )=0 $$

Q2: Is Step 2 just a property of square-integrable martingales? Has this property a name or a specific reference? What should I condition on the expectation?

Step 3: This martingale is bounded in $L^2(P)$. That is, $$ \sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $$ since $$E\Big[\frac{1}{k^2}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)^2\Big] \le \frac{1}{4k^2}.$$

Q3: Isn't Step 3 a simple consequence of Step 1? That is, if $E(M_n(b)^2)<\infty$ $\forall n\in \mathbb{N}$, then $\sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $.

Step 4: By Steps 1-3, $M_n(b)$ converges almost surely (to what?) and in $L^2(P)$.

Q4: What is the name of the theorem applied here? Any specific reference?

Step 5: We deduce that the averages
$$\frac{S_n(b)}{n} := \frac{1}{n}\sum_{k=1}^n \big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ converge almost surely to $0$, by Cesàro lemma since $$\frac{S_n(b)}{n} = \frac{1}{n}\sum_{k=1}^n k(M_n(b)-M_{n-1}(b)) = \frac{1}{n}\Big(nM_n(b) - \sum_{k=0}^{n-1}M_k(b)\Big).$$

Step 6: As a result, the averages $\frac{S_n(b)}{n}$ and $\frac{1}{n}\sum_{k=1}^n P[a_k = b|a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to \infty$, which belong to the same interval.

Q6: How can I conclude this from Step 5? And, from here, how does the statement that I want to prove hold? Does $x_N(b)$ have actually a limit point?

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

The answer below is very insightful. I have some clarifying questions, as I am not an expert of martingales, which I list below.

Step 1: for each $b \in B$, the formula $$M_n(b) := \sum_{k=1}^n\frac{1}{k}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ defines a square-integrable martingale. That is $$ E(M_n(b)^2)<\infty\quad \forall n\in \mathbb{N}. $$

Q1: How do I show that?

Step 2: This martingale has orthogonal increments. That is $$ E\Big((M_{m_2}(b)-M_{n_2}(b))(M_{m_1}(b)-M_{n_1}(b))\Big| ? \Big )=0 $$

Q2: Is Step 2 just a property of square-integrable martingales? Has this property a name or a specific reference? What should I condition on the expectation?

Step 3: This martingale is bounded in $L^2(P)$. That is, $$ \sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $$ since $$E\Big[\frac{1}{k^2}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)^2\Big] \le \frac{1}{4k^2}.$$

Q3: Isn't Step 3 a simple consequence of Step 1? That is, if $E(M_n(b)^2)<\infty$ $\forall n\in \mathbb{N}$, then $\sup_{n \in \mathbb{N}}E(M_n(b)^2)<\infty $.

Step 4: By Steps 1-3, $M_n(b)$ converges almost surely (to what?) and in $L^2(P)$.

Q4: What is the name of the theorem applied here? Any specific reference?

Step 5: We deduce that the averages
$$\frac{S_n(b)}{n} := \frac{1}{n}\sum_{k=1}^n \big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ converge almost surely to $0$, by Cesàro lemma since $$\frac{S_n(b)}{n} = \frac{1}{n}\sum_{k=1}^n k(M_n(b)-M_{n-1}(b)) = \frac{1}{n}\Big(nM_n(b) - \sum_{k=0}^{n-1}M_k(b)\Big).$$

Step 6: As a result, the averages $\frac{S_n(b)}{n}$ and $\frac{1}{n}\sum_{k=1}^n P[a_k = b|a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to \infty$, which belong to $[R_l(b),R_u(b)]$

Q6: How can I conclude this from Step 5? And, from here, how does the statement that I want to prove hold? Does $x_N(b)$ have actually a limit point?