An official website of the United States government
A well-known question in planar first-passage percolation concerns the convergence of the empirical distribution of weights as seen along geodesics. We demonstrate this convergence for an explicit model, directed last-passage percolation on\mathbb{Z}^{2}with i.i.d. exponential weights, and provide explicit formulae for the limiting distributions, which depend on the asymptotic direction. For example, for geodesics in the direction of the diagonal, the limiting weight distribution has density(1/4+x/2+x^{2}/8)e^{-x}, and so is a mixture of Gamma(1,1), Gamma(2,1), and Gamma(3,1) distributions with weights1/4,1/2, and1/4respectively. More generally, we study the local environment as seen from vertices along geodesics (including information about the shape of the path and about the weights on and off the path in a local neighborhood). We consider finite geodesics from(0,0)ton\boldsymbol{\rho}for some vector\boldsymbol{\rho}in the first quadrant, in the limit asn\to\infty, as well as semi-infinite geodesics in direction\boldsymbol{\rho}. We show almost sure convergence of the empirical distributions of the environments along these geodesics, as well as convergence of the distributions of the environment around a typical point in these geodesics, to the same limiting distribution, for which we give an explicit description.We make extensive use of a correspondence with TASEP as seen from an isolated second-class particle for which we prove new results concerning ergodicity and convergence to equilibrium. Our analysis relies on geometric arguments involving estimates for last-passage times, available from the integrable probability literature.
more »
« less
Infinite order phase transition in the slow bond TASEP
Abstract In the slow bond problem the rate of a single edge in the Totally Asymmetric Simple Exclusion Process (TASEP) is reduced from 1 to for some small . Janowsky and Lebowitz posed the well‐known question of whether such very small perturbations could affect the macroscopic current. Different groups of physicists, using a range of heuristics and numerical simulations reached opposing conclusions on whether the critical value of is 0. This was ultimately resolved rigorously in Basu‐Sidoravicius‐Sly which established that . Here we study the effect of the current as tends to 0 and in doing so explain why it was so challenging to predict on the basis of numerical simulations. In particular we show that the current has an infinite order phase transition at 0, with the effect of the perturbation tending to 0 faster than any polynomial. Our proof focuses on the Last Passage Percolation formulation of TASEP where a slow bond corresponds to reinforcing the diagonal. We give a multiscale analysis to show that when is small the effect of reinforcement remains small compared to the difference between optimal and near optimal geodesics. Since geodesics can be perturbed on many different scales, we inductively bound the tails of the effect of reinforcement by controlling the number of near optimal geodesics and giving new tail estimates for the local time of (near) geodesics along the diagonal.
more »
« less
- Award ID(s):
- 2246664
- PAR ID:
- 10514527
- Publisher / Repository:
- Wiley, Courant Institute of Mathematical Sciences
- Date Published:
- Journal Name:
- Communications on Pure and Applied Mathematics
- Volume:
- 77
- Issue:
- 6
- ISSN:
- 0010-3640
- Page Range / eLocation ID:
- 3107 to 3140
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We obtain new quantitative estimates on Weyl Law remainders under dynamical assumptions on the geodesic flow. On a smooth compact Riemannian manifold ( M , g ) of dimension n , let $$\Pi _\lambda $$ Π λ denote the kernel of the spectral projector for the Laplacian, $$\mathbb {1}_{[0,\lambda ^2]}(-\Delta _g)$$ 1 [ 0 , λ 2 ] ( - Δ g ) . Assuming only that the set of near periodic geodesics over $${W}\subset M$$ W ⊂ M has small measure, we prove that as $$\lambda \rightarrow \infty $$ λ → ∞ $$\begin{aligned} \int _{{W}} \Pi _\lambda (x,x)dx=(2\pi )^{-n}{{\,\textrm{vol}\,}}_{_{{\mathbb {R}}^n}}\!(B){{\,\textrm{vol}\,}}_g({W})\,\lambda ^n+O\Big (\frac{\lambda ^{n-1}}{\log \lambda }\Big ), \end{aligned}$$ ∫ W Π λ ( x , x ) d x = ( 2 π ) - n vol R n ( B ) vol g ( W ) λ n + O ( λ n - 1 log λ ) , where B is the unit ball. One consequence of this result is that the improved remainder holds on all product manifolds, in particular giving improved estimates for the eigenvalue counting function in the product setup. Our results also include logarithmic gains on asymptotics for the off-diagonal spectral projector $$\Pi _\lambda (x,y)$$ Π λ ( x , y ) under the assumption that the set of geodesics that pass near both x and y has small measure, and quantitative improvements for Kuznecov sums under non-looping type assumptions. The key technique used in our study of the spectral projector is that of geodesic beams.more » « less
-
The calculation of off-diagonal matrix elements has various applications in fields such as nuclear physics and quantum chemistry. In this paper, we present a noisy intermediate scale quantum algorithm for estimating the diagonal and off-diagonal matrix elements of a generic observable in the energy eigenbasis of a given Hamiltonian without explicitly preparing its eigenstates. By means of numerical simulations we show that this approach finds many of the matrix elements for the one and two qubits cases. Specifically, while in the first case, one can initialize the ansatz parameters over a broad interval, in the latter the optimization landscape can significantly slow down the speed of convergence and one should therefore be careful to restrict the initialization to a smaller range of parameters.more » « less
-
Near-Optimal Bayesian Online Assortment of Reusable Resources Motivated by rental services in e-commerce, we consider revenue maximization in the online assortment of reusable resources for different types of arriving consumers. We design competitive online algorithms compared with the optimal online policy in the Bayesian setting, where consumer types are drawn independently from known heterogeneous distributions over time. In scenarios with large initial inventories, our main result is a near-optimal competitive algorithm for reusable resources. Our algorithm relies on an expected linear programming (LP) benchmark, solves this LP, and simulates the solution through independent randomized rounding. The main challenge is achieving inventory feasibility efficiently using these simulation-based algorithms. To address this, we design discarding policies for each resource, balancing inventory feasibility and revenue loss. Discarding a unit of a resource impacts future consumption of other resources, so we introduce postprocessing assortment procedures to design and analyze our discarding policies. Additionally, we present an improved competitive algorithm for nonreusable resources and evaluate our algorithms using numerical simulations on synthetic data.more » « less
-
In order to compare and interpolate signals, we investigate a Riemannian geometry on the space of signals. The metric allows discontinuous signals and measures both horizontal (thus providing many benefits of the Wasserstein metric) and vertical deformations. Moreover, it allows for signed signals, which overcomes the main deficiency of optimal transportation-based metrics in signal processing. We characterize the metric properties of the space of signals and establish the regularity and stability of geodesics. Furthermore, we introduce an efficient numerical scheme to compute the geodesics and present several experiments which highlight the nature of the metric.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/cpa.22185
