UOJ Logo WuHongxun的博客

博客

UER#8 A 的最优复杂度

2019-01-31 14:46:49 By WuHongxun

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$的集合,不能直接用于这道题。有没有同学试一试不严格的随机方法能不能通过?

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。