|
Speaker:
Robert Ellis, (Texas A&M University)
Title:
A 2-player game for adaptive covering codes
Abstract:
A sequence of q games are played with Win/Loss outcomes. A single bet
consists of q W/L predictions, one for each game. A payoff occurs
for a bet which predicts at most k games incorrectly. We first
consider the minimum number of bets needed to guarantee a payoff,
and the relationship to covering codes of fixed radius. We then
consider the minimum number of bets needed when each prediction is
allowed to be made just before the corresponding game. We reformulate
the question as a 2-player perfect information game and analyze it to
show that the minimum size of an adaptive covering code of fixed radius
is within an absolute constant of the sphere bound. Time permitting,
connections with random walks will be discussed. (Joint work with
Vadim Ponomarenko and Catherine Yan.)
|