solution

Cho $n$ biến ngẫu nhiên độc lập cùng phân phối đều liên tục trên $[0,1]$: $U_1,\dots,U_n$. Gọi $U_{(k)}$ là thống kê thứ tự thứ $k$ nhỏ nhất ($1\le k\le n$). Một kết quả kinh điển: $U_{(k)}$ tuân theo phân phối Beta với tham số $(k,\ n-k+1)$.

Có một hệ thức liên hệ đẹp giữa CDF của Beta (khi hai tham số đều nguyên) và phân phối nhị thức: với $X \sim \text{Beta}(k, n-k+1)$, $P(X \le x) = P(U_{(k)} \le x) = P\big(\text{Bin}(n,x) \ge k\big) = \sum_{j=k}^{n}\binom{n}{j}x^j(1-x)^{n-j}, \quad 0\le x\le 1$

(Ý nghĩa trực quan: $U_{(k)}\le x$ khi và chỉ khi có ít nhất $k$ trong số $n$ biến $U_i$ rơi vào đoạn $[0,x]$, mà số biến rơi vào $[0,x]$ có phân phối nhị thức $\text{Bin}(n,x)$.)

Cho $n, k$ ($1\le k\le n$) và $q$ giá trị truy vấn $x_1,\dots,x_q \in [0,1]$, hãy tính $P(U_{(k)}\le x_i)$ với mỗi truy vấn bằng công thức trên (KHÔNG dùng thư viện xác suất/thống kê ngoài, chỉ dùng tổ hợp).

Ví dụ: $n=3, k=2$ (trung vị của 3 mẫu), $x=0.5$: $P = \binom{3}{2}0.5^2(0.5) + \binom{3}{3}0.5^3 = 0.375+0.125=0.5$.