An official website of the United States government
We investigate the uniform reshuffling model for money exchanges: two agents picked uniformly at random redistribute their dollars between them. This stochastic dynamics is of mean-field type and eventually leads to a exponential distribution of wealth. To better understand this dynamics, we investigate its limit as the number of agents goes to infinity. We prove rigorously the so-called propagation of chaos which links the stochastic dynamics to a (limiting) nonlinear partial differential equation (PDE). This deterministic description, which is well-known in the literature, has a flavor of the classical Boltzmann equation arising from statistical mechanics of dilute gases. We prove its convergence toward its exponential equilibrium distribution in the sense of relative entropy.
more »
« less
From interacting agents to Boltzmann-Gibbs distribution of money
Abstract We investigate the unbiased model for money exchanges: agents give at random time a dollar to one another (if they have one). Surprisingly, this dynamics eventually leads to a geometric distribution of wealth (shown empirically by Dragulescu and Yakovenko, and rigorously by several follow-up papers). We prove a uniform-in-time propagation of chaos result as the number of agents goes to infinity, which links the stochastic dynamics to a deterministic infinite system of ordinary differential equations. This deterministic description is then analyzed by taking advantage of several entropy–entropy dissipation inequalities and we provide a quantitative almost-exponential rate of convergence toward the equilibrium (geometric distribution) in relative entropy.
more »
« less
- PAR ID:
- 10613669
- Publisher / Repository:
- IOP Science
- Date Published:
- Journal Name:
- Nonlinearity
- Volume:
- 37
- Issue:
- 12
- ISSN:
- 0951-7715
- Page Range / eLocation ID:
- 125020
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Some microscopic dynamics are also macroscopically irreversible, dissipating energy and producing entropy. For many-particle systems interacting with deterministic thermostats, the rate of thermodynamic entropy dissipated to the environment is the average rate at which phase space contracts. Here, we use this identity and the properties of a classical density matrix to derive upper and lower bounds on the entropy flow rate from the spectral properties of the local stability matrix. These bounds are an extension of more fundamental bounds on the Lyapunov exponents and phase space contraction rate of continuous-time dynamical systems. They are maximal and minimal rates of entropy production, heat transfer, and transport coefficients set by the underlying dynamics of the system and deterministic thermostat. Because these limits on the macroscopic dissipation derive from the density matrix and the local stability matrix, they are numerically computable from the molecular dynamics. As an illustration, we show that these bounds are on the electrical conductivity for a system of charged particles subject to an electric field.more » « less
-
Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs.more » « less
-
Abstract Transfer entropy is emerging as the statistical approach of choice to support the inference of causal interactions in complex systems from time-series of their individual units. With reference to a simple dyadic system composed of two coupled units, the successful application of net transfer entropy-based inference relies on unidirectional coupling between the units and their homogeneous dynamics. What happens when the units are bidirectionally coupled and have different dynamics? Through analytical and numerical insights, we show that net transfer entropy may lead to erroneous inference of the dominant direction of influence that stems from its dependence on the units’ individual dynamics. To control for these confounding effects, one should incorporate further knowledge about the units’ time-histories through the recent framework offered by momentary information transfer. In this realm, we demonstrate the use of two measures: controlled and fully controlled transfer entropies, which consistently yield the correct direction of dominant coupling irrespective of the sources and targets individual dynamics. Through the study of two real-world examples, we identify critical limitations with respect to the use of net transfer entropy in the inference of causal mechanisms that warrant prudence by the community.more » « less
-
A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d. We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1}m for m ≈ δ dt with min-entropy m−O(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X1∘ … ∘ Xt, accumulate most of the entropy in X.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1088/1361-6544/ad8c8c
