Two Bayesian sampling schemes are outlined to estimate a K-state Markov switching model with time-varying transition probabilities. Data augmentation for the multinomial logit model of the transition probabilities is alternatively based on a random utility and a difference in random utility extension. We propose a definition to determine a relevant threshold level of the covariate determining the transition distribution, at which the transition distributions are balanced across states. Identification issues are addressed with random permutation sampling. In terms of efficiency, the extension to the difference in random utility specification in combination with random permutation sampling performs best. We apply the method to estimate a regime dependent two-pillar Phillips curve for the euro area, in which lagged credit growth determines the transition distribution of the states.