Markov strings: jump times, translations, càdlàg paths, Markov property #
Formalization of Section 3.3–3.4 of
M.L. Bujorianu and J. Lygeros, "Toward a General Theory of Stochastic Hybrid Systems", LNCIS 337, Springer, 2006.
A Markov string is obtained by concatenating killed Markov processes: the
current piece is run until its sojourn time S, then the string is restarted
from a new state according to the renewal kernel. The paper describes the
resulting object through
- the recursion
T_{k+1}(ω) = T_k(ω) + S^{i_k}(ω^{i_k})for the jump times (Eq. (10)), - the translation operators
θ_t(ω) = (θ^{i_k}_{t - T_k}(ω^{i_k}) * ω^{i_{k+1}} * …)(Eq. (13)), - the counting process
N_t = Σ_k I_{t ≥ T_k}and Assumption 6 (non-Zeno), - the Markov property (Eq. (14)) and the càdlàg property (Proposition 3).
We formalize the combinatorial/analytic content of this construction in the
structure PiecedProcess, whose axioms are exactly the two properties of the
construction that the proofs of Lemma 1 and Propositions 2–4 use: shifting
inside the current piece does not change the future pieces, and shifting past
the current sojourn time is the same as restarting. From these we derive:
- the shift identity
T_{i+1}(θ_t ω) = T_{k+i+1}(ω) - ton{T_k ≤ t < T_{k+1}}(the computation in the proof of Lemma 1); - the equivalence between the non-Zeno condition and the divergence of the jump times;
- right continuity of a path obtained by concatenation (Proposition 3);
- the semigroup property and Chapman–Kolmogorov equation for a process with the Markov property (Eq. (14)) (Proposition 2).
The pieced-together construction #
The data of the pieced-together (Markov string) construction of
Section 3.3: a shift system, the sojourn time S of the current piece (a
terminal time, Assumption 5(i)), and the map restart sending a trajectory
ω = ω^{i_0} * ω^{i_1} * … to the trajectory ω^{i_1} * ω^{i_2} * … that the
string follows after the first jump.
- S : Ω → ENNReal
The sojourn time of the current piece.
- restart : Ω → Ω
The trajectory followed after the first jump.
- S_terminal : IsTerminalTime self.toShiftSystem self.S
Assumption 5(i):
Sis a terminal time (Eq. (5)). - restart_shift (t : ℝ) (ω : Ω) : 0 ≤ t → ENNReal.ofReal t < self.S ω → self.restart (self.θ t ω) = self.restart ω
Assumption 5(ii)(b): translating inside the current piece does not change the future pieces.
- θ_restart (t r : ℝ) (ω : Ω) : 0 ≤ r → ENNReal.ofReal r = self.S ω → r ≤ t → self.θ t ω = self.θ (t - r) (self.restart ω)
Equation (13): after the current sojourn time the translation operator is the translation of the restarted trajectory.
Instances For
Equation (10): the jump times of the string,
T_0 = 0, T_{k+1}(ω) = S(ω) + T_k(restart ω).
Instances For
The jump times increase with the index.
The sojourn time of the first piece is bounded by every later jump time.
Lemma 1, first step: inside the first piece, translating by t shifts
every jump time back by t: T_{k+1}(θ_t ω) = T_{k+1}(ω) - t whenever
t < S(ω).
Lemma 1 (the computation in its proof): if T_k(ω) ≤ t < T_{k+1}(ω)
then the jump times of the translated trajectory are the later jump times of
ω, shifted back by t:
T_{i+1}(θ_t ω) = T_{k+i+1}(ω) - t.
Explosion time, the counting process and Assumption 6 #
The explosion time T_∞ = lim_k T_k.
Equations
- P.explosionTime ω = ⨆ (k : ℕ), P.jumpTime k ω
Instances For
Assumption 6 (non-Zeno dynamics), pathwise form: the jump times do not
accumulate, i.e. T_∞ = ∞.
Equations
- P.NonZeno = ∀ (ω : Ω), P.explosionTime ω = ⊤
Instances For
The number of jumps in [0, t], N_t = Σ_{k ≥ 1} I_{t ≥ T_k}, as an
element of ℕ∞.
Instances For
N is nondecreasing in time.
If some jump time exceeds t, then only finitely many jumps occur before
t.
Non-Zeno dynamics: the explosion time is infinite exactly when the jump
times eventually exceed every finite horizon; in that case the counting process
N_t is finite for every t.
Under the non-Zeno assumption, only finitely many jumps occur in a bounded time interval.
Proposition 3: the càdlàg property of a concatenation #
The paper's argument is that the sample paths of a Markov string are obtained
by concatenating the sample paths of the component processes, in a way that
preserves right continuity and left limits. The following lemma is the
analytic content of that argument: a path that coincides with a right
continuous function on a right-open interval containing the time t is right
continuous at t.
Proposition 3 (càdlàg property), the piecewise form: if the path f
agrees on each interval [T_k, T_{k+1}) with a right continuous function g k,
and the intervals cover [0, ∞), then f is right continuous on [0, ∞).
Proposition 2: the Markov property #
Equation (14): the simple Markov property of a Markov string, expressed
through a family of expectation operators E^x[·]:
E^x[f · (g ∘ θ_t)] = E^x[f · E^{x_t}[g]].
Equations
Instances For
The f = 1 case of the Markov property: E^x[g ∘ θ_t] = E^x[E^{x_t}[g]].
Chapman–Kolmogorov equation for a Markov string:
E^x[g ∘ θ_{s+t}] = E^x[E^{x_t}[g ∘ θ_s]].
The transition semigroup P_t h(x) = E^x[h(x_t)] of a Markov string.
Equations
- Bujorianu2006.ShiftSystem.semigroupOp E t h y = E y fun (ω : Ω) => h (M.x t ω)
Instances For
The transition operators form a semigroup: P_{t+s} = P_t ∘ P_s. This
is the standard consequence of the Markov property (Eq. (14)) together with the
identity x_s ∘ θ_t = x_{s+t} of Lemma 1.