The Length of Path for Finite Markov Chains and its Application to Modelling Program Behaviour and Interleaved Memory Systems
Percy Tzelnic · Birkhäuser Boston eBooks · 1982
The distribution of the number of distinct states visited along a Markov chain path is obtained. This random variable is hereby called length of path , to be distinguished from the well known first passage time (the number of steps taken firstly to reach a given state). The length of path is related to a notion of capacity in potential theory for Markov chains. The use of these results is warranted in a variety of possible applications, wherever probabilistic walks on graphs may be benefically described not only in terms of the number of steps taken, but also by the number of distinct nodes traversed. In this paper, two different areas of application are considered. One concerns modelling program behaviour in virtual memory systems by a Markov chain model. In this context, the paging rate of the Least Recently Used paging algorithm is obtained. The other concerns the memory bandwidth in interleaved memory systems with saturated demand, where the stream of memory requests is Markovian. An approach to computing the mean memory bandwidth is proposed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.