We present a simple, effective generalisation of variable order Markov
models to full online Bayesian estimation. The mechanism used is close
to that employed in context tree weighting. The main contribution is
the addition of a prior, conditioned on context, on the Markov
order. The resulting construction uses a simple recursion and can be
updated efficiently. This allows the model to make predictions using
more complex contexts, as more data is acquired, if necessary.  In
addition, our model can be alternatively seen as a mixture of tree
experts.  Experimental results show that the predictive model exhibits
consistently good performance in a variety of domains.