How good the average of a sample estimates the average. Let $X$ be be a finite set with $n$ elements and let $f:X\to [c,d]$ be a function where $[c,d]$ in an interval in $\Bbb R$ and let $\epsilon > 0$ and the positive integer $m\le n$ be fixed.
For every $Y\subseteq X$, we let $M(Y)=\sum_{y\in Y}$f(y).
Let $\mathcal P_m(X)$ be the set of all subsets $Y\subseteq X$ with $|Y|=m$. Is there a way to approximate or calculate the probability that
$$\left |\frac{M(X)}{|X|}-\frac{M(Y)}{|Y|}\right |\le \epsilon$$
when $Y$ is accidentally chosen from  $\mathcal P_m(X)$.
In fact, this probability shows if a sample with $m$ members is chosen from $X$, how good the average of the sample estimates the average of $X$.
The main problem is that there any incountably many functions $f$, and it seems hard to find a probability formula for all functions or the mean value of all probabilities for different $f$s.
 A: You are correct that the probability of the deviation from the true sample statistic does not have a nice general form for all $f$. You have very general conditions on $f$, so there will not be any such formula. I'll offer two suggestions:
Option 1
Since $X$ is finite, you can actually calculate this statistic exactly (in principle) under the assumption of simple random sampling of subsets $Y$:


*

*There will be $K_m= {n \choose m}$ subsets in $\mathcal{P}_m(X)$.

*For each $y \in \mathcal{P}_m(X)$, calculate $f(y)$ and record its value in a list $L_m$

*Sort the items in $L_m$ from smallest to largest to get $L_m^*$

*Divide each element in $L^*_m$ by $K_m$.

*Now, if this is a theoretical study and you actually know $M(X)$, then you can subtract $\frac{M(X)}{|X|}$ from $L^*_m$ to get $\textrm{adj-}L^*_m$. This will give you a sorted list of deviations from the true population statistic. You can convert it to a distribution of absolute deviations by taking the absolute value of each element in $\textrm{adj-}L^*_m$ and then creating the cumulative distribution function from this list.

*If you are actually performing inference, then you won't know $M(X)$, so you can apply bootstrapping by replacing $\frac{M(X)}{|X|}$ with $\frac{M(Y)}{|Y|}$ (the statistic of the sample, and then proceeding with step $5$. This will be a bootstrap estimate of the absolute deviation statistic.


Option 2
If we assume that $f$ is bounded over $X$ and that $m,n$ are large (say, $\gg 30$), then the assumption of simple random sampling of subsets of $X$ suggests we can use the Central Limit Theorem to approximate the deviation:


*

*For a given sample $Y\subseteq X$, calculate $\frac{M(Y)}{|Y|}$ and calculate the finite population sample standard deviation: $s_{m,n} = s_m\sqrt{\frac{n-m}{n-1}}$

*Approximate the sampling distribution of the deviations by a gaussian distribution $\mathcal{N}(0,s_{m,n})$ (the mean is zero because the sample estimate is unbiased).

*You can get the approximate cdf of the absolute deviations by taking advantage of the symmetry of the normal distribution.


$$P\left(\left |\frac{M(X)}{|X|}-\frac{M(Y)}{|Y|}\right |\le \epsilon\right) \approx 2\Phi\left(\frac{\epsilon}{s_{m,n}}\right)-1$$
