Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T20:51:14.718Z Has data issue: false hasContentIssue false
  • English
  • Français

The Largest Missing Value in a Sample of Geometric Random Variables

Published online by Cambridge University Press:  22 May 2014

MARGARET ARCHIBALD  and
ARNOLD KNOPFMACHER
MARGARET ARCHIBALD
Affiliation:
The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, PO Wits, 2050 Johannesburg, South Africa (e-mail: [email protected])
ARNOLD KNOPFMACHER
Affiliation:
The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, PO Wits, 2050 Johannesburg, South Africa (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider samples of n geometric random variables with parameter 0 < p < 1, and study the largest missing value, that is, the highest value of such a random variable, less than the maximum, that does not appear in the sample. Asymptotic expressions for the mean and variance for this quantity are presented. We also consider samples with the property that the largest missing value and the largest value which does appear differ by exactly one, and call this the LMV property. We find the probability that a sample of n variables has the LMV property, as well as the mean for the average largest value in samples with this property. The simpler special case of p = 1/2 has previously been studied, and verifying that the results of the present paper coincide with those previously found for p = 1/2 leads to some interesting identities.

Keywords

Primary 60C05Secondary 05A16
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 670 - 685
Copyright
Copyright © Cambridge University Press 2014 

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]Archibald, M. and Knopfmacher, A. (2007) The average position of the first maximum in a sample of geometric random variables. In Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings Vol. AH, pp. 269–278.CrossRefGoogle Scholar
[2]Archibald, M. and Knopfmacher, A. (2011) The largest missing value in a composition of an integer. Discrete Math. 311 723–731.CrossRefGoogle Scholar
[3]Archibald, M., Knopfmacher, A. and Prodinger, H. (2006) The number of distinct values in a geometrically distributed sample. Europ. J. Combin. 27 1059–1081.CrossRefGoogle Scholar
[4]Bondesson, L., Nilsson, T. and Wikstrand, G. (2007) Probability calculus for silent elimination: A method for medium access control. Research report in mathematical statistics 3, Department of Mathematics and Mathematical Statistics, Umeå University.Google Scholar
[5]Flajolet, P. and Martin, G. N. (1985) Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31 182–209.CrossRefGoogle Scholar
[6]Flajolet, P. and Sedgewick, R. (1995) Mellin transforms and asymptotics: Finite differences and Rice's integrals. Theoret. Comput. Sci. 144 101–124.CrossRefGoogle Scholar
[7]Goh, W. and Hitczenko, P. (2007) Gaps in samples of geometric random variables. Discrete Math. 307 2871–2890.CrossRefGoogle Scholar
[8]Hitczenko, P. and Knopfmacher, A. (2005) Gap-free compositions and gap-free samples of geometric random variables. Discrete Math. 294 225–239.CrossRefGoogle Scholar
[9]Kirschenhofer, P. and Prodinger, H. (1996) The number of winners in a discrete geometrically distributed sample. Ann. Appl. Probab. 6 687–694.CrossRefGoogle Scholar
[10]Louchard, G. and Prodinger, H. (2008) On gaps and unoccupied urns in sequences of geometrically distributed random variables. Discrete Math. 308 1538–1562.Google Scholar
[11]Louchard, G. and Prodinger, H. (2010) Asymptotic results for silent elimination. In Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings Vol. 12, pp. 185–196.CrossRefGoogle Scholar
[12]Louchard, G. and Prodinger, H. (2013) The largest missing value in a composition of an integer and some Allouche–Shallit-like identities. J. Integer Sequences 16 #13.2.2.Google Scholar
[13]Prodinger, H. (1996) Combinatorics of geometrically distributed random variables: Left-to-right maxima. Discrete Math. 153 253–270.CrossRefGoogle Scholar
[14]Szpankowski, W. (2001) Average Case Analysis of Algorithms on Sequences, Wiley.CrossRefGoogle Scholar
[15]Szpankowski, W. and Rego, V. (1990) Yet another application of a binomial recurrence: Order statistics. Computing 43 401–410.CrossRefGoogle Scholar