Another problem by fakalin.<\/p>\n
A data structure has the entropy bound if all queries have amortized time \\(O(\\sum_k p_k \\log 1\/p_k)\\), where \\(p_k\\) is the fraction of the time that key \\(k\\) is queried. It has the working-set property if the time to search for an element \\(x_i\\) is \\(O(\\log t_i)\\), where \\(t_i\\) is the number of elements queried since the last access to \\(x_i\\). Prove that the working-set property implies the entropy bound.<\/p><\/blockquote>\n
This isn’t really a data structure problem, per se.
\n
\nThe general intuition here is that, if the waiting time between two queries to a key \\(k\\) is \\(t(k)\\), then key \\(k\\) ends up taking up about a \\(p_k = 1\/t(k)\\) fraction of the queries, and therefore the average query time is about \\(\\sum_{k\\in K} 1\/t(k) (\\log t(k))\\).<\/p>\nWhile this is exactly true for evenly spaced-out queries, the general case only requires a slight modification using any of the rudimentary convex inequalities such as:<\/p>\n
Jensen’s inequality:<\/strong> If \\(f\\) is a convex function and \\(X\\) is a random variable, then \\(\\mathbb{E}f(X)\\ge f(\\mathbb{E}X)\\).<\/p>\n
(The proof just uses the definition of what a convex function is. Furthermore, if we recognize that \\(-\\log x\\) is a convex function, then we get \\(\\mathbb{E}\\log(X)\\le \\log(\\mathbb{E}X)\\), which restates the well-known fact that the geometric mean is less than or equal to the arithmetic mean of a collection of real numbers.)<\/p>\n
Now, let \\(N\\) be the total number of queries. Let \\(n(k)\\) be the number of queries on key \\(k\\). Let \\(t_i(k)\\) be the time between the \\(i\\)th query on key \\(k\\) and the previous query on the same key. Let \\(\\bar{a}(k)< C \\sum_{i=1}^{n(k)} \\log t_i(k) \/ n(k)[\/latex] (for some [latex]C>0\\)) be the average<\/em> query time looking up key \\(k\\), as guaranteed by the working-set property (*). Let \\(\\bar{t}(k) = \\sum_{i=1}^{n(k)} t_i(k) \/ n(k)\\) be the average<\/em> time between queries for key \\(k\\).<\/p>\n
Note that we must have \\(\\bar{t}(k) \\le N\/n(k)\\). Furthermore, \\(p_k = n(k)\/N\\) by definition, hence \\(\\bar{t}(k) \\le 1\/p_k\\) (**). The average query time over all keys is therefore:<\/p>\n
\\(\\sum_k \\bar{a}(k) n(k) \/ N\\)
\n\\(\\)< \\sum_k [C \\sum_{i=1}^{n(k)} \\log t_i(k) \/ n(k)] [n(k) \/ N][\/latex], by (*)\n[latex]\\le C \\sum_k [\\log \\sum_{i=1}^{n(k)} t_i(k) \/ n(k)] [n(k) \/ N][\/latex], by Jensen's inequality\n[latex]= C \\sum_k [\\log \\bar{t}(k)] p_k[\/latex]\n[latex]\\le C \\sum_k p_k \\log 1\/p_k[\/latex], by (**)\n\n\u220e\n<\/p>\n","protected":false},"excerpt":{"rendered":"Another problem by fakalin. A data structure has the entropy bound if all queries have amortized time , where is the fraction of the time that key is queried. It has the working-set property if the time to search for an element is , where is the number of elements queried since the last access […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2732,127,10,2735,624],"class_list":["post-854","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-entropy","tag-fraction","tag-mathbb","tag-query","tag-structure"],"_links":{"self":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=854"}],"version-history":[{"count":0,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/854\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}