The waiting time distribution is studied for the Markov-modulated M/G/1 queue with both the arrival rate βi and the distribution Bi of the service time of the arriving customer depending on the state i of the environmental process. The analysis is based on ladder heights and occupation measure identities, and the fundamental step is to compute the intensity matrix Q of a certain Morkov jump process as the solution of a non-linear matrix equation. The results come out as close matrix parallels of the Pollaczek-Khinchine formula without using transforms or complex variables. Further it is shown that if the Bi are all phase-type, then the waiting time distribution is so as well.
