论文标题
二级足球池问题和广义覆盖代码的最佳速度
The Second-Order Football-Pool Problem and the Optimal Rate of Generalized-Covering Codes
论文作者
论文摘要
经典足球池问题的目的是确定要购买多少张彩票，以确保至少$ n-r $正确的猜测，从$ n $游戏中的序列中猜出。我们研究了此问题的广义（二阶）版本，其中这些$ n $游戏中的任何一个由两个子游戏组成。足球池问题的二阶版本是使用广义覆盖半径的概念提出的，该概念最近提出是线性代码的基本属性。我们考虑将此属性扩展到一般（不一定是线性）代码，并通过找到固定的归一化覆盖半径的二阶覆盖代码的最佳速率函数来为我们的问题提供渐近解决方案。我们还证明，由于代码长度趋向于$ \ infty $，因此覆盖足够大的代码之间的二阶覆盖代码的分数往往$ 1 $。
The goal of the classic football-pool problem is to determine how many lottery tickets are to be bought in order to guarantee at least $n-r$ correct guesses out of a sequence of $n$ games played. We study a generalized (second-order) version of this problem, in which any of these $n$ games consists of two sub-games. The second-order version of the football-pool problem is formulated using the notion of generalized-covering radius, recently proposed as a fundamental property of linear codes. We consider an extension of this property to general (not necessarily linear) codes, and provide an asymptotic solution to our problem by finding the optimal rate function of second-order covering codes given a fixed normalized covering radius. We also prove that the fraction of second-order covering codes among codes of sufficiently large rate tends to $1$ as the code length tends to $\infty$.
