NON-SKIP-FREE M G/1 AND G/M/1 TYPE MARKOV-CHAINS/

For Markov chains of M/G/1 type that are not skip-free to the left, th e corresponding G matrix is shown to have special structure and be det ermined by its first block row. An algorithm that takes advantage of t his structure is developed for computing G. For non-skip-free M/G/1 ty pe Markov chains, the algorithm sig nificantly reduces the computation al complexity of calculating the G matrix, when compared with reblocki ng to a system that is skip-free to the left and then applying usual i teration schemes to find G. A similar algorithm to calculate the R mat rix for G/M/1 type Markov chains that are not skip-free to the right i s also described.