【Note】 一些有趣的概率论问题

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

不独立但同分布的情况

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

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

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

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

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\) 个盒子无区别，不允许有空盒（母函数法）

采样相关

Q7-1 存在一样本大小为 \(N\) 的样本，记为 \(a_1,a_2,\ldots,a_N\). 样本均值为 \(\mu=\sum_i a_i / N\)，样本方差为 \(\sigma^2=\sum_i (a_i-\mu)^2 / N\)。现从中(无放回地)采样出 \(n\) 个样本 (\(n\le N\))，问采样结果的均值和方差是多少。

杂题

Q8-1 记\((N)_k=N(N-1)\cdots(N-k+1)=N!/(N-k)!\) 证明 \(\sum_{k=1}^{N}\dfrac{k (N)_k}{N^{k+1}}=1\) ## 答案

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

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

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

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

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

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

A7-1

视角一：将选出的样本记为 \(X_1,\ldots,X_n\) 视为随机变量，则有 \(X_i\) 不独立但同分布：\(P(X_i=a_1)=P(X_i=a_2)=\ldots=P(X_i=a_N)=1/N, \forall i\)

\(\mathbb{E}[X_i]=\sum_{k=1}^{N} 1/N*a_k, \mathbb{E}[X_i^2]=\sum_{k=1}^{N}1/N*a_k^2=\sum_k a_k^2/N\)

\(\mathbb{E}[X_iX_j]=\sum_{k\ne l} a_ka_l / N(N-1)\)

而 \(N\mu=\sum_{k=1}^{N} a_k,\quad N\sigma^2=\sum_{k=1}^{N}(a_k-\mu)^2=\sum_{k=1}^{N}a_k^2-N\mu^2,\quad N^2\mu^2=\sum_{k,l}a_ka_l\)

故 \(\mathbb{E}[X_i]=\mu,\mathbb{E}[X_i^2]=\mu^2+\sigma^2,\mathbb{E}[X_iX_j]=(N^2\mu^2-(N\mu^2+N\sigma^2))/N(N-1)=\mu^2-\sigma^2/(N-1)\)

则\(\mathbb{E}[Y]=\sum_{i=1}^{n}\mathbb{E}[X_i]=n\mu\)

\(\mathbb{E}[Y^2]=n \mathbb{E}[X_i^2]+n(n-1)\mathbb{E}[X_iX_j]=n(\mu^2+\sigma^2)+n(n-1)(\mu^2-\sigma^2/(N-1))=n^2\mu^2+n(1-\frac{n-1}{N-1})\sigma^2\)

\(\text{Var}(Y)=\mathbb{E}[Y^2]-\mathbb{E}[Y]^2=\frac{N-n}{N-1}n\sigma^2\)

视角二：使用指示变量表示选出的结果。记 \(I_k\in \{0,1\}\) 表示 \(a_k\) 是否被选，则 \(I_k\) 同分布 (\(P(I_k=1)=n/N\)) 。所求为 \(Y=\sum_{k=1}^N a_kI_k\)

\(\mathbb{E}[Y] = \sum_{k=1}^{N}\mathbb{E}[a_kI_k]=\sum_{k=1}^{N}a_k\mathbb{E}[I_k]=\sum_{k=1}^{N}\frac{n}{N}a_k=\frac{n}{N}*N\mu=n\mu\)

为考察方差，注意到 \(\mathbb{E}[I_k^2]=n/N\), \(\mathbb{E}[I_kI_l]=\frac{n(n-1)}{N(N-1)}, (k\neq l)\)

且\(N^2\mu^2=(\sum_{k=1}^{N}a_k)^2=\sum_{i=1}^{N}\sum_{j=1}^{N}a_ia_j\), \(N\sigma^2=\sum_{k=1}^{N}(a_k-\mu)^2=\sum_{k=1}^{N} a_k^2-N\mu^2\) \[ \mathbb{E}[Y^2]=\sum_{k=1}^{N}a_k^2\mathbb{E}[I_k^2]+\sum_{k\neq l} a_ka_l\mathbb{E}[I_kI_l]=\frac{n}{N}\sum_k a_k^2+\frac{n(n-1)}{N(N-1)}\sum_{k\ne l} a_ka_l\\=\frac{n}{N}(N\mu^2+N\sigma^2)+\frac{n(n-1)}{N(N-1)}(N^2\mu^2-N\sigma^2-N\mu^2)\\=n^2\mu^2+\frac{n(N-n)}{N-1}\sigma^2 \] \(\text{Var}[Y]=\mathbb{E}[Y^2]-\mathbb{E}[Y]^2=\frac{N-n}{N-1}n\sigma^2\)

A8-1

解法一：考虑从编号1-N的球进行有放回抽样，直至抽到之前抽过的球停止。不难知最少抽两次即停止（第二次和第一次抽到一样的球），最多抽 \(N+1\) 次停止（前 \(N\) 次抽到 \(N\) 个不同的球，最后一次一定会抽到之前抽过的球。记 \(p_k\) 为停止时，之前抽的球的数量，则 \(\sum_{k=1}^{N}p_k=1\). 而 \(p_k\) 表示前 \(k\) 次都未重复，第 \(k+1\) 次重复，其概率不难计算为 \(p_k=\frac{N}{N}\cdot\frac{N-1}{N}\cdots\frac{N-k+1}{N}\cdot {k}{N}=\frac{k\cdot (N)_k}{N^{k+1}}\). 得证

解法二：注意到 \(\frac{k(N)_k}{N^{k+1}}=\frac{(N)_k}{N^k}-\frac{(N)_{k+1}}{N^{k+1}}\), 得\(\sum_{k=1}^{N}\frac{k(N)_k}{N^{k+1}}=\frac{(N)_1}{N^1}-\frac{(N)_{N+1}}{N^{N+1}}=1\)