Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T14:12:54.721Z Has data issue: false hasContentIssue false
  • English
  • Français

On a memory game and preferential attachment graphs

Part of: Combinatorial probability Probability theory on algebraic and topological structures Graph theory Limit theorems

Published online by Cambridge University Press:  10 June 2016

Hüseyin Acan  and
Paweł Hitczenko
Hüseyin Acan*
Affiliation:
Monash University
Paweł Hitczenko*
Affiliation:
Drexel University
*
* Current address: Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA. Email address: [email protected]
** Postal address: Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In their recent paper Velleman and Warrington (2013) analyzed the expected values of some of the parameters in a memory game; namely, the length of the game, the waiting time for the first match, and the number of lucky moves. In this paper we continue this direction of investigation and obtain the limiting distributions of those parameters. More specifically, we prove that when suitably normalized, these quantities converge in distribution to a normal, Rayleigh, and Poisson random variable, respectively. We also make a connection between the memory game and one of the models of preferential attachment graphs. In particular, as a by-product of our methods, we obtain the joint asymptotic normality of the degree counts in the preferential attachment graphs. Furthermore, we obtain simpler proofs (although without rate of convergence) of some of the results of Peköz et al. (2014) on the joint limiting distributions of the degrees of the first few vertices in preferential attachment graphs. In order to prove that the length of the game is asymptotically normal, our main technical tool is a limit result for the joint distribution of the number of balls in a multitype generalized Pólya urn model.

Keywords

Convergence in distributiongeneralized Pólya urnpreferential attachment graphmemory game

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 05C82: Small world graphs, complex networks 60B12: Limit theorems for vector-valued random variables (infinite-dimensional case) 60C05: Combinatorial probability
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 2 , June 2016 , pp. 585 - 609
Copyright
Copyright © Applied Probability Trust 2016 

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]Acan, H. and Hitczenko, P. (2015).On the covariances of outdegrees in random plane recursive trees.J. Appl. Prob. 52,904–907.CrossRefGoogle Scholar
[2]Acan, H. and Pittel, B. (2014).Formation of a giant component in the intersection graph of a random chord diagram. Preprint. Available at http://arxiv.org/abs/1406.2867.Google Scholar
[3]Andersen, J. E.,Penner, R. C.,Reidys, C. M. and Waterman, M. S. (2013).Topological classification and enumeration of RNA structures by genus.J. Math. Biol. 67,1261–1278.Google Scholar
[4]Barabási, A.-L. and Albert, R. (1999).Emergence of scaling in random networks.Science 286,509–512.Google Scholar
[5]Berger, N.,Borgs, C.,Chayes, J. T. and Saberi, A. (2014).Asymptotic behavior and distributional limits of preferential attachment graphs.Ann. Prob. 42,1–40.Google Scholar
[6]Bollobás, B. and Riordan, O. (2004).The diameter of a scale-free random graph.Combinatorica 24,5–34.CrossRefGoogle Scholar
[7]Bollobás, B.,Riordan, O.,Spencer, J. and Tusnády, G. (2001).The degree sequence of a scale-free random graph process.Random Structures Algorithms 18,279–290.Google Scholar
[8]Chmutov, S.,Duzhin, S. and Mostovoy, J. (2012).Introduction to Vassiliev Knot Invariants.Cambridge University Press.CrossRefGoogle Scholar
[9]Cori, R. and Marcus, M. (1998).Counting non-isomorphic chord diagrams.Theoret. Comput. Sci. 204,55–73.Google Scholar
[10]Dulucq, S. and Penaud, J.-G. (1993).Cordes, arbres et permutations.Discrete Math. 117,89–105.Google Scholar
[11]Flajolet, P. and Noy, M. (2000).Analytic combinatorics of chord diagrams. In Formal Power Series and Algebraic Combinatorics,Springer,Berlin, pp.191–201.Google Scholar
[12]Graham, R. L.,Knuth, D. E. and Patashnik, O. (1994).Concrete Mathematics,2nd edn.Addison-Wesley,Reading, MA.Google Scholar
[13]Janson, S. (2004).Functional limit theorems for multitype branching processes and generalized Pólya urns.Stoch. Process. Appl. 110,177–245.Google Scholar
[14]Janson, S. (2005).Asymptotic degree distribution in random recursive trees.Random Structures Algorithms 26,69–83.CrossRefGoogle Scholar
[15]Peköz, E.,Röllin, A. and Ross, N. (2013).Degree asymptotics with rates for preferential attachment random graphs.Ann. Appl. Prob. 23,1188–1218.Google Scholar
[16]Peköz, ,Ross, and Röllin, (2014).Joint degree distributions of preferential attachment random graphs. Preprint. Available at http://arxiv.org/abs/1402.4686v1.Google Scholar
[17]Riordan, J. (1975).The distribution of crossings of chords joining pairs of 2n points on a circle.Math. Comp. 29,215–222.Google Scholar
[18]Ross, N. (2013).Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution.Adv. Appl. Prob. 45,876–893.Google Scholar
[19]Stoimenow, A. (1998).Enumeration of chord diagrams and an upper bound for Vassiliev invariants.J. Knot Theory Ramifications 7,93–114.Google Scholar
[20]Velleman, D. J. and Warrington, G. S. (2013).What to expect in a game of memory.Amer. Math. Monthly 120,787–805.Google Scholar
[21]Zhang, L.-X.,Hu, F.,Chung, S. H. and Chan, W. S. (2011).Immigrated urn models—theoretical properties and applications.Ann. Statist. 39,643–671.Google Scholar