知乎被邀请回答了一个问题，和之前探索过的类似。问题如下：
10个不同的盒子，每个盒子里装有10块饼干。每次随机选择一个盒子，然后吃掉其中的一块饼干。直到第一次出现了任何一个空盒子就结束。求吃的饼干数目的期望。
这种问题是求第一次遇见的步长问题。我们可以转换为下面两步来求：
多键值排序是把快速排序(Quick Sort)和基数排序(Radix Sort)结合起来的算法。论文为 Fast Algorithms for Sorting and Searching Strings (J. Bentley, R. Sedgewick) 。Greenplum 6里面有实现，本文是我自己按论文搜索资料，一步一步复习、学习、整理的记录。
教授的讲座资料：
前两天有同事分享看到信息熵的公式觉得非常巧妙，一下子把我的回忆带回到了15年的前本科时代，那时候学习过一门很有意思的课程信息论。信息论基本上就是祖师爷Claude Shannon一篇无比经典的论文A Mathematical Theory of Communication 安排的明明白白。本科时候我准备尝试去看这个论文，结果卡在第一处后就不了了之了，至今记忆犹新。
今天在公司用白板做了一个简单的讲座，介绍如何用Analytical Combinatorics研究组合结构，分析算法。内容如下:
视频在此
Continue readingI solved the problem about 2 years ago and it was the Problem 1 of Final exam of EE of THU (see my previous solution here). That time I did not use symbolic method. Not sure why, a symbolic method just comes to my mind and here comes the blog.
Continue readingSee the PDF version of the article. It can also be downloaded here.
Continue readingSomeone on 知乎 invited me to answer this question. 中文版在此: https://www.zhihu.com/question/420632736/answer/1469911740
A point started at the origin, each step it can either move to left or right by one unit with equal probability.
Q: what is the probability for after m steps, this point never touch any negative point?
Continue readingThe problems are from the Book Jaynes, Edwin T. Probability theory: The logic of science. Cambridge university press, 2003. Chapter 3 of the book is on the topic of Elementary sampling theory. These problems can be easily solved using the symbolic method of analytical combinatorics.
Continue reading