Optimizing over iid distributions and the Beat the Average game

Dice version

• The casino manager problem asks for the largest probability of A < (B+C)/2 when A, B, and C are N-valued iid random variables.Dice are modeled as distributions over natural-number outcomes, including infinitely many-sided dice; the maximum may be approached by finite dice with increasingly many sides.Source: §1 · pp. 2–3

Card version

• For the card version, the casino’s largest winning probability is 2/3, independently of the deck size m ≥ 3.A suitably skewed deck achieves the bound, while a probabilistic-method argument shows that no larger deck can exceed it.Source: §1 · p. 4
• In the card game, players should play only when the casino offers more than three times the bet upon winning.If the payout is lower, the casino can choose a deck that gives it winning probability 2/3.Source: §1 · p. 4

Dice version

• For iid nonnegative dice outcomes, the casino’s winning probability is bounded above by 2/3, with strict inequality whenever the distribution has an atom.Equal-probability dice with values 1, 2, 4, 8 already let the casino win with a probability exceeding 1/2, and the optimal finite-die probabilities approach 2/3 as the number of sides grows.Source: §1 · p. 5
• The dice supremum 2/3 cannot be achieved by an iid distribution with discrete atoms, unlike the card version’s exact 2/3 optimum.The section leaves open whether continuous-outcome dice can attain 2/3 exactly and defers attainability to Section 5.Source: §1 · pp. 5–6

• The casino always has a strict average advantage, even though customers choose their own die and can approach a fair game.This follows from the non-achievability part of Theorem 1.5.Source: §1 · p. 6
• Any payout strictly larger than $3 would be unfair to the casino and could objectively bankrupt it.Source: §1 · p. 6

Notation

• Finite-set averaging is formalized using uniform averages over maps and injections between finite sets.The injection average normalizes by the falling factorial |B|(|B|−1)···(|B|−|A|+1).Source: §2 · p. 7

Proof strategy

• The upper bound is obtained by averaging f over injections into an m-element set and applying exchangeability and the supremum bound for expectations.The proof uses uniform averaging over injections and the fact that an integral cannot exceed the supremum of its integrand.Source: §2 · pp. 7–8

General method

• Theorem 2.4 characterizes iid optimization through a sequence of finite sampling-without-replacement upper bounds that converges to the exact value.These bounds are monotonically nonincreasing in the finite-set size m.Source: §2 · p. 8

Approximation guarantee

• For nonnegative f, the finite-m approximation is within a multiplicative factor determined by the probability that n samples from m items are distinct.A distribution supported on m points achieves the supremum up to the same factor.Source: §2 · p. 9

Application

• Applying the method to iid real variables proves P[|X1−X2|≤2] ≤ 3P[|X1−X2|≤1], and the factor 3 cannot be improved.The paper constructs distributions making the inequality tight in the relevant asymptotic sense.Source: §2 · pp. 9–10

Scope conditions

• The strict-inequality formulation is essential because non-strict inequalities can attain probability 1 using all-zero variables.The paper also excludes trivial deterministic solutions when the coefficient sum is nonzero.Source: §3 · p. 10

Structural tension

• A distribution near optimality faces a tension: it cannot be supported away from 0, yet it cannot place too much mass at 0.Shifting mass toward the left can improve the target probability, while excessive zero mass makes all variables zero too often.Source: §3 · p. 11

Casino manager’s problem

• The casino manager’s problem has an exact solution obtained by optimizing the probability of X1 + X2 − 2X3 > 0 over probability measures on N or R+.The paper notes that the finite-m bounds are constant and already tight at m=n=3 for this case.Source: §3 · pp. 10–11

Upper bounds

• For general strict linear inequalities, finite-m upper bounds equal the largest fraction of jointly satisfiable permuted inequality versions under a deterministic assignment.Computing this quantity is an instance of maximum feasible subsystem with strict linear inequalities, which is NP-hard in general [4, Theorem 4].Source: §3 · p. 11

Lower bounds

• For linear inequalities, a proposition converts distributions satisfying the inequality into measures on [0,1] that preserve the probability up to ε, with ε=0 for finitely supported discrete laws.This supplies improved lower bounds beyond those obtained directly from the finite-m approximation.Source: §3 · p. 11

Application

• The problem is presented as the n=3, m=4, α=9/8 instance of the general strict-inequality optimization framework.The paper uses its preceding results to derive both lower and upper bounds.Source: §4 · p. 12

Bounds

• 0.400695 ≤ supµ Pµ⊗4[X1 + X2 + X3 < 2X4] ≤ 673/1615 ≤ 0.417 for probability measures on R+.The precise value remains unknown.Source: §4 · p. 12

Lower bound.

• A positive atom forces equality to have positive probability, and the paper concludes that no finitely supported distribution can be optimal.The equality event includes the all-zero outcome, while the construction reallocates probability mass lost to equality.Source: Lower bound · pp. 12–14
• With N = 61 and q = 0.0546388, the construction achieves 0.398 in (4.2), while the atom weight at 0 is optimized.Taking p = 0.474346, approximately the value achieving the supremum on the right, yields the numerical lower bound in (4.1).Source: Lower bound · p. 13
• The lower-bound construction places positive mass on values of the form 1−1/2^i, enabling comparisons between distinct support values.If X3 < X4, the support structure implies 1 + X3 ≤ 2X4, which supports the conditional lower bound.Source: Lower bound · p. 14
• A distribution with an atom at 0 contributes explicitly through disjoint cases where zero and positive variables satisfy the strict inequality.The resulting bound includes p3(1 −p), 3p2(1 −p)2, and a distinct-positive-variable term.Source: Lower bound · p. 14
• The optimized rational function has a unique maximizer in (0, 1) satisfying 2 −2p −3p2 −4p3 + p4 = 0.The authors note that solving this equation gives a slightly sharper version of the numerical lower bound.Source: Lower bound · p. 14
• Numerical experimentation can be misleading: for this construction, N = 156 is the first tested value producing a probability above 2/5.Values for N = 1, . . . , 150 approached 2/5 without exceeding it.Source: Lower bound · p. 15

Upper bound.

• The counting method reduces the probabilistic upper bound to the largest number of jointly satisfiable deterministic inequality versions divided by the total number of versions.This argument is applied after ordering the variables monotonically.Source: Upper bound · p. 15
• For m = 6, 30 relevant inequality versions remain after discarding versions automatically violated by a monotone assignment.The versions are partitioned according to the position of the right-hand-side index.Source: Upper bound · pp. 15–16
• At least two of the 30 versions are jointly incompatible, so at most 28 can be satisfied simultaneously.An explicit assignment satisfies all 30 except one version on each side, proving attainability of the 28-inequality subsystem.Source: Upper bound · p. 16
• An upper bound is 7/15; because it is smaller than the upper bound in (4.8), upper bounds of Lemma 2.3 improve with increasing m in general.Source: Upper bound · p. 16
• The hand analysis is not expected to scale simply because the underlying maximum feasible subsystem problem is NP-hard in general.The inequalities here have additional permutation structure, which might nevertheless permit specialized algorithms.Source: Upper bound · p. 16

Upper bound for larger m by Mixed Integer Linear Programming.

• The first MILP maximizes satisfied non-strict constraints over ordered variables, using a small threshold to encode strict inequalities numerically.A big-M variable activates each selected constraint, while 0 ≤ x1 ≤ · · · ≤ xm ≤ 1 enforces monotonicity.Source: Upper bound for larger m by Mixed… · pp. 16–17
• The implementation terminates for m = 20 and the first MILP also reaches m = 25, but the improved m = 25 bound lacks a formal proof.The second MILP has only terminated through m = 20 so far.Source: Upper bound for larger m by Mixed… · pp. 17–19
• The MILP uses redundant monotonicity and unsatisfiable-subsystem constraints to accelerate computation.These constraints allow the m = 20 computation to terminate in a few seconds.Source: Upper bound for larger m by Mixed… · pp. 17–18
• The first MILP’s thresholded optimum does not by itself prove the desired strict-inequality bound, motivating the second MILP certificate.Non-strict MILP constraints and strict target inequalities need not coincide exactly.Source: Upper bound for larger m by Mixed… · p. 18
• The second MILP converts the first solution into disjoint infeasible subsystems, yielding a certificate that no larger feasible subsystem exists.Summing each subsystem and using monotonicity produces a contradiction.Source: Upper bound for larger m by Mixed… · pp. 18–19
• 8076/19380 = 673/1615 provides a formally proved upper bound using a two-MILP certificate at m = 20.The second MILP supplies 1614 disjoint infeasible subsystems, certifying maximality of the 8076 satisfied inequalities.Source: Upper bound for larger m by Mixed… · p. 19

5. Open problems

• Determining the exact value of the target supremum remains an open question.Source: The lower bound conjecture · p. 19

• The paper conjectures that the lower bound of Proposition 4.1 is the exact value.Source: The lower bound conjecture · p. 19
• MILP solutions often mimic the lower-bound pattern, including multiple scales and exponential spacing within each scale.Source: The lower bound conjecture · p. 20
• The observed pattern includes a top scale with x8 = 1 −2−1 through x14 = 1 −2−7, followed by a smaller scale.Source: The lower bound conjecture · p. 20
• Boundary effects appear in the final point before the upper scale, where x7 = x6 breaks the otherwise observed spacing pattern.Source: The lower bound conjecture · p. 20
• The upper-bound computation is limited by rapidly growing MILP size; the second MILP does not terminate within a day for m > 20, and the numerical strategy cannot determine its limit as m → +∞.Source: The lower bound conjecture · p. 20
• No existing mathematical approach is known to resolve Conjecture 5.1, which remains an open problem.Source: The lower bound conjecture · p. 20
• The paper also raises open questions about whether the supremum is attained and which coefficients can make Beat the Average-type games fair.Source: The lower bound conjecture · p. 20, Fair games · p. 21

Fair games.

• For a Bernoulli measure, the inequality fails only when X4=0 or all four variables equal 1.Source: Fair games · p. 21
• The computed value is 3 44/3 > 0.472, exceeding the upper bound at c*=2.Source: Fair games · p. 21
• At c*=2, the relevant left-hand side is discontinuous, so the intermediate value theorem cannot be applied.The discontinuity is exhibited using a Bernoulli measure supported at 0 and 1.Source: Fair games · p. 21
• For three iid random points in R2, the probability that their triangle is obtuse depends on the distribution µ.The triangle may be degenerate.Source: Obtuse random triangles · p. 21

Obtuse random triangles.

• Supporting µ on an arc smaller than a semicircle yields an obtuse-triangle probability of 1.Source: Obtuse random triangles · p. 21
• The minimal obtuse-triangle probability lies in [1 3, 4 9], but its exact value remains open.Source: Obtuse random triangles · p. 21
• The paper’s Section 4 techniques do not apply directly because the obtuseness condition is not linear in point coordinates.Source: Obtuse random triangles · p. 21