{"id":14724,"date":"2022-05-26T22:13:11","date_gmt":"2022-05-27T02:13:11","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14724"},"modified":"2026-06-09T11:16:17","modified_gmt":"2026-06-09T15:16:17","slug":"tr-53-optimal-list-organizing-strategy-which-uses-stochastic-move-to-front-operations","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/tr-53-optimal-list-organizing-strategy-which-uses-stochastic-move-to-front-operations\/","title":{"rendered":"TR-53: Optimal List Organizing Strategy Which Uses Stochastic Move-to-Front Operations"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-53: Optimal List Organizing Strategy Which Uses Stochastic Move-to-Front Operations\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/\">Technical Report<\/a>&nbsp;<strong>TR-53<\/strong><br>June 1984<\/p>\n\n\n\n<h2 id=\"constrained-string-editing\" class=\"wp-block-heading\">Constrained String Editing<\/h2>\n\n\n\n<p>B.J. Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Consider a list of elements {R 1 , \u2022, R}N in which the element Ri is accessed with an (unknown) probability Si\u2022 If the cost of accessing Ri is proportional to i (as in sequential search) then it is advantageous if each access is accompanied by a simple reordering operation. This operation is chosen so that ultimately the list will be sorted in the descending order of the access probabilities. We present a dynamic list organizing scheme which permits the element Rj to be moved to the front of the list on being accessed. However, as opposed to the schemes discussed in the literature, the move operation is performed with probability Pj\u2022 The latter quantity adaptively evolves in such a way that in the limit, no more move operations are performed. When this occurs we say that the scheme has converged. Although the scheme could converge to any one of the N! possible configurations, we shall show that by suitably updating the probabilities {pj} the probability of converging to the right arrangement can be made as close to unity as desired.<\/p>\n\n\n\n<h3 id=\"download\" class=\"wp-block-heading\">Download<\/h3>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-53.pdf\">TR-53.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-53June 1984 Constrained String Editing B.J. Oommen Abstract Consider a list of elements {R 1 , \u2022, R}N in which the element Ri is accessed with an (unknown) probability Si\u2022 If the cost of accessing Ri is proportional to i (as in sequential search) then it is advantageous if each access is accompanied [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11787,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-14724","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14724","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14724"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14724\/revisions"}],"predecessor-version":[{"id":24557,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14724\/revisions\/24557"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11787"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14724"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14724"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}