记录答疑过程中遇到的一些有趣的问题

不独立但同分布的情况

先考虑一个相对简单的题目,掌握方法后可尝试接下来的题目(答案见文末)。

Q1-1: \(n\) 个球放入 \(n\) 个盒子,球和盒子都标号 1-n,问球的编号和盒的编号相同的个数的期望和方差。

A1-1: 记 \(X_i\) 是第 \(i\) 个球是否放入第 \(i\) 个盒子,则总个数 \(Y=\sum_{i=1}^{n}X_i\)。注意到 \(X_i\) 同分布(但不独立),故 \(\mathbb{E}[Y] = n\mathbb{E}[X_1]\)。不难证明第 \(i\) 个球放入第 \(i\) 个盒子的概率是 \(1/n\),故 \(\mathbb{E}[X_1]=\mathbb{P}(X_1=1)=1/n\),进而 \(\mathbb{E}[Y]=1\)。 为求方差,需求 \(\mathbb{E}[Y^2]=\mathbb{E}[(\sum_{i=1}^{n}X_i)(\sum_{i=1}^{n}X_i)]\),故需要考虑 \(\mathbb{E}[X_iX_j]\)。根据此题背景,需要考虑两个情况

  • \(i=j\),此时 \(\mathbb{E}[X_iX_j]=\mathbb{P}[X_i=1]=1/n\),共有 \(n\) 对。
  • \(i\neq j\),此时 $[X_iX_j]=[X_i=1X_j=1] 为 第 \(i\) 个球和第 \(j\) 个球同时放对的,是 \(1/n(n-1)\)。共有 \(n(n-1)\) 对。

不难验证 \(X_iX_j\) 一共有 \(n^2\) 对,恰好为 \(n + n(n-1)\),故已经不重不漏地讨论完了。 此时 \(\mathbb{E}[Y^2] = n*\dfrac{1}{n}+n(n-1)*\dfrac{1}{n(n-1)}=2\), \(\text{Var}[Y] = 1\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def simulate(n, k=10000):
def _simulate(n):
arr = list(range(n))
import random
random.shuffle(arr)
return sum(arr[i] == i for i in range(n))
tmp = [_simulate(n) for _ in range(k)]
from statistics import mean, variance
return mean(tmp), variance(tmp)

def calculate(n):
return 1, 1

n = 10
print(simulate(n), calculate(n))

Q1-2: \(n\) 个男生 \(m\) 个女生随机排成一列,有 \(n+m-1\) 个相邻的配对,问配对中性别不同的个数的期望和方差。

Q1-3: 一个公交车在初始有 \(n\) 个乘客,中途只下不上。每个乘客独立随机地从 \(m\) 个站中选1个下。如果某站没有乘客下车,则公交车不停靠,问停靠次数的期望和方差。

Q1-4: n个顶点的随机图,任意两个顶点间有概率 \(p\) 连边,问形成的三角形的数目的期望和方差。

三角形/圆相关

ToDo

动态规划相关

Q3-1 不断投掷一枚硬币直至出现正面停止,每次结果独立且正面的概率为 \(0<p<1\),求投掷次数的期望。

A3-1 记投掷次数为 \(X\),第一次投掷结果是否为正面为 \(Y\)。由重期望公式有 \(\mathbb{E}[X]=\mathbb{E}[\mathbb{E}[X\mid Y]]=P(Y=1)\mathbb{E}[X\mid Y=1]+P(Y=1)\mathbb{E}[X\mid Y=0]\)。当 \(Y=1\)时,游戏停止,此时投了1次硬币。当 \(Y=0\)时,游戏回到了起点,需要投掷 \(1+Z\) 次,其中 \(Z\)\(X\) 同分布。因此,\(\mathbb{E}[X\mid Y=1]=1,\mathbb{E}[X\mid Y=0]=1+\mathbb{E}[Z]=1+\mathbb{E}[X]\)。带入式子中得 \(\mathbb{E}[X]=p*1+(1-p)*(1+\mathbb{E}[X])=1+(1-p)\mathbb{E}[X]\)\(\mathbb{E}[X]=1/p\)

注:其实该分布为几何分布,因此读者应该对这一结论并不感到意外。但从这个视角看这个过程,可能会更好地理解这一系列相关的题目。

注2:另一个视角是,我们从初始状态出发,首先扔了一次硬币,然后有 \(p\) 的概率出现正面,不再抛掷;有 \(1-p\) 的概率出现正面,回到初始状态。因此我们直接设 \(E\) 为从初始状态出发,到结束时投掷次数的期望,则有方程 \(E=1+p*0+(1-p)*E\Rightarrow E=1/p\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def simulate(p, k=10000):
def _simulate(p):
result = []
import random
while True:
result.append(random.random() < p)
if result[-1]:
break
return len(result)
tmp = [_simulate(p) for _ in range(k)]
from statistics import mean
return mean(tmp)

def calculate(p):
return 1/p

p = 0.7
print(simulate(p), calculate(p))

Q3-2: 不断投掷一枚硬币直至出现连续两次正面则停止,每次结果独立且正面的概率为 \(0<p<1\),求投掷次数的期望。(应至少有3个状态:空/反、正、正正,其中到达正正时游戏结束。设出每个状态到达正正结束时次数的期望,解方程组)

Q3-3: 不断投掷一枚硬币直至出现连续两次相同则停止,每次结果独立且正面的概率为 \(0<p<1\),求投掷次数的期望。(应至少有3个状态:空、正、反、正正,反反)

随机过程相关

ToDo

多元正态相关

预备知识1:如果 \(\boldsymbol{X}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma)\), 则 \(\boldsymbol{b+AX}\sim\mathcal{N}(\boldsymbol{b+A\mu},\boldsymbol{A}\Sigma\boldsymbol{A}^\intercal)\)

预备知识2:如果 \(\begin{pmatrix}\boldsymbol{X_1}\\\boldsymbol{X_2}\end{pmatrix}\sim\mathcal{N}\left(\begin{pmatrix}\boldsymbol{\mu_1}\\\boldsymbol{\mu_2}\end{pmatrix},\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{pmatrix}\right)\), 则给定 \(\boldsymbol{X_1}=\boldsymbol{x_1}\) 下,\(\boldsymbol{X_2}\) 条件分布为\(\mathcal{N}(\boldsymbol{\mu_2}+\Sigma_{21}\Sigma_{11}^{-1}(\boldsymbol{x_1}-\boldsymbol{\mu}),\Sigma_{22}-\Sigma_{21}\Sigma_{11}^{-1}\Sigma_{12})\)

Q5-1 已知 \(\begin{pmatrix}X\\Y\end{pmatrix}\sim\mathcal{N}\left(\begin{pmatrix}0\\0\end{pmatrix},\begin{pmatrix}\sigma^2&\rho\sigma^2\tau^2\\\rho\sigma^2\tau^2&\tau^2\end{pmatrix}\right)\),求 \(\mathbb{E}[X\mid X+Y=z]\)\(\text{Var}[X\mid X+Y=z]\)

排列组合相关

Q6-1 放球问题(详细答案见文末)

  • \(n\) 个球有区别,\(m\) 个盒子有区别,允许有空盒(简单的排列组合)
  • \(n\) 个球有区别,\(m\) 个盒子有区别,不允许有空盒(先考虑第四问)
  • \(n\) 个球有区别,\(m\) 个盒子无区别,允许有空盒(没有太好的形式)
  • \(n\) 个球有区别,\(m\) 个盒子无区别,不允许有空盒(没有太好的形式)
  • \(n\) 个球无区别,\(m\) 个盒子有区别,允许有空盒(隔板法)
  • \(n\) 个球无区别,\(m\) 个盒子有区别,不允许有空盒(隔板法)
  • \(n\) 个球无区别,\(m\) 个盒子无区别,允许有空盒(母函数法)
  • \(n\) 个球无区别,\(m\) 个盒子无区别,不允许有空盒(母函数法)

答案

A1-2: 记 \(X_i\) 是第 \(i\) 个配对的性别是否不同,则总个数 \(Y=\sum_{i=1}^{n+m-1}X_i\)。注意到 \(X_i\) 同分布(但不独立),故 \(\mathbb{E}[Y] = (n+m-1)\mathbb{E}[X_1]\)。不难证明每个配对都是从 \((n+m)(n+m-1)\) 种配对中等概率的选一种,其中性别不同的有 \(2nm\) 种,故 \(\mathbb{E}[X_1]=\mathbb{P}(X_1=1)=\dfrac{2nm}{(n+m)(n+m-1)}\),进而 \(\mathbb{E}[Y]=\frac{2nm}{(n+m)}\)。 为求方差,需求 \(\mathbb{E}[Y^2]=\mathbb{E}[(\sum_{i=1}^{n+m-1}X_i)(\sum_{i=1}^{n+m-1}X_i)]\),故需要考虑 \(\mathbb{E}[X_iX_j]\)。根据此题背景,需要考虑三个情况

  • \(i=j\),此时 \(\mathbb{E}[X_iX_j]=\dfrac{2nm}{(n+m)(n+m-1)}\),共有 \(n+m-1\) 对。
  • \(\lvert i-j\rvert > 1\),此时两组配对无交集,是从 \((n+m)(n+m-1)(n+m-2)(n+m-3)\) 中均匀抽出,其中两组性别不同的有 \(4nm(n-1)(m-1)\) 种,故 \(\mathbb{E}[X_iX_j]=\dfrac{4nm(n-1)(m-1)}{(n+m)(n+m-1)(n+m-2)(n+m-3)}\),共有 \((n+m-2)(n+m-3)\) 对。
  • \(\lvert i-j\rvert = 1\),此时两组配对邻接,是从 \((n+m)(n+m-1)(n+m-2)\) 中均匀抽出,其中两组性别不同的有 \(nm(n-1)+mn(m-1)\) 种,故 \(\mathbb{E}[X_iX_j]=\dfrac{mn(m+n-2)}{(n+m)(n+m-1)(n+m-2)}\),共有 \(2(n+m-2)\) 对。

此时 \(\mathbb{E}[Y^2] = \dfrac{2nm(2nm-1)}{(n+m)(n+m-1)}\), \(\text{Var}[Y] = \dfrac{2nm(2nm-m-n)}{(n+m)^2(n+m-1)}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def simulate(n, m, k=10000):
def _simulate(n, m):
a = ['0'] * n + ['1'] * m
import random
random.shuffle(a)
return sum(a[i-1] != a[i] for i in range(1, n+m))
tmp = [_simulate(n,m) for _ in range(k)]
from statistics import mean, variance
return mean(tmp), variance(tmp)

def calculate(n, m):
return 2*n*m / (n + m), 2*n*m * (2*n*m - m - n) / ((n + m)**2 * (n + m - 1))

n, m = 12, 8
print(simulate(n, m), calculate(n, m))

A1-3: 记 \(X_i\) 是第 \(i\) 站是否停靠,而 \(P(X_i=0)=(\frac{m-1}{m})^n\),故 \(\mathbb{E}[X_i]=P(X_i=1)=1-(\frac{m-1}{m})^n\),进而 \(\mathbb{E}[\sum_{i=1}^{m}X_i]=m(1-(\frac{m-1}{m})^n)\)。下考察 \(\mathbb{E}[X_iX_j]\),一共有 \(m^2\) 对,其中

  • \(i=j\),此时\(\mathbb{E}[X_iX_j]=\mathbb{E}[X_i]=(1-(\frac{m-1}{m})^n)\),共有 \(m\) 对。
  • \(i\neq j\),此时\(\mathbb{E}[X_iX_j]=1-2*(\frac{m-1}{m})^n+(\frac{m-2}{m})^n\),共有 \(m(m-1)\) 对。

此时 \(\mathbb{E}[Y^2] = m(1-(\frac{m-1}{m})^n)+m(m-1)(1-2*(\frac{m-1}{m})^n+(\frac{m-2}{m})^n)\), \(\text{Var}[Y] = m(\frac{m-1}{m})^n-m^2(\frac{m-1}{m})^{2n}-m\frac{m-2}{m})^n+m^2\frac{m-2}{m})^n\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def simulate(n, m, k=10000):
def _simulate(n, m):
import random
a = [random.randint(1, m) for _ in range(n)]
return len(set(a))
tmp = [_simulate(n,m) for _ in range(k)]
from statistics import mean, variance
return mean(tmp), variance(tmp)

def calculate(n, m):
t1 = (\frac{m-1}{m})**n
t2 = (\frac{m-2}{m})**n
return m * (1 - t1), m*t1 - m*m*t1*t1 - m*t2 + m*m*t2

n, m = 12, 8
print(simulate(n, m), calculate(n, m))

A1-4: 记 \(X_{ijk}\) 是顶点 \(i,j,k\) 是否构成三角形,\(P(X_{ijk}=1)=p^3\),故所求期望为 \(\binom{n}{3}p^3\)。 下考察 \(\mathbb{E}[X_{ijk}X_{i'j'k'}]\),一共有 \(\binom{n}{3}*\binom{n}{3}\) 对,其中

  • \(\{i,j,k,i',j',k'\} 内有三个元素\),此时共有三条边,\(\mathbb{E}[X_iX_j]=p^3\),共有 \(\binom{n}{3}\) 对。
  • \(\{i,j,k,i',j',k'\} 内有四个元素\),此时共有五条边,\(\mathbb{E}[X_iX_j]=p^5\),共有 \(\binom{n}{2}\binom{n-2}{1}\binom{n-3}{1}=12\binom{n}{4}\) 对。
  • \(\{i,j,k,i',j',k'\} 内有五个元素\),此时共有六条边,\(\mathbb{E}[X_iX_j]=p^6\),共有 \(\binom{n}{1}\binom{n-1}{2}\binom{n-3}{2}=30\binom{n}{5}\) 对。
  • \(\{i,j,k,i',j',k'\} 内有六个元素\),此时共有六条边,\(\mathbb{E}[X_iX_j]=p^6\),共有 \(\binom{n}{3}\binom{n-3}{3}=20\binom{n}{6}\) 对。

此时 \(\text{Var}[Y] = \binom{n}{3} p^3+12\binom{n}{4}p^5+(30\binom{n}{5}+20\binom{n}{6}-\binom{n}{3}\binom{n}{3})p^6\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def simulate(n, p, k=10000):
def _simulate(n, p):
import random
a=[[0]*n for j in range(n)]
for i in range(n):
for j in range(i+1, n):
a[i][j] = a[j][i] = random.random() < p
return sum(a[i][j]+a[j][k]+a[k][i] == 3 for i in range(n) for j in range(i+1,n) for k in range(j+1, n))
tmp = [_simulate(n, p) for _ in range(k)]
from statistics import mean, variance
return mean(tmp), variance(tmp)

def calculate(n, p):
import math
def nCr(n,r):
if n < r:
return 0
f = math.factorial
return f(n) // f(r) // f(n-r)
return nCr(n, 3) * p**3, nCr(n, 3) * p**3 + 12 * nCr(n, 4) * p**5 + (30*nCr(n,5)+20*nCr(n,6)-nCr(n,3)*nCr(n,3)) * p**6

n, p = 8, 0.7
print(simulate(n, p), calculate(n, p))

A3-2: 设从空、正出发的期望次数分别是 \(X\)\(Y\),则有关系 \(X=1+pY+(1-p)X\)\(Y=1+(1-p)X\)\(X=(1+p)/p^2\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def simulate(p, k=10000):
def _simulate(p):
import random
result = [random.random() < p]
while True:
result.append(random.random() < p)
if result[-1] and result[-2]:
break
return len(result)
tmp = [_simulate(p) for _ in range(k)]
from statistics import mean
return mean(tmp)

def calculate(p):
return (1+p)/p/p

p = 0.7
print(simulate(p), calculate(p))

A3-3: 设从空、正、反出发的期望次数分别是 \(Z,X,Y\),则有关系 \(Z=1+pX+(1-p)Y\)\(X=1+(1-p)Y\)\(Y=1+pY\)。解得 \(X=\dfrac{2-p}{1-p+p^2}\)\(Y=\dfrac{1+p}{1-p+p^2}\)\(Z=\dfrac{2+p-p^2}{1-p+p^2}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def simulate(p, k=10000):
def _simulate(p):
import random
result = [random.random() < p]
while True:
result.append(random.random() < p)
if result[-1] == result[-2]:
break
return len(result)
tmp = [_simulate(p) for _ in range(k)]
from statistics import mean
return mean(tmp)

def calculate(p):
return (2+p-p*p)/(1-p+p*p)

p = 0.7
print(simulate(p), calculate(p))

A6-1

  • \(n\) 个球有区别,\(m\) 个盒子有区别,允许有空盒(\(m^n\)
  • \(n\) 个球有区别,\(m\) 个盒子有区别,不允许有空盒(\(m!S(n,m)\)
  • \(n\) 个球有区别,\(m\) 个盒子无区别,允许有空盒(\(\sum_{i=1}{\min\{n,m\}}S(n,m)\)
  • \(n\) 个球有区别,\(m\) 个盒子无区别,不允许有空盒(\(S(n,m)\)
  • \(n\) 个球无区别,\(m\) 个盒子有区别,允许有空盒(\(\binom{n+m-1}{m-1}\)
  • \(n\) 个球无区别,\(m\) 个盒子有区别,不允许有空盒(\(\binom{n-1}{m-1}\)
  • \(n\) 个球无区别,\(m\) 个盒子无区别,允许有空盒(\(\dfrac{1}{(1-x)(1-x^2)\cdots(1-x)^m}\)展开后 \(x^n\)系数)
  • \(n\) 个球无区别,\(m\) 个盒子无区别,不允许有空盒(\(\dfrac{x^m}{(1-x)(1-x^2)\cdots(1-x)^m}\)展开后 \(x^n\)系数)