柯西（Cauchy）分布，也叫做洛仑兹分布，是个很特殊的分布。标准Cauchy分布的密度函数是

$$\frac{1}{\pi(x^2+1)}.$$

根据期望的定义，

$$\mathbb{E}=\int_{-\infty}^{\infty}\frac{1}{\pi(x^2+1)}dx.$$

可惜的是，上面这个积分并不可积尽管密度是对称的。积分不可积，数学期望当然也就不存在了。

题主所谓的n次试验，我们也可以做一做。因为标准柯西分布实际上是两个独立的标准正态分布变量的商，所以这个实验很容易完成。

我用的python，我直接把code复制过来。

>>>from numpy.random import normal; import numpy as np

>>>np.mean(normal(0,1,100)/normal(0,1,100))
1.71624142192124

>>>np.mean(normal(0,1,10000)/normal(0,1,10000))
-3.25718241481268

>>>np.mean(normal(0,1,1000000)/normal(0,1,1000000))
0.892417249736812

>>>np.mean(normal(0,1,100000000)/normal(0,1,100000000))
11.241299247890361

我从100个一直试到了一亿个，都没有看出收敛的迹象。所以题主说的，“总会趋向稳定” 并是不对。

可以看作是一串几何分布。在扔第一次之前，得到一个新数字的概率是$p_1=6/6$，因为不管出现几，这个数都是之前没有出现过的。之后要得到第二个新出现的数字的概率就变成了$p_2=5/6$。同理，要得到第$k$个新出现的数字的概率就是$p_k=(7-k)/6$。

根据几何分布，我们知道，得到一次成功所需要的试验的次数是$1/p$。所以，出现全部6个数字，我们所需要扔骰子的次数的期望是

$$\sum_{i=1}^6\frac{1}{p_i}=\frac{6}{6}+\frac{6}{5}+\frac{6}{4}+\frac{6}{3}+\frac{6}{2}+\frac{6}{1}=14.7$$

解法跟“一个女生说她跟12星座的男生都谈过，期望谈过男生的个数”类似...

Markov Inequality的表达式为

$$\text{Pr}(X>a)\leq \frac{\text{E}(x)}{a}.$$

它描述了一个非负随机变量大于一个给定值的概率的上限。比如说随机变量$X$的期望是10，那么$X>20$的概率不超过$1/2$。一个著名的应用是不超过五分之一的人口会有超过五倍于人均收入的收入。

证明如下：

假设$X$的密度函数为$f(x)$，那么期望可以写成

\begin{eqnarray*}\text{E}(x)&=&\int_0^\infty xf(x)dx\\&=&\int_0^a xf(x)+\int_a^\infty xf(x)dx\\&\leq&0+a\int_a^\infty f(x)=a\text{Pr}(X>a).\end{eqnarray*}

两边同时除以$a$,我们可以得到$\text{Pr}(X>a)\leq \frac{\text{E}(X)}{a}$.

泊松过程是基于连续时间的随机过程。

伯努利过程是基于离散时间的随机过程。伯努利过程是一串独立伯努利实验，也就是0，1组成的序列。

泊松过程和伯努利过程都是计数过程。

例子：

泊松过程：已知平均每小时来3辆公交车，接下来五小时，每小时来的公交车的数量就服从泊松分布。

伯努利过程：假设每分钟最多只能可能来一辆公交车，每分钟来公交车的概率为0.05，接下来五小时，每小时来的公交车的数量就服从伯努利分布。

若把伯努利过程中的时间间隔从$1$分钟变成$\frac{1}{n}$分钟，当$n$趋近于无穷大，这个伯努利过程就逼近于泊松过程。所以说伯努利过程是离散化的泊松过程；泊松过程是连续的伯努利过程。

鞅是一种特殊的随机过程。另外一个著名的随机过程马尔可夫链的特点是无记忆性，鞅的特点是公平性。鞅的英文是martingale，原意是骑马的缰绳，有一种“控制平衡、公平”的意思。

鞅的数学定义是，对于所有$n$，都满足

\begin{eqnarray*}&&\text{E}(|X_n|)\lt\infty\\&&\text{E}(X_{n+1}|X_1,X_2,\cdots,X_n)=X_n.\end{eqnarray*}

这个意思是说已知之前所有事件的观测值，下一次观测值的条件期望等于当前的观测值。

举个例子，一个爬虫从实数轴的原点出发，每天以0.5的概率向前爬1,0.5概率向后爬1，$X_n$是第$n$天后爬虫的坐标。显然$X_1,X_2,\cdots$这就是一个鞅，因为不管爬虫今天的坐标是什么，明天的期望坐标就是今天的坐标。

但是如果向前爬的概率是0.8，向后爬的概率是0.2，那么这个就不是鞅了，因为明天的期望坐标总是大于今天的坐标的。这也就是为什么说，鞅是个公平的随机过程。

这个题目应该有常规解法吧，但是我没想出来。我用的是递推的方法。

假设一共有$k$张牌，其中13张是黑桃，我随机地不放回地抽，在第$X_{k}$的时候，第一次抽到黑桃。

那么显然$\text{E}(X_{13})=1$。因为13张都是黑桃，我们把它们排一列，头一张必须是黑桃。

那么$\text{E}(X_{14})$怎么算呢？相当于在上面13张黑桃的基础上，任意插入一张其他牌。这张牌以$\frac{\text{E}(X_{13})}{14}$的概率插在第一张黑桃的前面，以$1-\frac{\text{E}(X_{13})}{14}$的概率插在第一张黑桃的后面。所以

$$\text{E}(X_{14})=\frac{\text{E}(X_{13})}{14}(\text{E}(X_{13})+1)+\left(1-\frac{\text{E}(X_{13})}{14}\right)\text{E}(X_{13}).$$

那么对于任意的$k$，已知$\text{E}(X_{k})$，怎么计算$\text{E}(X_{k+1})$呢？相当于我们已经排好了$k$张，再插入一张非黑桃的牌，这张牌排在第一张黑桃前面的概率是$\frac{\text{E}(X_{k})}{k+1}$，排在第一张黑桃后面的概率是$1-\frac{\text{E}(X_{k})}{k+1}$，那么

\begin{eqnarray*}\text{E}(X_{k+1})&=&\frac{\text{E}(X_{k})}{k+1}(\text{E}(X_{k})+1)+\left(1-\frac{\text{E}(X_{k})}{k+1}\right)\text{E}(X_{k})\\&=&\frac{k+2}{k+1}\text{E}(X_{k})\end{eqnarray*}

下面，我们就根据上面的递推式子

$$\text{E}(X_{14})=\frac{15}{14}$$

$$\text{E}(X_{15})=\frac{16}{15}\frac{15}{14}=\frac{16}{14}$$

$$\text{E}(X_{16})=\frac{17}{16}\frac{16}{14}=\frac{17}{14}$$

$$\text{E}(X_{17})=\frac{18}{17}\frac{17}{14}=\frac{18}{14}$$

一直到$52$，我们就可以得到

$$\text{E}(X_{52})=\frac{53}{52}\frac{52}{14}=\frac{53}{14}\approx 3.79.$$

所以我们期望在第3.79次第一次抽到黑桃。

找了下，应该用Negative_hypergeometric_distribution。定义是N个元素中有K个正元素，不放回地（without replacements）随机取一个元素，直到有r个负元素被取出，其中有k个正元素。在这个问题里N=52，负元素是黑桃，K=52-13=39，r=1，k+1是步数。按均值公式$E(k)=\dfrac{rK}{N-K+1}=\dfrac{39}{14}$,最后步数的期望是$E(k)+1=\dfrac{53}{14}\approx 3.79$

用MC验证下，就是3.79左右。

import numpy as np
import matplotlib.pyplot as plt
from numpy import random
n=1000000
k=52
x0=np.arange(k)
t=np.zeros([n,1])
for i in range(n):
    x=random.permutation(k)
    idx=x<13
    temp=x0[idx]
    t[i]=temp[0]+1
E=np.mean(t)
print(E)
plt.figure()
plt.hist(t,100,normed=True)
plt.plot([E,E],[0,1],'--',label='mean')
plt.legend()
plt.show()

---------------------

再分享张图，我是根据这图才找到的。

是独立的。

两个不相关的变量如果是联合正态分布的，那么就一定是独立的。

或者也可以用矩母函数的方法来证明，只要证明$M_{X+Y,X-Y}(t_1,t_2)=M_{X+Y}(t_1) M_{X-Y}(t_2)$，就可以说明它们是独立的了。

矩母函数的证明可以看这里。

还以证明$X+Y,X-Y$都是Gaussian，并且covariance=0。

$X+Y \sim N(0,2)$

$X-Y \sim N(0,2)$

$cov(X+Y,X-Y)=E((X+Y)(X-Y))=E(X^2-Y^2-2XY)$

$=E(X^2)-E(Y^2)-2E(XY)=1-1-0=0$

这个题目可以用递归的思想来做。

假设从一个病毒最终到没有病毒的概率为$p$。画成图，是这样

我们知道在最开始的时候，只有一个病毒，一秒之后，有三种情况：变两个；不变；挂了。概率都是三分之一。画成图，是这样

写成式子，就是

$$p=\frac{1}{3}p^2+\frac{1}{3}p+\frac{1}{3}.$$

解上面的方程，可得$p=1$。概率是1，也就是病毒最终肯定会都死光。

这是赌徒破产理论，是说即使是公平的游戏（比如硬币正反面概率都是1/2），在无限资金的对手面前，只要赌徒一直赌下去，破产的概率是1。最主要是因为0状态是吸收状态（Absorbing_Markov_chain），进去后出不来。如果允许负状态并能跳回正状态，则$E(x_{n+1}|x_n)=x_n$。

这里细菌数是赌本；游戏是公平的，-1/+1的概率都是1/3；细菌数无限制；时间无限。所以最后破产（细菌数为0）的概率为1。

答案是

$$\frac{2^n n!}{(2n)!}.$$

思路大致如下：

我们是随机按照均匀分布抽取$n$个闭区间的上下界。我们把$n$个区间的下界从小到大排序，也就是$(x_{1,1},x_{1,2}),(x_{2,1},x_{2,2}),\cdots,(x_{n,1},x_{n,2})$，满足$x_{1,1}<x_{2,1}<x_{3,1}<\cdots < x_{n,1}$。

在这种情况下，唯一能够达到所有闭区间不重叠的情况是

$$x_{1,1} < x_{1,2} < x_{2,1} < x_{2,2} < x_{3,1} < x_{3,2} < \cdots < x_{n,1} < x_{n,2}.$$

因为我们只在乎其排序，而且均匀随机抽样。这个问题就等价于从集合$\{1,2,3,\cdots,2n\}$中无放回的抽样。

符合不重叠的唯一可能性是

$$x_{1,1}=1,x_{1,2}=2,x_{2,1}=3,\cdots,x_{n,1}=2n-1,x_{n,2}=2n,$$

而所有的可能性一共有

$$\frac{(2n)!}{2^n n!}.$$

然后就可以得到概率。

我用python验证了下高代兄的答案

import math

import pandas as pd

import numpy as np



n = 3

rounds = 10000

p = 0

for m in range(rounds):

    bounds = pd.DataFrame(columns=['lower_bound', 'upper_bound'])

    for i in range(n):

        bounds.loc[i] = np.sort(np.random.uniform(0, 1, 2))

    bounds.sort_values('lower_bound', inplace=True)

    diff = np.diff(bounds['upper_bound'].values)

    p += np.all(diff <= 0) / float(rounds)

print('simulation', p)

print('true:', ((2 ** n) * math.factorial(n)) / math.factorial(2*n))

得到的结果：

simulation： 0.0675

true: 0.06666666666666667

将一个筛子扔两次可以得到36种组合，每五种组合代表一个数字，剩下的一种表示重扔。

第一步：

将这个筛子扔两次，假设第一次扔的时候得到a，第二次是b，表示为(a, b)。

第二步：

1: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)

2: (1, 6), (2, 1), (2, 2), (2, 3), (2, 4)

3: (2, 5), (2, 6), (3, 1), (3, 2), (3, 3)

4: (3, 4), (3, 5), (3, 6), (4, 1), (4, 2)

5: (4, 3), (4, 4), (4, 5), (4, 6), (5, 1)

6: (5, 2), (5, 3), (5, 4), (5, 5), (5, 6)

7: (6, 1), (6, 2), (6, 3), (6, 4), (6, 5)

重复第一步: (6, 6)

扔到奇数，记为0

扔到偶数，记为1

连续扔三次，就会得到一个0到7的二进制数。比如010就是3，100就是5。

如果最终得到0，就重新再扔三次。

如此反复，直到得到非0的数。

这个肯定是生成1到7等概率的随机数。

根据sasa的答案，想到一个随机数生成效率的问题。

sasa方法中扔2次骰子也只有35/36的概率可以生成1个随机数。扔一次可得0.486个随机数。

如果扔骰子的时间代价大，需要注意生成随机数的效率，可以扩展下算法。比如扔骰子三次，可以把一个三维空间均匀分为216份，编号为1-216，然后再把这216份编为49组，对应两个1-7的随机数。比如{1,2,3,4}为第一组，对应随机数{1,1}；{5,6,7,8}为第二组，对应随机数{1,2}；最后剩下20份{197,...,216}表示无效。扔一次骰子可得随机数个数是（216-20）/216*2/3=0.605。

以此类推可以得到接近6/7的生成效率。

——————-

扔k次生成k位6进制数$x$，把这个数换为一个n位7进制数$y$。第n位在[0,6]的分布并不均匀，比如0会多于6，需要去掉。这样可表示n-1位7进制数，变换为n-1个均匀分布$U([0,6])$随机数。

扔到1-5的数，就保留。

扔到6，就重扔，偶数的话就是6，奇数的话就是7。

我觉得是$\frac{17}{53}$。

把54张牌随机打乱，第1到18张属于甲，第19到36张属于乙，第37张到54张属于丙。

甲拿到大王和小王的概率是$$\frac{18 选 2}{54 选 2}=\frac{18\times 17}{54 \times 53}=\frac{17}{159}$$

同样，乙拿到大王和小王的概率也是$\frac{17}{159}$。丙也是。

所以同一个人拿到大王和小王的概率是$$3\times \frac{17}{159}=\frac{17}{53}$$

大王必被其中一个人拿到，就看小王被这个人拿到的概率了。除大王外的53张牌里他还能拿17张，所以是17/53

大王小王同时被抓住只有在大王小王位置相隔3的倍数的时候才可能,大王可以出现在1到54的任何位置,同时不管大王出现在任何位置小王都有17个位置可以满足被同时抓住的情况,所以有54*17个位置组合,而整副牌有54 * 53种位置组合来安放大小王,所以概率是54*17/54*53=17/53

概率我搞不来，只能怒怼一波simulation。并且验证了MrMath大神的答案准确无误。

import numpy as np
a = [1] * 2 + [0] * 52
count = 0
for i in range(10000000):
    np.random.shuffle(a)
    count += sum(a[:18]) == 2
print 3. * count / 10000000.
print 17. / 53

返回结果

0.3208085
0.320754716981

假设三段的长度从小到大依次为$a$，$a+b$，$a+b+c$，并且满足

$$(a)+(a+b)+(a+b+c)=3a+2b+c=1$$

以及

$$a>0, b\geq 0, c\geq 0.$$

那么可以得到$a\leq \frac{1}{3}$，$b\leq \frac{1}{2}$，$c\leq 1$，不妨可以认为$a\sim U(0, 2k)$,$b\sim U(0, 3k)$,$c\sim U(0, 6k)$。

绳子最长的一段的期望为$k+1.5k+3k=5.5k$

绳子长度的期望为$3k+3k+3k=9k$

因为$9k=1$，所以$5.5k=\frac{11}{18}=0.61111$

应该是可以有理论解的（可惜我不会）

如果你把这绳子剪一千万次，你会发现最长的那段的均值为0.611左右。

我画了个图，最长那段的长度的分布差不多是这样

众数感觉是在0.5

答案里提到“马尔可夫链，可做图求解递归方程”。这应该是靠谱的思路。

假定扔出正面(H)的概率为p，扔出反面(T)的概率为1-p。

我们需要扔出连续2个H。在整个过程有这么几种状态

1）当前连续0个正面（0H）；2）当前连续1个正面（1H）；当前连续2个正面（2H）。

状态转换图如上。

如果当前是0H，那么p的概率，下一个状态是1H；1-p的概率维持在0H。

如果当前是1H，那么p的概率，下一个状态为2H（达到条件，任务完成）；1-p的概率回到0H。

假设期望$x$次后，得到2H。

那么$$x=(1-p)(1+x)+p^2 \times 2 + p (1-p)(2+x)$$

第一个部分$(1-p)(1+x)$的意思是说，如果先扔出一个T，然后状态保持在0H，所以人仍然需要$x$次来完成任务。第二部分是说，先扔出H，再扔出H，两步完成任务，这种情况的概率为$p^2$。第三部分是先扔出一个H，此时状态为1H，然后又扔出一个T，状态回到0H，这种情况的概率为$p(1-p)$，用了两次回到0H，所以需要$2+x$次。

根据上面的式子，可以解得$$x=\frac{1+p}{p^2}.$$

这个硬币是无偏差的，所以$p=0.5$，所以$x=6$。

Markov Chain hitting time公式http://www.statslab.cam.ac.uk/~james/Markov/s13.pdf

相关网页：https://www.quora.com/What-is-the-expected-number-of-coin-flips-until-you-get-two-heads-in-a-row

假设有三个状态，S1是开始或抛出反面，S2是抛出一个正面，S3是连续抛出两个正面并且游戏结束。

初始状态$x_0=[1, 0 ,0]$，状态转移矩阵是

$P=[0.5, 0.5 ,0;$

$    0.5, 0, 0.5;$

$0, 0 ,1]$

根据第一个链接里定理1.3.5

$K_i^A $是状态i到状态A的步数的期望

$K_1^3 = 1 + \sum\limits_{j = 1}^2 {{P_{1j}}K_j^3}$

$K_2^3 = 1 + \sum\limits_{j = 1}^2 {{P_{2j}}K_j^3}$ 

最后从起始S1到S3的步数的期望

$K_1^3 = {{1+0.5} \over {{0.5}^2}}=6$

可以通过矩阵计算得出每一个状态的期望，首先状态转移矩阵transition matrix是$P=[[0.5,0.5,0],[0.5,0,0.5],[0,0,1]]$,然后我们计算fundamental matrix，$N=(I-Q)^{-1}$,其中$Q=[[0.5,0.5],[0.5,0]]$,得到$N=[[4,2],[2,2]]$,然后得到S1,和S2状态分别的期望：$t=NI$其中$I=[[1],[1]]$,result：$[6,4]$说明从最初的状态开始需要6次，从第二个状态开始只需要4次。

假设圆心为原点，$\theta_A=0$,

当$0 < {\theta _B} < \pi \\ $时，$-\pi+\theta_B<\theta_C<\pi$为钝角三角形。

$$\int_0^\pi {\int_{ - (\pi - {\theta _B})}^\pi {p({\theta _C})p({\theta _B})d{\theta _C}} } d{\theta _B}=\frac{1}{4{\pi^2}}\int_0^\pi({2\pi-\theta_B})d\theta_B=\frac{3}{8}$$

当$\pi< {\theta _B} < 2\pi$时，$\pi<\theta_C<3\pi-\theta_B$, 概率也等于3/8。所以最终为钝角三角形的概率为3/4。

假设要组成一个钝角三角形，那么三个点必须在圆心的一侧。

固定第一个点。这样就变成了俩个变量的概率题了。

此时设第二个点落在第一个点为0°，落在第一个点对面为180°。设第二个点落在θ的位置。经过画图验证，第三个点可以组成钝角三角形的可行范围是（360°-θ)。

计算面积得到0.75的概率。

所以锐角三角形是0.25。

假设圆周的总长度为1，并且A点是固定的，从A点顺时针方向的第一个点为B，第二个点为C。

假设圆弧长度$AB=x_1$，圆弧长度$AC=x_2$，为了使得$ABC$为一个锐角三角形，我们需要

$$x_1\in (0, 0.5),~~x_2 \in (0.5, 0.5+x_1)$$

那么A、B、C能构成锐角的概率为

$$\int_{0}^{1/2}1\int_{1/2}^{x_1+1/2}1dx_2dx_1=\int_0^{1/2}x_1dx_1=\frac{1}{4}$$

钝角的概率就是0.75

-------------------------

感谢Zealing的指正！答案已修正。

最近刚好在一个网站上看到过

第一种思路是考虑三个点组成钝角三角形的概率。分为三种情况: 顺时针方向第一个是A且B, C均距离A不超过一个半圆的概率，两个概率都是恰好1/2所以总概率1/4.然后再考虑顺时针方向第一个是B，概率也是1/4；顺时针方向第一个是C，概率也是1/4。故总概率为3/4。

另一种做法更加巧妙，但不太容易描述清楚。

不一定吧，比如变量$Y=X_1+X_2$，那么$X_1$和$X_2$肯定不是条件独立的。

类似这些问题可以看bayes graph相关的知识。可以为你解答所有可能的组合情况。

三门问题又叫Monty Hall problem。拿wiki一张图解释。讲个花絮，有个电影“21”，讲个大学教授培训学生去赌场玩21点。教授在课堂上问过这个问题。

-------------------------------

1.这问题其实有两次采样，第一次没有任何已知条件，所以小球在箱子A的概率$P(A=1)=1/3$;

2.接着朋友在箱子B和C中打开一个空箱子B或C，此时第二次采样剩下一个箱子有球的概率为 $P(ABC=010||ABC=001)=P(A=0)=2/3$

3. 这问题的机关是朋友一定会在第二步打开一个空箱子，引入了已知信息，所以第一次采样的概率比第二次采样的概率小。

这是一个条件概率的问题，可以由贝叶斯公式进行求解，令盒1， 2， 3中有球分别为事件A, B, C， 则在一直盒2中没有球的情况下盒1中有球的概率为P(A=1 | B=0) = P(A=1, B=0) / P(B=0) = 2/3

我们要从数据流中抽取$k$个数据点，那对于第$n$个样本$X_n$，($n\geq k$)，它有$k/n$的概率被选进池子中；如果被选中了，我们随机从池子中的$k$个样本中挑选一个$X_i$被$X_n$取代。这个就是蓄水池算法的基本思想。

---------------------------

下面开始证明

---------------------------

用数学归纳法证明，每个样本被选中的概率的都是相等的。

初始情况是，当前只有$k$个样本，此时每个样本都被选中进入池子，也就是$k /k=1$的概率。

如果我们一共有$n$个数据点，假设每个数据点被选进入池子的概率相等，都是$k / n$。

根据数学归纳法的思想，下面我们只要证明如果一共有$n+1$个数据点，每个数据进入池子中的概率都是$k/(n+1)$。

对于第$n+1$个样本$X_{n+1}$，它进入池子的概率显然是$k/(n+1)$。

对于第$j$个样本$X_j$，$j\leq n$，它在前一轮中已经在池子里的概率为$k/n$。

下面我们分两种情况讨论：第一种情况，$X_{n+1}$没被选中，所以$X_j$依然留在池子中。这种情况的概率为

$$P_1=1-\frac{k}{n+1}=\frac{n+1-k}{n+1}$$

第二种情况，$X_{n+1}$被选中但是$X_j$没有被替换。这种情况发生的概率为

$$P_2=\frac{k}{n+1}\frac{k-1}{k}=\frac{k-1}{n+1}$$

两者相加

$$P_1+P_2=\frac{n}{n+1}$$

所以$X_j$此时在池子中的概率为

$$\frac{k}{n}(P_1+P_2)=\frac{k}{n}\frac{n}{n+1}=\frac{k}{n+1}$$

证毕

中餐馆过程就是一个离散的随机过程，它是模拟了中餐馆里客人拼桌的情况，反映了“中国同胞们爱扎堆、凑热闹的情况”。

先假设有无限个桌子，每桌有无限个座位。

第$1$位客人，随便找了个桌子坐下。

第$2$位客人，以$1/2$的概率和第1位客人坐在同一桌；以$1/2$的概率找了个没人的桌子坐下。

...

第$k+1$位客人，以$m/(k+1)$的概率坐在了一个已经有$m$个客人的桌子上；以$1/(k+1)$的概率找了个没人的桌子坐下。

另外还有维基百科里的动画演示

比如说有个数列$\{X_n\}$，$\{X_n\}$依概率收敛到$X_0$的意思就是，对于任意的正数$\epsilon>0$

$$\lim_{n\rightarrow \infty}\text{Prob}(|X_n-X_0|\gt \epsilon)=1$$

依概率收敛比平时说的收敛要弱些，平时的收敛是这样的

$$\lim_{n\rightarrow \infty}(X_n-X_0)=0$$

Jensen不等式刻画了凸函数的一个性质。假如$f(X)$是个凸函数，，对于一个随机变量$X$，那么

$$\mathbb{E}[f(X)] \geq f(\mathbb{E}[X])$$

举个直观点的例子，假设$f(X)$是点$X$到原点的欧式距离。

一个聚类中有$m$个点，这些点到原点的平均欧式距离肯定是大于等于这个聚类的中心点到原点的欧式距离的。

凸函数$f(x)$的性质是

$$tf(x_1)+(1-t)f(x_2) \geq f(tx_1+(1-t)x_2)$$

如果取$t=0.5$，那么

$$\frac{1}{2}(f(x_1)+f(x_2)) \geq f\left(\frac{1}{2}(x_1+x_2)\right)$$

推广到$n$个元素

$$\frac{1}{n} \sum_{i=1}^n f(x_i) \geq f \left(\frac{1}{n}\sum_{i=1}^n x_i\right)$$

也就是

$$\mathbb{E}(f(X)) \geq f(\mathbb{E}(X))$$

不太清楚你说的“解答”是什么意思

但是根据题意，今天和明天都下雨的概率是$p+q-m$，这个是对的。

你假设了今天下雨和明天下雨是独立的，这显然太草率了，否则你就可以根据$p$和$q$直接推导出

$$m=1-(1-p)(1-q)=p+q-pq$$

令$x,y$为Lyft和Uber到达时间，所求$min(x,y)$的期望，有3种可能，

$$A=\{0<x<3\}$$

$$B=\{3<x<6,x<y<11\}$$

$$C=\{3<y<x<6\}$$

因为$x,y$独立，$p(x,y)=p(x)p(y)$

$$E(min(x,y))=\int_0^3 xp(x)dx + \int_3^6 xp(x)\int_x^{11} p(y)dydx + \int_3^6yp(y)\int_y^6 p(x)dxdy$$

$$E(min(x,y))=\int_0^3 \dfrac{x}{6}dx + \int_3^6 \dfrac{x}{6}\int_x^{11} \dfrac{1}{8}dydx + \int_3^6 \dfrac{y}{8}\int_y^6 \dfrac{1}{6}dxdy$$

$$=3/4+57/32+3/8$$

$$=2.90625$$

用Monte Carlo去验证

import numpy as np
n=1000000
x=np.random.uniform(0.,6.,n)
y=np.random.uniform(3.,11.,n)
z=np.minimum(x,y)
indexA=x<3.
xA=x[indexA]
yA=y[indexA]
xBC=x[~indexA]
yBC=y[~indexA]
indexBC=xBC<yBC
xB=xBC[indexBC]
yB=yBC[indexBC]
xC=xBC[~indexBC]
yC=yBC[~indexBC]
pA=xA.size*1./n
pB=xB.size*1./n
pC=xC.size*1./n

print 'termA : monte carlo=%.4f, real=%.4f'%(xA.mean()*pA,3./4)
print 'termB : monte carlo=%.4f, real=%.4f'%(xB.mean()*pB,57./32)
print 'termC : monte carlo=%.4f, real=%.4f'%(yC.mean()*pC,3./8)
print 'E(min(x,y)): monte carlo=%.4f, real=%.4f'%(z.mean(),1.5/2+57./32+3./8)

结果是

termA      : monte carlo=0.7505, real=0.7500
termB      : monte carlo=1.7804, real=1.7812
termC      : monte carlo=0.3731, real=0.3750
E(min(x,y)): monte carlo=2.9040, real=2.9062

我也验证了一下@Zealing的计算结果，正确无误。

import numpy as np
x = np.random.uniform(0, 6, 1000000)
y = np.random.uniform(3, 11, 1000000)
min_wait = np.mean(np.min([x, y], axis=0))
print(min_wait)

2.9058634569908963

题目感觉有陷阱，是等了三分钟没来再叫呢，还是一开始就决定了如果车不来，第三分钟就叫uber呢？

假设是第二种情况，在叫车前就决定了第三分钟叫。

假设Lyft先来的概率为$p$，假设Lyft的车第$x$分钟来，Uber的车第$y$分钟来，那么最后的等待的期望是

$$p\int_{3}^{11}\frac{y}{8}\int_{0}^y\frac{x}{6}dxdy+(1-p)\int_{3}^6\frac{x}{6}\int_3^x\frac{y}{8}dydx$$

这个可以手算的。

至于$p$，也很好算，画图就能得到，等于$8/9$。

假设扔完$k$次之后，手上钱的期望为$E_k$。

显然

$$E_1=\frac{0+2+3+4+5+6}{6}=\frac{10}{3}$$

并且

$$E_{k+1}=\frac{1}{6}0+\frac{5}{6}(E_k+4)=\frac{5}{6}E_k+\frac{10}{3}$$

当$E_{k+1}=E_k$的时候，停止扔骰子，此时$E_k=20$。

有个Hold at 20 turn的策略，每一步期望的最大值是20，如果当前得分达到20，就要见好而收。

假设策略是一直扔骰子，求扔到1前得分的均值。

第$k$步的概率$p_k=\frac{(5/6)^{k-1}}{\sum_{k=1}^{\infty}(5/6)^{k-1}}$，分子为归一化因子。

第$k$步得分的均值是$E_{k}(score)=4k*(5/6)+0*1/6$

得分的均值

$$E(score)=\sum_{k=1}^{\infty}p_kE_k(score)$$

$$=\frac{\sum_{k=1}^{\infty}4k(5/6)^k}{\sum_{k=1}^{\infty}(5/6)^{k-1}}$$

$$=120/6$$

$$=20$$

用MC验证：

import numpy as np
n=10000
score=np.zeros(n)
step=np.zeros(n)
for i in range(n):
  x=np.random.randint(low=1,high=7)
  while x>1:
    score[i]+=x
    step[i]+=1
    x=np.random.randint(low=1,high=7)
    
print("E(score)=%f"%score.mean())
print("E(step)=%f"%step.mean())

结果是

E(score)=19.878700
E(step)=4.978100

对于有向图$G$，如果存在一个子图$\hat G$，对于$\hat G$中的任何顶点$v_1, v_2$，总存在一条路径从$v_1$到$v_2$，同时也存在一条路径从$v_2$到$v_1$，那么我们就说$\hat G$是$G$的强连通子图或者强连通分量。

上面就是一个有向图。$\{a, b, e\}$是强连通的，$\{c,d,h\}$是一个强连通分量，$\{f,g\}$是一个强连通分量。

有个取巧的解法。假设甲先开枪，乙中弹总概率为$p$。有0.5概率第一枪没中，这时甲乙相当于互换位置，乙先开枪，甲有$p$概率中弹。

$p+0.5p=1$,  $p=2/3$

-------------------

等比级数$\sum_{i=1}^{\infty}(0.5^i)=1$,令奇数项和为 $p$，则偶数项和为$0.5p$，$p+0.5p=1$, $p=2/3$

我们直接列举出乙先中弹的情况：

1. 乙中

2. 乙不中、甲不中、乙中

3. 乙不中、甲不中、乙不中、甲不中、乙中

4. 乙不中、甲不中、乙不中、甲不中、乙不中、甲不中、乙中

5. 乙不中、甲不中、乙不中、甲不中、乙不中、甲不中、乙不中、甲不中、乙中

...省略...

第一种情况发生的概率为：$P_1=0.5$

第二种情况发生的概率为：$P_2=0.5^3$

第三种情况发生的概率为：$P_3=0.5^5$

...省略...

把所有情况的概率加起来

$$P=\sum_{i=1}^\infty P_i=2\sum_{i=1}^\infty 0.25^i=\frac{0.5}{1-0.25}=\frac{2}{3}$$

乙先中弹的概率为$2/3$，甲先中弹的概率$1-2/3=1/3$

1. 从$x_1$到$x_2$

$x_1$概率密度函数pdf $f_{x_1}=1$

条件pdf $f_{x_2|x_1}=\frac{1}{x_1}$

联合pdf $f_{x_2,x_1}=\frac{1}{x_1}*1=\frac{1}{x_1}$

$x_2$ pdf $f_{x_2}=\int_{x_2}^{1}\frac{1}{x_1}dx_1=-ln(x_2)$

2. 从$x_2$到$x_3$

条件pdf $f_{x_3|x_2}=\frac{1}{x_2}$

联合pdf $f_{x_3,x_2}=\frac{1}{x_2}*-ln(x_2)$

$x_3$ pdf $f_{x_3}=\int_{x_3}^{1}\frac{1}{x_2}*-ln(x_2)dx_2=\frac{ln^2(x_3)}{2}$

同理可得$f_{x_4,x_3}=\frac{ln^2(x_3)}{2x_3}$

推理得$f_{x_{n+1},x_n}=\frac{ln^{n-1}(1/x_{n})}{(n-1)!x_{n}}$

只有满足条件$x_{n+1}<a<x_{n}$时才考虑$n$，此时的概率是联合pdf在$0<x_{n+1}<a$和$a<x_n<1$上的积分

$\int_0^a\int_a^1f_{x_{n+1},x_n}dx_ndx_{n+1}$

根据均值定义

$\sum_{n=1}^{\inf}n*\int_0^a\int_a^1f_{x_{n+1},x_n}dx_ndx_{n+1}+1$

$=\sum_{n=1}^{\inf}\int_0^a\int_a^1\frac{nln^{n-1}(1/x_{n})}{(n-1)!x_{n}}dx_ndx_{n+1}+1$

$=\sum_{n=1}^{\inf}\frac{naln^n(1/a)}{n!}+1$

最后一步化简暂时没做出，用实验验证应该没错。

import numpy as np
import matplotlib.pyplot as plt
def GetN(a):
    result = 1
    n=10000
    for i in range(n):
        t=0
        x = np.random.uniform(0., 1.)
        while a < x:
            x=np.random.uniform(0., x)
            t+=1
        result += (t*1. / n)
    return result

def GetN_my(a):
    result=1.
    n=20
    ln_a=np.log(1/a)
    for i in range(1,n):
        temp=i*a*np.power(ln_a,i)/np.math.factorial(i)
        result+=temp
    return result

a = np.linspace(0.02, 0.98, 40)
expN = [GetN(i) for i in a]
expN_my = [GetN_my(i) for i in a]

plt.plot(a,expN,'-o',label='Sim')
plt.plot(a,expN_my,'-*',label='My')
plt.legend()
plt.show()

没有什么思路，只能解一个简单的情况，假如$X$不是随机的，是固定的在每个区间的中间，$X_1=2^{-1}, X_2=2^{-2}, X_n=2^{-n}$，那么对于给定的$a$，$n$的值也是可以确定的，等于

$$\lfloor 1-\log_2^a\rfloor$$

但问题就是这里的$X$都是随机的，所以我就只能用代码试试了

def GetN(a):
    result = 0
    for i in range(100000):
        x = [1]
        while a < x[-1]:
            x.append(np.random.uniform(0, x[-1]))
        result += ((len(x) - 1) / 100000)
    return result
a = np.linspace(0.02, 0.98, 49)
expN = [GetN(i) for i in a]

下图横轴是$a$，纵轴是$n$。蓝色的线是模拟的结果，绿色是按照固定X计算的结果。感觉差不了太多。

超几何分布描述了从N个物品（其中包含M个指定种类的物品）中无放回抽出n个物件，成功抽出该指定种类的物件的次数。

根据你的题目，假设1到6名的商学院毕业生的平均GPA低于3.50。

a. 恰巧一所是1到6，一所7到10，所以有$6\times 4=24$种选择。一共有$10\times 9 / 2 = 45$。概率为$$\frac{24}{45}=\frac{8}{15}$$

b. 两所都是7到10，有$4\times 3 / 2=6$种。概率为$$\frac{6}{45}=\frac{2}{15}$$

c. 两所都是1到6，有$6\times 5 / 2=15$种。概率为$$\frac{15}{45}=\frac{1}{3}$$

这个结论不一定成立，但是当事件$a$和事件$b$独立的时候，结论是成立的。

1）如果事件$a$和$b$独立，那么$P(a,b)=P(a)P(b)$，那么

$$P(a,b|c)=P(a|c) P(b|c)>P(a)P(b)=P(a,b)$$

问题中的结论是成立的。

2）如果事件$a$和$b$不独立，上面的结论就不一定成立。举例：

事件$a=${扔一个骰子，1或者2朝上}

事件$b=${扔一个骰子，2或者3朝上}

事件$c=${扔一个骰子，1或者3朝上}

我们可以计算得到

$$P(a|c)=\frac{1}{2}, P(a)=\frac{1}{3}, P(b|c)=\frac{1}{2}, P(b)=\frac{1}{3}$$

符合条件中的$P(a|c) > P(a)$和$P(b|c) > P(b)$

但是

$$P(a,b|c)=0<P(a,b)=\frac{1}{6}$$

所以这个例子里原问题中的结论不成立。

可以从Bayesian考虑。$P(a,b|c)=P(c|a,b)/P(c)*P(a,b)$, 假如a和b的交集${a,b}$也和c相交，那么$P(c|a,b)/P(c)>1$，所以$P(a,b|c)>P(a,b)$。也就是如果有概率a,b,c同时发生，则证明成立。

iid指的是独立同分布

Independent Identical Distributed

比如说x，y i.i.d.，指的就是变量x和y是独立的，且服从同一个分布