Sheet 10

Exercise 1.

Show that the set of all finitely generated cylinder sets form a semiring $𝒬$.

Hint.

First draw some pictures and then try to formalize your findings using projections.

Solution.

1. $\mathrm{\varnothing }\in 𝒬$ because $\mathrm{\varnothing }={\pi }_{\{t_1\}}^{-1}(\mathrm{\varnothing })$

2. Stability under intersections

   Let $A,B\in 𝒬$ with $J_A=\{t_1,\mathrm{\dots },t_{n_A}\}$ and $J_B$ index sets and

   $A={\pi }_{J_A}^{-1}(A_{t_1}\times \mathrm{\cdots }\times A_{t_{n_A}})\mathit{\hspace{1em}\hspace{1em}}B={\pi }_{J_B}^{-1}(B_{t_1}\times \mathrm{\cdots }\times B_{t_{n_B}}).$

   Without loss of generality we can assume $J_A=J_B$. If not consider $J=J_A\cup J_B$ with $A_t=E$ for all $t\in J_B\setminus J_A$ and similarly for $B_t$. Then

   $A=\{f:I\to E|\forall t\in J:f(t)\in A_t\}=\{f:I\to E|\forall t\in J_A:f(t)\in A_t\}$

   since $f(t)\in E$ is always a given for all $t\in J\setminus J_A$. Okay so now we can assume $J_A=J_B=J$ and write $A_i=A_{t_i}$. Then simply considering the definition of the pre-image it is easy to check that

   $A\cap B$ $={\pi }_J^{-1}(A_1\times \mathrm{\cdots }\times A_n)\cap {\pi }_J^{-1}(B_1\times \mathrm{\cdots }\times B_n)$

   $={\pi }_J^{-1}(A_1\cap B_1\times \mathrm{\cdots }\times A_n\cap B_n).$

   Notice how $A_1\cap B_1$ is the intersection in one dimension. Just like in the simple two dimensional case, where we simply intersect every dimension individually (cf. picture).

3. $\forall A,B\in 𝒬$ there exist disjoint $C_1,\mathrm{\dots }{C}_n\in 𝒬$ such that $A\setminus B=\underset{k=1}{\overset{n}{\uplus }}{C}_k$.

   Assume the same $A,B$ as in the previous step. Because $A\setminus B=A\cap B^c$ we only need to prove that $B^c=\underset{k=1}{\overset{n}{\uplus }}{C}_k$ for $C_k\in 𝒬$ as we can then use $A\cap C_k\in 𝒬$. But

   $B^c$ $={\{f\in E^I|\forall t\in J_B:f(t)\in B_t\}}^c=\{f\in E^I|\exists t\in J_B:f(t)\notin B_t\}$

   $={\displaystyle \bigcup _{t\in J_B}}\{f\in E^I|\forall s\in \{t\}:f(t)\in B_t^c\}$

   unfortunately this is not yet a disjoint union. So we need to work a little harder. Sorting the $t_1,\mathrm{\dots },t_n\in J_B$, we can do

   $B^c$ $={\displaystyle \underset{i=1}{\overset{n}{\uplus }}}\{f\in E^I|\underset{\text{if not, then already in previous set}}{\underbrace{\forall s\in \{t_1,\mathrm{\dots },t_{i-1}\}:f(s)\in B_s}},f(t_i)\in B_{t_i}^c\}$

   $={\displaystyle \underset{i=1}{\overset{n}{\uplus }}}{\pi }_{\{t_1,\mathrm{\dots },t_i\}}^{-1}(B_{t_1}\times \mathrm{\cdots }\times B_{t_{i-1}}\times B_{t_i}^c)\mathit{∎}$

Exercise 2 (Multivariate Central Limit Theorem).

Let $X_1,X_2,\mathrm{\dots }$ be iid random vectors with $\mu =𝔼[X_1]$, $\mathrm{\Sigma }=\text{Cov}(X_1)$. Then prove that

$M_n:={\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \sum _{k=1}^n}(X_k-\mu )\to 𝒩(0,\mathrm{\Sigma })\mathit{\hspace{1em}}(n\to \mathrm{\infty })$

Hint.

Consider $\mathrm{⟨}{M}_n\mathrm{,}t\mathrm{⟩}$.

Solution.

We have that $⟨X_i,t⟩$ are iid distributed with

$𝔼[⟨X_1,t⟩]=⟨\mu ,t⟩\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}\text{Var}(⟨X_1,t⟩)=𝔼[{⟨X_1-\mu ,t⟩}^2]=t^T\mathrm{\Sigma }t$

So by the univariate central limit theorem we have

${\displaystyle \frac{1}{\sqrt{n⟨t,\mathrm{\Sigma }t⟩}}}{\displaystyle \sum _{k=1}^n}(⟨X_k,t⟩-⟨\mu ,t⟩)\to 𝒩(0,1),$

and with the Continuous Mapping Theorem

$⟨M_n,t⟩=⟨{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \sum _{k=1}^n}{X}_k-\mu ,t⟩={\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \sum _{k=1}^n}⟨X_k-\mu ,t⟩\to 𝒩(0,⟨t,\mathrm{\Sigma }t⟩).$

So looking at the characteristic function of $M_n$ we have

${\phi }_{M_n}(t)=𝔼[e^{i⟨M_n,t⟩}]\to e^{-\frac{1}{2}⟨t,\mathrm{\Sigma }t⟩}={\phi }_{𝒩(0,\mathrm{\Sigma })}(t).$

And therefore have proven the CLT by Lévy’s continuity theorem. ∎

Exercise 3 (Markov Chain Existence).

Let $p(x,y)=\kappa (x,\{y\})$ be a discrete probability kernel on ${ℝ}^d$, $p_0$ a discrete probability distribution. Prove that there exists a stochastic process $X_n$, such that

1. $\mathbb{P}(X_n=y|X_{n-1}=x)=p(x,y)$ and $\mathbb{P}(X_0=x)=p_0(x)$

2. $X_n$ is a Markov Chain, i.e.

   $\mathbb{P}(X_{n+1}=x_{n+1}|X_n=x_n,\mathrm{\dots },X_0=x_0)=\mathbb{P}(X_{n+1}=x_{n+1}|X_n=x_n).$

Hint.

Consider

${\mathbb{P}}_{X_0,\mathrm{\dots },X_{n+1}}(A_0,\mathrm{\dots },A_{n+1}):={\displaystyle \sum _{x_0\in A_0}}\mathrm{\dots }{\displaystyle \sum _{x_n\in A_n}}\kappa (x_n,A_{n+1})p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0).$

and prove that ${\mathbb{P}}_{X_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_{n\mathrm{+}\mathrm{1}}}\mathit{}\mathrm{(}{A}_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{A}_n\mathrm{,}{ℝ}^d\mathrm{)}\mathrm{=}{\mathbb{P}}_{X_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_n}\mathit{}\mathrm{(}{A}_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{A}_n\mathrm{)}$. Then construct a consistent family of distributions.

Solution.

We want to define a set of consistent probability measures and then apply Kolmogorov’s extension theorem. We define

${\mathbb{P}}_{\{0,\mathrm{\dots },n+1\}}(A_0\times \mathrm{\cdots }\times A_{n+1}):={\displaystyle \sum _{x_0\in A_0}}\mathrm{\dots }{\displaystyle \sum _{x_n\in A_n}}\kappa (x_n,A_{n+1})p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0).$

and for any $J=\{k_1,\mathrm{\dots },k_n\}$ where w.l.o.g. $k_1\le \mathrm{\cdots }\le k_n$, we define

${\mathbb{P}}_J(A_{k_1}\times \mathrm{\cdots }\times A_{k_n}):={\mathbb{P}}_{\{1,\mathrm{\dots },k_n\}}({ℝ}^d\times \mathrm{\cdots }\times {ℝ}^d\times A_{k_1}\times \mathrm{\dots }).$

To prove this family is consistent, as we are infilling anyway, we only need to prove that we can chop of things at the end, i.e.

${\mathbb{P}}_{\{0,\mathrm{\dots },n+1\}}(A_0\times \mathrm{\cdots }\times A_n\times {ℝ}^d)={\mathbb{P}}_{\{0,\mathrm{\dots },n\}}(A_0\times \mathrm{\cdots }\times A_n).$

But this is true because by definition

${\mathbb{P}}_{\{0,\mathrm{\dots },n+1\}}(A_0\times \mathrm{\cdots }\times A_n\times {ℝ}^d)$ $:={\displaystyle \sum _{x_0\in A_0}}\mathrm{\dots }\underset{=\kappa (x_{n-1},A_n)}{\underbrace{{\displaystyle \sum _{x_n\in A_n}}\underset{=1}{\underbrace{\kappa (x_n,{ℝ}^d)}}p(x_{n-1},x_n)}}\mathrm{\dots }p(x_0,x_1)p_0(x_0)$

$={\mathbb{P}}_{\{0,\mathrm{\dots },n\}}(A_0\times \mathrm{\cdots }\times A_n).$

Note that we did not really use the discreteness of our kernel so far. To show the markov property we are going to exchange summation which would be a bit more difficult in the case of measures.

$\mathbb{P}(X_{n+1}=x_{n+1}|X_n=x_n,\mathrm{\dots },X_0=x_0)$

$={\displaystyle \frac{\mathbb{P}(X_{n+1}=x_{n+1},X_n=x_n,\mathrm{\dots },X_0=x_0)}{\mathbb{P}(X_n=x_n,\mathrm{\dots },X_0=x_0)}}$

$={\displaystyle \frac{{\sum }_{x_0\in \{x_0\}}\mathrm{\dots }{\sum }_{x_n\in \{x_n\}}p(x_n,x_{n+1})p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}{{\sum }_{x_0\in \{x_0\}}\mathrm{\dots }{\sum }_{x_{n-1}\in \{x_{n-1}\}}p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}}$

$={\displaystyle \frac{p(x_n,x_{n+1}){\sum }_{x_0\in \{x_0\}}\mathrm{\dots }{\sum }_{x_{n-1}\in \{x_{n-1}\}}p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}{{\sum }_{x_0\in \{x_0\}}\mathrm{\dots }{\sum }_{x_{n-1}\in \{x_{n-1}\}}p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}}$

$=p(x_n,x_{n+1})$

$={\displaystyle \frac{p(x_n,x_{n+1}){\sum }_{x_0\in {ℝ}^d}\mathrm{\dots }{\sum }_{x_{n-1}\in {ℝ}^d}p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}{{\sum }_{x_0\in {ℝ}^d}\mathrm{\dots }{\sum }_{x_{n-1}\in {ℝ}^d}p(x_{n-1},x_n)\mathrm{\dots }p(x_0,x_1)p_0(x_0)}}$

$={\displaystyle \frac{\mathbb{P}(X_{n+1}=x_{n+1},X_n=x_n,X_{n-1}\in {ℝ}^d\mathrm{\dots },X_0\in {ℝ}^d)}{\mathbb{P}(X_n=x_n,X_{n-1}\in {ℝ}^d\mathrm{\dots },X_0\in {ℝ}^d)}}$

$=\mathbb{P}(X_{n+1}=x_{n+1}|X_n=x_n).\mathit{∎}$

Exercise 4 (Positive semi-definite Functions).

Prove the following statements

1. Let $\phi :[0,\mathrm{\infty })\to ℝ$ be a continuous convex function with ${lim}_{x\to \mathrm{\infty }}\phi (x)=0$. Then $k(s,t)=\phi (|t-s|)$ is positive semi-definite for all $s,t\in ℝ$.

   Hint.

   Pòlya’s Theorem.

   Solution.

   $x\mapsto \phi (|x|)$ fulfills all the requirements of Pòlya’s theorem. It is therefore a characteristic function and by Bochner’s theorem positive semi-definite. ∎

2. $k(s,t)=e^{-|t-s|}$ is positive semi-definite for all $s,t\in ℝ$.

   Solution.

   Since $e^{-x}$ is continuous, convex and ${lim}_{x\to \mathrm{\infty }}{e}^{-x}=0$ it fulfills all the requirements of (i) which implies the claim. ∎

Another trick to check positive semi-definiteness is based around scalar products in an arbitrary hilbertspace.

Remark.

This is closely related to “kernels” from support vector machines, where you want to separate data with a “hyper-surface”. For the surface to be not necessarily a hyperplane, you first map the data to some hilbertspace and look for a separating hyperplane in that space instead – recall that a hyperplane can be parametrized as $\mathrm{\{}x\mathrm{\in }H\mathrm{:}\mathrm{⟨}x\mathrm{,}a\mathrm{⟩}\mathrm{=}c\mathrm{\}}$, where $a$ is the normal vector.

1. Let $H$ be a complex hilbertspace, $\varphi :M\to H$ any function. Then $k(x,y)=⟨\varphi (x),\varphi (y)⟩$ is positive semi-definite for all $x,y\in M$.

   Solution.

   Let $x_1,\mathrm{\dots },x_n\in M$ and $a_1,\mathrm{\dots },a_n\in ℂ$. Then

   ${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=1}^n}{a}_i\overline{a_j}k(x_i,x_j)$ $={\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=1}^n}{a}_i\overline{a_j}⟨\varphi (x_i),\varphi (x_j)⟩=⟨{\displaystyle \sum _{i=1}^n}{a}_i\varphi (x_i),{\displaystyle \sum _{j=1}^n}{a}_j\varphi (x_j)⟩\ge 0,$

   by bilinearity of the scalar product of the hilbertspace. ∎

2. $k(s,t)=e^{i(s-t)}$ is positive semi-definite for all $s,t\in ℝ$.

   Solution.

   Defining $\varphi (s):=e^{is}\in ℂ$ and using the complex scalar product results in the claim by (iii), since

   $k(s,t)$ $=⟨\varphi (s),\varphi (t)⟩=e^{is}\overline{e^{it}}=e^{is}{e}^{-it}=e^{i(s-t)}.\mathit{∎}$

3. $k(s,t)=\cos (s-t)$ is positive semi-definite for all $s,t\in ℝ$.

   Solution.

   Using

   $\varphi (s):={\displaystyle \frac{1}{\sqrt{2}}}\left(\begin{array}{c}\hfill e^{is}\hfill \\ \hfill e^{-is}\hfill \end{array}\right)\in {ℂ}^2$

   with the complex scalar product, we get the claim with (iii) and

   $k(s,t)$ $={\displaystyle \frac{1}{2}}⟨\left(\begin{array}{c}\hfill e^{is}\hfill \\ \hfill e^{-is}\hfill \end{array}\right),\left(\begin{array}{c}\hfill e^{it}\hfill \\ \hfill e^{-it}\hfill \end{array}\right)⟩={\displaystyle \frac{1}{2}}(e^{i(s-t)}+\underset{=\overline{e^{i(s-t)}}}{\underbrace{e^{i(t-s)}}})$

   $={\displaystyle \frac{\cos (s-t)+i\sin (s-t)+\cos (s-t)-i\sin (s-t)}{2}}$

   $=\cos (s-t).\mathit{∎}$

And sometimes you just have to apply the definition manually.

1. $k(s,t)=\min \{s,t\}$ is positive semi-definite for $s,t\in [0,\mathrm{\infty })$.

   Hint.

   Sort the $t_i$ and start induction with $n\mathrm{=}\mathrm{2}$.

   Solution.

   Assuming $0\le t_1\le \mathrm{\cdots }\le t_n$ with $a_i\in ℝ$, then by induction over $n$ with induction start $n=2$ given by

   ${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=1}^n}{a}_i{a}_j\min \{t_i,t_j\}=a_1^2{t}_1+2a_1{a}_2{t}_1+a_2^2\underset{\ge t_1}{\underbrace{t_2}}\ge \underset{={(a_1+a_2)}^2}{\underbrace{(a_1^2+2a_1{a}_2+a_2^2)}}{t}_1\ge 0,$

   we can prove positive semi-definiteness with the induction step

   ${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=1}^n}{a}_i{a}_j\min \{t_i,t_j\}$ $={\displaystyle \sum _{i=1}^n}{a}_i\left(a_i{t}_i+2{\displaystyle \sum _{j=i+1}^n}{a}_j\min \{t_i,t_j\}\right)$

   $={\displaystyle \sum _{i=1}^n}{a}_i\left(a_i+2{\displaystyle \sum _{j=i+1}^n}{a}_j\right)t_i$

   $=a_n^2\underset{\ge t_{n-1}}{\underbrace{t_n}}+a_{n-1}(a_{n-1}+2a_n)t_{n-1}+{\displaystyle \sum _{i=1}^{n-2}}{a}_i\left(a_i+2{\displaystyle \sum _{j=i+1}^n}{a}_j\right)t_i$

   $\ge (a_n^2+2a_n{a}_{n-1}+a_{n-1}^2)t_{n-1}+{\displaystyle \sum _{i=1}^{n-2}}{a}_i\left(a_i+2{\displaystyle \sum _{j=i+1}^n}{a}_j\right)t_i$

   $\ge {(\underset{=:{\tilde{a}}_{n-1}}{\underbrace{a_n+a_{n-1}}})}^2{t}_{n-1}+{\displaystyle \sum _{i=1}^{n-2}}{a}_i\left(a_i+2{\displaystyle \sum _{j=i+1}^n}{a}_j\right)t_i$

   $={\displaystyle \sum _{i=1}^{n-1}}{\tilde{a}}_i\left({\tilde{a}}_i+2{\displaystyle \sum _{j=i+1}^{n-1}}{\tilde{a}}_j\right)t_i$

   $\ge 0\mathit{\hspace{1em}}\text{(by induction)}$

   using ${\tilde{a}}_i=a_i$ for all . ∎