On a memory game and preferential attachment graphs

DOI10.1017/APR.2016.16MaRDI QIDQ5740704zbMATH OpenOpenAlexFDO

Authors Hüseyin Acan, Paweł Hitczenko

Publication date 27 July 2016

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.5751, http://projecteuclid.org/euclid.aap/1465490764

zbMATH Keywords

convergence in distributiongeneralized Pólya urnmemory gamepreferential attachment graph

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Limit theorems for vector-valued random variables (infinite-dimensional case) (60B12) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Probabilistic games; gambling (91A60)

Abstract: In a recent paper Velleman and Warrington 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 simpler proofs (although without rate of convergence) of some of the results of Pek"oz, R"ollin, and Ross on the joint limiting distributions of the degrees of the first few vertices in preferential attachment graphs. For proving 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 multi--type generalized P'olya urn model.

Recommendations

• Joint degree distributions of preferential attachment random graphs
• Degree asymptotics with rates for preferential attachment random graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Fluctuations in a general preferential attachment model via Stein's method
• Pólya urns with immigration at random times

Cited in

(4)

• An asymptotic distribution theory for Eulerian recurrences with applications
• Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
• What to expect in a game of memory
• On Bollobás‐Riordan random pairing model of preferential attachment graph

This page was built for publication: On a memory game and preferential attachment graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740704)