37-rule-is-optimal

zhiqiang五月 18, 2007 自然科学

Theorem: Any protocol of date problem has success probability less than $\frac{u}{n}\sum\limits_{i=u}^{n-1}\frac1i$ which is about $37\%$ . Here $u$ is the biggest number such that $\sum_{i=u}^{n-1}\frac1i\leq 1$ .

Proof: First, let's introduce some notation. $\Pi_n$ is the set of permutations of $\{1,2,\cdots, n\}$ .

For any two permutations $\alpha\in \Pi_a$ and $\beta\in \Pi_b$ , we say $\alpha \leq \beta$ if $a\leq b$ and $\alpha$ fit with the first a-th entries with $\beta$ (i.e. for any $1\leq i,j\leqa$ , $\alpha_i < \alpha_j \Leftrightarrow \beta_i < \beta_j$ )

For $\alpha\in\Pi_n$ , let $F_k(\alpha)$ is the permutation $\beta\in \Pi_k$ who $\leq \alpha$ .

Because the expectation of any randomized protocol is no more than the maximum of some deterministic protocol (randomized protocol is actually a distribution on the set of deterministic protocols), it suffice to consider deterministic protocol.

Let's look out how a protocol works. The protocol check the permutation one by one and determine when to stop. When the protocol examine the permutation $\alpha$ to the $k$ -th entries, the protocol doesn't have all the information of $\alpha$ but only knows $F_k(\alpha)$ . Supposed $S_k\in \Pi_k$ be the set of permutations who make the protocol stop. Let $s_k=|S_k|$ .

Obviously, any $\alpha\in S_k$ satisfies $\alpha_k=k$ .

For any $\alpha\in S_k$ , there are $\frac{n!}{k!}$ permutations larger than $\alpha$ . Among them, there are $\frac{(n-1)!}{(k-1)!}$ success permutations (i.e. the k-th entry is $n$ ). So the success probability is

$P=\frac{1}{n!}\sum_k\frac{(n-1)!}{(k-1)!}\cdot s_k$

Lemma 1: $S_k$ is disorder with each other, i.e. for any $i<j$ , $\alpha\in S_i$ and $\beta\in S_j$ , $\alpha$ couldn't be smaller than $\beta$ .

Otherwise the protocol will stop at $i$ -th entry when encounter permutation $\beta$ , then $\beta$ can't be in $S_j$ .

From Lemma 1, we know that for any $i$ ,

$\sum_{j=1}^{j-1}s_j\frac{(i-1)!}{j!} + s_i\leq (i-1)!$

by computing the number of permutation $\gamma\in \Pi_i$ whose $i$ -th entry is $i$ .

Let $t_i=s_i/i!$ and $u$ be the largest number makes $\sum_i=u^{n-1}\frac1i\leq 1$ , then for any $i$ ,

$\sum_{j=1}^{i-1}t_j+it_i\leq 1$

and

$\begin{array}{rcl}P&=&\frac1n\sum\limits_{k=1}^n kt_k\\&\leq&\frac1n\sum\limits_{i=u}^n(\sum\limits_{j=1}^{i-1}t_j+it_i)(1-\sum\limits_{j=i}^{n-1}\frac1i)\\&=&\frac1n\sum\limits_{i=u}^n(1-\sum\limits_{j=i}^{n-1}\frac1i)\\&=&\frac{u}{n}\sum\limits_{i=u}^{n-1}\frac1i\end{array}$

And the equality is made when the protocol ignores the first $u$ entries then stop at the first entry who is larger than the first $u$ -th entries.

关于婚姻模型, 策略, 约会 »

最佳约会策略题外话：最近阅微堂发的都是网友转发的政治方面的文章，不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题，已经被研究了很多年，有...
飞机加油问题珍爱生命，远离政治。今天我们讨论一个数学问题。这个问题的一个基本版本是说，有N架完全相同的飞机停留在一个机场，每一架最多装的油可以支...
硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
硬币游戏的答案前两天贴出了一个硬币游戏，希望寻找一种胜利策略。这是一个非常有意思的题目，没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布...
摸箱子问题以及在Static data structure problems上的应用以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆...
帽子游戏一在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们...
帽子游戏二这个题目听说是MSRA的面试题。在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
策略游戏：医生和病人（I）我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想...
征集3个人分蛋糕的方法 Yao在课程《理论计算机II》的第一节课上提到的一个问题：三个人如何平分一块蛋糕？要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自...