On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search

摘要

Random walks (RWs) have been extensively studied for more than a century (Feller, 1968). 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 analysis is typically impossible because the difference equations of the steady-state probabilities are not solvable. One endeavor on such an analysis is found in Yazidi et al. (2011). 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 counterpart 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 article, 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 time reversibility. Apart from the analysis being interesting in itself from an analytical perspective, the RW on the tree that this article 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 effciently 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 article contains the analysis of the chain, reports some fascinating limiting properties, and also includes simulations that justify the analytic steady-state results.