标题： k个两两独立的位都为1的最大概率 显示英文标题

标题： The Maximal Probability that k-wise Independent Bits are All 1

摘要： 一个k-wise独立的n位分布是这样的联合分布，其中任意k个位都是独立的。 在本文中，我们考虑具有相同边缘分布的k-wise独立分布，每个位取1的概率为p。 我们研究以下问题：对于这样的分布，所有位都为1的概率最高可以达到多少？ 对于n、k和p的广泛参数范围，我们找到了该概率的显式下界，该下界与Benjamini等人给出的上界相匹配，仅在低阶乘数因子上有所差异。 我们研究的问题可以看作是纠错码理论中一个主要开放问题的放松形式，即如何确定给定参数下的线性纠错码的最大可能大小？ 这个问题是一种离散矩问题，我们的方法基于证明从经典矩问题理论中得到的界限对该问题提供了良好的近似。 我们使用的主要工具是一个控制多项式在其零点经过小扰动后期望值变化的界限。 显示英文摘要

摘要： A k-wise independent distribution on n bits is a joint distribution of the bits such that each k of them are independent. In this paper we consider k-wise independent distributions with identical marginals, each bit has probability p to be 1. We address the following question: how high can the probability that all the bits are 1 be, for such a distribution? For a wide range of the parameters n,k and p we find an explicit lower bound for this probability which matches an upper bound given by Benjamini et al., up to multiplicative factors of lower order. The question we investigate can be seen as a relaxation of a major open problem in error-correcting codes theory, namely, how large can a linear error correcting code with given parameters be? The question is a type of discrete moment problem, and our approach is based on showing that bounds obtained from the theory of the classical moment problem provide good approximations for it. The main tool we use is a bound controlling the change in the expectation of a polynomial after small perturbation of its zeros.