Probabilistic inference provides a language for describing how organisms may learn from and adapt to their environment. The computations needed to implement probabilistic inference often require specific representations, akin to having the suitable data structures for implementing certain algorithms in computer programming. Yet it is unclear how such representations can be instantiated in the stochastic, parallel-running biochemical machinery found in cells such as single-celled organisms). Here, we show how representations for supporting inference in Markov models can be embodied in cellular circuits, by combining a concentration-dependent scheme for encoding probabilities with a mechanism for directional counting. We show how the logic of protein production and degradation constrains the computation we set out to implement. We argue that this process by which an abstract computation is shaped by its biochemical realization strikes a compromise between "rationalistic" information-processing perspectives and alternative approaches that emphasize embodiment.