Generating and generalizing MSTD sets through Markov processes
Abstract
The classical More Sums Than Differences (MSTD) problem studies finite sets A⊂{0,1,…,n} for which |A+A|>|A−A|, where A+A={a1+a2:a1,a2∈ A} and A−A={a1−a2:a1,a2∈ A}. As addition is commutative and subtraction is not, it was conjectured that as n→∞ almost all subsets A chosen uniformly from the power set of {0,1,…,n} are difference-dominated, and it was thus a surprise when Martin and O'Bryant proved a positive percentage of sets are sum-dominant. We greatly generalize this model by introducing a Markov-chain framework, where the classical MSTD model is now just a special case. Let (Xi)i=0n be a stationary two-state Markov chain on {0,1} with transition probabilities P(0,0)=p and P(1,1)=q, where p,q∈(0,1). We include i in A exactly when Xi=1, and define A={i∈{0,…,n}:Xi=1}. The usual independent Bernoulli model is recovered when consecutive inclusion decisions are independent, equivalently when p=1−q. In particular, the uniformly random subset model corresponds to p=q=1/2. Using the fringe-middle method from the MSTD literature, we show that the middle sums and differences are filled with high probability, so the comparison between |A+A| and |A−A| is again governed by endpoint fringes. By fringe manipulation, we prove that the probabilities of sum-dominant, difference-dominant, and balanced sets tend to strictly positive limits as n→∞. We also give numerical estimates of these three probabilities for finite n over a range of values of p and q. Through combinatorial methods, we find a closed-form expression for 𝔼[|A−A|−|A+A|] as n→∞.
Related
- Accumulated-Variance Functionals of Hidden Markov and Semi-Markov Processes: Finite-Sample Upper and Lower Bounds
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
- Entanglement-Inducing Quantum Markov Processes
- Spectral theory for dynamical large deviations in non-Markov self-interacting processes
- Thermodynamic Cyclic Processes with Markov Samplers in Bayesian Inference
BibTeX
@misc{he2026generating,
title = {{Generating and generalizing MSTD sets through Markov processes}},
author = {Frank He and Karol Daniewski and Steven J. Miller},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08394},
eprint = {2610.08394},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08394},
}
RIS
TY - UNPB
TI - Generating and generalizing MSTD sets through Markov processes
AU - Frank He
AU - Karol Daniewski
AU - Steven J. Miller
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08394
UR - https://arxiv.org/abs/2610.08394
AB - The classical More Sums Than Differences (MSTD) problem studies finite sets A⊂{0,1,…,n} for which |A+A|>|A−A|, where A+A={a_1+a_2:a_1,a_2∈ A} and A−A={a_1−a_2:a_1,a_2∈ A}. As addition is commutative and subtraction is not, it was conjectured that as n→∞ almost all subsets A chosen uniformly from the power set of {0,1,…,n} are difference-dominated, and it was thus a surprise when Martin and O'Bryant proved a positive percentage of sets are sum-dominant. We greatly generalize this model by introducing a Markov-chain framework, where the classical MSTD model is now just a special case. Let (X_i)_i=0^n be a stationary two-state Markov chain on {0,1} with transition probabilities P(0,0)=p and P(1,1)=q, where p,q∈(0,1). We include i in A exactly when X_i=1, and define A={i∈{0,…,n}:X_i=1}. The usual independent Bernoulli model is recovered when consecutive inclusion decisions are independent, equivalently when p=1−q. In particular, the uniformly random subset model corresponds to p=q=1/2. Using the fringe-middle method from the MSTD literature, we show that the middle sums and differences are filled with high probability, so the comparison between |A+A| and |A−A| is again governed by endpoint fringes. By fringe manipulation, we prove that the probabilities of sum-dominant, difference-dominant, and balanced sets tend to strictly positive limits as n→∞. We also give numerical estimates of these three probabilities for finite n over a range of values of p and q. Through combinatorial methods, we find a closed-form expression for 𝔼[|A−A|−|A+A|] as n→∞.
ER -