More Like this

1. Local Access to Random Walks , January 2022

   Biswas, A.S.; Pyne, E.; Rubinfeld, R. (January 2022, Innovations in Theoretical Computer Science (ITCS 2022))

   For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 

   more » « less
2. Sample-Path Large Deviations for Unbounded Additive Functionals of the Reflected Random Walk

   https://doi.org/10.1287/moor.2020.0094  

   Bazhba, Mihail; Blanchet, Jose; Rhee, Chang-Han; Zwart, Bert (March 2024, Mathematics of Operations Research)

   We prove a sample-path large deviation principle (LDP) with sublinear speed for unbounded functionals of certain Markov chains induced by the Lindley recursion. The LDP holds in the Skorokhod space [Formula: see text] equipped with the [Formula: see text] topology. Our technique hinges on a suitable decomposition of the Markov chain in terms of regeneration cycles. Each regeneration cycle denotes the area accumulated during the busy period of the reflected random walk. We prove a large deviation principle for the area under the busy period of the Markov random walk, and we show that it exhibits a heavy-tailed behavior. Funding: The research of B. Zwart and M. Bazhba is supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 639.033.413]. The research of J. Blanchet is supported by the National Science Foundation (NSF) [Grants 1915967, 1820942, and 1838576] as well as the Defense Advanced Research Projects Agency [Grant N660011824028]. The research of C.-H. Rhee is supported by the NSF [Grant CMMI-2146530]. 

   more » « less
3. Least squares as random walks

   https://doi.org/10.1016/j.physleta.2025.130449  

   Kostinski, Alexander; Ierley, Glenn; Kostinski, Sarah (June 2025, Physics Letters A)

   Linear least squares (LLS) is perhaps the most common method of data analysis, dating back to Legendre, Gauss and Laplace. Framed as linear regression, LLS is also a backbone of mathematical statistics. Here we report on an unexpected new connection between LLS and random walks. To that end, we introduce the notion of a random walk based on a discrete sequence of data samples (data walk). We show that the slope of a straight line which annuls the net area under a residual data walk equals the one found by LLS. For equidistant data samples this result is exact and holds for an arbitrary distribution of steps. 

   more » « less
4. A Study on How Conformation Entropy of Attached Macromolecules Drives Polymeric Collapse and Protein Folding

   https://doi.org/10.1002/mats.202400004  

   Popa, Ionel (March 2024, Macromolecular Theory and Simulations)

   Abstract The conformation of macromolecules attached to a surface is influenced by both their excluded volume and steric forces. Here, self‐avoiding random walk simulations are used to evaluate the occurrence of various conformations as a function of the number of monomeric units to estimate the effect of conformational entropy of a tethered chain. Then, a more realistic scenario is assessed, which can more accurately reproduce the shape of a tethered macromolecule. The simulations presented here confirm that it is more likely for a polymer to undergo a collapse conformation rather than a stretched one, as a collapse conformation can be realized in more different ways. Also, they confirm the “mushroom” shape of polymers close to a surface. From this simple approach, the conformation entropy of a model 100‐unit polymer close to a surface is estimated to contribute with over 129 toward its collapse. This conformation entropy is higher than that of typical hydrogen bonds and even barriers that keep proteins folded. As such, entropic collapse of macromolecules plays an important role in realizing the mushroom shape of attached polymers and can be the driving force in protein folding, while the polypeptide chain emerges from the ribosome. 

   more » « less
5. Efficient Approximate Unitary Designs from Random Pauli Rotations

   https://doi.org/10.1109/FOCS61266.2024.00036  

   Haah, Jeongwan; Liu, Yunchao; Tan, Xinyu (October 2024, IEEE)

   We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order t. The spectral gap of this random walk is shown to be Ω(1/t), which coincides with the best previously known bound for a random walk on the permutation group on {0, 1}^n. This implies that the walk gives an ε-approximate unitary t-design. Our simple proof uses quadratic Casimir operators of Lie algebras. 

   more » « less