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.

  • 1
    $\begingroup$ What kinds of objects are the $s_i$ and how do you measure closeness? $\endgroup$
    – whuber
    Jul 12, 2021 at 18:21
  • $\begingroup$ Every object is an integer between $a$ and $b$. $\endgroup$ Jul 13, 2021 at 12:27
  • $\begingroup$ the average=mean. i.e., sum of all elements divided by number of elements. $\endgroup$ Jul 13, 2021 at 12:38
  • 1
    $\begingroup$ In what sense is the arithmetic mean a measure of "closeness"?? $\endgroup$
    – whuber
    Jul 13, 2021 at 13:29
  • 1
    $\begingroup$ +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! $\endgroup$
    – whuber
    Jul 14, 2021 at 13:47

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


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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