Appendix CMath

C.1 Martingales [102]

Martingale Definition

A stochastic process {Xn; n = 0, 1, …} is martingale if, for n = 0, 1, …,

  1. E[|Xn|] < ∞
  2. E[Xn+1|X0, …, Xn] = Xn

Def.: Let {Xn; n = 0, 1, …} and {Yn; n = 0, 1, …} be stochastic processes. We say {Xn} is martingale with respect to (w.r.t) {Yn} if, for n = 0, 1, …:

  1. E[|Xn|] < ∞
  2. E[Xn+1|Y0, …, Yn] = Xn

Examples of Martingales:

  1. Suns of independent random variables: Xn = Y1 + ⋯ + Yn.
  2. Variance of a Sum Xn = left-parenthesis sigma-summation Underscript k equals 1 Overscript n Endscripts italic upper Y k right-parenthesis2 − nσ2
  3. Have induced Martingales with Markov Chains! ….
  4. For HMM learning, sequences of likelihood ratios are martingale….

The asymptotic equipartition theorem (AEP) and Hoeffding Inequalities (critical in Chapter 11) have both been generalized to Martingales.

Induced Martingales with Markov Chains [102]

Let {Yn; n = 0, 1, …} be a Markov Chain (MC) process with transition probability matrix P = ||Pij||. Let f be a bounded right regular sequence for P:

f(i) is non‐negative and f left-parenthesis i right-parenthesis equals sigma-summation Underscript k equals 1 Overscript n Endscripts upper P Subscript italic i j Baseline f left-parenthesis j right-parenthesis. Let Xn = f(Yn) ➔ E[|Xn|] < ∞ (since f is bounded). Now have:

StartLayout 1st Row upper E left-bracket upper X Subscript n plus 1 Baseline bar upper Y 0 comma ellipsis comma upper Y Subscript n Baseline right-bracket 2nd Row equals upper E left-bracket f left-parenthesis upper Y Subscript n plus 1 Baseline right-parenthesis bar upper Y 0 comma ellipsis comma upper Y Subscript n Baseline right-bracket 3rd Row equals upper E left-bracket f left-parenthesis upper Y Subscript n plus 1 Baseline right-parenthesis bar upper Y Subscript n Baseline right-bracket left-parenthesis d u e to upper M upper C right-parenthesis 4th Row equals sigma-summation Underscript k equals 1 Overscript n Endscripts italic upper P upper Y Subscript n Baseline comma italic j f left-parenthesis j right-parenthesis left-parenthesis d e f period of upper P Subscript italic i j Baseline and f right-parenthesis 5th Row equals f left-parenthesis upper Y Subscript n Baseline right-parenthesis 6th Row equals upper X Subscript n EndLayout

In HMM Learning Have Sequences of Likelihood Ratios, Which Is a Martingale, Proof

Let Y0, Y1, … be iid rv.s and let f0 and f1 be probability density functions. A stochastic process of ...

Get Informatics and Machine Learning now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial