確率・統計

2以上の自然数 $n$ に対して, $P = (P_1, \dots, P_n)$ は一様ランダムに選ばれた $\{1, \dots, n\}$ の順列とする．任意の自然数 $i, j \ (1 \leq i < j \leq n)$ に対して,

$$X_{ij} = \begin{cases} 1 & (P_i > P_j \text{の場合}) \\ 0 & (\text{それ以外}) \end{cases}$$

また, $Y_i = \sum_{j=i+1}^n X_{ij} \ (1 \leq i \leq n-1)$ とし, $Z = \sum_{i=1}^{n-1} Y_i$ とする．以下の各問いに答えよ.

1. $Z$ の期待値 $E[Z]$ を求めよ.
2. $i \ (1 \leq i \leq n-2)$ と $k \ (0 \leq k \leq n-i)$ に対して, $Y_{n-1} = l \ (l \in \{0, 1\})$ の条件の下で $Y_i = k$ となる条件付確率 $P[Y_i = k | Y_{n-1} = l]$ を求めよ.
3. $Z$ の分散 $\mathrm{Var}[Z]$ を求めよ. ただし,

$$\sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$$

を用いて良い.

---

DeepSeekV3

解答

1. 求 $z$ 的期望 $e[z]$ 首先，考虑任意一对 $i < j$，$p_i$ 和 $p_j$ 是随机排列中的两个数，它们有相等的概率谁在前谁在后。所以 $e[x_{ij}] = p(p_i > p_j) = 1/2$。 然后 $y_i = \sum_{j=i+1}^n x_{ij}$，所以 $e[y_i] = \sum_{j=i+1}^n e[x_{ij}] = (n - i) \cdot 1/2$。 接着，$z = \sum_{i=1}^{n-1} y_i$，所以

   $$e[z] = \sum_{i=1}^{n-1} e[y_i] = \sum_{i=1}^{n-1} (n - i) \cdot 1/2 = \frac{1}{2} \sum_{k=1}^{n-1} k = \frac{1}{2} \cdot \frac{n(n-1)}{2} = \frac{n(n-1)}{4}$$

   因此，第一问的答案是

   $$e[z] = \frac{n(n-1)}{4}$$

2. 求条件概率 $p[y_i = k \mid y_{n-1} = l]$ 给定 $y_{n-1} = l$，其中 $l \in \{0, 1\}$，求 $p[y_i = k \mid y_{n-1} = l]$。 通过分析，发现 $y_i$ 和 $y_{n-1}$ 在给定 $y_{n-1} = l$ 时是独立的，因此

   $$p[y_i = k \mid y_{n-1} = l] = p[y_i = k]$$

   $y_i$ 是二项分布 $\text{binomial}(n - i, 1/2)$，所以

   $$p[y_i = k] = \binom{n-i}{k} \left(\frac{1}{2}\right)^{n-i}$$

   因此，第二问的答案是

   $$p[y_i = k \mid y_{n-1} = l] = \binom{n-i}{k} \left(\frac{1}{2}\right)^{n-i}$$

3. 求 $z$ 的方差 $\mathrm{var}[z]$ 首先，$z = \sum_{i=1}^{n-1} y_i$，其中 $y_i = \sum_{j=i+1}^n x_{ij}$，所以

   $$z = \sum_{1 \leq i < j \leq n} x_{ij}$$

   计算 $e[z^2]$：

   $$e[z^2] = \sum_{1 \leq i < j \leq n} e[x_{ij}] + \sum_{(i,j) \neq (k,l)} e[x_{ij} x_{kl}]$$

   其中，$e[x_{ij}] = \frac{1}{2}$，$e[x_{ij} x_{kl}] = \frac{1}{4}$（完全不相交）或 $\frac{1}{3}$（有共同元素）。 经过详细计算，得到

   $$\mathrm{var}[z] = \frac{n(n-1)(n+2)}{24}$$

   因此，第三问的答案是

   $$\mathrm{var}[z] = \frac{n(n-1)(n+2)}{24}$$