The Littlewood-Offord problem for Markov chains

DOI10.1214/21-ECP410MaRDI QIDQ2064822zbMATH OpenOpenAlexFDO

Authors Shravas Rao

Publication date 6 January 2022

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.13019

zbMATH Keywords

Littlewood-OffordMarkov chainpseudorandom generator

Mathematics Subject Classification ID

Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: The celebrated Littlewood-Offord problem asks for an upper bound on the probability that the random variable $epsilo{n}_1{v}_1+cdots+epsilo{n}_n{v}_n$ lies in the Euclidean unit ball, where $epsilo{n}_1,ldots,epsilo{n}_{n}in-1,1$ are independent Rademacher random variables and $v_1,ldots,v_{n}inmathbb{R}^d$ are fixed vectors of at least unit length.We extend many known results to the case that the $epsilo{n}_i$ are obtained from a Markov chain, including the general bounds first shown by ErdH{o}s in the scalar case and Kleitman in the vector case, and also under the restriction that the $v_i$ are distinct integers due to S'ark"ozy and Szemeredi. In all extensions, the upper bound includes an extra factor depending on the spectral gap. We also construct a pseudorandom generator for the Littlewood-Offord problem using similar techniques.

Recommendations

• On the Littlewood‐Offord problem for arbitrary distributions
• A non-uniform Littlewood-Offord inequality
• Resilience for the Littlewood-Offord problem
• A nonuniform Littlewood-Offord inequality for all norms
• Resilience for the Littlewood-Offord problem

Cites work

• A Chernoff Bound for Random Walks on Expander Graphs
• A polynomial restriction lemma with applications
• A simple proof of Stirling's formula for the gamma function
• A Sperner-type theorem
• Additive combinatorics
• Chernoff-type bound for finite Markov chains
• Concentration of Markov chains with bounded moments
• Estimates for the concentration function of combinatorial number theory and probability
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On the Kolmogorov-Rogozin inequality for the concentration function
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Ramanujan graphs
• Solution of the Littlewood-Offord problem in high dimensions
• Stronger form of an M-part Sperner theorem
• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
• Über ein Problem von Erdös und Moser

Cited in

(5)

• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
• scientific article; zbMATH DE number 3995885 (Why is no real title available?)
• scientific article; zbMATH DE number 4182081 (Why is no real title available?)
• Littlewood-Offord problems for Ising models
• Covering problems for Markov chains

This page was built for publication: The Littlewood-Offord problem for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064822)