Optimizing over iid distributions and the Beat the Average game 2412 15179v1

Potcast by Google NotebookLM(20241221토)

Subjects: Probability (math.PR)

Briefing Doc: Optimizing over IID Distributions and the Beat the Average Game

Authors: Pierre C. Bellec and Tobias Fritz

Source: "Optimizing over iid distributions and the Beat the Average game" (arXiv:2412.15179v1)

Main Theme: This paper investigates the problem of maximizing the expected value of a function under independent and identically distributed (iid) random variables. This question is explored through the lens of a gambling game called "Beat the Average," where the casino seeks to design dice that maximize their profit.

Key Ideas and Facts:

The "Beat the Average" Game: The game involves three identical dice. A player wins if their die's value is at least the average of the other two dice. The casino's goal is to design the dice to maximize their winning probability.
Optimizing over iid distributions: The paper tackles the general problem of finding the maximum expected value of a bounded function under iid random variables. They establish a theoretical framework and an algorithm to approach this optimization problem.
Bounding the winning probability: The authors prove that the maximum probability the casino can achieve in the "Beat the Average" game is 2/3, regardless of the number of sides on the dice.
"In the card version, the largest winning probability P [A less B+C / 2] for the casino is 2/3, independently of the number of cards m ≥ 3." (Proposition 1.4)
Discrete vs. continuous distributions: Interestingly, while the casino can approach the 2/3 winning probability with discrete dice by increasing the number of sides, this upper bound cannot be achieved with discrete distributions.
"It is still unclear if 2/3 in Theorem 1.5, which is the supremum of the probability in (1.6) over all distributions on R+, can be achieved by distributions with no atom."
"Bring Your Own Die": The authors analyze a variant where players bring their own die, demonstrating that even in this seemingly player-favorable scenario, the casino retains an advantage due to the non-achievability of the 2/3 bound with discrete distributions.
Maximizing probability of strict inequalities: The paper also delves into the problem of maximizing the probability of a strict linear inequality involving iid random variables. They introduce techniques, such as perturbing the variables, to derive lower bounds.
The 2/5 conjecture: The authors study the specific case of maximizing P[X1 + X2 + X3 less 2X4] for non-negative iid random variables. They provide a lower bound of 2/5 and an upper bound of 0.422, derived using mixed integer linear programming (MILP).
"0.4 = 2/5 ≤ sup µ Pµ⊗n [X1 +X2 +X3 less 2X4] ≤ 2304/5460 ≤ 0.422" (Equation 4.1)
They conjecture that the lower bound is actually the true supremum.

Overall, this paper offers a comprehensive analysis of optimizing over iid distributions, with practical implications for game design and theoretical insights into the behavior of random variables. The open problems presented provide exciting avenues for future research in this area.

Glossary

IID: Independent and identically distributed. In this context, it refers to random variables that are drawn from the same distribution and are independent of each other.
Non-standard dice: Dice with an arbitrary number of sides and non-uniform probability distribution for each outcome.
Probabilistic method: A mathematical technique that utilizes randomness to prove the existence of a particular object or property. It involves constructing a probability space where the desired object or property occurs with a non-zero probability, thereby guaranteeing its existence.
Maximum feasible subsystem problem: A combinatorial optimization problem where the goal is to find the largest subset of a given set of linear inequalities that can be simultaneously satisfied.
Mixed Integer Linear Programming (MILP): A type of optimization problem where the objective function and constraints are linear, and some of the variables are restricted to be integers.
Atom (in probability): A point in the sample space that has a non-zero probability assigned to it by a probability measure.
Essential infimum: The greatest lower bound of a random variable that holds almost surely (i.e., with probability 1).
Big-M method: A technique in MILP for encoding logical implications as linear inequalities using a large constant (M).
Farkas' lemma: A fundamental theorem in linear programming that provides a necessary and sufficient condition for the feasibility of a system of linear inequalities.