\(1.\) 指示器变量
设事件 \(A\),设指示器变量 \(X_{A}\),指示事件 \(A\) 发生,具体为
\[X_{A} = \left\{\begin{matrix}
1,\ & A\ happens\\
0,\ & A\ not\ happens
\end{matrix}\right.
\]
由定义知道,指示器变量 \(X_{A}\) 返回数值 \(0\) 或 \(1\)
容易知道,指示器变量 \(X_{A}\) 的期望 \(E(X_{A}) = Pr[X_{A}]\),事实上
\[E(X_{A}) = 1\cdot Pr[X_{A}] + 0\cdot (1 - Pr[X_{A}]) = Pr[X_{A}]
\]
所以 \(E(X_{A}) = Pr[X_{A}]\)
下面使用指示器变量分析具体的随机问题
\(2.\) 抛 \(n\) 次硬币,计算正面朝上的期望次数
\(Sol.\ 1\) 常规期望分析
设正面朝上的次数为 \(X\)
则
\[Pr[X = i] = C_{n}^{i}(\frac{1}{2})^i(\frac{1}{2})^{n - i},\ i = 0,\ 1,\ ..,\ n
\]
则
\[\begin{aligned}
E(X) & = \sum\limits_{i = 0}^{n}E(X = i)\\
& = \sum\limits_{i = 0}^{n}\left[i\cdot C_{n}^{i}(\frac{1}{2})^i(\frac{1}{2})^{n - i}\right]\\
& = \sum\limits_{i = 1}^{n}\left[i\cdot C_{n}^{i}(\frac{1}{2})^{i}(\frac{1}{2})^{n - i}\right]\\
& = \frac{n}{2}\sum\limits_{i = 0}^{n - 1}\left[C_{n - 1}^{i}(\frac{1}{2})^{i - 1}(\frac{1}{2})^{n - i}\right]\\
& = \frac{n}{2}\cdot (\frac{1}{2} + \frac{1}{2})^{n - 1}\\
& = \frac{n}{2}
\end{aligned}
\]
\(Sol.\ 2\) 指示器变量分析
设事件 \(A\) 表示硬币朝上
设立指示器变量 \(X_{i}\),指示第 \(i\) 次抛掷事件 \(A\) 发生,具体为
\[X_{i} = \left\{\begin{matrix}
1,\ & A\ happens\\
0,\ & A\ not\ happens
\end{matrix}\right.
\]
仍然设朝上次数为 \(X\),易得 \(X = \sum\limits_{i = 1}^{n}X_{i}\),且 \(E(X_{i}) = Pr[X_{i}] = \frac{1}{2}\)
因此
\[\begin{aligned}
E(X) & = E(\sum_{i = 1}^{n}X_{i})\\
& = \sum_{i = 1}^{n}E(X_{i})\\
& = \frac{n}{2}
\end{aligned}
\]
\(3.\) 生日问题,设有 \(n\) 个人,一年有 \(m\) 天,求生日相同的对的期望
这个问题与如下问题等价
有 \(n\) 个元素,\(m\) 个桶,采用均匀分布的哈希映射,求碰撞数的期望值
形式化的说,记一个 \(pair\) 为 \((i,\ j)\),计算集合
\[S = \left\{(i,\ j)\mid \ i\neq j,\ H(i) = H(j)\right\}
\]
基数的期望
\(Sol.\ 1\) 常规期望分析
记 \(N = C_{n}^{2}\),表示一共有 \(N\) 个 \(pair\)
记 \(P(i)\) 表示有 \(i\) 个 \(pair\) 满足条件的概率,其中任意一个 \(pair\) 满足条件的概率均为 \(\frac{1}{m}\),于是
\[P(i) = C_{N}^{i}(\frac{1}{m})^{i}(1 - \frac{1}{m})^{N - i}
\]
于是 \(pair\) 数 \(X\) 的期望为
\[E(X) = \sum_{i = 0}^{N}i\cdot C_{N}^{i}(\frac{1}{m})^{i}(1 - \frac{1}{m})^{N - i}
\]
这个式子类似于之前硬币问题的推导,最终结果为
\[E(X) = \frac{N}{m} = \frac{n(n - 1)}{2m}
\]
\(Sol.\ 2\) 指示器变量分析
设事件 \(A\) 表示 \(pair(i,\ j)\) 满足条件
设立指示器变量 \(I(i,\ j)\),指示对于 \(pair(i,\ j)\),事件 \(A\) 发生,具体为
\[I(i,\ j) = \left\{\begin{matrix}
1,\ & A\ happens\\
0,\ & A\ not\ happens
\end{matrix}\right.
\]
易得
\[E\left[I(i,\ j)\right] = Pr[I(i,\ j)] = \frac{1}{m}
\]
设 \(X\) 为满足条件的 \(pair\) 数,则
\[X = \sum_{i = 1}^{n}\sum_{j = i + 1}^{n}I(i,\ j)
\]
则
\[\begin{aligned}
E(X) & = E\left[\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}I(i,\ j)\right]\\
& = \sum_{i = 1}^{n}\sum_{j = i + 1}^{n}E\left[I(i,\ j)\right]\\
& = N\cdot Pr[I(i,\ j)]\\
& = \frac{n(n - 1)}{2m}
\end{aligned}
\]