Number of Fixed Points in Random Permutations

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

对于排列 , 设 是它的不动点集合:

设 是所有可能 元排列的集合, 则错排数 可定义如下:

当排列等可能随机分布时, 其不动点个数的随机变量 , 这篇文章主要在总结 的性质.

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

首先给了错排数公式 的三种推导. 容斥原理与递推式的倒是很常见了, 不过我最喜欢的是用 Inversion Formula 的, 简洁巧妙.

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

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

中间一节跑了个题, 证了 , 为之后用到做准备.

然后是一些估计的话题. 把 的分布与 Poisson 分布做了比较, 证了 . 也就是说, 有 的排列是全部排错的. 这也是个不错的结论.

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

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

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

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

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

太高端了给跪..

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