Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Zeros of random tropical polynomials, random polygons and stick-breaking

Authors: Francois Baccelli and Ngoc Mai Tran
Journal: Trans. Amer. Math. Soc. 368 (2016), 7281-7303
MSC (2010): Primary 11S05, 60C05, 60D05, 14T05
Published electronically: February 2, 2016
MathSciNet review: 3471091
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For $ i = 0, 1, \ldots , n$, let $ C_i$ be independent and identically distributed random variables with distribution $ F$ with support $ (0,\infty )$. The number of zeros of the random tropical polynomials $ \mathcal {T}f_n(x) = \min _{i=1,\ldots ,n}(C_i + ix)$ is also the number of faces of the lower convex hull of the $ n+1$ random points $ (i,C_i)$ in $ \mathbb{R}^2$. We show that this number, $ Z_n$, satisfies a central limit theorem when $ F$ has polynomial decay near 0. Specifically, if $ F$ near 0 behaves like a $ gamma(a,1)$ distribution for some $ a > 0$, then $ Z_n$ has the same asymptotics as the number of renewals on the interval $ [0,\log (n)/a]$ of a renewal process with inter-arrival distribution $ -\log (Beta(a,2))$. Our proof draws on connections between random partitions, renewal theory and random polytopes. In particular, we obtain generalizations and simple proofs of the central limit theorem for the number of vertices of the convex hull of $ n$ uniform random points in a square. Our work leads to many open problems in stochastic tropical geometry, the study of functionals and intersections of random tropical varieties.

References [Enhancements On Off] (What's this?)

  • [1] Josh Abramson and Jim Pitman, Concave majorants of random walks and related Poisson processes, Combin. Probab. Comput. 20 (2011), no. 5, 651-682. MR 2825583 (2012i:60106),
  • [2] Josh Abramson, Jim Pitman, Nathan Ross, and Gerónimo Uribe Bravo, Convex minorants of random walks and Lévy processes, Electron. Commun. Probab. 16 (2011), 423-434. MR 2831081 (2012g:60147),
  • [3] Marianne Akian, Ravindra Bapat, and Stéphane Gaubert, Asymptotics of the Perron eigenvalue and eigenvector using max-algebra, C. R. Acad. Sci. Paris Sér. I Math. 327 (1998), no. 11, 927-932 (English, with English and French summaries). MR 1659185 (99k:15012),
  • [4] M. Akian, R. Bapat, and S. Gaubert, Min-plus methods in eigenvalue perturbation theory and generalised Lidskii-Vishik-Ljusternik theorem, arXiv preprint arXiv:math/0402090v3, 2004.
  • [5] Erik Sparre Andersen, On the fluctuations of sums of random variables. II, Math. Scand. 2 (1954), 195-223. MR 0068154 (16,839e)
  • [6] F. J. Anscombe, Large-sample theory of sequential estimation, Biometrika 36 (1949), 455-458. MR 0034006 (11,529d)
  • [7] R. Arratia and L. Goldstein, Size bias, sampling, the waiting time paradox, and infinite divisibility: when is the increment independent?, arXiv preprint arXiv:1007.3910, 2010.
  • [8] François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR 1204266 (94b:93001)
  • [9] Jean Bertoin, The convex minorant of the Cauchy process, Electron. Comm. Probab. 5 (2000), 51-55 (electronic). MR 1747095 (2001i:60081),
  • [10] Tamara Broderick, Michael I. Jordan, and Jim Pitman, Beta processes, stick-breaking and power laws, Bayesian Anal. 7 (2012), no. 2, 439-475. MR 2934958,
  • [11] Christian Buchta, On the distribution of the number of vertices of a random polygon, Anz. Österreich. Akad. Wiss. Math.-Natur. Kl. 139 (2003), 17-19 (2004). MR 2135177 (2005k:52014)
  • [12] Christian Buchta, Exact formulae for variances of functionals of convex hulls, Adv. in Appl. Probab. 45 (2013), no. 4, 917-924. MR 3161289,
  • [13] Rick Durrett, Probability: theory and examples, 4th ed., Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010. MR 2722836 (2011e:60001)
  • [14] L. Elsner and P. van den Driessche, Max-algebra and pairwise comparison matrices, Linear Algebra Appl. 385 (2004), 47-62. MR 2063346 (2005b:15015),
  • [15] Steven N. Evans, The expected number of zeros of a random system of $ p$-adic polynomials, Electron. Comm. Probab. 11 (2006), 278-290 (electronic). MR 2266718 (2007m:60013),
  • [16] Alexander V. Gnedin, The Bernoulli sieve, Bernoulli 10 (2004), no. 1, 79-96. MR 2044594 (2004k:60018),
  • [17] Alexander V. Gnedin, Alexander M. Iksanov, Pavlo Negadajlov, and Uwe Rösler, The Bernoulli sieve revisited, Ann. Appl. Probab. 19 (2009), no. 4, 1634-1655. MR 2538083 (2011e:60042),
  • [18] Piet Groeneboom, The concave majorant of Brownian motion, Ann. Probab. 11 (1983), no. 4, 1016-1027. MR 714964 (85h:60119)
  • [19] Piet Groeneboom, Limit theorems for convex hulls, Probab. Theory Related Fields 79 (1988), no. 3, 327-368. MR 959514 (89j:60024),
  • [20] Piet Groeneboom, Convex hulls of uniform samples from a convex polygon, Adv. in Appl. Probab. 44 (2012), no. 2, 330-342. MR 2977398,
  • [21] Allan Gut, Stopped random walks, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2009. Limit theorems and applications. MR 2489436 (2010f:60131)
  • [22] M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49 (1943), 314-320. MR 0007812 (4,196d)
  • [23] M. Kac, On the average number of real roots of a random algebraic equation. II, Proc. London Math. Soc. (2) 50 (1949), 390-408. MR 0030713 (11,40e)
  • [24] D. A. Korshunov, Limit theorems for general Markov chains, Sibirsk. Mat. Zh. 42 (2001), no. 2, 354-371, ii (Russian, with Russian summary); English transl., Siberian Math. J. 42 (2001), no. 2, 301-316. MR 1833162 (2002c:60113),
  • [25] Dmitry Korshunov, The key renewal theorem for a transient Markov chain, J. Theoret. Probab. 21 (2008), no. 1, 234-245. MR 2384480 (2009a:60097),
  • [26] J. E. Littlewood, On the Number of Real Roots of a Random Algebraic Equation, J. London Math. Soc. S1-13, no. 4, 288. MR 1574980,
  • [27] D. Maclagan and B. Sturmfels, Introduction to tropical geometry, Book in preparation, 2014.
  • [28] Jim Pitman, Exchangeable and partially exchangeable random partitions, Probab. Theory Related Fields 102 (1995), no. 2, 145-158. MR 1337249 (96e:60059),
  • [29] J. Pitman, Combinatorial stochastic processes, Lecture Notes in Mathematics, vol. 1875, Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7-24, 2002; With a foreword by Jean Picard. MR 2245368 (2008c:60001)
  • [30] Jim Pitman and Gerónimo Uribe Bravo, The convex minorant of a Lévy process, Ann. Probab. 40 (2012), no. 4, 1636-1674. MR 2978134,
  • [31] J. Pitman and N. M. Tran, Size-biased permutation of a finite sequence with independent and identically distributed terms, arXiv preprint arXiv:1206.2081v1, 2012.
  • [32] Rolf Schneider, Recent results on random polytopes, Boll. Unione Mat. Ital. (9) 1 (2008), no. 1, 17-39. MR 2387995 (2008m:52011)
  • [33] Rolf Schneider and Wolfgang Weil, Stochastic and integral geometry, Probability and its Applications (New York), Springer-Verlag, Berlin, 2008. MR 2455326 (2010g:60002)
  • [34] D. Stoyan, W. S. Kendall, and J. Mecke, Stochastic geometry and its applications, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1987. With a foreword by D. G. Kendall. MR 895588 (88j:60034a)
  • [35] T. Tao and V. Vu, Local universality of zeroes of random polynomials, arXiv preprint arXiv:1307.4357v2, 2013.
  • [36] Ngoc Mai Tran, Pairwise ranking: choice of method can produce arbitrarily different rank order, Linear Algebra Appl. 438 (2013), no. 3, 1012-1024. MR 2997792,
  • [37] M. van Manen and D. Siersma, Power diagrams and their applications, arXiv preprint arXiv:math/0508037v2, 2005.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11S05, 60C05, 60D05, 14T05

Retrieve articles in all journals with MSC (2010): 11S05, 60C05, 60D05, 14T05

Additional Information

Francois Baccelli
Affiliation: Department of Mathematics, University of Texas, Austin, Texas 78712

Ngoc Mai Tran
Affiliation: Department of Mathematics, University of Texas, Austin, Texas 78712

Received by editor(s): April 1, 2014
Received by editor(s) in revised form: August 11, 2014, and September 20, 2014
Published electronically: February 2, 2016
Additional Notes: This work was supported by an award from the Simons Foundation ($#197982$ to The University of Texas at Austin). The authors would like to thank an anonymous referee for the careful reading and helpful suggestions.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society