Coupon Collector Problem on Graphs

Mohammed Barmaki

doi:https://doi.org/10.14445/22315373/IJMTT-V58P540

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 58 | Number 4 | Year 2018 | Article Id. IJMTT-V58P540 | DOI : https://doi.org/10.14445/22315373/IJMTT-V58P540

Coupon Collector Problem on Graphs

Mohammed Barmaki

Citation :

Mohammed Barmaki, "Coupon Collector Problem on Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 58, no. 4, pp. 306-308, 2018. Crossref, https://doi.org/10.14445/22315373/IJMTT-V58P540

Abstract

In this article, we start from the combinatorial version of the coupon collector problem, in order to generalize it to the infinitely generated groups. We introduce it analogously to the waiting time in order to complete an n-collection and then after, we establish the graph invariance associated with a finitely generated group. We compute the average of this waiting time for monogenic and free groups.

Keywords

Random walk, Group, Markov Chain, Isoperimetric profile.

References

[1] Boneh, Arnon and Hofri, Micha, "The Coupon-Collector Problem Revisited". Computer Science Technical Reports. Paper 807, e-Pubs Perdue University 1989.
[2] Amy N. Myers And Herbert S. WILF, Some new aspects of the coupon collector problem, SIAM J. DISCRETE MATH. Vol. 17, No. 1, pp. 1?17 (2003).
[3] Bendikov, A. Pittet,Ch. Roman Sauer, Spectral distribution and $L2$-isoperimetric profile of Laplace operators on groups, - Arxiv preprint arXiv:0901.0271, 2009 - arxiv.org.
[4] Coulhon,Th.Grigor'yan, A. On diagonal lower bounds for heat kernels on non-compact manifolds and Markov chains. Duke Math. J. 89 (1997), 133-199. MR1458975.
[5] Coulhon,Th.Grigor'yan,A.Pittet, Ch. A geometric approach to on-diagonal heat kernel lower bounds on groups. Ann. Inst. Fourier 51 (2001), 1763-1827. MR1871289.
[6] Gretete, D. Stabilit\'e du comportement des marches aléatoires sur un groupe localement compact, Ann. Inst. Henri PoincaréeProbab. Stat. 44(2008), no. 1, 129-142 (French, with English and French summaries).
[7] Hebisch, W. On heat kernels on Lie groups. Math. Zeit. 210 (1992), 593-605. MR1175724.
[8] Kesten, H. Full Banach mean values on countable groups, Math. Scand. 7 (1959) 146-156.
[9] Mustapha, S., C.R. Acad.Sci. Paris, Ser.I 340(2005).
[10] Mustapha, S.,Lower estimates for random walks on a class of amenable. p-adicgroups,Journal URL, vol. 14 , no 51, pp. 1513-1531(2009).
[11] Pittet, C., and Saloff-Coste, L. Random walks on finite rank Solvable Groups}, (May 2002).