The Second-Order Football-Pool Problem and the Optimal Rate of
Generalized-Covering Codes
Abstract
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$.