exercise:Bc093aec03: Difference between revisions
From Stochiki
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> Consider an absorbing Markov chain with state space <math>S</math>. Let <math>f</math> be a function defined on <math>S</math> with the property that <math display="block"> f(i) = \sum_{j \in S} p_{ij} f(j)\ , </math> or in vector form <math di...") |
No edit summary |
||
| Line 5: | Line 5: | ||
\newcommand{\secstoprocess}{\all} | \newcommand{\secstoprocess}{\all} | ||
\newcommand{\NA}{{\rm NA}} | \newcommand{\NA}{{\rm NA}} | ||
\newcommand{\mathds}{\mathbb}</math></div> Consider an absorbing Markov chain with state | \newcommand{\mathds}{\mathbb}</math></div> Consider an absorbing Markov chain with state space <math>S</math>. Let <math>f</math> be a function defined on <math>S</math> with the property that | ||
space <math>S</math>. Let <math>f</math> be a function defined on <math>S</math> with the property that | |||
<math display="block"> | <math display="block"> | ||
| Line 21: | Line 20: | ||
harmonic condition means that the game is ''fair'' in the sense that your | harmonic condition means that the game is ''fair'' in the sense that your | ||
expected fortune after one step is the same as it was before the step. | expected fortune after one step is the same as it was before the step. | ||
<ul><li> Show that for <math>f</math> harmonic | <ul style="list-style-type:lower-alpha"><li> Show that for <math>f</math> harmonic | ||
<math display="block"> | <math display="block"> | ||
| Line 38: | Line 37: | ||
\mat{P}^\infty = \lim_{n \to \infty} \mat{P}^n = | \mat{P}^\infty = \lim_{n \to \infty} \mat{P}^n = | ||
\pmatrix{ | \pmatrix{ | ||
\begin{array}{l|r} \mat{0} & \mat{B} \\ \hline | |||
\begin{ | \mat{0} & \mat{I} \\ \end{array} | ||
\mat{0} & \mat{I} \\ \end{ | |||
\cr}\ . | \cr}\ . | ||
</math> | </math> | ||
</li> | </li> | ||
<li> Using (b), prove that when you start in a transient state <math>i</math> your | <li> Using (b), prove that when you start in a transient state <math>i</math> your | ||
| Line 52: | Line 48: | ||
\sum_k b_{ik} f(k) | \sum_k b_{ik} f(k) | ||
</math> | </math> | ||
is equal to your starting fortune <math>f(i)</math>. In other words, a fair game on a | |||
finite state space remains fair to the end. (Fair games in general are called | is equal to your starting fortune <math>f(i)</math>. In other words, a fair game on a finite state space remains fair to the end. (Fair games in general are called ''martingales.'' Fair games on infinite state spaces need not remain fair with an unlimited number of plays allowed. For example, consider | ||
''martingales.'' Fair games on infinite state spaces need | the game of Heads or Tails (see [[guide:4f3a4e96c3#exam 1.3 |Example]]). Let Peter start with 1 penny and play until he has 2. Then Peter will be sure to end up 1 penny ahead.) | ||
not | |||
remain fair with an unlimited number of plays allowed. For example, consider | |||
the game of | |||
Heads or Tails (see [[guide:4f3a4e96c3#exam 1.3 |Example]]). Let Peter start with 1 penny and | |||
play until he has 2. Then Peter will be sure to end up 1 penny ahead.) | |||
</li> | </li> | ||
</ul> | </ul> | ||
Latest revision as of 00:32, 16 June 2024
[math]
\newcommand{\NA}{{\rm NA}}
\newcommand{\mat}[1]{{\bf#1}}
\newcommand{\exref}[1]{\ref{##1}}
\newcommand{\secstoprocess}{\all}
\newcommand{\NA}{{\rm NA}}
\newcommand{\mathds}{\mathbb}[/math]
Consider an absorbing Markov chain with state space [math]S[/math]. Let [math]f[/math] be a function defined on [math]S[/math] with the property that
[[math]]
f(i) = \sum_{j \in S} p_{ij} f(j)\ ,
[[/math]]
or in vector form
[[math]]
\mat{f} = \mat{Pf}\ .
[[/math]]
Then [math]f[/math] is called a harmonic function for [math]\mat{P}[/math]. If you imagine a game in which your fortune is [math]f(i)[/math] when you are in state [math]i[/math], then the harmonic condition means that the game is fair in the sense that your expected fortune after one step is the same as it was before the step.
- Show that for [math]f[/math] harmonic
[[math]] \mat{f} = \mat{P}^n{\mat{f}} [[/math]]for all [math]n[/math].
- Show, using (a), that for [math]f[/math] harmonic
[[math]] \mat{f} = \mat{P}^\infty \mat{f}\ , [[/math]]where[[math]] \mat{P}^\infty = \lim_{n \to \infty} \mat{P}^n = \pmatrix{ \begin{array}{l|r} \mat{0} & \mat{B} \\ \hline \mat{0} & \mat{I} \\ \end{array} \cr}\ . [[/math]]
- Using (b), prove that when you start in a transient state [math]i[/math] your
expected final fortune
[[math]] \sum_k b_{ik} f(k) [[/math]]is equal to your starting fortune [math]f(i)[/math]. In other words, a fair game on a finite state space remains fair to the end. (Fair games in general are called martingales. Fair games on infinite state spaces need not remain fair with an unlimited number of plays allowed. For example, consider the game of Heads or Tails (see Example). Let Peter start with 1 penny and play until he has 2. Then Peter will be sure to end up 1 penny ahead.)