【数理知识】概率论试题（一）
【数理知识】概率论试题（一）
6Young1 确定与随机
问题
设你和朋友玩一个游戏，规则如下：
1、桌子上有7颗棋子，你们二人轮流拿走一定数量，最终谁先拿走最后一颗棋子的人获胜；
2、你的朋友相信随机，在他的回合里，他可以投掷一枚6面子，并拿走对应数目的棋子（如果剩下的棋小于这个数目则全部拿走)；
3、你不喜欢随机，因此在你的回合里可以自行决定拿走1颗棋子或2颗棋子，但是不能不拿，同时你可以选择先走或后走那么在最优决策的情况下你的获胜几率是多少？
解答
首先最优决策的情况一定是选择后手，且每次只拿1颗棋子，除非到你的回合时场上只剩1-2颗棋子，此时可以全部拿走获胜，因为在没有把握决胜时，给对方回合留的棋子越少，你失败的概率更高。
定义轮到你时，如果还剩$n$个棋子，胜率为$p_n$。则易得：$p_1 = p_2 = 100%$
$n=3$时，你拿1，对方拿1，你再拿1才能胜利，即：$p_3 = \frac{1}{6}p_1=\frac{1}{6}$
同理$p_4 = \frac{1}{6}p_1+\frac{1}{6}p_2=\frac{2}{6}$
可以得到规律：$p1=p2=1， p_n=\frac16\sum\limits_1^{n-2}p_i$
所以$p_{win}=\sum\limits_1^6p_i=\frac{59}{108}$
2 切分三角形
问题
一个等边三角形，一定能够分成n个等腰三角形，其中n大等于3。
解答
首先，我们可以将任意一个等边三角形分为3个120°的等腰钝角三角形；也可以将之分为4个等边三角形。
而其中120°的等腰钝角三角形可以分为2个120°的等腰钝角三角形和一个等边三角形。
所以从图1情况出发，我们一定可以分出2n+1(n≥1)个三角形。
而从图2情况出发，再将其中的等边三角形按照图一方式切割，一定能分出2n(n≥2)个三角形。
两者结合，就证明一个等边三角形，一定能够分成n(n≥3)个等腰三角形。
3 交换次数期望
问题
对于$n$个不相同的数$a_1,a_2, …, a_n$。用如下算法得到其中最大值$m$：令$m=a_1$(算作一次赋值)，依次将$m$与$a_2,a_3, …, a_n$比较，若$a_i>m$，则令$m=a_i$，求对$m$做赋值操作次数的期望。
解答
令$E_n$为$n$个数时，$m$的期望，那么若$a_n=\max\limits_{i=1}^n(a_i)$，那么$E_n=E_{n-1}+1$，若$a_n\neq\max\limits_{i=1}^n(a_i)$，那么$E_n=E_{n-1}$
所以容易得出：$E_n = \frac{1}{n}(E_{n-1}+1)+\frac{n-1}{n}E_{n-1}$并且有$E_1=1$，所以$E_n=\sum_\limits{i=1}^n\frac{1}{i}$
4 样品检查
问题
假设有200瓶测试样品（每个样品不限量），其中一瓶是有毒的，如果我们的检验试剂混合了有毒的测试样品，在20mm内会变为黑色（没有变色的检测试剂可以重复使用，变色后的不可使用）。试问如果我们想在1h内快速找到有毒的测试样品至少需要多少瓶检验试剂？
解答
1h内一瓶试剂最多可以测试3组，如果这3组都没毒，那么第4组有毒。$4^3=64<200<4^4=256$所以4瓶试剂即可。
为了更好理解这一结论，我们用14个样品来做检验，将他们用4进制方式进行编号如下：
14个：00 01 02 03 10 11 12 13 20 21 22 23 30 31
| 试剂1 | 试剂2 | |
|---|---|---|
| 轮次1 | 10 11 12 13（黑，锁定第一位编号为1） | 01 11 21 31 |
| 轮次2 | 不能用了 | 02 12 22 |
| 轮次3 | 不能用了 | 03 13 23（三轮都不黑，锁定第二位编号为0） |
如此就可以检验出有毒的一瓶，本质上就是依此检验四进制编号的各个位置，哪个“百位”有毒？哪个“十位”有毒？哪个“个位”有毒？最终锁定一组有毒的“个十百”就锁定了有毒的样品。
5 拿取棋子
问题
你和你的朋友玩一个小游戏，每个人轮流从桌上2023枚棋子中拿走2^n个(1,2,4,8,16等等)，拿走最后1枚棋子的人获胜，请问是否存在一个必胜的策略（谁先开始也没有确定)？
解答
1+2=3；2+4=6；4+8=12均为3的倍数，因此，如果我们能保证我们每次拿取后保证剩余3的倍数个棋子即可。
而2023并不是3的倍数，因此我们要先拿（比如4个），那么剩余2019个，是3的倍数，我们就必胜了。
6 相关系数-证明
问题
设随机变量$X_1, X_2, …, X_n$两两之间的相关系数都是$\rho$，求证：$\rho\geq-\frac{1}{n-1}$
解答
$$
\begin{align*}
&\because 0 \leq Var(\sum\limits_{i=1}^nx_i) \
&\therefore 0 \leq \sum\limits_{i=1}^n{(Var(x_i))} + 2\rho\sum\limits_{i\lt j}(\sqrt {Var(x_i)Var(x_j)}) \
&\because 2\sqrt{xy} \leq x+y\
&\therefore 2\rho\sum\limits_{i\lt j}(\sqrt {Var(x_i)Var(x_j)}) \leq \rho\sum\limits_{i\lt j}(Var(x_i)+Var(x_j)) \
&\therefore 2\rho\sum\limits_{i\lt j}(\sqrt {Var(x_i)Var(x_j)}) \leq \rho(n-1)\sum\limits_{i=1}^n(Var(x_i)) \
&\therefore 0 \leq (1+\rho(n-1))\sum\limits_{i=1}^n{(Var(x_i))} \
&\because \sum\limits_{i=1}^n{(Var(x_i))} \geq 0 \
&\therefore 1+\rho(n-1) \geq 0 \
&\therefore \rho \geq -\frac{1}{n-1}
\end{align*}
$$
7 四因数平方和
问题
对所有的$n$，使得$n$可以表示为其最小四个因数平方值和（注：1也是因数，且因数不必为质因数）
解答
- 假设$n$为奇数：
则$n$的因数$a$、$b$、$c$、$d$一定均为奇数。
根据题意，有如下关系成立：$n=a^2+b^2+c^2+d^2$为偶数，与假设矛盾。
假设$n$为偶数：
那么$n$一定有因数1和2，所以有$n=1^2+2^2+c^2+d^2=5+c^2+d^2$成立，且$c$与$d$奇偶性不同。不妨设$c$为奇数，$d$为偶数，那么：
假设$n$不为4的倍数，那么$n=2c=1d$，所以$n=5+c^2+(2c)^2=5(1+c^2)$，说明$n$有一个因数5，即$c$最大为5。
若$c=3$，$n=50$不成立；
若$c=5$，$n=130$，$(130=1^2+2^2+5^2+10^2)$成立。
假设n为4的倍数，那么$n$有因数$d=4$，即$n=5+4^2+c^2=21+c^2$。
有$\frac{21+c^2}{c}$为整数，即$c=3 or 7$，带入显然不成立。
综上所述，$n=130$。
8 半圆相交
问题
平面上等距离分布着无数条平行直线，随机扔一个半径为$\frac12$的半圆，求半圆和直线相交的概率。
解答
- 首先计算一条长为1的线段与平行线相交的概率：
$$
P=\frac{\int_0^{\frac\pi2}\sin\theta d\theta}{\frac\pi2}=\frac{2}{\pi}
$$
两个半圆A、B（各自包含边）组合成的圆与直线相交的概率为1。
利用容斥原理计算可得：
$$
\begin{align}
P(A \cup B) &= P(A) + P(B)-P(A \cap B) \
1 &= 2P(A)+\frac{2}{\pi} \
P(A) &= \frac{\pi-2}{2\pi}\end{align}
$$
9 回归中的系数约束
问题
岭回归和Lasso回归都通过引入正则项控制模型复杂度，它们的正则项有什么区别，有哪些不同的作用？（例如，在特征选择方面：在多重共线性处理方面）
解答
Ridge的正则项$\frac{\lambda}{2}\sum\limits_{j=1}^p \beta_j^2$是L2的，而Lasso的正则项$\lambda\sum\limits_{j=1}^p|\beta_j|$是L1的。两者都相当于在OLS的基础上加了一定前提条件。
结合上图可得到：Lasso的边界是直线，而Ridge的边界是圆。当最优点不落在边界上时，相当于没有进行正则项约束的OLS方法。当最优点落在边界上时（原有的OLS最佳点在边界外），因为原有的OLS中有平方项，可以看做向外扩张的椭圆，与直线的交点可能在坐标轴上，而与圆的交点则不会。因此Lasso往往倾向于将某些$\beta_j$缩减到0（当$\lambda$足够大时），相当于忽略某些特征，有利于特征筛选和降低模型复杂度：而Ridge不会有这样的能力（特征选择方面）。
当自变量有多重共线性时，Lasso可能会直接将其中的一个自变量系数变为0，而Ridge倾向于降低它们的系数以增强泛化性能（处理多重共线性方面）。总之，在特征筛选方面，Lasso强于Ridge，但当模型需要更强的复杂度或解释度时，Ridge的精度不一定会低于Lasso。
10 逐步回归
问题
逐步回归主要有哪些做法，它们分别是怎样处理特征的？
解答
向前逐步选择：从零开始，将自变量一个个引入模型，引入自变量时看结果是否有显著性变化，有则保留变量，无则删除。
向后逐步选择：先将所有变量放入模型，然后尝试将变量一一删除，查看删除后结果是否有显著性变化，如果没有则删除，有则保留。
双向逐步选择：用forward的方法引入一个变量后，如果这个变量使得模型发生显著性变化，则再保留它的同时，对模型中原有的变量一个个按backward的方式检验，最终得到一个比较好的变量集。
11 正则回归与逐步问归
问题
正则回归和逐步问归都有筛选重要变量与简化模型的作用，这些实现方式在特征选择、回归结果方面会带来哪些不同？（例如，特征选择准则灵活性，系数估计是否偏差）
解答
特征选择：正则回归的特征选择通过最小化包含正则项的目标函数来自动进行，通过入来控制限制的松紧而不使用额外的判断标准，特征选择的准则不太直观、灵活。逐步回归的特征选择遵循指定的步骤，并使用指定的标准来判断，特征选择准则的灵活性更高。
回归结果：两类方法的系数估计均有偏差。正则回归的正则项压缩变量系数，导致模型光滑度降低，偏差增大。逐步回归仅枚举了$2_p$种可能模型的一部分，受限于指定的步骤和判断标准，可能找不到最优的特征组合，而且逐步回归计算的复杂度更高。
12 掷骰子
问题
同时掷出n枚4面体骰子（1,2,3,4），计算所有点数之和可被5整除的概率。
解答
设$S_n$为$n$个骰子点数之和，$p_n$为$n$个骰子点数之和被5整除的概率。
显然，如果$S_n$能被5整除，那么$S_{n-1}$一定不能被5整除，而如果$S_{n-1}$不能被5整除，那么无论$S_{n-1}$的值是多少，第$n$次一定能且只能投出一个点数使得$S_n$能被5整除。因此可以得到：
$$P_n = 0 * P_{n-1} + \frac{1}{4} * (1-p_{n-1})$$，其中$P_1=0$
因此可以计算出$P_n=\frac{1}{5}(1-(-\frac{1}{4})^{n-1})$
