Number of Fixed Points in Random Permutations

概率论课, 一项作业是写篇小论文. 错排数是高中就总结过的, 恰好概率论某次习题课还讲到, 就花了一周时间又整理了下错排数(Rencontres Number)有关的东西. pdf放在github.

对于排列$\pi$, 设$\mathcal{F}(\pi)$是它的不动点集合: $$ \mathcal{F}(\pi) = \{ k \in [1,n]\cap \mathbb{N} : \pi(k) = k \} $$

设$\Pi_n$是所有可能$n$元排列的集合, 则错排数$D_{n,k}$可定义如下: $$ D_{n,k} = | \{ \pi \in \Pi_n : | \mathcal{F}(\pi) | = k \} |, k = 0,1,\cdots n $$

当排列等可能随机分布时, 其不动点个数的随机变量$X = | \mathcal{F}(\pi)|$, 这篇文章主要在总结$X$的性质.

(以上这些是在练习怎么把简单的东西用公式说出来..paper不是都这么发的么)

首先给了错排数公式$D_n = D_{n, 0}= n!\sum\limits_{i=0}^n{\frac{(-1)^i}{i!}}$的三种推导. 容斥原理与递推式的倒是很常见了, 不过我最喜欢的是用Inversion Formula的, 简洁巧妙.

然后利用错排数, 就可以得出随机变量$X$的分布, 便可以利用分布列求其期望方差. 当然也可以用期望可加性和协方差, 绕道求期望方差, 更美观.

求这个随机变量的各阶矩用到了第二类Stirling数 的性质, 最终发现, 它的前$n$阶矩恰好是Bell Number.

中间一节跑了个题, 证了$D_n = \dfrac{\Gamma(n+1, -1)}{e}$, 为之后用到做准备.

然后是一些估计的话题. 把$X$的分布与Poisson分布做了比较, 证了$D_n \approx \dfrac{n!}{e} $. 也就是说, 有$\dfrac{1}{e}$的排列是全部排错的. 这也是个不错的结论.

之后就求了四个母函数. $D_n$的普通母函数和指数母函数, 以及$X$的概率母函数和矩母函数. 竟然要解两个ODE.

其实都是些小结论, 网上一般也找得到. 不过整理出来看感觉很爽而已..


开哥那时候同时也在写一个好玩的论文, 是判断一个无理数的小数位数是否随机的..听上去有点伪科学, 不过这是老师给的题.

他先证明了十进制小数各数字均匀分布与二进制下均匀分布等价, 然后就转到二进制下研究$\sqrt{3}与\pi$的随机性.想了各种神奇的方法:

  • 把二进制画出黑白图来看: 看不出规律
  • 各位数平均数: 都趋于0.5
  • 研究无理数整数倍的小数部分的分布: 然后我查了一下发现根据Weyl's Criterion, 任何无理数整数倍的小数部分都均匀分布.
  • 衡量连续的相同块的长度, 看与理论值的偏差: $\pi$比$\sqrt{3}$更随机.
  • 用它们作为随机数的生成种子, 生成均匀分布与正态分布, 看生成的好不好..
  • 把它们拼成一个矩阵算秩, 跟随机矩阵的理论秩比较..

太高端了给跪..

(update: 虽然论文得了最高分不过考试还是跪了= =不会背书..)

Comments