记录答疑过程中遇到的一些有趣的问题。其实比起“正统”的概率论问题来说是挺简单的,但因为这些大多有一些生活背景所以比较有趣。

不独立但同分布的情况

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

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\) 连边,问形成的三角形的数目的期望和方差。

三角形/圆相关

Q2-1 线段均与取两点,得到的三段构成三角形的概率。

Q2-3 圆周上均匀取三点,问构成钝角三角形的概率。

Q2-4 圆周上均匀取三点,问构成的最大角的分布。

动态规划相关

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

A3-1 记投掷次数为 \(X\),第一次投掷结果是否为正面为 \(I\)。注意此时 \(I\) 为二元变量,且 \(\mathbb{E}[I^2]=\mathbb{E}[I]=\mathbb{P}[I=1]=p\)。 根据投掷情况,若投掷出正面,则停止,此时投掷了一次。否则游戏回到原点,需投 \(X\) 次,故需投掷 \(1+X\) 次。故 \(X=I\times 1+(1-I)\times (1+X)\)。 由于当前投掷的一次不可避免,我们一般会写为 \(X=1 + I\times 0+(1-I)\times X = 1 + (1-I)\times X\) 更为简洁直观。 基于该关系式,我们可以很容易的算出期望和方差(注意 \(I\)\(X\) 独立) \(\mathbb{E}[X]=1+(1-p)\mathbb{E}[X]\Rightarrow \mathbb{E}[X] = 1/p\) \(\text{Var}[X]=\text{Var}[(1-I)X]=\mathbb{E}[((1-I)X)^2]-(\mathbb{E}[(1-I)X])^2=\mathbb{E}[(1-I)^2]\mathbb{E}[X^2]-(\mathbb{E}[(1-I)X])^2\)\(=(1-p)\mathbb{E}[X^2]-(1-p)^2\mathbb{E}[X]^2=(1-p)\text{Var}[X]+(p-p^2)\mathbb{E}[X]^2\)\(\text{Var}[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):
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, variance
return mean(tmp), variance(tmp)

def calculate(p):
return 1/p, (1-p)/p/p

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

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

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

随机过程相关

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]\)

Q5-2 已知 \(X,Y\) 独立且服从标准正态分布,设 \(Z=\mathbb{E}[X\mid (3X-Y+2)]\),求 \(\mathbb{E}[Z], \text{Var}[Z], \mathbb{E}[YZ]\)

A5-2 (解一) 我们不用什么结论,直接用正交变换来做这一题。令 \(U=(3X-Y)/\sqrt{10}, V=(X+3Y)/\sqrt{10}\)\(U,V\) 也独立且服从标准正态分布,且

\(Z=\mathbb{E}[(3U+V)/\sqrt{10}\mid \sqrt{10}U+2]=3U/\sqrt{10}\)。因此 \(\mathbb{E}[Z]=0\), \(\text{Var}(Z)=9\text{Var}(U)/10=9/10\)\(\mathbb{E}[YZ]=\mathbb{E}[Y\cdot (9X-3Y)/10]=-3/10\)

(解二)令 \(A=3X-Y+2\),则\(\mathbb{E}[A]=2\)\(\text{Var}[A]=10\) \(\text{Cov}[AX]=\mathbb{E}[AX]=3\)

\(\begin{pmatrix}X\\A\end{pmatrix}\sim\mathcal{N}\left(\begin{pmatrix}0\\2\end{pmatrix},\begin{pmatrix}1&3\\3&10\end{pmatrix}\right)\) 则有条件期望

\[ X\mid_{A=a}\sim\mathcal{N}\left(0+\dfrac{3}{10}(a-2), 1-3\cdot\dfrac{1}{10}\cdot 3\right)=\mathcal{N}\left(\dfrac{3(a-2)}{10},\dfrac{1}{10}\right) \]\(Z=\dfrac{3}{10}(A-2)\) 进而得 \(\mathbb{E}[Z]=0,\text{Var}[Z]=9\text{Var}[A]/100=9/10\)

\(\mathbb{E}[YZ]=\mathbb{E}[Y\cdot\frac{3}{10}(3X-Y)]=-3/10\)

排列组合相关

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\)系数)