6
$\begingroup$

Suppose I have sets $S_1\subset S_2\subset S_3$. I know exactly the size, mean, and standard deviation of both $S_1$ and $S_3$ and want to estimate the mean and standard deviation of $S_2$, where I only know its size.

  1. What's the best estimation I can make of mean & standard deviation of $S_2$?
  2. What's the max error?
  3. What additional statistics on $S_1$ and $S_3$ can improve the max error bounds, and by how much?

I'm offering a bounty on this question for anyone to improve on my answer. At the end of the February I will accept my answer if no better answers are given.

A good answer will be quantitative and include proof, calculation, or authoritative references, and will not need any additional assumptions on the set $S_3\setminus S_1$. If no closed form solution exists, provide charts, approximations, or just looser bounds.

Please don't pester me for details about the source of this question. It is no longer relevant to the context that brought it up, and is only a matter of frustrated curiosity to me.

$\endgroup$
  • 3
    $\begingroup$ How exactly are the elements of $S_2 \backslash S_1$ sampled from $S_3 \backslash S_1$? This question does not seem to match the context, which would involve lots of subsets having no definite inclusion relationships among them, so what are $S_1$, $S_2$, and $S_3$ intended to represent? $\endgroup$ – whuber Jan 28 '15 at 15:52
  • $\begingroup$ In my application these are contiguous ranges of a one-dimensional array. By precalculating statistics for ranges of length $2^n$ I can calculate stats for any range in $O(\log n)$ for an up-front cost of $O(n)$ space & time with good precision. (The "obvious" $O(1)$ algorithm suffers from catastrophic cancellation.) Anyway, I'm now interested in the general problem as posed :P. I think I know now what the estimates must be, but haven't figured out the error yet. $\endgroup$ – Kevin S Jan 28 '15 at 16:01
  • $\begingroup$ Unfortunately, the problem as generally posed admits only the most extreme possible ranges (upper and lower bounds) for answers, whereas more precise conclusions could be drawn for your specific problem if you make statistical assumptions about the array. Such assumptions could range from asserting it is in completely random order all the way through assuming it is sorted. Databases often are the latter and almost never are the former. $\endgroup$ – whuber Jan 28 '15 at 16:14
  • $\begingroup$ Well, derive for me what those extreme ranges are and I can accept your answer. This is not a database and my data isn't sorted. $\endgroup$ – Kevin S Jan 28 '15 at 16:25
  • 2
    $\begingroup$ It amounts to finding the full image of a quadratic map from $\mathbb{R}^4$ into $\mathbb{R}^2$, which might be best done numerically because I believe the solution can be described in general only qualitatively. Whether you call it a "dataset" or "database" is immaterial: the same caution holds about what can be achieved. What might be of even greater interest would be to find skip lengths (which might be smaller or larger than powers of two) that guarantee the estimates for $S_2$ lie within specified ranges. (3) is a good question. Having max and min would be both useful and tractable. $\endgroup$ – whuber Jan 28 '15 at 16:42
1
$\begingroup$

I'm going to solve this by calculation. I'm sure there's some clever statistics way to figure this out -- if you know, please make a post and I'll probably accept it :p. Until then, this will have to do.

Problem statement

We know $\mu_1=\mu(S_1)$, $\sigma_1=\sigma(S_1)$, and $N_1=\lvert S_1\rvert$, as well as the equivalent statistics on $S_3$: $\mu_3$, $\sigma_3$, and $N_3$. We also know $N_2$ and wish to find estimates for $\mu_2$ and $\sigma_2$ along with error bounds.

Statistical identities on disjoint unions

For $X\cap Y=\emptyset$ we'll make frequent use of the identities

$$ \mu_{X\cup Y}=\frac{N_X\mu_X+N_Y\mu_Y}{N_X+N_Y} $$

and

$$ (N_X+N_Y)\sigma_{X\cup Y}^2=N_X\sigma_X^2+N_Y\sigma_Y^2+\frac{N_XN_Y}{N_X+N_Y}(\mu_X-\mu_Y)^2. $$

S3 minus S1

Using these formula, we can immediately find exactI mean and variance for $S_3\setminus S_1$, namely

$$ \mu_{3\setminus1}=\frac{N_3\mu_3-N_1\mu_1}{N_3-N_1} $$

and

$$ (N_3-N_1)\sigma_{3\setminus1}^2=N_3\sigma_3^2-N_1\sigma_1^2-\frac{N_1N_3}{N_3-N_1}(\mu_3-\mu_1)^2. $$

S2 minus S1

If we can use this information to find good estimates for $\mu_{2\setminus1}$ and $\sigma_{2\setminus1}$, the mean and standard deviation of $S_2\setminus S_1$, then we can use the union formulae to make estimates for $\mu_2$ and $\sigma_2$. Intuitively we expect that $\mu_{2\setminus1}\approx\mu_{3\setminus1}$ and $\sigma_{2\setminus1}\approx\sigma_{3\setminus1}$ are reasonable estimates on that subset, but we would need to justify this, at least finding upper and lower bounds to determine how good (or bad) these estimates are.

Now we have by identity an equation we'll repeatedly refer to as (A)

$$ N_{3\setminus1}\sigma_{3\setminus1}^2=N_{3\setminus2}\sigma_{3\setminus2}^2+N_{2\setminus1}\sigma_{2\setminus1}^2+\frac{N_{3\setminus2}N_{2\setminus1}}{N_{3\setminus1}}(\mu_{3\setminus2}-\mu_{2\setminus1})^2 $$

where we've abbreviated $N_{a\setminus b}:=\lvert{S_a\setminus S_b\rvert}=N_a-N_b$. If we wish to maximize $\sigma_{2\setminus1}$ it suffices to note that we could choose a distribution of $S_3\setminus S_1$ so that all the varianceII is in $S_2\setminus S_1$ and the means $\mu_{3\setminus2}-\mu_{2\setminus1}=0$. In this case, all the terms of (A) become zero except the LHS and the $\sigma_{2\setminus1}$ term, yielding

$$ N_{3\setminus1}\sigma_{3\setminus1}^2=N_{2\setminus1}\sigma_{2\setminus1}^2, $$

implying that $\sigma_{2\setminus1}^2\leq\frac{N_{3\setminus1}}{N_{2\setminus1}}\sigma_{3\setminus1}^2$. By the same reasoning we could choose a different distribution so that all the variance is in $S_3\setminus S_2$, in which case $\sigma_{2\setminus1}^2=0$, obviously a lower bound. So we have these bounds on $\sigma_{2\setminus1}$:

$$ 0\leq\sigma_{2\setminus1}\leq\sqrt{\frac{N_3-N_1}{N_2-N_1}}\sigma_{3\setminus1}. $$

To find the maximum difference of the mean $\mu_{2\setminus1}$ from our proposed estimate $\mu_{2\setminus1}$ a good first step is to note we can maximize $(\mu_{3\setminus2}-\mu_{2\setminus1})^2$ in (A) by choosing a distribution where $\sigma_{3\setminus2}=\sigma_{2\setminus1}=0$. In this case all the variance in $S_3\setminus S_1$ is due to the wide disparity between the means on $S_3\setminus S_2$ and $S_2\setminus S_1$. So from (A) we get

$$ \lvert\mu_{3\setminus2}-\mu_{2\setminus1}\rvert\leq\frac{N_{3\setminus1}}{\sqrt{N_{3\setminus2}N_{2\setminus1}}}\sigma_{3\setminus1}. $$

If we rearrange this along with our mean union identity at the top, we get two equations with two unknowns:

$$ \begin{align} N_{3\setminus2}(\mu_{3\setminus2}-\mu_{3\setminus1}) +N_{2\setminus1}(\mu_{2\setminus1}-\mu_{3\setminus1}) &=0 \\ (\mu_{3\setminus2}-\mu_{3\setminus1}) -(\mu_{2\setminus1}-\mu_{3\setminus1}) &={\frac{N_{3\setminus1}}{\sqrt{N_{3\setminus2}N_{2\setminus1}}}}\sigma_{3\setminus1} \end{align} $$

Solving this gives us our bounded error:

$$ \left\lvert\mu_{2\setminus1}-\mu_{3\setminus1}\right\rvert\leq\sqrt{\frac{N_3-N_2}{N_2-N_1}}\sigma_{3\setminus1}. $$

So now all the pieces are in place, and we need to simply combine what we got on $S_2\setminus S_1$ with what we already know for $S_1$ and we will have our estimate and error bounds.

S2

Now the estimated mean and its bounds on $S_2$ can readily be found:

$$ \begin{align} \mu_2&=\frac{N_1\mu_1+(N_2-N_1)\left(\mu_{3\setminus1}\pm\sqrt{\frac{N_3-N_2}{N_2-N_1}}\sigma_{3\setminus1}\right)}{N_2}\\ &=\frac{N_1\mu_1+(N_2-N_1)\mu_{3\setminus1}}{N_2}\pm\frac{\sqrt{(N_2-N_1)(N_3-N_2)}}{N_2}\sigma_{3\setminus1}\\ \end{align} $$

These bounds are exact and this estimate is quite good when $N_3-N_1\ll N_2$ and $\sigma_{3\setminus1}$ is small.

Solving for $\sigma_2$, we find that

$$ \sigma_2^2=\frac{N_{2\setminus1}}{N_2}\sigma_{2\setminus1}^2+\frac{N_1}{N_2}\sigma_1^2+\frac{N_{2\setminus1}N_1}{N_2}(\mu_{2\setminus1}-\mu_1)^2 $$

We won't find the exact error here because $\mu_{2\setminus1}$ and $\sigma_{2\setminus1}$ aren't independent, but the $v$ term gives rise to an error of order $\frac{N_{3\setminus1}}{N_2}\sigma_{3\setminus1}^2$ and the squared difference of means gives rise to the (small if the mean error is small) error term

$$ \frac{N_{2\setminus1}^2N_{3\setminus2}N_1}{N_2^4}\sigma_{3\setminus1} $$

and the potentially more concerning error term

$$2\left\lvert\mu_{3\setminus1}-\mu_1\right\rvert\frac{N_{2\setminus1}N_1\sqrt{N_{2\setminus1}N_{3\setminus2}}}{N_2^3}\sigma_{3\setminus1}. $$


ITheoretically we can find this exactly. In practice there are precision issues with this calculation. In my particular case I actually have these values already, but if you don't, beware!

II There's a actually special cases here where $N_{3\setminus2}=1$ or $N_{3\setminus2}=1$ since one element sets don't have any variance. But the bounds derived still hold -- we could just have made them tighter for these cases.

$\endgroup$
  • $\begingroup$ Care to point out what assumptions I'm using and where? @Glen_b $\endgroup$ – Kevin S Jun 16 '15 at 16:30
  • $\begingroup$ My apologies; from your framing of it originally as a statistics problem, I subsequently misunderstood something about your notation and assumed you were doing something different from what you're actually doing.. I deleted the comment. $\endgroup$ – Glen_b -Reinstate Monica Jun 17 '15 at 4:29

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.