두브 마르팅게일

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2021년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수학 확률 이론의 두브 마팅게일(Joseph L. Dob,^[1] 일명 레비 마팅게일의 이름)은 주어진 랜덤 변수에 근사하며 주어진 여과와 관련하여 마팅게일 속성을 갖는 확률적 과정의 구성이다.특정 시간까지 축적된 정보를 바탕으로 무작위 변수에 대한 최선의 근사치의 진화하는 순서라고 생각할 수 있다.

독립 랜덤 변수의 합계, 랜덤 워크 또는 기타 첨가 함수를 분석할 때 중심 한계 정리, 대수의 법칙, 체르노프의 불평등, 체비셰프의 불평등이나 이와 유사한 도구를 적용할 수 있는 경우가 많다.차이가 독립적이지 않은 유사한 물체를 분석할 때 주된 도구는 마팅게일과 아즈마의 불평등이다.^{[clarification needed]}

정의

Let ${\displaystyle Y}$ be any random variable with ${\displaystyle \mathbb {E} [ Y ]<\infty }$. Suppose ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\dots \right\}}$ is a filtration, i.e.${\displaystyle {\mathcal{F}}_{}}$ ${\displaystyle s_{}}$ ${\displaystyle {}_{}}$ F ${\displaystyle t_{}}$ ${\$. s < $>$ {\$displaystyle s<t}$ 정의

${\displaystyle Z_{t}=\mathb {E} [Y\mid {\mathcal {F}_{t}],}$

then ${\displaystyle \left\{Z_{0},Z_{1},\dots \right\}}$ is a martingale,^[2] namely Doob martingale, with respect to filtration ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\dots \right\}}$.

이를 보려면 다음을 참고하십시오.

• ${\displaystyle \mathbb {E} [ Z_{t} ]=\mathbb {E} [ \mathbb {E} [Y\mid {\mathcal {F}}_{t}] ]\leq \mathbb {E} [\mathbb {E} [ Y \mid {\mathcal {F}}_{t}]]=\mathbb {E} [ Y ]<\infty }$;
• ${\displaystyle \mathbb {E} [Z_{t}\mid {\mathcal {F}}_{t-1}]=\mathbb {E} [\mathbb {E} [Y\mid {\mathcal {F}}_{t}]\mid {\mathcal {F}}_{t-1}]=\mathbb {E} [Y\mid {\mathcal {F}}_{t-1}]=Z_{t-1}}$ as ${\displaystyle {\mathcal{F}}_{t-1}\subset }$${\displaystyle {\mathcal{F}}_{}}$ ${\displaystyle t_{}}$ ${\$

In particular, for any sequence of random variables ${\displaystyle \left\{X_{1},X_{2},\dots ,X_{n}\right\}}$ on probability space ${\displaystyle (\Omega ,{\mathcal {F}},{\text{P}})}$ and function ${\displaystyle f}$ such that ) 【 [ $【\displaystyle \mathb$ {$E}】$ [$f(X_{1},X_{2},\dots,X_{n}, 】<\inflty$$},$ 선택할 수 있다.

${\displaystyle Y:=f(X_{1},X_{2},\dots,X_{n}}}}$

그리고$$ 여과$\{{\displaystyle F{\mathcal{}}_{}}$ ${\displaystyle 0_{\mathrm{}}}$ F ${\displaystyle 1_{\mathrm{}}}$,${\displaystyle \dots \}}$ ${\$

${\displaystyle {\begin{aligned}{\mathcal {F}}_{0}&:=\left\{\phi ,\Omega \right\},\\{\mathcal {F}}_{t}&:=\sigma (X_{1},X_{2},\dots ,X_{t}),\forall t\geq 1,\end{aligned}}}$

예: ${\displaystyle \sigma }$ -algebra가$$ ${\displaystyle {X\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$,${\displaystyle {}_{}}$X ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ X ${\displaystyle t_{}}$ ${\$에 의해 생성됨$.$그런 다음 Dub martingale의 정의에 따라 프로세스${\displaystyle }${ ${\displaystyle Z{}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {Z\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$, ${\displaystyle ...\}}$ ${\$Z_${1},\dots \$right\}}을$$(를) 사용하십시오.

${\displaystyle {\begin{aligned}Z_{0}&:=\mathbb {E} [f(X_{1},X_{2},\dots ,X_{n})\mid {\mathcal {F}}_{0}]=\mathbb {E} [f(X_{1},X_{2},\dots ,X_{n})],\\Z_{t}&:=\mathbb {E} [f(X_{1},X_{2},\dots ,X_{n})\mid {\mathcal {F}}_{t}]=\mathbb {E} [f(X_{1},X_{2},\dots ,X_{n})\mid X_{1},X_{2},\dots ,X_{t}],\forall t\geq 1\end{aligned}}}$

두브 마팅게일을 만들다$Z{\displaystyle {}_{}}$ ${\displaystyle n_{}}$= ${\displaystyle f}$( X ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$X ${\displaystyle {}_{}{}_{}}$,${\displaystyle }$… ,${\displaystyle X_{}}$n ) ${\displaystyle Z_{n}=f(X_{1},X_{2},\dots ,X_{n$이 마팅게일은 맥디아미드의 불평등을 증명하는 데 사용될 수 있다.

맥디아미드의 부등식

성명서^[1]

Consider independent random variables ${\displaystyle X_{1},X_{2},\dots X_{n}}$ on probability space ${\displaystyle (\Omega ,{\mathcal {F}},{\text{P}})}$ where ${\displaystyle X_{i}\in {\mathcal {X}}_{i}}$ for all ${\displaystyle i}$ and a mapping $$${\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }$. Assume there exist constant ${\displaystyle c_{1},c_{2},\dots ,c_{n}}$ such that for all ${\displaystyle i}$,

${\displaystyle {\underset {x_{1},\cdots ,x_{i-1},x_{i},x_{i}',x_{i+1},\cdots ,x_{n}}{\sup }} f(x_{1},\dots ,x_{i-1},x_{i},x_{i+1},\cdots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\cdots ,x_{n}) \leq c_{i}.}$

(즉, $i{\displaystyle }$ ${\displaystyle i}$의 값을 좌표 ${\displaystyle x_{}}$ $i{\displaystyle {}_{}}$ ${\$로 변경하면 $f{\displaystyle }$ ${\displaystyle f}$의 값이 최대 ${\displaystyle c_{}}$ i ${\$만큼$$ 변경됨$$)$$그런 다음, > ${\displaystyle \epsilon >0}$에 대해

${\displaystyle {\text{P}}(f(X_{1},X_{2},\cdots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\cdots ,X_{n})]\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}$

${\displaystyle {\text{P}}(f(X_{1},X_{2},\cdots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\cdots ,X_{n})]\leq -\epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}$

그리고

${\displaystyle {\text{P}}( f(X_{1},X_{2},\cdots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\cdots ,X_{n})] \geq \epsilon )\leq 2\exp \left(-{\frac {2\epsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}$

증명

Pick any ${\displaystyle x_{1}',x_{2}',\cdots ,x_{n}'}$ such that the value of ${\displaystyle f(x_{1}',x_{2}',\cdots ,x_{n}')}$ is bounded, then, for any ${\displaystyle x_{1},x_{2},\cdots ,x_{n}}$, by triangle inequa리트,

${\displaystyle{\begin{정렬}&, f(x_{1},x_{2},\cdots ,x_{n})-f(x_{1}',x_{2}',\cdots ,x_{n}')\\\leq&f(x_{1},x_{2},\cdots ,x_{n})-f(x_{1}',x_{2},\cdots ,x_{n})\\&, +\sum _{i=1}^{n-1}f(x_{1}',\cdots{나는}',x_{i+1},\cdots ,x_{n},x_)-f(x_{1}',x_{2}',\cdots{나는}',x_{i+1}',x_{i+2},\cdots ,x_{n},x_)\\\leq&\sum _{i=1}^{n}c_{나는},\end{aligne.d}}}$

$따라서{\displaystyle }$ f $[\displaystyle f}$이(가) 경계된다$$.

$Z{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle :=}$ E${\displaystyle }$[ ${\displaystyle f}$ (${\displaystyle }$X ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$X ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}\cdots }$, ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$) ${\displaystyle \mid }$ X ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}\cdots }$, ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ 정의. ${\displaystyle Z_{i}:$$=\mathbb {E} [f(X_{1},X_{2},\cdots ,X_{n})\mid X_{1},X_{2},\cdots ,X_{i}]}$ for all ${\displaystyle i\geq 1}$ and ${\displaystyle Z_{0}:=\mathbb {E} [f(X_{1},X_{2},\cdots ,X_{n})]}$. Note that ${\displaystyle Z_{n}=f(X_{1$$}},X_{2},\cdots,X_{n$ $f{\displaystyle }$ ${\displaystyle$ f$}$이(가) 경계되기$$ 때문에 Dub martingale의 정의에 따라 $Zi${\$displaystyle \{Z_}\i$}\right$\}}}}}}}$이 마팅게일을 형성한다$$.Now define ${\$U_{나는}&, ={\underset{x\in{{X\mathcal}}_{나는}}{\sup}};={\underset{x\in{{X\mathcal}}_{나는}}{\inf}}{E}는 경우에는 f(X_{1},\cdots ,X_{n})\mid X_{1}{E}[f(X_{1},\cdots ,X_{n})\mid X_{1},\cdots ,X_{i-1},x]-\mathbb \mathbb{E}[f(X_{1},\cdots ,X_{n})\mid X_{1},\cdots ,X_{i-1},x]-\mathbb{E}[f(X_{1},\cdots ,X_{n})\mid X_{1},\cdots ,X_{i-1}],\\L_{나는}& \mathbb.,\cdots$,X_{i-1}].$$\end{정렬}}}$

Note that ${\displaystyle L_{i}\leq Z_{i}-Z_{i-1}\leq U_{i}}$ and ${\displaystyle U_{i},L_{i}}$ are both ${\displaystyle {\mathcal {F}}_{i-1}}$-measurable.게다가.

${\displaystyle {\reasoned}U_{i}-L_{i}&={\underset {x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}{\sup }}\mathbb {E} [f(X_{1},\cdots ,X_{n})\mid X_{1},\cdots ,X_{i-1},x_{u}]-\mathbb {E} [f(X_{1},\cdots ,X_{n})\mid X_{1},\cdots ,X_{i-1},x_{l}]\\&={\underset {x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}{\sup }}\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}f(X_{1},\cdots ,X_{i-1},x_{u},x_{i+1},\cdots ,x_{n}){\text{d}}{\text{P}}_{X_{i+1},\cdots ,X_{n}\mid X_{1},\cdots ,X_{t-1},x_{u}}(x_{i+1},\cdots ,x_{n})\\&\quad -\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}f(X_{1},\cdots ,X_{i-1},x_{l},x_{i+1},\cdots ,x_{n}){\text{d}}{\text{P}}_{X_{i+1},\cdots,X_{n}\mid X_{1},\cdots,X_{t-1},x_{l}}(x_{i+1},\cdots,x_{n})\\&={\underset {x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}{\sup }}\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}f(X_{1},\cdots ,X_{i-1},x_{u},x_{i+1},\cdots ,x_{n}){\text{d}}{\text{P}}_{X_{i+1},\cdots ,X_{n}}(x_{i+1},\cdots ,x_{n})\\&\quad -\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}f(X_{1},\cdots ,X_{i-1},x_{l},x_{i+1},\cdots ,x_{n}){\text{d}}{\text{P}}_{X_{i+1},\cdots,X_{n}(x_{i+1},\cdots,x_{n})\\&={\underset {x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}{\sup }}\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}f(X_{1},\cdots ,X_{i-1},x_{u},x_{i+1},\cdots ,x_{n})\\&\quad -f(X_{1},\cdots ,X_{i-1},x_{l},x_{i+1},\cdots ,x_{n})\ {\text{d}}{\text{P}}_{X_{i+1},\cdots ,X_{n}}(x_{i+1},\cdots ,x_{n})\\&\leq {\underset {x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}{\sup }}\int _{{\mathcal {X}}_{i+1}\times \cdots \times {\mathcal {X}}_{n}}c_{i}\ {\text{d}}{\text{P}_{X_{i+1},\cdots,X_{n}(x_{i+1},\cdots,x_{n}}\&\leq c_{i}\end{aigned}}}}}}}}}}}$

$여기$서 세 번째${\displaystyle {}_{}{평등}_{}}$은 X 1, X ${\displaystyle {}_{}}$,${\displaystyle \{,}$ ${\displaystyle X_{}}$ n$${\$displaystyle X_{1},X_{2},\cdots,X_{n}}$의 독립성 때문에 이루어진다$.$ 그런 다음, 아즈마의 불평등의 일반적 형식을${\displaystyle }${ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$}\$ri$}오른쪽$\}}}}$에 적용한다$.$

${\displaystyle {\text{P}}(f(X_{1},\cdots ,X_{n})-\mathbb {E} [f(X_{1},\cdots ,X_{n})]\geq \epsilon )={\text{P}}(Z_{n}-Z_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}$

아즈마의 불평등을 { -${\displaystyle Z_{}}$ ${\displaystyle {}_{}}$ ${\$에 적용하여 다른 방향에서 한쪽으로 치우친 바운드를 얻으며$$, 조합 바운드에서 양쪽으로 치우친 바운드를 따른다.${\displaystyle \square }$

참고 항목

참조