We propose two sum-product laws for imprecise Markov chains, and use these laws to derive two algorithms to efficiently compute lower and upper expectations for imprecise Markov chains under complete independence and epistemic irrelevance. These algorithms work for inferences that have a corresponding sum-product decomposition, and we argue that many well-known inferences fit their scope. We illustrate our results on a simple epidemiological example.

The possibility of flexibly assigning spectrum resources with channels of different sizes greatly improves the spectral efficiency of optical networks, but can also lead to unwanted spectrum fragmentation. We study this problem in a scenario where traffic demands are categorized in two types (low or high bit-rate) by assessing the performance of three allocation policies. Our first contribution consists of exact Markov chain models for these allocation policies, which allow us to numerically compute the relevant performance measures. However, these exact models do not scale to large systems, in the sense that the computations required to determine the blocking probabilities-which measure the performance of the allocation policies-become intractable. In order to address this, we first extend an approximate reduced-state Markov chain model that is available in the literature to the three considered allocation policies. These reduced-state Markov chain models allow us to tractably compute approximations of the blocking probabilities, but the accuracy of these approximations cannot be easily verified. Our main contribution then is the introduction of reduced-state imprecise Markov chain models that allow us to derive guaranteed lower and upper bounds on blocking probabilities, for the three allocation policies separately or for all possible allocation policies simultaneously.