Doob Finite Markov Bridge

Worked Example: Conditioning the Lazy Path

Let the chain be "Lazy path" with state space {0, 1, 2}. The transition matrix P is given by rows [(0.5, 0.5, 0), (0.25, 0.5, 0.25), (0, 0.5, 0.5)]. Suppose we start at a=0 and condition on ending at b=2 after length N=4. Let the probe state be i=1. The midpoint time is t=2.

1. The unconditioned transition matrix P² is:
   Row 0: (0.375, 0.5, 0.125)
   Row 1: (0.25, 0.5, 0.25)
   Row 2: (0.125, 0.5, 0.375)
2. The event probability is (P⁴)_0,2. We calculate P⁴ by squaring P²:
   (P⁴)_0,2 = 0.375*0.125 + 0.5*0.25 + 0.125*0.375 = 0.046875 + 0.125 + 0.046875 = 0.21875.
3. We compute the probability of being in the probe state i=1 at midpoint t=2. This is (P²)_0,1 * (P²)_1,2 / 0.21875. From P², (P²)_0,1 = 0.5 and (P²)_1,2 = 0.25.
4. Thus, the midpoint probability is (0.5 * 0.25) / 0.21875 = 0.125 / 0.21875 = 4/7 ≈ 0.5714285714285714.
5. The first-step probability to the probe state (at t=1) is P_0,1 * (P³)_1,2 / 0.21875. Since (P³)_1,2 = (P² * P)_1,2 = 0.25*0 + 0.5*0.25 + 0.25*0.5 = 0.25. Thus, first-step probability = 0.5 * 0.25 / 0.21875 = 0.5714285714285714.
6. The initial h at probe is the unconditional probability of reaching the end state from the probe state in N steps: (P⁴)_1,2. (P⁴)_1,2 = 0.25*0.125 + 0.5*0.25 + 0.25*0.375 = 0.03125 + 0.125 + 0.09375 = 0.25.

Experiment with Actual Controls

You can interactively modify the variables and observe how the transition weights change over time to guarantee reaching the final state. Try it out at https://riano.app/module/doob-finite-markov-bridge.

1. Set Chain to "Lazy path".
2. Set Start to 0 and End to 2.
3. Set Length to 4 and Probe state to 1.
4. Observe the computed probabilities: The endpoint event probability is 0.21875, and both midpoint and first-step bridge probabilities to the probe state are ~0.571428.
5. Change the Chain to "Cycle". The endpoint event probability becomes 0 because state 2 cannot be reached from state 0 in exactly 4 steps. The bridge status becomes "Impossible endpoint event".
6. Change the Length to 2 with "Cycle" to see that the endpoint event probability becomes 1.0, and the bridge is defined.

Limitations and Boundaries

The Doob Finite Markov Bridge relies on the assumption that the specified final state is reachable from the specified initial state in exactly N steps.

If the endpoint event probability is 0, such as in the Cycle chain from Start 0 to End 2 with Length 3, the conditional law is undefined. Impossible endpoint events have no conditional law: the probabilities are reported as Unavailable rather than all zeroes, since we cannot condition on an event with zero probability.

Also, at N=0, only a=b is possible. If a=b, the midpoint is the start point, and the first step is Unavailable.

References

The fundamental ideas behind conditioning Markov chains and Doob's h-transform are discussed in the literature on time-inhomogeneous Markov bridges. For details on constructing Markov bridges and specific reweighting mechanisms, refer to:

https://arxiv.org/abs/0905.2155 - A mathematical treatment of Markov bridges, which supports the time-varying transition reweighting framework.