Source author record

David A. Levin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO math.AT math.ST Statistics Theory

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fast mixing of a randomized shift-register Markov chain

We present a Markov chain on the $n$ -dimensional hypercube $\{0,1\}^n$ which satisfies $t_{\rm mix}(ε) = n[1 + o(1)]$ . This Markov chain alternates between random and deterministic moves and we prove that the chain has cut-off with a window of size at most $O(n^{0.5+δ})$ where $δ>0$ . The deterministic moves correspond to a linear shift register.

preprint2020arXiv

A model for random braiding in graph configuration spaces

We define and study a model of winding for non-colliding particles in finite trees. We prove that the asymptotic behavior of this statistic satisfies a central limiting theorem, analogous to similar results on winding of bounded particles in the plane. We also propose certain natural open questions and conjectures, whose confirmation would provide new insights on configuration spaces of trees.

preprint2016arXiv

Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory

The spectral gap $γ$ of an ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $t$ may be observed. Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating $γ$ from this data. Let $π$ be the stationary distribution of $P$ , and $π_\star = \min_x π(x)$ . They showed that, if $t = \tilde{O}\bigl(\frac{1}{γ^3 π_\star}\bigr)$ , then $γ$ can be estimated to within multiplicative constants with high probability. They also proved that $\tildeΩ\bigl(\frac{n}γ\bigr)$ steps are required for precise estimation of $γ$ . We show that $\tilde{O}\bigl(\frac{1}{γπ_\star}\bigr)$ steps of the chain suffice to estimate $γ$ up to multiplicative constants with high probability. When $π$ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.

preprint2016arXiv

Mixing of the exclusion process with small bias

We analyze the mixing behavior of the biased exclusion process on a path of length $n$ as the bias $β_n$ tends to $0$ as $n \to \infty$ . We show that the sequence of chains has a pre-cutoff, and interpolates between the unbiased exclusion and the process with constant bias. As the bias increases, the mixing time undergoes two phase transitions: one when $β_n$ is of order $1/n$ , and the other when $β_n$ is order $\log n/n$ .

preprint2010arXiv

A Fourier-analytic Approach to Counting Partial Hadamard Matrices

In this paper, we study a family of lattice walks which are related to the Hadamard conjecture. There is a bijection between paths of these walks which originate and terminate at the origin and equivalence classes of partial Hadamard matrices. Therefore, the existence of partial Hadamard matrices can be proved by showing that there is positive probability of a random walk returning to the origin after a specified number of steps. Moreover, the number of these designs can be approximated by estimating the return probabilities. We use the inversion formula for the Fourier transform of the random walk to provide such estimates. We also include here an upper bound, derived by elementary methods, on the number of partial Hadamard.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.