Multiplicities of eigenvalues of some linear search schemes Original Research Article

We consider the problem of dynamically reorganizing a linear list when the list is subject to a random number of requests during a unit time interval. Three different heuristics are considered in which the selected items are moved to the front of the list in random order, the same order and finally the opposite order to the previous one. We find the eigenvalues and their multiplicities for the corresponding transition probability matrices. These are given in terms of the weights representing the probability of selection of the individual items. The methods employed are purely algebraic, being based on properties of permutations, and so our results are valid for arbitrary complex weights.