BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
David A. Levin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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.
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.
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$.
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.