# Bounding the distance of empirical average from its expected value

Suppose we have three sequences of random variables, $$(Y_n)_n$$, $$(W_n)_n$$, and $$(X_n)_n$$ such that:

1. If $$Y_n=a$$, then $$X_n=b$$. If $$X_n=b$$, then $$W_n=c$$. That is $$1_{[Y_n=a]}\leq 1_{[X_n=b]}\leq 1_{[W_n=c]}$$ for all $$n=1,2,\dots$$, where $$a,b,c$$ are real numbers.
2. $$(1_{[Y_n=a]})_n$$ are i.i.d.; $$(1_{[W_n=c]})_n$$ are i.i.d.
3. $$\Pr(1_{[Y_n=a]}=1)=\nu_{a}$$ and $$\Pr(1_{[W_n=c]}=1)=\nu_{c}$$ for all $$n=1,2,\dots$$, where $$\nu_a \leq \nu_c$$.

Some implications of the above:

A. $$\Pr\Big(\Big|\frac{1}{n}\sum_{k=1}^n 1_{[Y_k=a]} -\nu_{a}\Big|\geq \epsilon \sqrt{\frac{\nu_{a}(1-\nu_{a})}{n}\Big)}\le \frac{1}{\epsilon^2}$$ $$\forall \epsilon>0$$ $$\forall n$$ (Chebyshev inequality)

B. $$\Pr\Big(\Big|\frac{1}{n}\sum_{k=1}^n 1_{[W_k=c]} -\nu_{c}\Big|\geq \epsilon \sqrt{\frac{\nu_{c}(1-\nu_{c})}{n}\Big)}\le \frac{1}{\epsilon^2}$$ $$\forall \epsilon>0$$ $$\forall n$$ (Chebyshev inequality)

C. $$\Pr\bigg(\liminf_{n\rightarrow \infty} \frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}\geq \nu_a\bigg)=1$$

D. $$\Pr\bigg(\limsup_{n\rightarrow \infty} \frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}\leq \nu_c\bigg)=1$$

Can we use the above relations to bound the distance between $$\frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}$$ and its mean?

• (2) implies $\nu_a=\nu_c.$ Did you really mean to assume identically distributed??
– whuber
Commented Sep 25, 2023 at 22:35
• My mistake. I meant: $(1_{[Y_n=a]})_n$ are i.i.d.; $(1_{[W_n=c]})_n$ are i.i.d.
– Star
Commented Sep 26, 2023 at 10:26
• I don't understand the subscript $_n$ in $(1_{[Y_n=a]})_n$. Commented Oct 2, 2023 at 9:48
• The use of these indicator makes it difficult to read the equations. Effectively we are just talking about a Bernoulli distributed variable or not? Commented Oct 2, 2023 at 9:51
• $(1_{[Y_n=a]})$ indicates a sequence. I'm talking about Bernoulli.
– Star
Commented Oct 2, 2023 at 14:16

It appears to be impossible to say anything meaningful without extra assumptions.

To illustrate, take $$\nu_a = 0$$, $$\nu_c = 1$$. Then $$(X_n)$$ is a totally unconstrained sequence of random variables: considering $$1_{[X_1 = b]} \sim \mathrm{Bernoulli}(1/2)$$, $$X_2 = X_1$$, $$X_3 = X_1$$, etc shows that no nontrivial concentration result is possible.

For any $$\nu_a$$ and $$\nu_c$$, we know that $$\frac1n \sum_{k=1}^n 1_{[Y_k = a]} \le \frac1n \sum_{k=1}^n 1_{[X_k = b]} \le \frac1n \sum_{k=1}^n 1_{[W_k = c]} .\tag{*}$$ Thus we can use Hoeffding's inequality to say that $$\Pr\left( \frac1n \sum_{k=1}^n 1_{[Y_k = a]} \le \nu_a - \sqrt{\frac{1}{2 n} \log \frac1\delta} \right) < \delta;$$ an analogous bound holds for $$\frac1n \sum_{k=1}^n 1_{[W_k = c]}$$, and so then by a union bound with each of those having $$\delta/2$$ probability and plugging in (*) we have that $$\Pr\left( \nu_a - \sqrt{\frac{1}{2 n} \log \frac2\delta} \le \frac1n \sum_{k=1}^n 1_{[X_k = b]} \le \nu_c + \sqrt{\frac{1}{2 n} \log \frac2\delta} \right) \ge 1 - \delta.$$

From taking the expectation of all sides of (*), we also know that $$\mu := \mathbb E \frac1n \sum_{i=1}^n 1_{[X_k = b]} \in [\nu_a, \nu_c]$$. Thus, combining the two, we have with probability at least $$1 - \delta$$ that $$\Bigl\lvert \frac1n \sum_{i=1}^n 1_{[X_k = b]} - \mu \Bigr\rvert \le (\nu_c - \nu_a) + \sqrt{\frac{1}{2 n} \log \frac2\delta} .$$ Again, this is only saying that $$\mu \in [\nu_a, \nu_c]$$ and the sample mean is not far outside of that same interval.

You could slightly improve the term with $$\delta$$ in it by using the actual binomial CDF function; it also might be possible to avoid the union bound with a more clever argument, but that would just be a tiny constant improvement. But the example at the start shows that reducing the $$\nu_c - \nu_a$$ term is impossible.

• ...much bigger than $\nu_a$ and much smaller than $\nu_c$ perhaps? Commented Sep 28, 2023 at 0:31
• Could you add more details on the case $\nu_a>0$ and $\nu_c<1$? In particular, could you translate in formal statements the second paragraph of your answer? Thank you
– Star
Commented Sep 28, 2023 at 10:30
• Also, I wonder what is wrong with the following steps: [1] by C and D, $$\Pr\bigg(\lim_{n\rightarrow \infty}d\big(\frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}, \big[\nu_a, \nu_c\big]\big)= 0\bigg)=1.$$ [2] For each $n$, it holds that $$\Pr\bigg(d\big(\frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}, \big[\nu_a, \nu_c\big]\big)\geq \epsilon\bigg)\leq \Pr\bigg(d\big(\frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]}, \nu_b\big)\geq \epsilon\bigg)\leq \frac{Var(\frac{1}{n}\sum_{k=1}^n 1_{[X_k=b]})}{n^2\epsilon^2}\leq \frac{\max_{p\in [\nu_a, \nu_c ] } p(1-p)}{n^2 \epsilon^2}$$ Can we do something from here?
– Star
Commented Sep 28, 2023 at 11:31
• I updated the second part of the answer; assuming that $d(t,[\nu_a,\nu_c])$ means the distance to the interval, i.e. $\max(\{\nu_a−t,t−\nu_b,0\})$, then that approach is just going to amount to the same idea as what I did above (but worse because it's Chebyshev instead of Hoeffding). (Incidentally, @AlecosPapadopoulos, I in fact meant what I said – that the mean can't be too far outside $[\nu_a, \nu_c]$.) Commented Sep 30, 2023 at 21:54
• Thanks. Just a clarification: how do we know that $\mu \equiv E(\frac{1}{n}\sum_{i}^n 1_{[X_k=b]})\in [\nu_a, \nu_c]$? Also, is the change from $\sqrt{\frac{1}{2n} \log\frac{1}{\delta}}$ to $\sqrt{\frac{1}{2n} \log\frac{2}{\delta}}$ when you apply the union bound correct, or a typo?
– Star
Commented Oct 2, 2023 at 14:27

There is not much information about the variable $$B_n := 1_{[Y_n=b]}$$ except that it is in between $$A_n = 1_{[Y_n=a]}$$ and $$C_n := 1_{[W_n=c]}$$.

We can imagine a process where the variable $$B_n$$ is being generated by being either equal to $$A_n$$ or equal to $$C_n$$ depending on a random coin flip at the beginning of generating the sequence. Then the mean of $$B_n$$ can be anywhere between the $$\nu_a$$ and $$\nu_c$$, and it's limits will be equal to the largest of the limits for the sequences $$A_n$$ and $$C_n$$ plus the range of the mean $$\nu_b$$.