Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
From MaRDI portal
Publication:2904755
DOI10.4230/LIPIcs.STACS.2012.124zbMath1245.68143arXiv1201.0559MaRDI QIDQ2904755
Zhenming Liu, Henry Lam, Kai-Min Chung, Michael Mitzenmacher
Publication date: 23 August 2012
Full work available at URL: https://arxiv.org/abs/1201.0559
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Periodic words, common subsequences and frogs, A Hoeffding inequality for Markov chains, Adaptive Huber regression on Markov-dependent data, On Approximating the Stationary Distribution of Time-reversible Markov Chains, Hoeffding's inequality for non-irreducible Markov models, Unnamed Item, Function-specific mixing times and concentration away from equilibrium, Concentration of Markov chains with bounded moments, On the Complexity of Sampling Vertices Uniformly from a Graph, On approximating the stationary distribution of time-reversible Markov chains, Balanced allocation on dynamic hypergraphs, Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model, Tight bounds on probabilistic zero forcing on hypercubes and grids, Game of Thrones: Fully Distributed Learning for Multiplayer Bandits, Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes, Unnamed Item, Analysis of the Blockchain Protocol in Asynchronous Networks
