Extending the V-sequence reduction to arbitrary independent distributions
Let $X_1,\ldots,X_n$ be independent random variables with arbitrary known distributions, where $n\ge2$. The optimal probability $V_n(X_1,\ldots,X_n)$ of choosing an overall maximum satisfies $V_n(X_1,\ldots,X_n)\ge(1-1/n)^{n-1}$, and this bound is attained. We obtain this known sharp bound by extending the reduction lemma of Allaart and Islas (2016) from continuous to arbitrary distributions. We construct a $V$-sequence whose optimal win probability does not exceed that of the original sequence, and then apply the bound for $V$-sequences. The construction first replaces atoms by uniform…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.35600
curl -X POST /api/v1/records/arxiv/2610.35600/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.35600/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'