Instead of a naive dense matrix, you can use some implementation that allows sparsity. If element does not exist, gets a non-zero value which can still be sampled. Which theoretically enables all outputs.

i think at that point it's definitionally not a markov chain anymore. how do you sample an open set of unknown values?