[数学]抽扑克

2n张牌,n张红n张黑.随机从这副牌里连续抽牌(抽出来后就不扔回去了),平均能够看见多少次连续两张红牌?如连续三张红牌,视为看见两次.平均能看见多少次前一张红牌后一张黑牌?

Sol: 先定义随机变量

I_{i}=\begin{cases} 1 & \textrm{ith,(i+1)th are both read}\\
0 & \textrm{otherwise}
\end{cases}

这样能看见的连续红牌次数X = I_1+I_2+...+I_(2n-1). 虽然I_i和I_j之间并不独立(比如你前n张都抽的是红牌,那么后n张只能是黑牌了),但是如果是对X求期望,就可以把各个I_i单独拎出来求期望,再对期望求和:

E[X] = E[I_1]+\cdots+E[I_{2n-1}]=(2n-1)\frac{n}{2n}\frac{n-1}{2n-1}=\frac{n-1}{2}

同理可以得到看见先红后黑的平均次数是 n/2

[数学]关于扔硬币得到的序列

现在有一枚硬币, 每次以概率p得到正面(下面以H代表),概率q=1-p得到反面(以T代表).反复投掷这枚硬币并记录出现的结果序列, 比如 T H H T T T H H T H...这样的一个序列. 针对这个序列我们可以说,在时间4我们完成了一个pattern THHT, 在时间6我们完成pattern TTT, 时间9又重复出现了pattern THHT.

下面是一些直观上容易理解的以及费解的:)结论: 

1. 一个长度为k的给定pattern,在t时刻出现的概率为 p^i q^(k-i).这里i是pattern中T出现的次数. 这个很好理解.比如TTT在任意时刻出现的概率是p^3,  THHT是p^2 q^2, HTHT也是p^2 q^2
2. 同一个pattern, 两次出现的时间间隔的期望是 1/[p^i q^(k-i)]. 这个结果也很直观. 可以根据Delayed Renewal Process得到. 所以THHT出现间隔是1/(p^2 q^2),HTHT出现间隔也是1/(p^2 q^2)
3. 一个pattern, 从第一次扔硬币开始到第一次出现的时间期望
   
   E[time until HTHT] =  E[time until HT] + E[time between HTHT] = E[time between HT] + E[time between HTHT] = 1/(pq) + 1/(p^2 q^2)
   
   这里的一个trick是把pattern HT和HTHT之间的时间间隔等同于出现pattern HTHT 的间隔. 仔细想一下的话, 出现一次HTHT后这个pattern对下一次出现HTHT的贡献(或者影响)就是它的尾巴HT了. 同理我们还有
   
   E[time until THHT] =  E[time until T] + E[time between THHT] = E[time between T] + E[time between THHT] = 1/p + 1/(p^2 q^2)
   
   所以从第一次投硬币开始观察的话,  HTHT和THHT第一次出现的平均时间是不同的.
   同样我们也可以得到连续k个T出现的平均时间, 注意每一次连续出现i个T都对i+1个T有贡献
   
   E[time until k consecutive T] = 1/p + 1/p^2 + ... + 1/p^k
   

这个问题还有一个利用Martingale的方法来算,而且是Bob Li提出来的(A martingale approach to the study of occurrence of sequence
patterns in repeated experiments, Annals of Probability, 1980).比如我们要求E[time until HTHT].设在第i轮,一个赌徒下注1块钱.如果第i轮结果是H,赌徒就赢得1/p块钱,接下来第i+1轮结果是T,赌徒就赢得1/(pq)块钱,以此类推.不过如果一旦没有压准,所有钱就输了.请注意这是一个公平赌博.如果每一轮都有一个赌徒来下注.设Xn为第n轮下来赌场的收入:
Xn=(n-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1

因为Xn是Martingale,所以 0 = E[Xn] = (E[n]-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1
也就得出E[n] = 1/(pq) + 1/(p^2 q^2)

[数学]比较k个随机数加权后的大小

如果有k个随机变量x_1..x_k独立同分布于U[0,1],每个随机变量对应一个非负权重a_1...a_k.
那么加权后第一个随机变量比其他随机变量加权后都大的概率(i.e., a_1x_1>= a_ix_i for all i):

Sol:
如果给定x_1=x, a_1x_1比a_ix_i大的概率为min(a_1x_1/a_k,1)

\int_{0}^1\min(\frac{a_1x}{a_2},1)\cdots \min(\frac{a_1x}{a_k},1) d x

[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n　也就是出现第i种新coupon的概率.

E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n

该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:

\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}

[数学]停车问题

Mathproblem上看来的问题. 一条街长度为4,最初这条街是空的.大家都开着长度为1的车子来来往往,寻寻觅觅.一旦发现街上有足够大的长度空着, 就会把车停下来.糟糕的是大家停车的时候在所有可能的泊车位随机的挑选,丝毫不会去为后面的人考虑.那么这条街,平均能停几辆车.

Sol:假设f(x)是在一条长度为x的空街上平均能停的汽车数目,当x>1的时候

f(x) = 1+\frac{\int_0^{x-1}[f(t)+f(x-1-t)]dt}{x-1} = 1 + \frac{2}{x-1}\int_0^{x-1}f(t)dt

不难得知

• 0<x<1: f(t)=0
• 1<x<2: f(t)=1
• 2<x<3:
  

  f(t)=1+2\frac{\int_0^{t-1}f(u)du}{(t-1)} = 1+\frac{2(t-2}{t-1}
  

所以

f(4)=1+\frac{2}{3}[\int_0^{1}f(t)dt + \int_1^{2}f(t)dt + \int_2^{3}f(t)dt] = \frac{11}{3} - \frac{4}{3}ln 2

[数学]挑西瓜 (optimal stopping problem)

有N个房间,每个房间有一个西瓜,需要你挑出最大的那个西瓜.你需要按着房间顺序一个房间一个房间的查看西瓜.每当你看完一个房间的西瓜后,你需要立即决定是(1)挑选当前的西瓜还是(2)接着往下看.如果挑了当前的西瓜你就不能看后面其他房间.如果往下看了就要放弃当前西瓜而只能选择后面房间里的西瓜.使用怎样的策略能够让你最大化自己挑到最大西瓜的概率.

Sol: 这是传说中的Secretary Problem. 一个众所周知的算法是: 对于前s个房间只用于观察,我们记下前s-1个房间最大西瓜的尺寸.然后从第s+1个房间开始,一旦碰到比我们记下的尺寸还大的,就挑选之.如果一直没有碰到,就挑选最后一个房间里的.记Pr(s)为挑到最大西瓜的概率.

Pr(s) = \sum_{j=s}^n \frac{1}{n}\frac{s-1}{j-1}=\frac{s-1}{n}\sum_{j=s}^n \frac{1}{j-1}

这里1/n 是最大西瓜在第j个房间的概率,(s-1)/(j-1)是之前j-1个房间中最大的西瓜在房间1到房间s-1的概率. 可以证明s取n/e的时候这个概率取最大值.


Odds算法是该题另一种解法,事实上它的实用性更广.

[数学]连续两天降雨的概率

问题:(from mitbbs) Weather forecast: 50% chance of rain tomorrow, 75% chance of rain the day after tomorrow. What is the chance of rain for both tomorrow and the day after tomorrow?

Sol: 50%*75%? 这并不是一个严谨的答案.因为明天降雨和后天降雨未必是两个独立事件. 所以应该给出的是一个界

1/4=max{0, P[明天降雨]+ P[后天降雨]-1}< P[明天降雨 and 后天降雨] < min{P[明天降雨], P[后天降雨]}=1/2

[数学]比较两个随机数大小

问题:(zz from mitbbs)在两张纸A,B上分别随机写两个数字，两个数字不相等。所以猜对哪个大的概率为1／2。现在随机翻开A或者B，再猜A或者B上哪个数字大。设计一种策略使得你猜对的概率大于1/2。

答案:不妨设A,B都为[0,1]之间的均匀分布.如果我们在猜之前知道A=x,那么当x<1/2的时候我们以概率(1-x)猜测B大,如果x>1/2我们以概率x猜测A大.采用这种随机策略,我们可以获得准确率:

\int_{x=0}^{1}x^2+(1-x)^2 d x = \frac{2}{3}

[数学]三个囚徒的问题

从mitbbs上看到这道题,并查了wiki,觉得挺有意思的. 特别是两个版本细微的差别就会导致结果的不一样.

版本1
一个国王决定从3个囚徒A,B以及C中释放一个,处决另外两个.国王告诉A说,处决的犯人中不是A的那个(如果两个都不是A,则随机说一个)是B.A在得知这个信息以后,他被处决的概率是多少?
SOL: 1/3

版本2
一个国王决定从3个囚徒A,B以及C中释放一个,处决另外两个.国王告诉A说,处决的犯人包括B.A在得知这个信息以后,他被处决的概率是多少?
SOL: 1/2

用列举法来解释结果:

国王的决定	版本1国王告诉A	版本1可以排除掉	版本2可以排除掉
放A 杀B 杀C	B
放A 杀B 杀C	C	x
杀A 放B 杀C	C	x	x
杀A 放B 杀C	C	x	x
杀A 杀B 放C	B
杀A 杀B 放C	B