求Y的方差：概率测试中X_i、S_{i,j,k}相关的方差求解问题
Let's walk through this step by step—you already have the right starting point with ( \text{Var}(Y) = \mathbb{E}[Y^2] - (\mathbb{E}[Y])^2 ), so we just need to unpack ( \mathbb{E}[Y^2] ) properly.
First, let's formalize ( Y ) as a sum of indicator variables. Since ( Y ) counts the number of triples ( (i,j,k) ) where ( X_i=X_j=X_k=1 ), we can write:
$$ Y = \sum_{\substack{1 \leq i < j < k \leq n}} S_{i,j,k} $$
Each ( S_{i,j,k} ) is a 0-1 indicator, so squaring ( Y ) expands to:
$$ Y^2 = \left( \sum_A S_A \right)^2 = \sum_A S_A^2 + 2\sum_{A < B} S_A S_B $$
Because ( S_A^2 = S_A ) (it's either 0 or 1), this simplifies the expectation:
$$ \mathbb{E}[Y^2] = \sum_A \mathbb{E}[S_A] + 2\sum_{A < B} \mathbb{E}[S_A S_B] $$
We already know ( \sum_A \mathbb{E}[S_A] = \mathbb{E}[Y] = \Theta(n^{1.5}) ), so now the key is computing the cross terms ( \mathbb{E}[S_A S_B] ) for distinct triples ( A ) and ( B ). We'll split this into cases based on how many elements ( A ) and ( B ) share:
Case 1: Triples ( A ) and ( B ) are disjoint (no shared elements)
Here, the sets of ( X )-variables for ( A ) and ( B ) are completely separate, so ( S_A ) and ( S_B ) are independent. That means:
$$ \mathbb{E}[S_A S_B] = \mathbb{E}[S_A] \mathbb{E}[S_B] = \left(n{-3/2}\right)2 = n^{-3} $$
The number of such unordered pairs ( (A,B) ) is roughly ( \frac{1}{2} \binom{n}{3} \binom{n-3}{3} \approx \frac{n^6}{72} ) for large ( n ). Multiplying by the probability gives a total contribution of ( \approx \frac{n^3}{72} ), and doubling it (from the ( 2\sum ) term) gives ( \frac{n^3}{36} ), which is ( \Theta(n^3) ).
Case 2: Triples ( A ) and ( B ) share exactly 1 element
Suppose ( A = (i,j,k) ) and ( B = (i,l,m) ) (sharing ( i )). For ( S_A S_B = 1 ), all five variables ( X_i,X_j,X_k,X_l,X_m ) must be 1, so the probability is:
$$ \mathbb{P}(X_i=1)^5 = n^{-5/2} $$
The number of such pairs is roughly ( \frac{1}{2} n \binom{n-1}{2} \binom{n-3}{2} \approx \frac{n^5}{8} ) for large ( n ). Multiplying by the probability gives ( \approx \frac{n^{5/2}}{8} ), and doubling it gives ( \frac{n^{5/2}}{4} = \Theta(n^{2.5}) ).
Case 3: Triples ( A ) and ( B ) share exactly 2 elements
Suppose ( A = (i,j,k) ) and ( B = (i,j,l) ) (sharing ( i,j )). For ( S_A S_B = 1 ), all four variables ( X_i,X_j,X_k,X_l ) must be 1, so the probability is:
$$ \mathbb{P}(X_i=1)^4 = n^{-2} $$
The number of such pairs is roughly ( \frac{1}{2} \binom{n}{2} (n-2)(n-3) \approx \frac{n^4}{4} ) for large ( n ). Multiplying by the probability gives ( \approx \frac{n^2}{4} ), and doubling it gives ( \frac{n^2}{2} = \Theta(n^2) ).
Putting It All Together
Now let's compute ( \text{Var}(Y) ):
- ( (\mathbb{E}[Y])^2 = \left(\Theta(n{1.5})\right)2 = \Theta(n^3) ), which matches the leading term from Case 1.
- When we subtract ( (\mathbb{E}[Y])^2 ) from ( \mathbb{E}[Y^2] ), the ( \Theta(n^3) ) terms cancel out.
- The next largest term is ( \Theta(n^{2.5}) ) from Case 2, which dominates the smaller ( \Theta(n^2) ) and ( \Theta(n^{1.5}) ) terms.
So the final result is:
$$ \text{Var}(Y) = \Theta(n^{2.5}) $$
内容的提问来源于stack exchange，提问作者asaf92
