[Linux]Makefile速查

基本语法:

target: prerequisites
    command

target:	规则生成的目标. 可以是最终的目标文件,也可以是中间文件,还可以是“伪目标”(比如all,clean)
prerequisites:	生成规则目标所需要的文件名列表
command:	生成规则目标所要执行的动作,可以是一行也可以多行.但每行必须以tab开头

一个Makefile就是由一个或多个规则构成.默认的情况下，make执行的是Makefile中的第一个规则.比如下面例子:

# 定义变量可以方便修改
objects = main.o utils.o
#默认最终生成目标:edit
edit : $(objects)
    cc -o edit $(objects)
#指给定.o目标所需要的.h文件,make自动使用.o文件同名的.c文件,并且使用cc编译
main.o : defs.h
utils.o : defs.h
#告诉make clean是一个伪目标而不是真实文件
.PHONY : clean
clean :
    rm edit $(objects)

内部宏:

$?：	比目标的修改时间更晚的那些依赖模块表。
$@ ：	当前目标的全路径名。可用于用户定义的目标名的相关行中。
$<：	比给定的目标文件时间标记更新的依赖文件名。
$* ：	去掉后缀的当前目标名。例如，若当前目标是pro.o，则$*表示pro。

通配符

HEADERS=$(wildcard ./*.h)

参考:
[1] GNU Make中文手册

[数学]抽扑克

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