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

Question

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.

Answer 1

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$