Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T05:25:47.039Z Has data issue: false hasContentIssue false
  • English
  • Français

On random quadratic forms: supports of potential local maxima

Part of: Asymptotic theory Combinatorial probability

Published online by Cambridge University Press:  16 January 2019

Boris Pittel
Boris Pittel*
Affiliation:
The Ohio State University
*
* Postal address: Department of Mathematics, The Ohio State University, Columbus, Ohio 43210, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The selection model in population genetics is a dynamic system on the set of the probability distributions 𝒑=(p1,…,pn) of the alleles A1…,An, with pi(t+1) proportional to pi(t) multiplied by ∑jfi,jpj(t), and fi,j=fj,i interpreted as a fitness of the gene pair (Ai,Aj). It is known that 𝒑̂ is a locally stable equilibrium if and only if 𝒑̂ is a strict local maximum of the quadratic form 𝒑T𝒇𝒑. Usually, there are multiple local maxima and lim𝒑(t) depends on 𝒑(0). To address the question of a typical behavior of {𝒑(t)}, John Kingman considered the case when the fi,j are independent and [0,1]-uniform. He proved that with high probability (w.h.p.) no local maximum may have more than 2.49n1∕2 positive components, and reduced 2.49 to 2.14 for a nonbiological case of exponentials on [0,∞). We show that the constant 2.14 serves a broad class of smooth densities on [0,1] with the increasing hazard rate. As for a lower bound, we prove that w.h.p. for all k≤2n1∕3, there are many k-element subsets of [n] that pass a partial test to be a support of a local maximum. Still, it may well be that w.h.p. the actual supports are much smaller. In that direction, we prove that w.h.p. a support of a local maximum, which does not contain a support of a local equilibrium, is very unlikely to have size exceeding ⅔log2n and, for the uniform fitnesses, there are super-polynomially many potential supports free of local equilibriums of size close to ½log2n.

Keywords

Stable polymorphismrandom fitnessasymptotics

MSC classification

Primary: 34E05: Asymptotic expansions
Secondary: 60C05: Combinatorial probability
Type
Applied Probability Trust Lecture
Information
Journal of Applied Probability , Volume 55 , Issue 4 , December 2018 , pp. 1113 - 1130
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andrews, G. E., Askey, R. and Roy, R. (1999). Special Functions. Cambridge University Press.Google Scholar
[2]Baum, L. E. and Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc. 73, 360–363.Google Scholar
[3]Chen, X. and Peng, J. (2015). New analysis on sparse solutions to random standard quadratic optimization problems and extensions. Math. Operat. Res. 40, 725–738.Google Scholar
[4]Chen, X., Peng, J. and Zhang, S. (2013). Sparse solutions to random standard quadratic optimization problems. Math. Program. (Ser. A 141), 273–293.Google Scholar
[5]Feller, W. (1971). An Introduction to Probability Theory and Its Applications, 2nd edn. John Wiley, Oxford.Google Scholar
[6]Fisher, R. A. (1930). The Genetical Theory of Natural Selection. Oxford Clarendon Press.Google Scholar
[7]Haigh, J. (1988). The distribution of evolutionarily stable strategies. J. Appl. Prob. 25, 113–125.Google Scholar
[8]Haigh, J. (1989). How large is the support of an ESS. J. Appl. Prob. 26, 164–170.Google Scholar
[9]Hofbauer, J. and Sigmund, K. (1998). Evolutionary Games and Replicator Dynamics. Cambridge University Press.Google Scholar
[10]Kingman, J. F. C. (1961). A mathematical problem in population genetics. Proc. Camb. Phil. Soc. 57, 574–582.Google Scholar
[11]Kingman, J. F. C. (1961). A matrix inequality. Quart. J. Math. 12, 78–80.Google Scholar
[12]Kingman, J. F. C. (1988). Typical polymorphisms maintained by selection at a single locus. J. Appl. Prob. 25, 113–125.Google Scholar
[13]Kingman, J. F. C. (1989). Maxima of random quadratic forms on a simplex. In Probability, Statistics and Mathematics. Academic Press, Boston, MA, pp. 123–141.Google Scholar
[14]Kingman, J. F. C. (1990). Some random collections of finite sets. In Disorder in Physical Systems, A Volume in Honour of John M. Hammersley, Oxford University Press, pp. 241–247.Google Scholar
[15]Knuth, D. E. (1996). Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. CRM Proc. Lecture Notes 10, 74 pp.Google Scholar
[16]Kontogiannis, S. C. and Spirakis, P. G. (2009). On the support size of stable strategies in random games. Theoret. Comput. Sci. 410, 933–942.Google Scholar
[17]Lewontin, R. C., Ginzburg, L. R. and Tuljapurkar, S. D. (1978). Heterosis as an explanation for large amounts of genic polymorphism. Genetics 1988, 149–170.Google Scholar
[18]Pittel, B. (1989). The average number of stable matchings. SIAM J. Discrete Math. 2, 530–549.Google Scholar
[19]Pittel, B. (2018). On random stable partitions. Preprint. To appear in Internat. J. Game Theory Available at https://doi.org/10.1007/s00182-018-0635-9.Google Scholar
[20]Scheuer, P. and Mandel, S. (1959). An inequality in population genetics. Heredity 13, 519–524.Google Scholar