# CLT theorem and Berry–Esseen bounds for this special case of sampling

Consider a finite set $$S=\{s_1,s_2,..s_n\}$$, where $$a \leq s_i\leq b$$ are integers. Each element in $$S$$ can be chosen to a subset $$S'$$ in probability $$p$$. We consider $$n$$ to be very large.

My question: How is there a way to messure how the mean element in $$S'$$ (i.e., $$(s'_1+s'_2...+s'_{n'})/n'=s'$$, where $$n'$$ is the number of elements in $$S'$$) to the mean element in $$S$$ (denoted by $$s$$)?

Formally, this means, given an error parameter $$\alpha$$, and mean values $$s, s'$$ I am trying to find the probability that $$Pr(|s-s'|< \alpha)$$.

Since $$n$$ is large, I consider to use the central limit theorem and use Berry–Esseen theorem to approximate the error, which depends on $$n$$. But I cannot express the problem as a sum of independent random variables, since this not a "standard way" of using sampling with replacement.

What can I do to approximate error?

Note: I did not found how to express the problem cannot as sum of independt RVs. For example, suppose we denote $$X_i$$ if element i is chosen or not- then

$$s'=(\sum_{i=0}^{n} X_i *s_i )/(\sum_{i=0}^n X_i).$$

And this cannot be expressed a a sum of independent RVs, as done in CLT or Berry Essen Thorems.

• What kinds of objects are the $s_i$ and how do you measure closeness?
– whuber
Jul 12, 2021 at 18:21
• Every object is an integer between $a$ and $b$. Jul 13, 2021 at 12:27
• the average=mean. i.e., sum of all elements divided by number of elements. Jul 13, 2021 at 12:38
• In what sense is the arithmetic mean a measure of "closeness"??
– whuber
Jul 13, 2021 at 13:29
• +1 Why can you not express $s^\prime$ as the sum of independent random variables? After all, it is explicitly constructed in terms of such a sum!
– whuber
Jul 14, 2021 at 13:47

First of all, I want to ensure whether I have understood the question correctly or not. $$n$$ is 'very large' and $$S=\{s_1,\dots, s_n\}$$. Now with probability $$p\in(0,1)$$, each $$s_i$$ is chosen to form the collection $$S'$$ (where $$X_i:=I_{s_i \in S'}$$). Then $$s'=\frac{\sum_{i=0}^n s_i I(s_i \in S')}{\sum_{i=0}^n I(s_i \in S')}=\frac{\sum_{i=0}^n s_i X_i}{n'}$$ and $$s=\sum_{i=0}^n s_i/n$$. (We have to keep in our mind that $$n'$$ and $$s'$$ are random and $$p$$ is fixed.) Also let $$m:=min\{|a|,|b|\} \le |s_i|\le max\{|a|,|b|\}=:M.$$

Now, this might help you: \begin{align} &\frac{\sum_{i=0}^n s_i I(s_i \in S')}{n'} - \frac{\sum_{i=0}^n s_i}{n} \\ &= \frac{1}{\sum X_i} \left(\sum_{i=0}^n s_i X_i - \frac{n'}{n} \sum_{i=0}^n s_i\right) \\ &= \frac{n}{n'} \cdot \frac{1}{n}\left(\sum_{i=0}^n s_i X_i - p \sum_{i=0}^n s_i\right) - \left(\frac{n'}{n}-p\right)\frac{\sum s_i}{\sum X_i} \end{align}

• Now, for the first part, you need a weighted version of CLT - check Lyapunov CLT condition (or Lindeberg condition).
• Lyapunov CLT with variables $$Y_i=s_i X_i$$ will give you $$\frac{\sum s_iX_i - p \sum s_i}{p(1-p)\sqrt{\sum s_i^2}} \to N(0,1)$$ as $$n\to \infty.$$ (I have not checked thoroughly though, please check them - you might need boundedness of the random variables.)
• $$m\sqrt{n}\le \sqrt{\sum s_i^2}\le M\sqrt{n}$$ - for simplified calculations, you have to assume $$m>0$$ - though this assumption can be relaxed.
• For the other part, note $$\sqrt{n}\left(\frac{n'}{n}-p\right) \to N(0,1)$$.
• $$\frac{\sum s_i}{\sum X_i} = \left(\frac{\sum s_i}{n}\right)\frac{n}{n'} \to \left(\frac{\sum s_i}{pn}\right)$$ Now $$s_i$$ are bounded which gives you required consistency from here.

For CLT type result, I would tweak the previous part in this way, \begin{align} &P\left(\sqrt{n}|\frac{\sum_{i=0}^n s_i I(s_i \in S')}{n'} - \frac{\sum_{i=0}^n s_i}{n}|>\epsilon\right) \\ &\le P\left(\sqrt{n}|\frac{n}{n'} \cdot \frac{1}{n}\left(\sum_{i=0}^n s_i X_i - p \sum_{i=0}^n s_i\right)|>\epsilon/2\right) + P\left(\sqrt{n}|\left(\frac{n'}{n}-p\right)\frac{\sum s_i}{n'}|>\epsilon/2\right) \\ &= P\left(\frac{n}{n'} \cdot \frac{1}{\sqrt{n}}|\left(\sum_{i=0}^n s_i X_i - p \sum_{i=0}^n s_i\right)|>\epsilon/2\right) + P\left(\frac{\sum s_i}{n} \cdot \frac{n}{n'} \cdot \sqrt{n}|\left(\frac{n'}{n}-p\right)|>\epsilon/2\right) \end{align}

• You can use Slutsky's theorem with $$\frac{n'}{n}\to p$$ and the normality you got from the Lyapunov CLT here.
• For the second part, use boundedness of $$\sum_1^n s_i/n$$ and a Slutsky theorem type approach will give you some bound.

Sorry for the mess.

## Edit:

There should be another condition on the values of $$s_i$$'s. These values should be such that $$\sum_{i=0}^n s_i/n \to c$$ for some constant $$c$$ as $$n \to \infty$$