概率题, since 2020-09-23

作者: Mc杰夫 | 来源:发表于2020-09-23 22:02 被阅读0次

概率题, since 2020-09-23
LeetCode刷题笔记
概率题
概率题
概率题
随机概率题
概率题3
概率题4
概率题2
概率题1

(2020.09.23/29/30 Wed/Tues/Wed)

Case 1 Random Walk 随机游走问题**

无限制随机游动
质点初始时刻 $t=0$ 位置为0，每个时刻向左或向右移动一个距离，以 $p$ 或 $q$ 的概率。在 $t=n$ 时位于 $k$ 的概率是多少？
最终位置为 $k$ ，则向右移动的次数比向左移动的次数多 $k$ 次。设向右移动 $r$ 次，向左移动 $l$ 次，有 $r+l=n,\space r-l=k$

则有 $r=\frac{k+n}{2}$ 和 $l=\frac{n-k}{2}$
注意到 $k$ 和 $n$ 的奇偶性相同。
利用二项分布可得到， $P\{S_n=k\}=\tbinom{n}{\frac{n+k}{2}}p^{\frac{k+n}{2}}q^{\frac{n-k}{2}}$
当 $k$ 和 $n$ 的奇偶性相反，概率为0。

两端带有吸收壁的随机游走
假定质点在时刻 $t=0$ 时，位于 $x=a$ ，在 $x=0$ 和 $x=a+b$ 处各有一个吸收壁，求质点在 $x=0$ 或 $x=a+b$ 被吸收的概率。(差分方程)
解决方案：
记 $q_n$ 为质点的初始位置为 $n$ 且最终在 $a+b$ 点被吸收的概率，显然有 $q_0 = 0, \space q_{a+b} = 1$ 。
如果某质点位于 $x=n$ ， $1\leq n\leq a+b+1$ ，则它要被 $x=a+b$ 吸收，有两种方式来实现：1) 接下去的一次移动是向右而最终被 $x=a+b$ 吸收，2) 接下去的一次移动是向左而最终被 $x=a+b$ 吸收。按全概率公式，有 $q_n = pq_{n+1} + qq_{n-1}$ ，其中的 $p, \space q$ 分别是每一步向左和向右的概率，且有 $p+q=1$ 。
该公式可改写成 $p(q_{n+1}-q_{n}) = q(q_n - q_{n-1})$
若记 $c_n = q_{n+1}-q_n$ ， $r=\frac{q}{p}$ ，于是又可以写成 $c_n = rc_{n-1},\space n=1,2,\dots,a+b-1$
下面分两种情况解决，
(i) $r=1$ ，即 $p=q=\frac{1}{2}$ ，也对称随机游动的场合。此时， $c_n=c_{n-1}$ ，即 $q_{n+1}-q_n=q_n-q_{n-1}=\dots=q_1-q_0=d$
则 $q_n=q_0+nd$
由于 $q_0=0,q_{a+b}=1$ ，有 $q_n=\frac{n}{a+b}$
(ii) $r\ne i$ ，即 $p\ne q$ 的场合，有 $c_n = rc_{n-1} = r^2 c_{n-2} = \dots = r^nc_0$
从而 $q_n-q_0=\sum_{k=0}^{n-1}(q_{k+1}-q_k)=\sum_{k=0}^{n-1}c_k=\sum_{k=0}^{n-1}r_kc_0=\frac{1-r^n}{1-r}c_0$
由于 $q_0=0,q_{a+b}=1$ ，故有 $\frac{1-r_{a+b}}{1-r}c_0=1$
因此
$q_n = \frac{1-r^n}{1-r^{a+b}}$
由 $n=a$ 代入该方程可以得到所求。

(2020.09.28 Mon)
Case 2 硬币头像期望问题(该题同时出现在动态规划部分)
硬币均匀，分为头像和数字两面，抛硬币两面分别有50%的概率。求连续5次得到同一面A需要抛次数的期望。
分析：设 $e(n)$ 是连续抛出n次A面时抛次数的期望。当连续出现 $(n-1)$ 次A面时，下一步可能出现两种情况，即A或B，各有50%概率。当与上一次的面相反，则截止到第 $(n-1)$ 次连续得到A面之前的所有抛次数都无效，且之后的一次B面也无效，需要重新计算。于是有 $e(n) = 0.5 \cdot (e(n-1)+1) + 0.5 \cdot (e(n-1) + 1 + e(n))$
$e(n) = 2\cdot e(n-1) +2$ 推导得到 $e(n) = e(1)^{n+1}-2$ 。
下面计算 $e(1)$ 。 $e(1)$ 代表着抛出1次A面需要的抛次数期望。有可能第一次就抛出A面，或者前面 $(n-1)$ 次都是B面，到了第 $n$ 次是A面。可根据这个分析求得 $e(1) = 1\cdot\frac{1}{2}(此项代表第一次即A面)+2\cdot (\frac{1}{2})^2(第二次是A面) + 3 \cdot (\frac{1}{2})^3(第三次是A面)+ \dots$
$e(1) = \sum_{n=1}n(\frac{1}{2})^n$
有
$2e(1) = 2\sum_{n=1}n(\frac{1}{2})^n = \sum_{n=1}(n-1+1)(\frac{1}{2})^{n-1} = \sum_{n=1}(n-1)(\frac{1}{2})^{n-1}+\sum_{i=1}(\frac{1}{2})^{n-1}$ 其中的 $\sum_{n=1}(n-1)(\frac{1}{2})^{n-1} = e(1)$ ，而 $\sum_{i=1}(\frac{1}{2})^{n-1}=2$ ，于是有 $2e(1) = e(1) + 2$ ， $e(1) = 2$ ，所以 $e(n) = 2^{n+1} -2$ 。
Case 2-1 生孩子的男女比例问题
(2020.10.17)
某个地方有奇特的生育传统，家里只要生了一个女孩，便会停止生育，如果生了男孩就继续生，直到生了一个女孩。问该地区男女孩的比例是多少？
计算各种男女孩比例家庭的概率：用 $p_i$ 表示有 $i$ 个孩子的家庭比例，如果只有1个女孩，则 $i=1$ ，如果有男有女，则男孩数目为 $i-1$ 。
$p_1 = \frac{1}{2}$ , $p_2 = \frac{1}{2}\cdot \frac{1}{2}$ , $p_3 = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2}$ , $p_n = (\frac{1}{2})^n$ 。每个家庭只有一个女孩，则女孩总数目是 $N_g = 1 \cdot \sum_{i=1} p_i = \sum_{i=1} (\frac{1}{2})^i$ 。由等比数列求和公式 $S=a_1\cdot \frac{1-q^n}{1-q}$ ，有 $N_g=1$ 。男孩总数目 $N_b = \sum_{i=1} p_i \cdot (i-1) = \sum_{i=2} p_i + \sum_{i=3} p_i + \sum_{i=4} p_i +\cdots$ $= \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots = 1$ 。因此，女男的比例是1。

Case 3 两个独立分布的比较 (2020.09.30 Wed)

无限多个数据服从相同分布，从其中任取出10个数据组成A组和20个数据组成B组，A组中的最大值比B组中的最大值大的概率是多少？
(2020.10.17)
该问题等价于，在30个数据中有一个最大值，该最大值落入前10个数据的概率，显然 $\frac{1}{3}$ 。

Case 4 高速公路上看到车的概率

(2020.10.17)
高速公路上过车的概率是恒定，半小时内看到至少一辆车的概率是95%，求10分钟内看到至少一辆车的概率是多少？
解答：设10分钟内看不到车的概率是 $p$ ，根据半小时内看到至少一辆车的概率得到 $p^3 = 1 - 95%$ ，可得到 $p$ 的值，而所求为 $1-p$ 。

(2020.10.18 Sun)

Case 5 生另一个性别的概率

一堆couple生了两个孩子，其中一个是女孩，另一个孩子是男孩的概率是多少？
生两个孩子的性别组合有四种可能(f,m),(f,f),(f,f),(m,m)。有三种情况有女孩，在这三种情况中，有男孩的情况只有一种，所以所求概率是 $\frac{1}{3}$ 。

Case 6 同时拿到两个King的概率

54张牌，分成18张一组的共三组，求两个King在同一组的概率是多少？
分析：想象这两个King捆绑在一起，作为一张牌。
总的分组个数， $t = C_{54}^{18} \cdot C_{36}^{18} \cdot C_{18}^{18}$ ，两个King作为一张牌的分组个数， $t_k = C_{3}^{1} \cdot C_{52}^{16} \cdot C_{36}^{18} \cdot C_{18}^{18}$ 。所求概率是 $\frac{t_k}{t}$ 。

Case 7 有蓝色和红色各50个球，有两个不能见到内部的黑箱，如何分配两个箱子中的各色球，使得随机从黑箱中取到红球的概率最高？

一个黑箱中放1个红球，另一个黑箱中放50蓝和49红，取得红球的概率 $p = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{49}{99} = \frac{74}{99} \times 100\%$

Case 8 一个箱子里有N个球，每次取一个球并放回去，求每个球都被取出一次的期望。

该思路类似于动态规划。设 $E(i)$ 表示有 $i$ 个球被取出过的条件下取出其他球还需要多少次。取到了一个被取过的球，需要的次数期望是 $\frac{i}{N} \cdot (1 + E(i))$ ；取到了一个没有被取过的球，需要的次数期望是 $(1-\frac{i}{N}) \cdot (1 +E(i+1))$ 。因此有 $E(i) = \frac{i}{N} \cdot (1 + E(i)) + (1-\frac{i}{N}) \cdot (1 +E(i+1))$
$E(i) = \frac{N}{N-i} + E(i+1)$
初始条件， $E(N) = 0$ ， $E(N-1) = N, \space E(N-2) = N+ \frac{N}{2}, \space E(N-3) = N + \frac{N}{2} + \frac{N}{3}$
$E(0) = N \cdot \sum_{i=1}^{N} \frac{1}{i}$

Case 8-1：一个骰子抛出所有点数的期望次数是多少？

根据Case 8推出的公式可以算出结果。

Reference

1 李贤平，概率论基础，高等教育出版社，2010年4月

概率题, since 2020-09-23
(2020.09.23/29/30 Wed/Tues/Wed) Case 1 Random Walk 随机游走问题...
LeetCode刷题笔记
(Since 2020.10.14-2021.3.10) LeetCode刷题笔记，共两百多题，记录整理如下：动...
概率题
某市场上某种零件由甲、乙、丙、丁四厂供货，供货数量之比为 4:3:2:1。各厂产品的合格率分别为 99%、 98%...
概率题
看到常见题目，顺手记下。常见概率题二十道概率题 1. 扔硬币直到连续两次出现正面，求扔的期望次数。假设期望次数...
概率题
已知某事件发生的概率为p，则要让该事件发生所需的试验次数期望值为1/p 已知事件A发生的概率为p，试验1次，事件A...
随机概率题
对数组的每一个位置随机排序： https://blog.csdn.net/cyningsun/article/de...
概率题3
随机变量和相互独立。在均匀分布，的概率密度为(1) 求随机变量的分布函数(2) 求随机变量的数学期望(3) 求随机...
概率题4
六个团队每队六个人参加了体测。已知有一个队全员通过，有两个队有一个人没通过，其余队都有两个没通过。随机选取一个队，...
概率题2
随机变量和相互独立。在均匀分布，的概率密度为(1) 求随机变量的分布函数(2) 求随机变量的数学期望(3) 求随机...
概率题1
随机变量和相互独立。的概率密度为的概率密度为(1) 求随机变量的分布函数(2) 求随机变量的数学期望(3) 求随机...