# Few random variables cannot influence $n$ independent others too much?

I have $n$ standard normal and independent random variables $X_i$ (In reality I have a large known number of them, but let's just say I have $n$). In my experiment I want to on average get exactly 3 random variables $X_i$ under a threshold $c$. To get that, I can compute $c$ having that property easily, because the average number of $X_i$ that are under a threshold $c$ is $n \Phi(c)$ where $\Phi$ is the cdf of the standard normal distribution.

So I choose $c = \Phi^{-1}(3/n)$ in this case. (Which is a negative number for large $n$.)

But unfortunately I already know the value of two other standard normal random variables $Y$ and $Z$ which may depend on each other and on any number of the other $X_i$.

So my question is: if I know that $Y$ and $Z$ are under the threshold $c=\Phi^{-1}(3/n)$, is it then still true that on average at most a constant number of the other random variables $X_i$ are under the threshold $c$? So by knowing that $Y$ and $Z$ are under the threshold, they can't suddenly make many of the other random variables go under it too.

I am almost certain that they can't, but I don't know how to prove it. Any hints are welcome. Or books where you think this might be in.

-
That initial probability $n\Phi(c)$ only applies if the collection of $X_{i}$ are independent of $Y$ and $Z$ - so if that applies, then you are correct. But you mentioned correlations, so it is likely your initial formula is not applicable. If you have conditional independence given $Y$ and $Z$, then you would need to modify the constant $c$ in $\Phi(c)$ so that it is a function of $Y$ and $Z$. –  probabilityislogic Apr 25 '11 at 7:30
Say I keep the constant $c$ as it is. Then on average not more than a constant (any constant) amount of the $X_i$ should be under the threshold still, right? –  Josiane Lucie Apr 25 '11 at 8:17
If anything is unclear please let me know, and I will clarify as much as I can. –  Josiane Lucie Apr 25 '11 at 10:03

In the asymptotic sense seemingly suggested by the phasing of the question, it's not true, but the analysis might be revealing.

We don't even need $Z$.

Let $p$ be the chance of a standard normal variable being $c$ or less; that is, $p = \Phi(c)$. Then the chance that at least $k$ or more of the $X_i$ are less than or equal to $c$ is given by a Binomial distribution

$$\sum_{i=0}^{n-k} \binom{n}{i} p^{n-i}(1-p)^i\text{.}$$

Because this sum runs from $p^n \lt p$ to $1 \gt p$, there exists a $k$ between $1$ and $n-1$ where the sum is as large as possible but still less than $p$.

For future reference, note that as $n$ grows large, $k$ is approximately equal to $p n$. This is a consequence of the Central Limit Theorem (for Binomial variates), because the sum is approximately equal to $\Phi((n-k - (1-p) n) / \sqrt{n p (1-p)})$. If eventually $k$ were less than $p n$, say $k \lt (p - \epsilon)n$ for $\epsilon \gt 0$, then the sum would approximate $\Phi(\epsilon \sqrt{n} / \sqrt{p(1-p)})$, which approaches $1$ as $n$ increases, but the sum is constructed to stay below $p$. Similarly, if $k \gt (p + \epsilon)n$, the sum would go to zero, again contradicting the construction of $k$ (to be as large as possible).

Define $q$ (which depends implicitly on $c$ and $n$) to be the value of the sum for such a $k$. Let $b = \Phi^{-1}(q) \le c$.

Conditional on at least $k$ of the $X_i$ not exceeding $c$, let $Y$ have a truncated standard normal distribution ranging from $-\infty$ to $b$. This happens with probability $q$. Otherwise, let $Y$ have a truncated standard normal distribution ranging from $b$ to $+\infty$. This gives $Y$ a standard normal distribution but it depends on the $X_i$.

If $Y \le c$, the chance that $Y \le b$ equals $q/p$. With sufficiently large $n$, an easy estimate shows this value is close to $1$. Given that $Y \le b$, we know at least $k$ of the $X_i$ are below $c$, by construction of $Y$. Therefore the expected number of such $X_i$ is at least $p n$ (asymptotically in $n$). This quantity grows without bound, it is not limited by a constant (independent of $n$).

You can work this analysis in reverse: if the expected number of $X_i$ below the threshold $c$, conditional on $Y \le c$, is much larger than $p n$, then the probability that $Y \le c$ would have to be greater than $\Phi(c)$, implying $Y$ does not have a standard Normal distribution. In this sense the preceding construction is a worst case: asymptotically, it achieves the largest possible expected number of $X_i$ below $c$ consistent with the assumptions on $X_i$ and $Y$.

-
I have to reread your answer again to make sure I really understand. But in the first part you seem to construct a counterexample; yet in your last paragraph you say "if the expected number of X_i below the threshold c, conditional on Y≤c, is much larger than pn, then the probability that Y≤c would have to be greater than Φ(c), implying Y does not have a standard Normal distribution." So you are suggesting that one can not have many more X_i under the treshold than pn, and thus if p=3/n also no more than a constant amount of X_i will be under it? –  Josiane Lucie Apr 27 '11 at 2:10
@Josiane That's correct. In fact, the expectation of the number of $X_i$ less than $c$ is at most $pn + O(\sqrt{n})$, so if $p$ changes with $n$ like $O(1/n)$, the number of such $X_i$ is a constant plus $O(n^{-1/2})$. –  whuber Apr 27 '11 at 12:55
But if that's plus $\sqrt n$ then it grows without bounds? I.e., the number of $X_i$ is not bounded by a constant? –  Josiane Lucie Apr 28 '11 at 3:28
Say if I had to prove it formally that there is no more than a constant amount, could I formulate X_i as the weighted sum of a RV dependent on Y (and Z) and another one which is independent of it? Maybe that could help. –  Josiane Lucie Apr 28 '11 at 3:34
@Josiane You have to work in the other direction: you cannot have the $X_i$ depend on $Y$ or $Z$, because that would violate their assumed independence: $Y$ and $Z$ have to depend on the $X_i$. Construct $Y$ and $Z$ as mixtures of disjoint truncated Normal distributions (so that they each become univariate Normal). Arrange it so that when $n$ of the $X_i$ are less than $c$, then so are $Y$ and $Z$ (if possible). Then repeat for $n-1$, $n-2$, ..., etc., until you have completely accounted for $\Pr(Y\le c, Z\le c)$. This maximizes the conditional expectation of the number of $X_i \le c$. –  whuber Apr 28 '11 at 14:11