6
$\begingroup$

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?

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

2 Answers 2

6
+50
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ ...much bigger than $\nu_a$ and much smaller than $\nu_c$ perhaps? $\endgroup$ Sep 28, 2023 at 0:31
  • $\begingroup$ 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 $\endgroup$
    – Star
    Sep 28, 2023 at 10:30
  • $\begingroup$ 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? $\endgroup$
    – Star
    Sep 28, 2023 at 11:31
  • $\begingroup$ 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]$.) $\endgroup$
    – Danica
    Sep 30, 2023 at 21:54
  • $\begingroup$ 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? $\endgroup$
    – Star
    Oct 2, 2023 at 14:27
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.