# Randomized and Exchangeable Improvements of Markov's, Chebyshev's and Chernoff's Inequalities

arXiv: https://arxiv.org/abs/2304.02611 · HTML: https://mlsanity.com/paper/2304.02611/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2023.

## Built on by (most cited first, 15 of 15)

- [Reliable Text-to-SQL with Adaptive Abstention](https://mlsanity.com/paper/2501.10858/) (2025)
- [E-valuator: Reliable Agent Verifiers with Sequential Hypothesis Testing](https://mlsanity.com/paper/2512.03109/) (2025)
- [Conformal online model aggregation](https://mlsanity.com/paper/2403.15527/) (2024)
- [Online Detection of LLM-Generated Texts via Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2410.22318/) (2024)
- [Improving the statistical efficiency of cross-conformal prediction](https://mlsanity.com/paper/2503.01495/) (2025)
- [Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2502.07774/) (2025)
- [Combining Evidence Across Filtrations](https://mlsanity.com/paper/2402.09698/) (2024)
- [Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance](https://mlsanity.com/paper/2310.03722/) (2023)
- [Sharp Matrix Empirical Bernstein Inequalities](https://mlsanity.com/paper/2411.09516/) (2024)
- [Derandomizing Simultaneous Confidence Regions for Band-Limited Functions by Improved Norm Bounds and Majority-Voting Schemes](https://mlsanity.com/paper/2506.17764/) (2025)
- [Concentration Inequalities for Exchangeable Tensors and Matrix-valued Data](https://mlsanity.com/paper/2601.20152/) (2026)
- [Positive Semidefinite Matrix Supermartingales](https://mlsanity.com/paper/2401.15567/) (2024)
- [Data-light Uncertainty Set Merging with Admissibility](https://mlsanity.com/paper/2410.12201/) (2024)
- [On the Precise Asymptotics of Universal Inference](https://mlsanity.com/paper/2503.14717/) (2025)
- [Set-Preserving Calibration from Conformal P-Values to E-Values](https://mlsanity.com/paper/2606.03600/) (2026)

## Abstract (arXiv)

We present simple randomized and exchangeable improvements of Markov's inequality, as well as Chebyshev's inequality and Chernoff bounds. Our variants are never worse and typically strictly more powerful than the original inequalities. The proofs are short and elementary, and can easily yield similarly randomized or exchangeable versions of a host of other inequalities that employ Markov's inequality as an intermediate step. We point out some simple statistical applications involving tests that combine dependent e-values. In particular, we uniformly improve the power of universal inference, and obtain tighter betting-based nonparametric confidence intervals. Simulations reveal nontrivial gains in power (and no losses) in a variety of settings.