37-rule-is-optimal

Theorem: Any protocol of date problem has success probability less than $\frac{u}{n}\sum_{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\leq a$, $\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.

Q.E.D., ©zhiqiang, 2007.05.18。请参考右边的相关文章列表。

---