Strong uniform times and finite random walks

DOI10.1016/0196-8858(87)90006-6zbMath0631.60065OpenAlexW2086490380WikidataQ105583541 ScholiaQ105583541MaRDI QIDQ1094756

Publication date: 1987

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-8858(87)90006-6

zbMATH Keywords

coupling randomized stopping time bounds for the rate of convergence to the stationary distribution Fourier analysis procedures strong symmetry properties

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items (98)

On the rate of mixing for \(p\)-shuffles. ⋮ Antiduality and Möbius monotonicity: generalized coupon collector problem ⋮ Cutoff thermalization for Ornstein-Uhlenbeck systems with small Lévy noise in the Wasserstein distance ⋮ On Möbius duality and coarse-graining ⋮ Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration ⋮ No cutoff for circulants: an elementary proof ⋮ On distributionally regenerative processes ⋮ Efficient Markovian couplings: Examples and counterexamples. ⋮ Conditioned, quasi-stationary, restricted measures and escape from metastable states ⋮ Strong memoryless times and rare events in Markov renewal point processes. ⋮ The nearest neighbor random walk on subspaces of a vector space and rate of convergence ⋮ On times to quasi-stationarity for birth and death processes ⋮ The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof ⋮ Precise estimates on the rate at which certain diffusions tend to equilibrium ⋮ Classification with asymmetric label noise: consistency and maximal denoising ⋮ Abrupt convergence and escape behavior for birth and death chains ⋮ Cut-off for \(n\)-tuples of exponentially converging processes ⋮ A large scale analysis of unreliable stochastic networks ⋮ Convergence rates in strong ergodicity for Markov processes ⋮ Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains ⋮ An exact formula for the move-to-front rule for self-organizing lists ⋮ The cut-off phenomenon for random reflections. II: Complex and quaternionic cases ⋮ Probabilistic models of genome shuffling ⋮ The evolution of the random reversal graph ⋮ On coupling and the approximation of the permanent ⋮ Rifflescrambler -- a memory-hard password storing function ⋮ Random induced subgraphs of generalized \(n\)-cubes ⋮ Approximate counting, uniform generation and rapidly mixing Markov chains ⋮ Thermalisation for small random perturbations of dynamical systems ⋮ Comparison inequalities and fastest-mixing Markov chains ⋮ The cut-off phenomenon for random reflections ⋮ Rates of convergence for lamplighter processes ⋮ Strong stationary duality for Möbius monotone Markov chains ⋮ Measuring bias in cyclic random walks ⋮ On the construction of measure-valued dual processes ⋮ Distortion risk measures, ROC curves, and distortion divergence ⋮ The cutoff phenomenon for the stochastic heat and wave equation subject to small Lévy noise ⋮ Cutoff phenomenon for the warp-transpose top with random shuffle ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Random induced subgraphs of Cayley graphs induced by transpositions ⋮ A probabilistic proof of Cooper and Frieze's "First Visit Time Lemma" ⋮ Gibbs sampling, conjugate priors and coupling ⋮ Likelihood orders for the \(p\)-cycle walks on the symmetric group ⋮ The cutoff phenomenon for Ehrenfest chains ⋮ Mixing time of the adjacent walk on the simplex ⋮ On interweaving relations ⋮ Fluctuations analysis of finite discrete birth and death chains with emphasis on Moran models with mutations ⋮ Hitting times and interlacing eigenvalues: a stochastic approach using intertwinings ⋮ Mixing times of lozenge tiling and card shuffling Markov chains ⋮ Separation cutoffs for random walk on irreducible representations ⋮ Cut-off and exit from metastability: Two sides of the same coin ⋮ On the strategic impact of an event under non-common priors ⋮ Choosing a random spanning subtree: A case study ⋮ Limits and rates of convergence for the distribution of search cost under the move-to-front rule ⋮ Comparison of Cutoffs Between Lazy Walks and Markovian Semigroups ⋮ Strong stationary duality for discrete time Möbius monotone Markov chains on \(\mathbb{Z}_+^d\) ⋮ The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise ⋮ Duality and intertwining for discrete Markov kernels: relations and examples ⋮ Aging of asymmetric dynamics on the random energy model ⋮ Explicit criteria on separation cutoff for birth and death chains ⋮ On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes ⋮ A rule of thumb for riffle shuffling ⋮ The \(L^{2}\)-cutoff for reversible Markov processes ⋮ Some new results on strong ergodicity ⋮ The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms ⋮ Approximation of sojourn-times via maximal couplings: motif frequency distributions ⋮ Separation cut-offs for birth and death chains ⋮ Some simple but challenging Markov processes ⋮ Separation cutoff for upward skip-free chains ⋮ Existence condition of strong stationary times for continuous time Markov chains on discrete graphs ⋮ On absorption times and Dirichlet eigenvalues ⋮ Commutation relations and Markov chains ⋮ Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ Relaxation of product Markov chains on product spaces ⋮ Large components in random induced subgraphs of \(n\)-cubes ⋮ Efficient Simulation via Coupling ⋮ Exact results on the first hitting via conditional strong quasi-stationary times and applications to metastability ⋮ Threshold phenomena in the transient behaviour of Markovian models of communication networks and databases ⋮ On the Markov commutator ⋮ A Ray-Knight representation of up-down Chinese restaurants ⋮ On strong stationary times and approximation of Markov chain hitting times by geometric sums ⋮ Random doubly stochastic tridiagonal matrices ⋮ Logarithmic Sobolev inequalities for finite Markov chains ⋮ Examples for the Theory of Strong Stationary Duality with Countable State Spaces ⋮ Time to Stationarity for a Continuous-Time Markov Chain ⋮ Spectral Analysis, without Eigenvectors, for Markov Chains ⋮ Lumpings of algebraic Markov chains arise from subquotients ⋮ On the cut-off phenomenon for the transitivity of randomly generated subgroups ⋮ An interruptible algorithm for perfect sampling via Markov chains ⋮ Two convergence properties of hybrid samplers ⋮ A conversation with David J. Aldous ⋮ Cut-off Phenomenon for Converging Processes in the Sense of α-Divergence Measures ⋮ Random subgraphs of Cayley graphs over \(p\)-groups ⋮ Convergence time to the Ewens sampling formula in the infinite alleles Moran model ⋮ Rapidly mixing random walks and bounds on characters of the symmetric group ⋮ Efficient Markovian couplings: Examples and counterexamples ⋮ Norm convergence of random walks on compact hypergroups

Cites Work

This page was built for publication: Strong uniform times and finite random walks