Choices and intervals

DOI10.1007/S11856-016-1289-6MaRDI QIDQ2630873zbMATH OpenOpenAlexFDO

Authors P. Maillard, Elliot Paquette

Publication date 22 July 2016

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3931

zbMATH Keywords

convergenceempirical distributionprobability measurerandom interval splitting processstochastic approximation

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Strong limit theorems (60F15)

Abstract: We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive. In finite-dimensional settings, convergence results like this usually go under the name of stochastic approximation and can be approached by a general method of Kushner and Clark. An important technical contribution of this article is the extension of this method to an infinite-dimensional setting.

Review text

\textit{H. J. Kushner} and \textit{D. S. Clark} [Stochastic approximation methods for constrained an unconstrained systems. Applied Mathematical Sciences 26. New York-Heidelberg-Berlin: Springer-Verlag (1978; Zbl 0381.60004)] developed general methods for convergence results, in finite-dimensional settings, for stochastic approximation. The authors extend their methods to an infinite dimensional setting. More precisely, the authors consider a random interval splitting process, where the splitting rule depends on the empirical distribution of interval lengths. It is shown that the empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. The resulting limit is characterized by an ODE, which is used to provide the tail estimates of the limit distribution. Moreover, the convergence is established by showing that the size-based empirical distribution evolves in the limit according to a certain deterministic evolution equation.

Recommendations

• Choices and intervals
• Splitting intervals
• Weak convergence results for the Kakutani interval splitting procedure.
• The size of random fragmentation intervals
• The limit behavior of an interval splitting scheme

Cites work

• A first course in Sobolev spaces
• A log log law for maximal uniform spacings
• A proof of Kakutani's conjecture on random subdivision of longest intervals
• Achlioptas process phase transitions are continuous
• An invariance principle for the Robbins-Monro process in a Hilbert space
• Balanced Allocations
• Choices, intervals and equidistribution
• Compositions of random transpositions
• Correction to “entropy and maximal spacings for random partitions”
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Entropy and maximal spacings for random partitions
• Explosive percolation in random networks
• scientific article; zbMATH DE number 53382 (Why is no real title available?)
• scientific article; zbMATH DE number 3613892 (Why is no real title available?)
• scientific article; zbMATH DE number 2006037 (Why is no real title available?)
• Laws of the iterated logarithm for order statistics of uniform spacings
• On a Class of Problems Related to the Random Division of an Interval
• On h–valued stochastic approximation: finite dimenstional projections
• Random Fragmentation and Coagulation Processes
• Splitting intervals. II: Limit laws for lengths
• Stochastic approximation methods for constrained and unconstrained systems
• Strong limiting bounds for maximal uniform spacings
• The asymptotic behavior of spacings under Kakutani's model for interval subdivision
• The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transfor\-mations.
• The power of choice combined with preferential attachement
• The power of choice in growing trees
• The Stochastic Convergence of a Function of Sample Successive Differences

Cited in

(7)

• Interval fragmentations with choice: equidistribution and the evolution of tagged fragments
• Embedded choices
• The power of online thinning in reducing discrepancy
• Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes
• Choices and intervals
• scientific article; zbMATH DE number 1850763 (Why is no real title available?)
• Splitting intervals

This page was built for publication: Choices and intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2630873)