Search ResultsShowing 1-20 of 122
-
arXiv:2505.04218 (Published 2025-05-07)
Convergence rate of Euler-Maruyama scheme to the invariant probability measure under total variation distance
Comments: 21 pagesThis article shows the geometric decay rate of Euler-Maruyama scheme for one-dimensional stochastic differential equation towards its invariant probability measure under total variation distance. Firstly, the existence and uniqueness of invariant probability measure and the uniform geometric ergodicity of the chain are studied through introduction of non-atomic Markov chains. Secondly, the equivalent conditions for uniform geometric ergodicity of the chain are discovered, by constructing a split Markov chain based on the original Euler-Maruyama scheme. It turns out that this convergence rate is independent with the step size under total variation distance.
-
arXiv:2505.03198 (Published 2025-05-06)
Universality of the convergence rate for spectral radius of complex IID random matrices
Comments: 8 pagesCategories: math.PRLet $X$ be an $n\times n$ matrix with independent and identically distributed entries $x_{ij} \stackrel{\text { d }}{=} n^{-1 / 2} x$ for some complex random variable $x$ of mean zero and variance one. Let $\{\sigma_i\}_{1\le i\le n}$ be the eigenvalues of $X$ and let $|\sigma_1|:=\max_{1\le i\le n}|\sigma_i|$ be the spectral radius. Set $Y_n=\sqrt{4 n \gamma_n}\left[|\sigma_1|-1-\sqrt{\frac{\gamma_n}{4 n}}\right],$ where $\gamma_{n}=\log{n}-2\log{\log{n}}-\log{2\pi}.$ As established in \cite{Cipolloni23Universality}, with specific moment-related conditions imposed on $x,$ the Gumbel distribution $\Lambda$ is identified as the universal weak limit of $Y_n.$ Subsequently, we extend this line of research and rigorously prove that the convergence rate, previously obtained for complex Ginibre ensembles in \cite{MaMeng25}, also possesses the property of universality. Precisely, one gets $$\sup_{x\in \mathbb{R}}|\mathbb{P}(Y_n \leq x)-e^{-e^{-x}}|=\frac{2\log\log n}{e\log n}(1+o(1))$$ and $$W_1\left(\mathcal{L}(Y_n), \Lambda\right)=\frac{2\log\log n}{\log n}(1+o(1))$$ for sufficiently large $n$, where $\mathcal{L}(Y_n)$ is the distribution of $Y_n$.
-
arXiv:2502.07704 (Published 2025-02-11)
A note on the $\mathcal{W}_2$-convergence rate of the empirical measure of an ergodic $\mathbb{R}^d$-valued diffusion
Comments: This is a companion paper to arXiv preprint arXiv:2406.13370Categories: math.PRIn this note, we consider a Stochastic Differential Equation under a strong confluence and Lipschitz continuity assumption of the coefficients. For the unique stationary solution, we study the rate of convergence of its empirical measure toward the invariant probability measure. We provide rate for the Wasserstein distance in the mean quadratic and almost sure sense.
-
arXiv:2502.00269 (Published 2025-02-01)
Probabilistic $(m,n)$-Parking Functions
Comments: 17 pages, 2 figuresIn this article, we establish new results on the probabilistic parking model (introduced by Durm\'ic, Han, Harris, Ribeiro, and Yin) with $m$ cars and $n$ parking spots and probability parameter $p\in[0,1]$. For any $ m \leq n$ and $p \in [0,1]$, we study the parking preference of the last car, denoted $a_m$, and determine the conditional distribution of $a_m$ and compute its expected value. We show that both formulas depict explicit dependence on the probability parameter $p$. We study the case where $m = cn $ for some $ 0 < c < 1 $ and investigate the asymptotic behavior and show that the presence of ``extra spots'' on the street significantly affects the rate at which the conditional distribution of $ a_m $ converges to the uniform distribution on $[n]$. Even for small $ \varepsilon = 1 - c $, an $ \varepsilon $-proportion of extra spots reduces the convergence rate from $ 1/\sqrt{n} $ to $ 1/n $ when $ p \neq 1/2 $. Additionally, we examine how the convergence rate depends on $c$, while keeping $n$ and $p$ fixed. We establish that as $c$ approaches zero, the total variation distance between the conditional distribution of $a_m$ and the uniform distribution on $[n]$ decreases at least linearly in $c$.
-
arXiv:2501.06535 (Published 2025-01-11)
Convergence rate for the coupon collector's problem with Stein's method
Comments: 27 pagesCategories: math.PRIn this paper, we consider the classical coupon collector problem with uniform probabilities. Since the seminal paper by P. Erd\"os and A. R\'enyi \cite{ErRe}, it is well-known that the renormalized number of attempts required to complete a collection of $n$ items distributed with uniform probability tends to a Gumbel distribution when $n$ goes to infinity. We propose to determine how fast this convergence takes place for a certain distance to be introduced by using the so-called generator approach of Stein's method. To do so, we introduce a semi-group similar to the classical Ornstein-Uhlenbeck semi-group and whose stationary measure is the standard Gumbel distribution. We give its essential properties and apply them to prove that the renormalized number of attempts converges to the Gumbel distribution at rate $\log n/n$.
-
arXiv:2412.19121 (Published 2024-12-26)
Convergence rate of Euler-Maruyama scheme for McKean-Vlasov SDEs with density-dependent drift
In this paper, we study weak well-posedness of a McKean-Vlasov stochastic differential equations (SDEs) whose drift is density-dependent and whose diffusion is constant. The existence part is due to H\"older stability estimates of the associated Euler-Maruyama scheme. The uniqueness part is due to that of the associated Fokker-Planck equation. We also obtain convergence rate in weighted $L^1$ norm for the Euler-Maruyama scheme.
-
arXiv:2412.14740 (Published 2024-12-19)
Recovering semipermeable barriers from reflected Brownian motion
Comments: 62 pages, 11 figuresWe study the recovery of one-dimensional semipermeable barriers for a stochastic process in a planar domain. The considered process acts like Brownian motion when away from the barriers and is reflected upon contact until a sufficient but random amount of interaction has occurred, determined by the permeability, after which it passes through. Given a sequence of samples, we wonder when one can determine the location and shape of the barriers. This paper identifies several different recovery regimes, determined by the available observation period and the time between samples, with qualitatively different behavior. The observation period $T$ dictates if the full barriers or only certain pieces can be recovered, and the sampling rate significantly influences the convergence rate as $T\to \infty$. This rate turns out polynomial for fixed-frequency data, but exponentially fast in a high-frequency regime. Further, the environment's impact on the difficulty of the problem is quantified using interpretable parameters in the recovery guarantees, and is found to also be regime-dependent. For instance, the curvature of the barriers affects the convergence rate for fixed-frequency data, but becomes irrelevant when $T\to \infty$ with high-frequency data. The results are accompanied by explicit algorithms, and we conclude by illustrating the application to real-life data.
-
arXiv:2412.00432 (Published 2024-11-30)
Convergence rate in the splitting-up method for rough differential equations
Comments: 12 pagesIn this note we construct solutions to rough differential equations ${\rm d} Y = f(Y) \,{\rm d} X$ with a driver $X \in C^\alpha([0,T];\mathbb{R}^d)$, $\frac13 < \alpha \le \frac12$, using a splitting-up scheme. We show convergence of our scheme to solutions in the sense of Davie by a new argument and give a rate of convergence.
-
arXiv:2411.11552 (Published 2024-11-18)
Convergence rate of Smoluchowski--Kramers approximation with stable Lévy noise
Categories: math.PRThe small mass limit of the Langevin equation perturbed by $\beta$-stable L\'{e}vy noise is considered by rewriting it in the form of slow-fast system, and spliting the fast component into three parts. By exploring the three parts respectively, the limit equation and the convergence rate are derived.
-
arXiv:2411.09949 (Published 2024-11-15)
$W_{\bf d}$-convergence rate of EM schemes for invariant measures of supercritical stable SDEs
By establishing the regularity estimates for nonlocal Stein/Poisson equations under $\gamma$-order H\"older and dissipative conditions on the coefficients, we derive the $W_{\bf d}$-convergence rate for the Euler-Maruyama schemes applied to the invariant measure of SDEs driven by multiplicative $\alpha$-stable noises with $\alpha \in (\frac{1}{2}, 2)$, where $W_{\bf d}$ denotes the Wasserstein metric with ${\bf d}(x,y)=|x-y|^\gamma\wedge 1$ and $\gamma \in ((1-\alpha)_+, 1]$.
-
arXiv:2409.14585 (Published 2024-09-22)
A convergent scheme for the Bayesian filtering problem based on the Fokker--Planck equation and deep splitting
Comments: 30 pages, 2 figuresA numerical scheme for approximating the nonlinear filtering density is introduced and its convergence rate is established, theoretically under a parabolic H\"{o}rmander condition, and empirically for two examples. For the prediction step, between the noisy and partial measurements at discrete times, the scheme approximates the Fokker--Planck equation with a deep splitting scheme, and performs an exact update through Bayes' formula. This results in a classical prediction-update filtering algorithm that operates online for new observation sequences post-training. The algorithm employs a sampling-based Feynman--Kac approach, designed to mitigate the curse of dimensionality. Our convergence proof relies on the Malliavin integration-by-parts formula. As a corollary we obtain the convergence rate for the approximation of the Fokker--Planck equation alone, disconnected from the filtering problem.
-
arXiv:2409.14212 (Published 2024-09-21)
Convergence rate for random walk approximations of mean field BSDEs
Categories: math.PRWe study the rate of convergence w.r.t. a Wasserstein type distance for random walk approximation of mean field BSDEs. This article continuous [Briand et al., Donsker-Type Theorem For BSDEs: Rate of Convergence, Bernoulli, 2021], where the rate of convergence of a Donsker-type theorem for standard BSDEs is studied.
-
arXiv:2409.08120 (Published 2024-09-12)
Quantitative periodic homogenization for symmetric non-local stable-like operators
Comments: 34 pagesHomogenization for non-local operators in periodic environments has been studied intensively. So far, these works are mainly devoted to the qualitative results, that is, to determine explicitly the operators in the limit. To the best of authors' knowledge, there is no result concerning the convergence rates of the homogenization for stable-like operators in periodic environments. In this paper, we establish a quantitative homogenization result for symmetric $\alpha$-stable-like operators on $\R^d$ with periodic coefficients. In particular, we show that the convergence rate for the solutions of associated Dirichlet problems on a bounded domain $D$ is of order $$ \varepsilon^{(2-\alpha)/2}\I_{\{\alpha\in (1,2)\}}+\varepsilon^{\alpha/2}\I_{\{\alpha\in (0,1)\}}+\varepsilon^{1/2}|\log \e|^2\I_{\{\alpha=1\}}, $$ while, when the solution to the equation in the limit is in $C^2_c(D)$, the convergence rate becomes $$ \varepsilon^{2-\alpha}\I_{\{\alpha\in (1,2)\}}+\varepsilon^{\alpha}\I_{\{\alpha\in (0,1)\}}+\varepsilon |\log \e|^2\I_{\{\alpha=1\}}. $$ This indicates that the boundary decay behaviors of the solution to the equation in the limit affects the convergence rate in the homogenization.
-
arXiv:2408.10662 (Published 2024-08-20)
Convergence rate in the law of logarithm for negatively dependent random variables under sub-linear expectations
Comments: 8 pages, submitted to Mathematica ApplicataCategories: math.PRLet $\{X,X_n,n\ge 1\}$ be a sequence of identically distributed, negatively dependent (NA) random variables under sub-linear expectations, and denote $S_n=\sum_{i=1}^{n}X_i$, $n\ge 1$. Assume that $h(\cdot)$ is a positive non-decreasing function on $(0,\infty)$ fulfulling $\int_{1}^{\infty}(th(t))^{-1}\dif t=\infty$. Write $Lt=\ln \max\{\me,t\}$, $\psi(t)=\int_{1}^{t}(sh(s))^{-1}\dif s$, $t\ge 1$. In this sequel, we establish that $\sum_{n=1}^{\infty}(nh(n))^{-1}\vv\left\{|S_n|\ge (1+\varepsilon)\sigma\sqrt{2nL\psi(n)}\right\}<\infty$, $\forall \varepsilon>0$ if $\ee(X)=\ee(-X)=0$ and $\ee(X^2)=\sigma^2\in (0,\infty)$. The result generalizes that of NA random variables in probability space.
-
arXiv:2407.12713 (Published 2024-07-17)
Tensor product Markov chains and Weil representations
Comments: 28 pagesWe obtain sharp bounds on the convergence rate of Markov chains on irreducible representations of finite general linear, unitary, and symplectic groups (in both odd and even characteristic) given by tensoring with Weil representations.
-
arXiv:2406.18888 (Published 2024-06-27)
On estimation of the convergence rate to invariant measures in markov branching processes with possibly infinite variance and allowing immigration
Comments: 11 pages. arXiv admin note: text overlap with arXiv:2006.09857Journal: https://www.mathnet.ru/php/archive.phtml?jrnid=jsfu&wshow=issue&year=2021&volume=14&issue=5&option_lang=engCategories: math.PRSubjects: 60J80Tags: journal articleThe paper discusses the continuous-time Markov Branching Process allowing Immigration. We are considering a critical case for which the second moment of offspring law and the first moment of immigration law are possibly infinite. Assuming that the nonlinear parts of the appropriate generating functions are regularly varying in the sense of Karamata, we prove theorems on convergence of transition functions of the process to invariant measures. We deduce the speed rate of these convergence providing that slowly varying factors are with the remainder.
-
arXiv:2406.09678 (Published 2024-06-14)
Convergence rate of nonlinear delayed McKean-Vlasov SDEs driven by fractional Brownian motions
In this paper, our main aim is to investigate the strong convergence for a McKean-Vlasov stochastic differential equation with super-linear delay driven by fractional Brownian motion with Hurst exponent $H\in(1/2, 1)$. After giving uniqueness and existence for the exact solution, we analyze the properties including boundedness of moment and propagation of chaos. Besides, we give the Euler-Maruyama (EM) scheme and show that the numerical solution converges strongly to the exact solution. Furthermore, a corresponding numerical example is given to illustrate the theory.
-
arXiv:2406.07292 (Published 2024-06-11)
Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavity
The Coordinate Ascent Variational Inference scheme is a popular algorithm used to compute the mean-field approximation of a probability distribution of interest. We analyze its random scan version, under log-concavity assumptions on the target density. Our approach builds on the recent work of M. Arnese and D. Lacker, \emph{Convergence of coordinate ascent variational inference for log-concave measures via optimal transport} [arXiv:2404.08792] which studies the deterministic scan version of the algorithm, phrasing it as a block-coordinate descent algorithm in the space of probability distributions endowed with the geometry of optimal transport. We obtain tight rates for the random scan version, which imply that the total number of factor updates required to converge scales linearly with the condition number and the number of blocks of the target distribution. By contrast, available bounds for the deterministic scan case scale quadratically in the same quantities, which is analogue to what happens for optimization of convex functions in Euclidean spaces.
-
arXiv:2404.04781 (Published 2024-04-07)
The convergence of the EM scheme in empirical approximation of invariant probability measure for McKean-Vlasov SDEs
Based on the assumption of the existence and uniqueness of the invariant measure for McKean-Vlasov stochastic differential equations (MV-SDEs), a self-interacting process that depends only on the current and historical information of the solution is constructed for MV-SDEs. The convergence rate of the weighted empirical measure of the self-interacting process and the invariant measure of MV-SDEs is obtained in the W2-Wasserstein metric. Furthermore, under the condition of linear growth, an EM scheme whose uniformly 1/2-order convergence rate with respect to time is obtained is constructed for the self-interacting process. Then, the convergence rate between the weighted empirical measure of the EM numerical solution of the self-interacting process and the invariant measure of MV-SDEs is derived. Moreover, the convergence rate between the averaged weighted empirical measure of the EM numerical solution of the corresponding multi-particle system and the invariant measure of MV-SDEs in the W2-Wasserstein metric is also given. In addition, the computational cost of the two approximation methods is compared, which shows that the averaged weighted empirical approximation of the particle system has a lower cost. Finally, the theoretical results are validated through numerical experiments.
-
arXiv:2401.11381 (Published 2024-01-21)
Symmetric KL-divergence by Stein's Method
Comments: 28 pagesCategories: math.PRIn this paper, we consider the symmetric KL-divergence between the sum of independent variables and a Gaussian distribution, and obtain a convergence rate of $O\left( \frac{\ln n}{\sqrt{n}}\right)$. The proof is based on Stein's method. The convergence rate of order $O\left( \frac{1}{\sqrt{n}}\right)$ and $O\left( \frac{1}{n}\right) $ are also obtained under higher moment condition.