Documentation

SHSLib.Bujorianu2006.MarkovString

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

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 pieced-together construction #

structure Bujorianu2006.PiecedProcess (Ω : Type u_1) (X : Type u_2) extends Bujorianu2006.ShiftSystem Ω X :
Type (max u_1 u_2)

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.

  • θ : ℝ → Ω → Ω
  • x : ℝ → Ω → X
  • θ_zero (ω : Ω) : self.θ 0 ω = ω
  • θ_add (s t : ℝ) (ω : Ω) : 0 ≤ s → 0 ≤ t → self.θ s (self.θ t ω) = self.θ (s + t) ω
  • x_shift (s t : ℝ) (ω : Ω) : 0 ≤ s → 0 ≤ t → self.x s (self.θ t ω) = self.x (s + t) ω
  • 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): S is 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
    def Bujorianu2006.PiecedProcess.jumpTime {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) :
    ℕ → Ω → ENNReal

    Equation (10): the jump times of the string, T_0 = 0, T_{k+1}(ω) = S(ω) + T_k(restart ω).

    Equations
    Instances For
      @[simp]
      theorem Bujorianu2006.PiecedProcess.jumpTime_zero {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (ω : Ω) :
      P.jumpTime 0 ω = 0
      theorem Bujorianu2006.PiecedProcess.jumpTime_succ {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (k : ℕ) (ω : Ω) :
      P.jumpTime (k + 1) ω = P.S ω + P.jumpTime k (P.restart ω)
      @[simp]
      theorem Bujorianu2006.PiecedProcess.jumpTime_one {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (ω : Ω) :
      P.jumpTime 1 ω = P.S ω
      theorem Bujorianu2006.PiecedProcess.jumpTime_mono {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (ω : Ω) :
      Monotone fun (k : ℕ) => P.jumpTime k ω

      The jump times increase with the index.

      theorem Bujorianu2006.PiecedProcess.S_le_jumpTime_succ {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (k : ℕ) (ω : Ω) :
      P.S ω ≤ P.jumpTime (k + 1) ω

      The sojourn time of the first piece is bounded by every later jump time.

      theorem Bujorianu2006.PiecedProcess.jumpTime_shift_first {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (k : ℕ) (t : ℝ) (ω : Ω) (ht : 0 ≤ t) (hlt : ENNReal.ofReal t < P.S ω) :
      P.jumpTime (k + 1) (P.θ t ω) = P.jumpTime (k + 1) ω - ENNReal.ofReal t

      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(ω).

      theorem Bujorianu2006.PiecedProcess.jumpTime_shift {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (k i : ℕ) (t : ℝ) (ω : Ω) (ht : 0 ≤ t) (hk : P.jumpTime k ω ≤ ENNReal.ofReal t) (hk' : ENNReal.ofReal t < P.jumpTime (k + 1) ω) :
      P.jumpTime (i + 1) (P.θ t ω) = P.jumpTime (k + i + 1) ω - ENNReal.ofReal t

      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 #

      def Bujorianu2006.PiecedProcess.explosionTime {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (ω : Ω) :

      The explosion time T_∞ = lim_k T_k.

      Equations
      Instances For
        theorem Bujorianu2006.PiecedProcess.jumpTime_le_explosionTime {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (k : ℕ) (ω : Ω) :
        def Bujorianu2006.PiecedProcess.NonZeno {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) :

        Assumption 6 (non-Zeno dynamics), pathwise form: the jump times do not accumulate, i.e. T_∞ = ∞.

        Equations
        Instances For
          def Bujorianu2006.PiecedProcess.jumpCount {Ω : Type u_1} {X : Type u_2} (P : PiecedProcess Ω X) (t : ℝ) (ω : Ω) :

          The number of jumps in [0, t], N_t = Σ_{k ≥ 1} I_{t ≥ T_k}, as an element of ℕ∞.

          Equations
          Instances For
            theorem Bujorianu2006.PiecedProcess.le_jumpCount {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (k : ℕ) (t : ℝ) (ω : Ω) (h : P.jumpTime k ω ≤ ENNReal.ofReal t) :
            ↑k ≤ P.jumpCount t ω
            theorem Bujorianu2006.PiecedProcess.jumpCount_mono {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (ω : Ω) :
            Monotone fun (t : ℝ) => P.jumpCount t ω

            N is nondecreasing in time.

            theorem Bujorianu2006.PiecedProcess.jumpCount_ne_top_of_lt {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} {t : ℝ} {ω : Ω} {K : ℕ} (h : ENNReal.ofReal t < P.jumpTime K ω) :
            P.jumpCount t ω ≤ ↑K

            If some jump time exceeds t, then only finitely many jumps occur before t.

            theorem Bujorianu2006.PiecedProcess.explosionTime_eq_top_iff {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (ω : Ω) :
            P.explosionTime ω = ⊤ ↔ ∀ (t : ℝ), ∃ (k : ℕ), ENNReal.ofReal t < P.jumpTime k ω

            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.

            theorem Bujorianu2006.PiecedProcess.jumpCount_ne_top {Ω : Type u_1} {X : Type u_2} {P : PiecedProcess Ω X} (h : P.NonZeno) (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.

            theorem Bujorianu2006.rightContinuousWithinAt_of_eqOn_Ico {X : Type u_1} [TopologicalSpace X] {f g : ℝ → X} {t a b : ℝ} (hta : a ≤ t) (htb : t < b) (heq : Set.EqOn f g (Set.Ico a b)) (hg : ContinuousWithinAt g (Set.Ici t) t) :
            theorem Bujorianu2006.rightContinuous_of_concatenation {X : Type u_1} [TopologicalSpace X] (f : ℝ → X) (T : ℕ → ℝ) (g : ℕ → ℝ → X) (hpiece : ∀ (k : ℕ), Set.EqOn f (g k) (Set.Ico (T k) (T (k + 1)))) (hg : ∀ (k : ℕ) (t : ℝ), ContinuousWithinAt (g k) (Set.Ici t) t) (hcover : ∀ (t : ℝ), 0 ≤ t → ∃ (k : ℕ), T k ≤ t ∧ t < T (k + 1)) (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 #

            def Bujorianu2006.ShiftSystem.HasMarkovProperty {Ω : Type u_1} {X : Type u_2} (M : ShiftSystem Ω X) (E : X → (Ω → ℝ) → ℝ) :

            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
            • M.HasMarkovProperty E = ∀ (t : ℝ), 0 ≤ t → ∀ (y : X) (f g : Ω → ℝ), (E y fun (ω : Ω) => f ω * g (M.θ t ω)) = E y fun (ω : Ω) => f ω * E (M.x t ω) g
            Instances For
              theorem Bujorianu2006.ShiftSystem.markov_apply {Ω : Type u_1} {X : Type u_2} {M : ShiftSystem Ω X} {E : X → (Ω → ℝ) → ℝ} (hE : M.HasMarkovProperty E) {t : ℝ} (ht : 0 ≤ t) (y : X) (g : Ω → ℝ) :
              (E y fun (ω : Ω) => g (M.θ t ω)) = E y fun (ω : Ω) => E (M.x t ω) g

              The f = 1 case of the Markov property: E^x[g ∘ θ_t] = E^x[E^{x_t}[g]].

              theorem Bujorianu2006.ShiftSystem.markov_chapman_kolmogorov {Ω : Type u_1} {X : Type u_2} {M : ShiftSystem Ω X} {E : X → (Ω → ℝ) → ℝ} (hE : M.HasMarkovProperty E) {s t : ℝ} (hs : 0 ≤ s) (ht : 0 ≤ t) (y : X) (g : Ω → ℝ) :
              (E y fun (ω : Ω) => g (M.θ (s + t) ω)) = E y fun (ω : Ω) => E (M.x t ω) fun (ω' : Ω) => g (M.θ s ω')

              Chapman–Kolmogorov equation for a Markov string: E^x[g ∘ θ_{s+t}] = E^x[E^{x_t}[g ∘ θ_s]].

              def Bujorianu2006.ShiftSystem.semigroupOp {Ω : Type u_1} {X : Type u_2} {M : ShiftSystem Ω X} (E : X → (Ω → ℝ) → ℝ) (t : ℝ) (h : X → ℝ) (y : X) :

              The transition semigroup P_t h(x) = E^x[h(x_t)] of a Markov string.

              Equations
              Instances For
                theorem Bujorianu2006.ShiftSystem.semigroupOp_comp {Ω : Type u_1} {X : Type u_2} {M : ShiftSystem Ω X} {E : X → (Ω → ℝ) → ℝ} (hE : M.HasMarkovProperty E) {s t : ℝ} (hs : 0 ≤ s) (ht : 0 ≤ t) (h : X → ℝ) :
                semigroupOp E (t + s) h = semigroupOp E t (semigroupOp E s h)

                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.