2023-01-03更新：

第一题我后来想到可以用Symbolic Method求解，参考后来写的英文blog: Symbolic Method to solve a probability problem.

---

刷知乎刷到一个问题

https://www.zhihu.com/question/419625606

咱看了看一时间想试试看。

1.

这个问题我第一反应竟然是Analytical Combinatorics里的cycle。经过一些简单的思考，在满足题目的条件下，合理的方案是N全排列对应的cycles里：如果存在长度大于1的cycle，则只存在一个，并且它包含1，并且按顺时针元素严格递增。这个证明这里省去了，大家想一想应该能明白。

那么接下来分情况讨论：

1. 这个cycle长度是1
2. 这个cycle长度是2
3. …
4. 这个 cycle长度是k
5. …
6. 这个cycle长度是N-1

上面是互斥事件，只需要各个击破，然后求和就得到题目的概率。考虑一般的, 这个 cycle长度是k贡献的概率，1 \rightarrow a_1 \rightarrow a_2 \rightarrow a_{k-1} \rightarrow 1 。在上面cycle的任意两点之间的位置，是乘客坐在了自己的本源位置，这些过程要扣除当安排a_i时候还剩下的选择。故而它贡献的概率是:

\sum \frac{1}{N} \frac{1}{b_i} \frac{1}{b_{i+1}}\dots... = \sum_{1<i_1<i_2\dots<i_{N-k}} \frac{1}{N!} i_1i_2\dots i_{N-k}

因此题目要我们求的概率就是:

\frac{1}{N!} (\sum_{1<i<N} i + \sum_{1<i_1<i_2<N}i_1i_2 +\dots + \sum_{1<i_1<i_2\dots < i_{N-2}})

注意到:

N! = 2*(1+2)*(1+3)*\dots *(1+N-1)

则:

\frac{N!}{2} = (1+2)*(1+3)*\dots *(1+N-1)

根据乘法原理，上式的右边展开后，就是最上面的分子。故而这个问题要求的概率就是\frac{1}{2}。

2.

设黑球b个，总共n，则\frac{{n-b \choose 2}}{{n \choose 2}}= \frac{1}{2}，展开化简：

n^2 - (4b+1)n + 2b^2+2b = 0

给定n,b都是整数，且b是偶数，令判别式是完全平方，最小的n是21.

3.

这个问题我根据《Probability: the logic of science》的知识，第一判断是有问题的，因为并没有清晰的有限模型，直接处理无限集合，讲打开无穷的烦恼。包括Gilbert Strang教授的http://www-math.mit.edu/~gs/videos/index.html 关于随机三角形的讲座，我认为也是有问题的。

不管怎样，我们尝试来解答的。套路就是求解累计分布函数，然后求导得到概率密度。随机取第一个点的夹角\theta_1, 第二个点是\theta_2, 它们都是[0,2\pi]上的均匀分布。则随机变量\theta = \theta_1 - \theta_2 = \theta_1 + (-\theta_2)的概率密度函数是U(0, 2\pi)密度函数和U(-2\pi, 0)的卷积，注意 \theta 的取值范围 [-2\pi, 2\pi] , 如下图所示:

F(s) = Prob\{S \le s\} = Prob\{ \frac{1}{2} r^2 |sin(\theta)| \le s \}

即

F(s) =Prob\{|sin(\theta)| \le \frac{2s}{r^2}\}

如果 \frac{2s}{r^2} > 1, 则 F(s) = 1 , 同时注意到面积的随机变量s范围是[0, \frac{r^2}{2}]。下面推理 \frac{2s}{r^2} \le 1 的情况。

F(s) = Prob\{ 0 \le sin(\theta) \le \frac{2s}{r^2} \} + Prob\{ -\frac{2s}{r^2} \le sin(\theta) \le 0 \}

接下来就是纯体力活了，考试时候能不错，还是挺需要训练的。

4.

经典的贝叶斯基本采样问题，logic of science的第三章有翔实的例子。设置一些符号:

• 从甲中取的俩球分别是A, B
• 事件I: 事后从乙中取了一个球是白色

我们需要计算P(A=B | I ) =\frac{ P(A=B \& I) } {P(I)} = \frac{P(A=B \& I)}{\sum_{A,B} P(A,B,I)}

P(A=B | I ) = \frac{ P(w,w,I) + P(b,b,I) }{P(w,w,I) + P(b,b,I) + P(w,b,I) + P(b,w,I)} = \frac{ P(w,w)P(I|w,w) + P(b,b)P(I|b,b) }{ P(w,w)P(I|w,w) + P(b,b)P(I|b,b) + P(w,b)P(I|w,b) + P(b,w)P(I|b,w) } = \frac{11}{41}

经知乎用户提醒，不需要考虑顺序wb和bw，我认为他说的对。上面的答案需要修改。

5.

这个问题不是和第三题一样么，怎么又来一次。先研究随机变量X的分布情况，

X = \min \{ l, 1-l \} , 其中l \sim U(0, 1)则

F(x) = Prob\{X \le x\} = 1 - Prob\{X > x\} = 1 - Prob\{ \min \{l,1-l\} > x \}

注意到 l \in [0, 1], X \in [0, \frac{1}{2}] 进一步可以有:

F(x) = 1 - Prob\{ l > x \& 1-l > x \} = 1 - Prob\{ x < l < 1-x \} = 1 - \int_{x}^{1-x}dx=2x, with\ x \in [0, \frac{1}{2}]

对应的X概率密度函数是 f(x)=2, for\ x \in [0, \frac{1}{2}]

接下来研究Y=tan(X)的累计分布函数, 可以知道Y的取值范围是[0, tan(\frac{1}{2})]

F(Y) = Prob\{Y\le y\} = Prob\{tan(X) \le y \} = Prob\{X \le arctan(y) \} = 2arctan(y)

则可以求出Y的pdf是:

f_y(y) = \frac{dF(Y)}{dy} = \frac{2}{1+y^2}

6.

根据高斯分布的线性性质，K = X+Y \sim N(0, 2)，下面求Z=cos(K)的期望和方差。本质就是求解一阶E(Z) 和二阶矩 E(Z^2) 。这个让人联想到了信号与系统的Fourier Transform (Logic of science和Analytical Combinatorics中也含有极多这样的例子).

E(Z) = \int_{-\infty}^{+\infty} cos(t) \frac{1}{2\sqrt{\pi}}e^{-\frac{t^2}{4}} dt

用微积分去处理我还真没啥直接思路。但是毕竟电子系出身，一下子就会想到Fourier Transform：F(\omega) = \int_{-\infty}^{+\infty}f(t)e^{-j\omega t} dt \implies F(0) = \int_{-\infty}^{+\infty}f(t) dt , 如此，上面的积分，就变成了如何求解乘积的Fourier Transform，时域相乘等价于频域卷积。再用一些复变函数的技巧（所谓的信号与系统的奇偶虚实特性）。

由奇函数特性， \int_{-\infty}^{+\infty} cos(t) \frac{1}{2\sqrt{\pi}}e^{-\frac{t^2}{4}} dt = 0 ，则

E(z) = \int_{-\infty}^{+\infty} (cos(t) + jsin(t)) \frac{1}{2\sqrt{\pi}}e^{-\frac{t^2}{4}} dt =\int_{-\infty}^{+\infty} e^{jt} \frac{1}{2\sqrt{\pi}}e^{-\frac{t^2}{4}} dt

其中 \mathcal{F}(e^{jt}) = 2\pi \delta(\omega-1), \mathcal{F}(\frac{1}{2\sqrt{\pi}}e^{-\frac{t^2}{4}}) = e^{-\omega^2} ，再根据频域卷积定理：

\mathcal{F}(e^{jt} \frac{1}{2\sqrt{2\pi}}e^{-\frac{t^2}{4}} ) = \frac{1}{2\pi} 2\pi \delta(\omega-1) * e^{-\omega^2} = e^{-(\omega-1)^2}

故而E(Z)=e^{-1}。

方差还可以照葫芦画瓢, 只不过用一下 cos(t) 的Fourier Transform，则E(Z^2) = \frac{e^{-4}+1}{2}。那么方差就是var(Z) = E(Z^2)-E(Z)^2 = \frac{e^{-4}+1}{2} - e^{-2}

7.

这个问题是概率密度函数的贝叶斯应用。先设 D=X+Y , 我们着手求解当D=d的时候， E(X^2|D=d) ，本质先要求解一个条件概率密度函数: f(x|d) . 根据贝叶斯公式:

f(x|d) = \frac{f(x) f(d|x)}{f(d)}

其中 f(x) = \lambda e^{-\lambda x}是指数分布的密度函数。然后D是Erlang分布，即 f(d) = \lambda^2 d e^{-\lambda d} 。花一点时间计算f(d|x)，用的技术就是这卷子好多题的重复技术，可以算出 f(d|x) = \lambda e^{-\lambda (d-x)} 。继而知道f(x|d) = \frac{1}{d}, x \in [0, d]。则

E(X^2|D=d) = \int_{0}^{d} x^2 dx = \frac{1}{3}d^2

那么E(X^2|X+Y) = \frac{1}{3}(X+Y)^2。

8.

题目问的是首次遇到加和超过1这个事情的平均等候时间。又可以请出老朋友了。还是学自普林斯顿大学教授Robert Sedgewick的课程。

首次出现的平均等候时间 = \sum_{N \ge 0} Prob\{ U_1 + U_2 + \dots + U_N \le 1 \}

专心求Prob\{ U_1 + U_2 + \dots + U_N \le 1 \} ，独立同分布的随机变量的和的概率密度就是卷积，我们恰好只求到1的积分，这就很好办了。它就是 \frac{1}{N!} ，故而

E[N] = \sum_{N\ge 0}\frac{1}{N!} = e