文章目录[隐藏]
昨晚和以前实习的同学讨论一个上界的问题，如果在未来博士的过程中也能有这样的氛围就好了。
主要就是一道概率论题
已知\(\begin{array}{l}A \sim B i n o m(n, p) \ B \sim B i n o m(\frac{A(A-1)} 2, q)\end{array}\)，求H（B），即B的entropy。
这里的难点是如何求二项随机分布的二项分布。直观上感觉后者的熵值是前者的 \(log(log())\) 这种。可对A的展开太过繁琐。敲在mathmetica当中可以是 \(P(B=i) = Sum[P(B=i|A=j)*P(A=j),{j,0,n}]\)，暂时我只想到这种解法。
这个问题我找了找网络前两节课上的信息论推荐的书，上面有类似对于二项式分布的相关性质，可是唯一提到的也就是在 \(p\) 上做文章。fix n，H（A）的 max 在 p 取 \(\frac12\) 时取到。然而没啥卵用。
概率论与图论背后的算法
算这个事为了做一个算法去recover这个
ER random graph，given每次只能query graph的一小部分里面有没有edge的存在。
这个 random graph 很有名，很多概率图都是基于此。也是 TCS 求 lower bound 的一种方式，很多人梦寐以求的方向。