Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T16:04:30.188Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymmetric Rényi Problem

Part of: Theory of computing Algorithms - Computer Science

Published online by Cambridge University Press:  27 June 2018

M. DRMOTA ,
A. MAGNER  and
W. SZPANKOWSKI
M. DRMOTA
Affiliation:
Institute for Discrete Mathematics and Geometry, TU Wien, A-1040 Vienna, Austria (e-mail: [email protected])
A. MAGNER
Affiliation:
Coordinated Science Lab, UIUC, Champaign, IL 61820, USA (e-mail: [email protected])
W. SZPANKOWSKI
Affiliation:
Department of Computer Science, Purdue University, IN 47907, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In 1960 Rényi, in his Michigan State University lectures, asked for the number of random queries necessary to recover a hidden bijective labelling of n distinct objects. In each query one selects a random subset of labels and asks, which objects have these labels? We consider here an asymmetric version of the problem in which in every query an object is chosen with probability p > 1/2 and we ignore ‘inconclusive’ queries. We study the number of queries needed to recover the labelling in its entirety (Hn), before at least one element is recovered (Fn), and to recover a randomly chosen element (Dn). This problem exhibits several remarkable behaviours: Dn converges in probability but not almost surely; Hn and Fn exhibit phase transitions with respect to p in the second term. We prove that for p > 1/2 with high probability we need

$$H_n=\log_{1/p} n +{\tfrac{1}{2}} \log_{p/(1-p)}\log n +o(\log \log n)$$
queries to recover the entire bijection. This should be compared to its symmetric (p = 1/2) counterpart established by Pittel and Rubin, who proved that in this case one requires
$$ H_n=\log_{2} n +\sqrt{2 \log_{2} n} +o(\sqrt{\log n})$$
 queries. As a bonus, our analysis implies novel results for random PATRICIA tries, as the problem is probabilistically equivalent to that of the height, fillup level, and typical depth of a PATRICIA trie built from n independent binary sequences generated by a biased(p) memoryless source.

MSC classification

Primary: 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Secondary: 68W40: Analysis of algorithms
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Special Issue 4: Analysis of Algorithms , July 2019 , pp. 542 - 573
Copyright
Copyright © Cambridge University Press 2018 

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

Footnotes

†

Research partially supported by Austrian Science Foundation FWF grant F50-02.

‡

Research supported by NSF Center for Science of Information (CSoI) grant CCF-0939370.

§

Research partially supported by NSF Center for Science of Information (CSoI) grant CCF-0939370, and in addition by NSF grants CCF-1524312, and NIH grant 1U01CA198941-01.

References

Abramowitz, M. and Stegun, I. A. (1964) Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Vol. 55 of National Bureau of Standards Applied Mathematics Series, US Government Printing Office.Google Scholar
Devroye, L. (1992) A note on the probabilistic analysis of PATRICIA trees. Random Struct. Alg. 3 203–214.CrossRefGoogle Scholar
Devroye, L. (2002) Laws of large numbers and tail inequalities for random tries and PATRICIA trees. J. Comput. Appl. Math. 142 27–37.CrossRefGoogle Scholar
Devroye, L. (2005) Universal asymptotics for random tries and PATRICIA trees. Algorithmica 42 11–29.CrossRefGoogle Scholar
Drmota, M., Krattenthaler, C. and Pogudin, G. (2017) Problem 11997, The Amer. Math. Monthly, vol. 124, number 7, p. 660.Google Scholar
Drmota, M., Magner, A. and Szpankowski, W. (2016) Asymmetric Rényi problem and PATRICIA tries. In 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms.Google Scholar
Drmota, M., Magner, A. and Szpankowski, W. (2017) Asymmetric Rényi problem. arXiv:1711.01528Google Scholar
Drmota, M. and Szpankowski, W. (2011) The expected profile of digital search trees. J. Combin. Theory Ser. A 118 1939–1965.CrossRefGoogle Scholar
Flajolet, P., Gourdon, X. and Dumas, P. (1995) Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 3–58.CrossRefGoogle Scholar
Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
Jacquet, P. and Szpankowski, W. (1998) Analytical depoissonization and its applications. Theoret. Comput. Sci. 201 1–62.CrossRefGoogle Scholar
Janson, S. and Szpankowski, W. (1997) Analysis of an asymmetric leader election algorithm. Electron. J. Combin. 4 #R17.Google Scholar
Kazemi, R. and Vahidi-Asl, M. (2011) The variance of the profile in digital search trees. Discrete Math. Theoret. Comput. Sci. 13 21–38.Google Scholar
Knuth, D. E. (1998) The Art of Computer Programming, Vol. 3: Sorting and Searching, second edition, Addison Wesley Longman.Google Scholar
Magner, A. (2015) Profiles of PATRICIA tries. PhD thesis, Purdue University.Google Scholar
Magner, A., Knessl, C. and Szpankowski, W. (2014) Expected external profile of PATRICIA tries. In Eleventh Workshop on Analytic Algorithmics and Combinatorics, SIAM, pp. 16–24.Google Scholar
Magner, A. and Szpankowski, W. (2016) Profiles of PATRICIA tries. Algorithmica 76 1–67.Google Scholar
Park, G., Hwang, H.-K., Nicodème, P. and Szpankowski, W. (2009) Profiles of tries. SIAM J. Comput. 38 1821–1880.CrossRefGoogle Scholar
Pittel, B. (1985) Asymptotic growth of a class of random trees. Ann. Probab. 18 414–427.CrossRefGoogle Scholar
Pittel, B. and Rubin, H. (1990) How many random questions are needed to identify n distinct objects? J. Combin. Theory Ser. A 55 292–312.CrossRefGoogle Scholar
Rényi, A. (1961) On random subsets of a finite set. Mathematica 3 355–362.Google Scholar
Szpankowski, W. (1990) PATRICIA tries again revisited. J. Assoc. Comput. Mach. 37 691–711.CrossRefGoogle Scholar
Szpankowski, W. (2001) Average Case Analysis of Algorithms on Sequences, Wiley.CrossRefGoogle Scholar