37-rule-is-optimal

zhiqiangMay 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}$