Asymmetric Renyi Problem and > PATRICIA Tries - Publikacja - MOST Wiedzy

Wyszukiwarka

Asymmetric Renyi Problem and > PATRICIA Tries

Abstrakt

In 1960 R´enyi asked for the number of random queries necessary to recover a hidden bijective labeling of n distinct objects. In each query one selects a random subset of labels and asks, what is the set of objects that have theselabels? Weconsider here anasymmetric version of the problem in which in every query an object is chosenwith probability p > 1/2 and we ignore “inconclusive” queries. We study the number of queries needed to recover the labeling in its entirety (the height), to recover at least one single element (the fillup level), and to recover a randomly chosen element (the typical depth). This problem exhibits several remarkable behaviors: the depth Dn converges in probability but not almost surely and while it satisfies the central limit theorem its local limit theorem doesn’t hold; the height Hn and the fillup level Fn exhibit phase transitions with respect to p in the second term. To obtain these results, we take a unified approach via the analysis of the external profile defined at level k as the number of elements recovered by the kth query. We first establish new precise asymptotic results for the average and variance, and a central limit law, for the external profile in the regime where it grows polynomially with n. We then extend the external profile results to the boundaries of the central region, leading to the solution of our problem for the height and fillup level. As a bonus, our analysis implies novel results for random PATRICIA tries, as it turns out that the problem is probabilistically equivalent to the analysis of the height, fillup level, typical depth, and external profile of a PATRICIA trie built from n independent binary sequences generated by a biased(p) memoryless source.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Proceedings of the 27th International Conference on Probab ilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms strony 1 - 18
Język:
angielski
Rok wydania:
2016
Opis bibliograficzny:
Drmota M., Magner A., Szpankowski W.: Asymmetric Renyi Problem and > PATRICIA Tries // Proceedings of the 27th International Conference on Probab ilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms/ ed. Ralph Neininger, Marek Zaione Kraków: , 2016, s.1-18
Weryfikacja:
Politechnika Gdańska

wyświetlono 19 razy

Publikacje, które mogą cię zainteresować

Meta Tagi