Applications of spanning trees to continuous-time Markov processes, with emphasis on loss systems

For any stationary, continuous-time, finite-state Markov process, there is a relationship between the solution of the stochastic balance equations and the family of spanning trees associated with the corresponding state transition diagram. In particular, the steady-state distribution can be expressed in terms of sums of products of the instantaneous transition rates, and there is a direct correlation between the form of the solution and the set of spanning trees.; This dissertation presents new applications of this theory, applicable to a wide variety of Markov processes. The most prominant general application involves the random generation of spanning trees. Numerical results were verified via a new application of Perfect Simulation to continuous-time problems. In both cases, an asymptotically unbiased estimator was developed to map from the discrete-time domain to the original continuous-time problem.; The work presented in this dissertation was originally motivated by a particular class of Erlang loss systems involving nonhierarchical overflow traffic. Exact analytical solutions, in terms of the parameter representing the offered traffic load, have been derived for several specific topologies. In addition, asymptotic analysis was applied to develop a closed-form approximate solution for the general case. The nonhierarchical overflow problem serves as the test case for assessing the effectiveness of all techniques presented here.