Carmér‘s Theorem

我们知道,两个独立的正态随机变量加起来还是一个正态的随机变量。但是反过来呢?是不是两个独立的随机变量加起来是个正态,它们就都是正态呢?Carmér定理说的就是这样一件事情:假设X_1, \cdots, X_n是一组独立的随机变量,并且X_1+\cdots+X_n是服从正态分布的,那么X_1,\cdots,X_n都是服从正态分布的。

这是这学期概率论课上老师给的bonus问题,这个定理原始论文是“Über eine Eigenschaft der normalen Verteilungsfunktion”,一篇用德文写的。然后我看着它的公式大概猜了一下这篇文章在干啥…… 证明见下面正文,应该是对的吧。感觉这个证明把这学期实分析、复分析学的东西都用上了一些。

主要的思路是,先证明特征函数\mathbb E[e^{itX}]可以定义在整个复平面上,并且是一个解析函数。同时,证明这个函数的增长阶是2并且没有零点,之后用Hadamard因子分解定理说明它的形式。

还有一个叫做Raikov定理,和这个定理非常相似,把定理中的“正态分布”换成“Poisson分布”就是Raikov定理的内容。证明和这个定理也很像,不过需要先说明两个随机变量都是离散的。

(more…)

Read More

FPGA Console——硬件实现的VT220兼容终端

这是和@HarryChen在这学期数字逻辑课上做的项目。主要是利用FPGA模拟一个终端。项目放在https://github.com/miskcoo/fpga-virtual-console上。

现在大部分的操作系统都是内置有虚拟终端,就像Linux下的xterm、gnome-terminal。但是,在最初控制台和计算机是相互独立的。控制台一般是由键盘和屏幕组成,键盘将用户输入传入计算机,计算机将输出发送显示给用户。这整个通信的过程是有一套标准来规定的,例如VT100就是一个早期的标准,更进一步有VT220、xterm-256color等。由于计算机回显的数据并不是单纯地整个屏幕的像素数据,而是更高层次的类似控制命令的内容,例如表示光标移动到某个位置,在某个位置插入某个字符,删除某一行的字符等。这些标准主要是定义了计算机发送回的这些控制命令的行为,和键盘发送给计算机的控制命令的行为。

我们做的这个项目就是一个物理上的终端!通过FPGA接受键盘的输入,将输入转化为控制命令通过串口输出给计算机。同时也通过串口接受计算机传回的控制命令名且解析、执行,修改对应位置的字符,再将字符进行渲染通过VGA输出到屏幕。

主要支持的标准是VT220,以及xterm-256color下大部分影响最终显示效果的指令,对于大部分linux下的程序的输出都可以正确地解析。同时串口速度提升到了3M可以支持以大约170fps的帧率播放黑白字符视屏,和约30fps的帧率播放彩色字符视屏。简单来说,就是正常终端可以做的事情这个物理终端都可以做到。

比如下面就是一个调用笔记本上摄像头的例子(我真的不是直接把VGA连到电脑上了),这时候串口速度还没那么快所以看起来有点卡……

fpga-camera

具体的细节我就不打算说了,文档里都写得非常明白。

https://github.com/miskcoo/fpga-virtual-console/raw/v1.0/doc/report.pdf

Read More

Pólya’s Urn

Pólya’s Urn是这样一个模型:假设现在有一个盒子,里面有r个红球和g个绿球,现在不断地随机从盒子取出一个球,之后再放回去,外加放入额外的c个和取出的球颜色相同的球。现在问,盒子中绿色球的比例在最后是否会趋向与某个分布?

实际上最后这个比例会是一个参数是g/cr/c的Beta分布。

首先我们设S_n = r + g + nc是第n次操作后盒子中所有球的数目。再设G_n, R_n分别是第n次操作后盒子中绿色球、红色球的数目。以及令X_n = G_n / S_n, \mathcal F_n = \sigma(G_k, S_k, 0 \leq k \leq n)。计算条件期望

 \begin{aligned}
\mathbb E[G_{n+1} | \mathcal F_n] &= \frac{G_n}{S_n}(G_n + c) + \frac{R_n}{S_n}G_n \\
&= (c + S_n) X_n = S_{n+1} X_n
\end{aligned}

可以看出\mathbb E[X_{n+1}|\mathcal F_n] = X_n\{X_n\}是一个鞅。再由于0\leq X_n \leq 1,我们知道X_n几乎处处收敛到一个随机变量X。现在考虑其分布。

首先可以计算出在第n步及以前,有m \leq n次取出绿色球的概率,并且写为紧凑的形式如下

 \begin{aligned}
&\mathbb P\left[ X_n = \frac{mc + g}{nc + g + r} \right] \\&= \frac{n!}{m!(n-m)!}\cdot \frac{\displaystyle\prod_{k=0}^{m-1}(k + g/c) \prod_{k=0}^{n - m - 1}(k + r/c)}{\displaystyle\prod_{k=0}^{n - 1}(\frac{g+r}{c} + k)}\\&= \frac{\Gamma(n + 1)}{\Gamma(m + 1)\Gamma(n - m + 1)}\cdot \frac{\Gamma(m + g/c)\Gamma(n - m + r/c)}{\Gamma(n + (g + r)/c)\text{B}(r/c, g/c)}
\end{aligned}

其中\Gamma\text{B}分别是Gamma函数和Beta函数。

接下来利用Stirling公式\Gamma(x) = \sqrt{2\pi/x} (x/e)^x (1 + O(1/x)),可以得到

 \frac{\Gamma(x + a)}{\Gamma(x + b)} = x^{a - b} \left( 1 + O\left( \frac{1}{x} \right) \right)\text{ as } x \to \infty

那么对于固定的\alpha, \beta, m满足0 < \alpha < \beta < 1以及\alpha n < m < \beta n,可以有

 \begin{aligned}
&\mathbb P\left[ X_n = \frac{mc + g}{nc + g + r} \right] \\&= \frac{1}{\text{B}(r/c, g/c)} n^{1 - (g + r)/c} (n - m)^{r/c - 1} m^{g/c - 1} \left( 1 + O\left( \frac{1}{n} \right) \right)\\
&= \frac{1}{n \text{B}(r/c, g/c)} \left (1 - \frac{m}{n} \right )^{r/c - 1} \left( \frac{m}{n} \right)^{g/c - 1} \left( 1 + O\left( \frac{1}{n} \right) \right)
\end{aligned}

对于所有满足\alpha n < m < \beta nm求和

 \lim_{n\to \infty} \mathbb P[\alpha \leq X_n \leq \beta] = \frac{1}{\text{B}(r/c, g/c)}\int_{\alpha}^\beta (1 - x)^{r/c - 1}x^{g/c - 1} dx

最后可以得到X的分布是\text{Beta}(g/c, r/c)

Read More