There are numerous applications in Artificial Intelligence (AI) and Machine Learning (ML) where the criteria for decisions are based on testing procedures. The most common tools used in such random phenomena involve Random Walks (RWs). The theory of RWs and its applications have gained an increasing research interest since the start of the last century. [1]. In this context, we note that a RW is, usually, defined as a trajectory involving a series of successive random steps, which are, quite naturally, modeled using Markov Chains (MCs). MCs are probabilistic structures that possess the so-called “Markov property” – which implies that the next “state” of the walk depends on the current state and not on the entire past states (or history). This imparts to the structure practical consequential implications since it permits the modeler to predict how the chain will behave in the immediate and distant future, and to thus quantify its behavior. Although Random Walks (RWs) with single-step transitions have been extensively studied for almost a century, problems involving the analysis of RWs that contain interleaving random steps and random “jumps” are intrinsically hard. In this paper, we consider the analysis of one such fascinating RW, where every step is paired with its counterpart random jump. Apart from this RW being conceptually interesting, it also has applications in the testing of entities (components or personnel), where the entity is never allowed to make more than a pre-specified number of consecutive failures. The paper contains the analysis of the chain, some fascinating limiting properties, and simulations that justify the analytic results. The generalization for a researcher to use the same strategy to know when an AI scheme should switch from “Exploration” to “Exploitation” is an extremely interesting avenue for future research. As far as we know, the entire field of RWs with interleaving steps and jumps is novel, and we believe that this is a pioneering paper in this field, with vast potential in AI and ML.

Additional Metadata
Persistent URL
Series Lecture Notes in Computer Science
Yazidi, A. (Anis), Granmo, O.-C. (Ole-Christoffer), & Oommen, J. (2011). A New Tool for the Modeling of AI and Machine Learning Applications: Random Walk-Jump Processes. In Lecture Notes in Computer Science. doi:10.1007/978-3-642-21219-2_2