You would marginalize state out of the model.
is an exampe with the DiscreteMarkovChain (which you never want to sample, it exists solely so you can marginalize it next): pymc-extras/tests/model/marginal/test_distributions.py at 7d62c53139419df8f9d7ef89b69ec07befbbad4d · pymc-devs/pymc-extras · GitHub
In that case chain is marginalized using the forward algorithm which has complexity P.shape[-1] * steps or something not P.shape[-1] ** steps if you did a naive enumeration.