{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T02:01:19Z","timestamp":1648605679502},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T00:00:00Z","timestamp":1530057600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,7]]},"abstract":"In 1960 R\u00e9nyi, in his Michigan State University lectures, asked for the number of random queries necessary to recover a hidden bijective labelling ofn<\/jats:italic>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 probabilityp<\/jats:italic>> 1\/2 and we ignore \u2018inconclusive\u2019 queries. We study the number of queries needed to recover the labelling in its entirety (H<\/jats:italic>n<\/jats:italic><\/jats:sub>), before at least one element is recovered (F<\/jats:italic>n<\/jats:italic><\/jats:sub>), and to recover a randomly chosen element (D<\/jats:italic>n<\/jats:italic><\/jats:sub>). This problem exhibits several remarkable behaviours:D<\/jats:italic>n<\/jats:italic><\/jats:sub>converges in probability but not almost surely;H<\/jats:italic>n<\/jats:italic><\/jats:sub>andF<\/jats:italic>n<\/jats:italic><\/jats:sub>exhibit phase transitions with respect top<\/jats:italic>in the second term. We prove that forp<\/jats:italic>> 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)$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>queries to recover the entire bijection. This should be compared to its symmetric (p<\/jats:italic>= 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})$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>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 fromn<\/jats:italic>independent binary sequences generated by a biased(p<\/jats:italic>) memoryless source.<\/jats:p>","DOI":"10.1017\/s0963548318000329","type":"journal-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T05:31:41Z","timestamp":1530077501000},"page":"542-573","source":"Crossref","is-referenced-by-count":0,"title":["Asymmetric R\u00e9nyi Problem"],"prefix":"10.1017","volume":"28","author":[{"given":"M.","family":"DRMOTA","sequence":"first","affiliation":[]},{"given":"A.","family":"MAGNER","sequence":"additional","affiliation":[]},{"given":"W.","family":"SZPANKOWSKI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,6,27]]},"reference":[{"key":"S0963548318000329_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90072-5"},{"key":"S0963548318000329_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/96559.214080"},{"key":"S0963548318000329_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770"},{"key":"S0963548318000329_ref7","unstructured":"Drmota M. , Magner A. and Szpankowski W. (2017) Asymmetric R\u00e9nyi problem. arXiv:1711.01528"},{"key":"S0963548318000329_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.04.001"},{"key":"S0963548318000329_ref14","volume-title":"The Art of Computer Programming","author":"Knuth","year":"1998"},{"key":"S0963548318000329_ref5","first-page":"660","article-title":"Problem 11997","volume":"124","author":"Drmota","year":"2017","journal-title":"The Amer. Math. Monthly"},{"key":"S0963548318000329_ref12","doi-asserted-by":"crossref","first-page":"#R17","DOI":"10.37236\/1302","article-title":"Analysis of an asymmetric leader election algorithm","volume":"4","author":"Janson","year":"1997","journal-title":"Electron. J. Combin."},{"key":"S0963548318000329_ref6","unstructured":"Drmota M. , Magner A. and Szpankowski W. (2016) Asymmetric R\u00e9nyi problem and PATRICIA tries. In 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms."},{"key":"S0963548318000329_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548318000329_ref3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0377-0427(01)00458-7","article-title":"Laws of large numbers and tail inequalities for random tries and PATRICIA trees.","volume":"142","author":"Devroye","year":"2002","journal-title":"J. Comput. Appl. Math."},{"key":"S0963548318000329_ref17","first-page":"1","article-title":"Profiles of PATRICIA tries.","volume":"76","author":"Magner","year":"2016","journal-title":"Algorithmica"},{"key":"S0963548318000329_ref21","first-page":"355","article-title":"On random subsets of a finite set.","volume":"3","author":"R\u00e9nyi","year":"1961","journal-title":"Mathematica"},{"key":"S0963548318000329_ref16","first-page":"16","volume-title":"Eleventh Workshop on Analytic Algorithmics and Combinatorics","author":"Magner","year":"2014"},{"key":"S0963548318000329_ref13","first-page":"21","article-title":"The variance of the profile in digital search trees.","volume":"13","author":"Kazemi","year":"2011","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"S0963548318000329_ref18","doi-asserted-by":"crossref","first-page":"1821","DOI":"10.1137\/070685531","article-title":"Profiles of tries.","volume":"38","author":"Park","year":"2009","journal-title":"SIAM J. Comput."},{"key":"S0963548318000329_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"S0963548318000329_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993000"},{"key":"S0963548318000329_ref1","volume-title":"Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables","author":"Abramowitz","year":"1964"},{"key":"S0963548318000329_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"S0963548318000329_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1137-7"},{"key":"S0963548318000329_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030209"},{"key":"S0963548318000329_ref15","unstructured":"Magner A. (2015) Profiles of PATRICIA tries. PhD thesis, Purdue University."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T10:51:42Z","timestamp":1604487102000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000329\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,27]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S0963548318000329"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000329","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,27]]}}}