COMP5270 Assignment 1 题解 - Problem 1
COMP5270 Assignment 1 题解
Problem 1: 随机集合的概率
题目
Suppose that two sets S and T are chosen independently and uniformly at random from all the 2ⁿ subsets of {1, 2, ..., n}. Give the values of Pr[S ⊆ T] and Pr[S ∪ T = {1, 2, ..., n}].
解答
(a) Pr[S ⊆ T]
分析：
对每个元素 i ∈ {1, 2, ..., n}：
- i ∈ S 的概率 = 1/2（因为 S 是均匀随机选取的子集）
- i ∈ T 的概率 = 1/2
要满足 S ⊆ T，意味着：如果 i ∈ S，那么必须有 i ∈ T。
所以对于每个元素 i：
\[P(i \text{ 满足 } S \subseteq T) = P(i \notin S) + P(i \in S) \cdot P(i \in T)\]
\[= \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}\]
由于每个元素的选取是独立的，所以 n 个元素都满足条件的概率是：
\[\boxed{Pr[S \subseteq T] = \left(\frac{3}{4}\right)^n}\]
(b) Pr[S ∪ T = {1, 2, ..., n}]
分析：
S ∪ T = {1, 2, ..., n} 意味着：对于每个元素 i，i 至少出现在 S 或 T 中。
所以：
\[P(i \in S \cup T) = 1 - P(i \notin S \cap T)\]
\[= 1 - \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}\]
同样，n 个元素独立：
\[\boxed{Pr[S \cup T = \{1,2,...,n\}] = \left(\frac{3}{4}\right)^n}\]
答案总结
| 题目 | 答案 |
|---|---|
| Pr[S ⊆ T] | (3/4)ⁿ |
| Pr[S ∪ T = {1,2,...,n}] | (3/4)ⁿ |
关键思路
- 均匀随机子集：从 2ⁿ 个子集中均匀选取，意味着每个元素独立地以 1/2 概率出现
- 独立性：不同元素之间是相互独立的
- 分类讨论：对每个元素考虑所有可能的情况（∈S, ∈T 的各种组合）
Hint: 这道题的核心在于理解"均匀随机选取子集"意味着每个元素是否在集合中是独立同分布的 Bernoulli(1/2)。