UER8的那天，uoj管理员群里突然出现一个神圣跳蚤君主国国王！

vfk：我证明了UER 8A的lower bound是1.206n，有没有人给一个match的upper bound啊？

众人：[惊呆]

然后我跑到vfk的寝室，看vfk表演了怎么得出这个lower bound和对应的upper bound。

whx：Orz 在uoj blog里写下这个做法吧！

vfk：太忙了，咕咕咕。

于是只有辣鸡whx来复读一遍了。

Lower bound

首先，我们考虑单轮交互的情况，也就是Bob先发一个信息$x$给Alice，然后Alice发一个信息$y$给Bob。

假设$|x| \leq m, |y| \leq m$，由于$x$只有$2^m$种，那么至少有$\frac{\binom{2n}{n}}{2^m}$个下标集合$I$会导致相同的$x$。

那么Alice要发给Bob这些集合的并，但是Alice发过去的集合最多覆盖$\binom{m}{n}$个集合。

为了解$\frac{\binom{2n}{n}}{2^m} \leq \binom{m}{n}$，我们设$m = n/r$，那么$\binom{m}{n} =\binom{m}{rm}=2^{m(H(r) + o(1))} $，其中$H(p) =plog_2\frac{1}{p}+(1-p)\log_2\frac{1}{1 - p}$是大家熟悉的信息熵。

所以$\frac{2^{2mr}}{2^m \sqrt{2mr}} \leq 2^{mH(r)}$，两边同时取$log$得：$2mr - log(mr) \leq m(H(r) + 1)$

因为我们只关心乘在$n$上的系数，不妨舍去log项，从而得到$2r \leq H(r) + 1$, 如果召唤mathematica，我们很快就知道$m = n / r =1.206n$

这个Bound同样适用于多轮的情况，不严谨的说，因为在多轮交互中，Alice发给Bob的信息只能依赖于Bob之前发过来的信息，以及Alice自己的串，从而在给出了Bob之前发来的串之后，对Bob手里的集合$I$信息量为0。（有人有兴趣用conditional mutual information严谨的证一下吗）所以最后Alice发给Bob的还是至少是$\frac{\binom{2n}{n}}{2^m}$个集合的并。

另外，这个Bound也一样适用于高概率正确的随机化算法，因为它要在趋近于1的比例的下标集合$I$上合法，就必须

Upper bound

Shannon在证明存在一种编码方式可以达到信道容量的时候，所用的方法就是给每个元素随机编码，我们也用一样的思路。

Bob要发给Alice的其实是$I$的一个超集，所以我们现在的问题其实是，我们要从$N=\binom{2n}{m} = \binom{2mr}{m} = 2^{2mr\left(H\left(\frac{1}{2r}\right)+o(1)\right)}$个大小为$m$的集合中，选出不超过$M=2^m$个，使得每个可能的下标集合$I$都是某个集合的子集，我们不妨随机选这$2^m$个集合。

因为一共有$K=\binom{n}{m-n} = \binom{mr}{m(1-r)}=2^{rm(H(\frac{1-r}{r})+o(1))}$个集合覆盖了$I$，其中一个集合都没被选的概率就是： $$ p=\frac{\binom{N-K}{M}}{\binom{N}{M}}=\frac{(N-K)^{\underline M}}{N^{\underline M}}\leq\left(1-\frac{K}N{}\right)^M=(1-2^{rm(H(\frac{1-r}{r})-2H(\frac{1}{2r})+o(1))})^{2^m} $$ 我们做一些简单的计算：

\begin{equation}\begin{split} &H\left(\frac{1-r}{r}\right)-2H\left(\frac{1}{2r}\right)\\ &= \frac{1-r}{r} log\left(\frac{r}{1-r}\right)+\left(1-\frac{1-r}{r}\right)log\left(\frac{1}{1-\frac{1-r}{r}}\right)-2\left(\frac{1}{2r}log\left(\frac{1}{2r}\right)+\left(1-\frac{1}{2r}\right)log\left(\frac{1}{1-\frac{1}{2r}}\right)\right) \\ &=\frac{1-r}{r}(log(r) - log(1-r))+\left(1-\frac{1-r}{r}\right)(log(r) -log(2r-1))+\frac{1}{r}(log(r)+1)-\left(2+\frac{1}{r}\right)(log(r)+1-log(2r-1)) \\ &=\left(\frac{1-r}{r}+1-\frac{1-r}{r}+\frac{1}{r}-2-\frac{1}{r}\right)log(r)-\frac{1-r}{r}log(1-r)+\left( \frac{1-r}{r}-1 +2-\frac{1}{r}\right)log(2r-1)+\frac{1}{r}-2-\frac{1}{r} \\ &=log\left(\frac{1}{r}\right)+\frac{1-r}{r}log(1-r)-2 \\ &=\frac{H(r)-2r}{r} \end{split}\end{equation}

也就有 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} $$ 因为$H(r)+1-2r\rightarrow 0$，所以$H(r)-2r<0$, $2^{m(H(r)-2r)}\rightarrow 0$，从而 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} =(1-2^{m(H(r)-2r)})^{2^{m(2r-H(r))+(H(r)-2r+1)m}}=e^{-2^{(H(r)+1-2r)m}} $$ 我们取$H(r)+1-2r> \varepsilon$，那么在$m \rightarrow \infty$的时候，$p \rightarrow 0$，不难发现$\binom{2n}{n}p\rightarrow 0$，我们随机选的集合大概率能覆盖所有这样的$I$。结论就是，我们可以任意逼近我们之前推出的lower bound。

Remark

这道题如果优化的目标，变成二者所发信息的和，那么就是一个典型的”通信复杂度“的问题了，但是那样的话，我们的方案$2.412n$还不如直接把整个串发给Bob。事实上直接把整个串发给Bob也最优的复杂度了，因为Bob可以计算出两个串对应的集合有没有交，也就是Set disjointness上。

同时这个方法因为需要uniform的随机取$2^m$个大小为$m$的集合，不能直接用于这道题。有没有同学试一试不严格的随机方法能不能通过？