Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-06T20:03:09.027Z Has data issue: false hasContentIssue false
  • English
  • Français

On random quadratic forms: supports of potential local maxima

Part of: Combinatorial probability Asymptotic theory

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: bgp@math.ohio-state.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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