Coupon Collector Problem on Graphs

  IJMTT-book-cover
 
International Journal of Mathematics Trends and Technology (IJMTT)
 
© 2018 by IJMTT Journal
Volume-58 Number-4
Year of Publication : 2018
Authors : Mohammed Barmaki
  10.14445/22315373/IJMTT-V58P540

MLA

Mohammed Barmaki "Coupon Collector Problem on Graphs" , International Journal of Mathematics Trends and Technology (IJMTT). V58(4):306-308 June 2018. ISSN:2231-5373. www.ijmttjournal.org. Published by Seventh Sense Research Group.

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.

Reference
[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).

Keywords
Random walk, Group, Markov Chain, Isoperimetric profile.