A Probability Inequality and Its Application to Switching Networks

The use of channel graphs to study the blocking probabilities of multistage switching networks was first proposed by Lee and has gained popularity ever since. A channel graph between an input terminal and an output terminal is the union of all paths connecting them in the network. Usually, the assumption is made that links connecting the same two stages, say the ith stage and the (i + 1)st stage, have constant and identical probability p_i of being busy. Let G(s,λ) denote the class of channel graphs with s stages and λ paths. We show that for every channel graph in G(s,λ) with multiple links, there exists a channel graph in the same class without multiple links that has smaller or equal blocking probabilities for all {p_i}. We obtain this result by first proving a probability inequality of a more general nature.