Show simple item record

dc.contributor.authorYazidi, Anis
dc.contributor.authorOommen, John
dc.date.accessioned2019-03-18T09:57:02Z
dc.date.accessioned2019-03-21T13:06:16Z
dc.date.available2019-03-18T09:57:02Z
dc.date.available2019-03-21T13:06:16Z
dc.date.issued2018-03-08
dc.identifier.citationYazidi A, Oommen J. On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search. Sequential Analysis. 2018;37(1):31-46en
dc.identifier.issn0747-4946
dc.identifier.issn0747-4946
dc.identifier.issn1532-4176
dc.identifier.urihttps://hdl.handle.net/10642/6858
dc.description.abstractRandom Walks (RWs) have been extensively studied for more than a century [1]. These walks have traditionally been on a line, and the generalizations for two and three dimensions, have been by extending the random steps to the corresponding neighboring positions in one or many of the dimensions. Among the most popular RWs on a line are the various models for birth and death processes, renewal processes and the gambler’s ruin problem. All of these RWs operate “on a discretized line”, and the walk is achieved by performing small steps to the current-state’s neighbor states. Indeed, it is this neighbor-step motion that renders their analyses tractable. When some of the transitions are to non-neighbour states, a formal analysisis, typically, impossible because the difference Equations of the steady-state probabilities are not solvable. One endeavor on such a nanalysis is foundin [2]. The problem is far more complex when the transitions of the walk follow an underlying tree-like structure. The analysis of RWs on a tree have received little attention, even though it is an important topic since a tree is a counter-part space representation of a line whenever there is some ordering on the nodes on the line. Nevertheless, RWs on a tree entail moving to non-neighbor states in the space, which makes the analysis involved, and in many cases, impossible. In this paper, we consider the analysis of one such fascinating RW. We demonstrate that an analysis of the chain is feasible because we can invoke the phenomenon of “time reversibility”. Apart from the analysis being interesting in itself from an analytical perspective, the RW on the tree that this paper models, is a type of generalization of dichotomous search with faulty feedback about the direction of the search, rendering the real-life application of the model to be pertinent. To resolve this, we advocate the concept of “backtracking” transitions in order to efficiently explore the search space. Interestingly, it is precisely these “backtracking” transitions that naturally render the chain to be “time reversible”. By doing this, we are able to bridge the gap between deterministic dichotomous search and its faulty version. The paper contains the analysis of the chain, reports some fascinating limiting properties, and also includes simulations that justify the analytic steady-state results.en
dc.language.isoenen
dc.publisherTaylor & Francisen
dc.relation.ispartofseriesSequential Analysis;Volume 37, 2018 - Issue 1
dc.rightsThis is an Accepted Manuscript of an article published by Taylor & Francis in Sequential Analysis, available online: http://www.tandfonline.com/10.1080/07474946.2018.1427971.en
dc.subjectTime reversibilitiesen
dc.subjectControlled random walksen
dc.subjectRandom walk jumpsen
dc.subjectDichotomous searchesen
dc.subjectLearning systemsen
dc.titleOn the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous searchen
dc.typeJournal articleen
dc.typePeer revieweden
dc.date.updated2019-03-18T09:57:02Z
dc.description.versionacceptedVersionen
dc.identifier.doihttp://dx.doi.org/10.1080/07474946.2018.1427971
dc.identifier.cristin1597594
dc.source.journalSequential Analysis


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record