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

HTML articles powered by AMS MathViewer

- by Francois Baccelli and Ngoc Mai Tran PDF
- Trans. Amer. Math. Soc.
**368**(2016), 7281-7303 Request permission

## 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

- 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**, DOI 10.1017/S0963548311000307 - 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**, DOI 10.1214/ECP.v16-1648 - 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**, DOI 10.1016/S0764-4442(99)80137-2 - 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. - Erik Sparre Andersen,
*On the fluctuations of sums of random variables. II*, Math. Scand.**2**(1954), 195–223. MR**68154** - F. J. Anscombe,
*Large-sample theory of sequential estimation*, Biometrika**36**(1949), 455–458. MR**34006**, DOI 10.1093/biomet/36.3-4.455 - 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. - 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** - Jean Bertoin,
*The convex minorant of the Cauchy process*, Electron. Comm. Probab.**5**(2000), 51–55. MR**1747095**, DOI 10.1214/ECP.v5-1017 - 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**, DOI 10.1214/12-BA715 - 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** - Christian Buchta,
*Exact formulae for variances of functionals of convex hulls*, Adv. in Appl. Probab.**45**(2013), no. 4, 917–924. MR**3161289**, DOI 10.1239/aap/1386857850 - Rick Durrett,
*Probability: theory and examples*, 4th ed., Cambridge Series in Statistical and Probabilistic Mathematics, vol. 31, Cambridge University Press, Cambridge, 2010. MR**2722836**, DOI 10.1017/CBO9780511779398 - L. Elsner and P. van den Driessche,
*Max-algebra and pairwise comparison matrices*, Linear Algebra Appl.**385**(2004), 47–62. MR**2063346**, DOI 10.1016/S0024-3795(03)00476-2 - Steven N. Evans,
*The expected number of zeros of a random system of $p$-adic polynomials*, Electron. Comm. Probab.**11**(2006), 278–290. MR**2266718**, DOI 10.1214/ECP.v11-1230 - Alexander V. Gnedin,
*The Bernoulli sieve*, Bernoulli**10**(2004), no. 1, 79–96. MR**2044594**, DOI 10.3150/bj/1077544604 - 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**, DOI 10.1214/08-AAP592 - Piet Groeneboom,
*The concave majorant of Brownian motion*, Ann. Probab.**11**(1983), no. 4, 1016–1027. MR**714964** - Piet Groeneboom,
*Limit theorems for convex hulls*, Probab. Theory Related Fields**79**(1988), no. 3, 327–368. MR**959514**, DOI 10.1007/BF00342231 - Piet Groeneboom,
*Convex hulls of uniform samples from a convex polygon*, Adv. in Appl. Probab.**44**(2012), no. 2, 330–342. MR**2977398**, DOI 10.1239/aap/1339878714 - 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**, DOI 10.1007/978-0-387-87835-5 - M. Kac,
*On the average number of real roots of a random algebraic equation*, Bull. Amer. Math. Soc.**49**(1943), 314–320. MR**7812**, DOI 10.1090/S0002-9904-1943-07912-8 - 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**30713**, DOI 10.1112/plms/s2-50.5.390 - 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**, DOI 10.1023/A:1004841130674 - Dmitry Korshunov,
*The key renewal theorem for a transient Markov chain*, J. Theoret. Probab.**21**(2008), no. 1, 234–245. MR**2384480**, DOI 10.1007/s10959-007-0132-8 - J. E. Littlewood and A. C. Offord,
*On the Number of Real Roots of a Random Algebraic Equation*, J. London Math. Soc.**13**(1938), no. 4, 288–295. MR**1574980**, DOI 10.1112/jlms/s1-13.4.288 - D. Maclagan and B. Sturmfels,
*Introduction to tropical geometry*, Book in preparation, 2014. - Jim Pitman,
*Exchangeable and partially exchangeable random partitions*, Probab. Theory Related Fields**102**(1995), no. 2, 145–158. MR**1337249**, DOI 10.1007/BF01213386 - 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** - 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**, DOI 10.1214/11-AOP658 - 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. - Rolf Schneider,
*Recent results on random polytopes*, Boll. Unione Mat. Ital. (9)**1**(2008), no. 1, 17–39. MR**2387995** - Rolf Schneider and Wolfgang Weil,
*Stochastic and integral geometry*, Probability and its Applications (New York), Springer-Verlag, Berlin, 2008. MR**2455326**, DOI 10.1007/978-3-540-78859-1 - 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** - T. Tao and V. Vu,
*Local universality of zeroes of random polynomials*, arXiv preprint arXiv:1307.4357v2, 2013. - 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**, DOI 10.1016/j.laa.2012.08.028 - M. van Manen and D. Siersma,
*Power diagrams and their applications*, arXiv preprint arXiv:math/0508037v2, 2005.

## Additional Information

**Francois Baccelli**- Affiliation: Department of Mathematics, University of Texas, Austin, Texas 78712
- MR Author ID: 28845
**Ngoc Mai Tran**- Affiliation: Department of Mathematics, University of Texas, Austin, Texas 78712
- MR Author ID: 1002503
- 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.
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**368**(2016), 7281-7303 - MSC (2010): Primary 11S05, 60C05, 60D05, 14T05
- DOI: https://doi.org/10.1090/tran/6565
- MathSciNet review: 3471091