这题是概率论入门的好题啊，用到了条件概率公式和全概率公式，甚至还用了一点组合公式和代数式的转化

题意

盒子里有\(n\)个球，每个球为红色或者蓝色，其中红球数量\(m\in \left\{ 1..n \right\}\)等概率分布。已知在抽出并扔掉\(p\)个球的情况下有\(q\)个球是红球。问再抽一个球是红球的概率。

预备知识

首先是条件概率公式，在已知事件\(B\)发生的条件下事件\(A\)发生的概率：

\[ P\left(A\right)=\frac{P\left(AB\right)}{P\left(B\right)} \]

接下来就是全概率公式，事件\(A\)发生的概率就是各个情况\(B_k\)下事件\(A\)发生概率的和：

\[ P\left(A\right)=\sum_k{P\left( A|B_k\right)P\left(B_k\right)} \]

最后就是一个奇妙的组合公式：

\[ \sum_{k=0}^s{\binom{k}{n}\binom{s-k}{m}}=\binom{s+1}{n+m+1} \]

这个可以这么理解：要从\(s+1\)个数中选出\(n+m+1\)个数，那么\(k\)相当于在枚举第\(n+1\)个数。

解法

有了上面预备知识，下面的推导就很好理解了：

令\(A\)表示下一个球取出来是红色的，\(B\)表示一开始抽出\(p\)个球有\(q\)个是红球，\(N_k\)表示最早袋子里面有\(k\)个红球。那么：

\[ \begin{eqnarray*} P\left(A|B\right)&=&\frac{P\left(AB\right)}{P\left(B\right)} \\ &=&\frac{\sum_{k=0}^n{P\left(AB|N_k\right)P\left(N_k\right)}}{\sum_{k=0}^n{ P\left(A|N_k\right)P\left(N_k\right)}} \\ &=&\frac{\sum_{k=0}^n{P\left(A|BN_k\right)P\left(B|N_k\right)P\left(N_k\right)}}{\sum_{k=0}^n{P\left(B|N_k\right)P\left(N_k\right)}} \end{eqnarray*} \]

又因为：

\[ \begin{eqnarray*} P\left(A|BN_k\right)&=&\frac{k-q}{n-p} \\ P\left(N_k\right)&=&\frac 1{n+1} \\ P\left(B|N_k\right)&=&\frac{\binom{k}{q}\binom{n-k}{p-q}}{\binom{n}{p}} \end{eqnarray*} \]

所以

\[ \begin{eqnarray*} P\left(A|B\right)&=&\frac{\sum_{k=0}^n \binom{k}{q} \binom{n-k}{p-q} (k-q)}{\sum_{k=0}^n \binom{k}{q} \binom{n-k}{p-q} (n-p)} & (*) \\ &=&\frac{\sum_{k=0}^n \binom{k}{q+1} \binom{n-k}{p-q} (q+1)}{\sum_{k=0}^n \binom{k}{q} \binom{n-k}{p-q} (n-p)} \\ &=&\frac{q+1}{n-p} \cdot \frac{\sum_{k=0}^n \binom{k}{q+1} \binom{n-k}{p-q}}{\sum_{k=0}^n \binom k q \binom{n-k}{p-q}} \\ &=&\frac{q+1}{n-p} \cdot \frac{\binom{n+1}{p+2}}{\binom{n+1}{p+1}} \\ &=&\frac{q+1}{p+2} \end{eqnarray*} \]

非常神奇吧，看起来十分复杂的题目竟然最后的答案如此简单。其实我推到\((*)\)式的时候，以为要用各种数论变换处理，把复杂度降到O(n)。后来才发现，这题没有mod，而且原来竟然有更神奇的代数变换和组合数变换。

这题是在太神！

代码

1
2
3
4
5
6
7
8

#include <stdio.h>
main(void)
{
  int n, p, q, T = 0;
  while (scanf("%d%d%d", &n, &p, &q) != EOF)
    printf("Case %d: %.4f\n", ++T, (q+1.)/(p+2));
  return 0;
}

后记

其实这篇题解跟贾教的题解差不多，原因是就是看着他题解做的……Orz贾教

那么本文的目的是什么呢，其实只是\(\LaTeX\)测试而已。