Greedy Dictator optimality conjecture for guessing efficiency on the binary erasure channel
Statement
Let be uniformly distributed over , let be obtained by passing through a memoryless binary erasure channel with erasure probability , and let denote the optimal guessing efficiency for moment order . A Greedy Dictator function sends the first non-erased bit, using an independent Bernoulli random bit when all bits are erased. Greedy Dictator conjecture. Greedy Dictator functions attain
for the binary erasure channel. This conjecture is motivated by the local optimality result for and numerical computations for moderate values of ; the statement concerns simultaneous optimality across the erasure parameter and moment order, and its resolution is not given here.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.