장 42 정지된 마팅게일 (작성 예정)

42.1 거의 확실하게 돈을 버는 방법

이제 측도론에 대해 새로 얻은 지식을 카지노로 가져가 봅시다.

여기 가장 고전적인 예시가 있습니다: 카지노에서 공정한 동전 던지기에 원하는 만큼 베팅할 수 있는 게임을 하게 해주는데, 승률이 나쁩니다: 동전이 앞면이면 $\$n$ 을 따지만, 뒷면이면 $\$2n$ 을 잃습니다. 여기서 $n$ 의 값은 우리가 선택합니다. 제정신인 사람이라면 아무도 하고 싶어하지 않을 것 같은 게임처럼 보입니다.

그런데, 시간과 돈이 무제한이라면, 실제로 거의 확실하게 이익을 낼 수 있습니다.

예제 42.1.1 (18세기 프랑스보다도 더 탐욕스러워지기).

위 게임에서, 우리는 $\$1$ 을 베팅하며 시작합니다.

•

이기면, $\$1$ 을 벌고 떠납니다.
•
지면, 대신 $\$10$ 을 베팅하고,
- –
  
  이기면, $\$10-\$2=\$8$ 을 벌고 떠나며,
- –
  지면 대신 $\$100$ 을 베팅하고,
  - *
    
    이기면, $\$1000-\$20-\$2=\$978$ 을 벌고 떠나며,
  - *
    
    지면 대신 $\$1000$ 을 베팅하고, 이런 식으로 계속됩니다…

동전은 언젠가 거의 확실하게 앞면이 나올 것이므로, 그 일이 일어날 때마다 돈을 법니다. 사실, 동전이 앞면을 보일 때까지 걸리는 기대 시간은 단 $2$ 번의 던지기입니다! 무엇이 잘못될 수 있을까요?

이 장에서는 “유한한 시간”이나 “유한한 돈”과 같은 정상적인 조건 하에서는, 실제로 이런 방식으로 돈을 벌 수 없다는 것을 보일 것입니다 — 바로 선택적 정지 정리입니다. 이는 조건부 확률을 정의할 구실을 마련해 주며, 그 다음 마팅게일(공정한 카지노를 일반화한 것)에 대해 이야기하게 될 것입니다.

라스베이거스에서 돈을 뽑아내려는 시도가 가망 없는 일임을 깨닫고 나면, 우리는 도박을 그만두고 수학 문제 풀이로 돌아가서, 도박과는 전혀 관계없어 보이는 문제들이 적절한 마팅게일을 고려함으로써 풀릴 수 있는 몇 가지 까다로운 놀라움들을 보여줄 것입니다.

이후 모든 내용에서, $\Omega=(\Omega,\mathscr{A},\mu)$ 는 확률 공간입니다.

42.2 부분 $\sigma$ -대수와 여과

대표적인 예: 확률 변수로 생성된 $\sigma$ -대수, 그리고 동전 던지기 여과

우리는 $\Omega$ 를, $\Omega$ 위에서 적분을 할 수 있게 해주는 $\sigma$ -대수 $\mathscr{A}$ 를 갖춘 세계들의 공간으로 생각했습니다. 그러나 슬픈 삶의 진실은, 어느 주어진 시점에서든 세계에 대해 부분적인 정보만을 알 수 있다는 것입니다. 예를 들어, 이 글을 쓰는 시점에서, 우리는 세계가 2012년에 끝나지 않았다는 것을 알고 있지만 (https://en.wikipedia.org/wiki/2012_phenomenon 참조), 앞으로 인류의 운명은 다소 불확실한 채로 남아 있습니다.

이를 측도론적으로 써 봅시다: 다음을 고려할 수 있습니다

	$\displaystyle\Omega$	$\displaystyle=A\sqcup B$
	$\displaystyle A$	$\displaystyle=\left\{\omega\text{$2012$년에 세상이 끝나는 경우}\right\}$
	$\displaystyle B$	$\displaystyle=\left\{\omega\text{$2012$년에 세상이 끝나지 않는 경우}\right\}.$

$A$ 와 $B$ 가 가측 집합, 즉 $A,B\in\mathscr{A}$ 라고 가정하겠습니다. 이는 $\mu(A)$ 와 $\mu(B)$ 의 값이 어떠해야 하는지에 대해(”세상이 $2012$ 년에 끝날 사전 확률”) 재미있게 논쟁할 수 있다는 뜻이지만, 이제 다른 엉뚱한 예시로 넘어갑시다.

이제 나중에 조건부 확률을 정의할 때 필요할 새로운 개념을 소개하겠습니다.

정의 42.2.1.

$\Omega=(\Omega,\mathscr{A},\mu)$ 를 확률 공간이라 합시다. $\Omega$ 위의 부분 $\sigma$ -대수 $\mathscr{F}$ 는 말 그대로의 의미입니다: 집합 $\Omega$ 위의 $\sigma$ -대수 $\mathscr{F}$ 로서, 각 $A\in\mathscr{F}$ 가 가측이도록 하는 것입니다(즉, $\mathscr{F}\subseteq\mathscr{A}$ ).

그 동기는, $\mathscr{F}$ 가 어떤 정보에 대해 질문을 던질 수 있게 해주는 집합들의 $\sigma$ -대수라는 것입니다. 예를 들어, 위에서 든 2012년 예시에서, 우리는 $\mathscr{F}=\{\varnothing,A,B,\Omega\}$ 로 둘 수 있는데, 이는 2012년만을 생각하고 있을 때 우리가 관심을 갖는 집합들입니다.

여기 좀 더 진지한 예시들이 있습니다.

예제 42.2.2 (부분 $\sigma$ -대수의 예시).

(a)

$X\colon\Omega\to\{0,1,2\}$ 를 세 값 중 하나를 취하는 확률 변수라고 합시다. 만약 우리가 $X$ 에 관심이 있다면 다음과 같이 정의할 수 있습니다

$\displaystyle A$ $\displaystyle=\{\omega\mid X(\omega)=1\}$

$\displaystyle B$ $\displaystyle=\{\omega\mid X(\omega)=2\}$

$\displaystyle C$ $\displaystyle=\{\omega\mid X(\omega)=3\}$

그러면 다음과 같이 쓸 수 있습니다

$\mathscr{F}=\left\{\varnothing,\;A,\;B,\;C,\;A\cup B,\;B\cup C,\;C\cup A,\;% \Omega\right\}.$

이것은 예컨대 ” $X\neq 3$ 일 확률은 얼마인가”와 같이 $X$ 에 대한 질문을 할 수 있게 해주는 $\mathscr{F}$ 위의 부분 $\sigma$ -대수입니다.
(b)

이제 $Y\colon\Omega\to[0,1]$ 가 또 다른 확률 변수라고 합시다. 만약 우리가 $Y$ 에 관심이 있다면, 우리의 궁금증을 담아내는 $\mathscr{F}$ 는 다음과 같습니다

$\mathscr{F}=\left\{Y^{\text{pre}}(B)\mid B\subseteq[0,1]\text{가측입니다}\right\}.$

여기서 어떤 경향을 눈치챘을 수도 있는데, 이제 이를 형식화합니다.

정의 42.2.3.

$X\colon\Omega\to\mathbb{R}$ 를 확률 변수라고 합시다. $X$ 에 의해 생성된 부분 $\sigma$ -대수는 다음과 같이 정의됩니다

\sigma(X)\coloneqq\left\{X^{\text{pre}}(B)\mid B\subseteq\mathbb{R}\text{가측입니다% }\right\}.

만약 $X_{1}$ , … 가 확률 변수들의 (유한 또는 무한) 수열이라면, 이들에 의해 생성된 부분 $\sigma$ -대수는 각 $i$ 에 대해 $\sigma(X_{i})$ 를 포함하는 가장 작은 $\sigma$ -대수입니다.

마지막으로, 이런 것들을 많이 모아볼 수 있습니다 — 시간에 대해 이야기하고 있으므로, 우리는 나이가 들수록 더 많은 것을 알게 되고, 이는 형식화될 수 있습니다.

정의 42.2.4.

$\Omega=(\Omega,\mathscr{A},\mu)$ 위의 여과는 중첩된 수열¹¹1편의를 위해 $\mathbb{Z}_{\geq 0}$ 로 색인된 여과로 한정하지만, 사실 어떤 색인 집합이든 상관없습니다.

\mathscr{F}_{0}\subseteq\mathscr{F}_{1}\subseteq\mathscr{F}_{2}\subseteq\dots

$\Omega$ 위의 부분 $\sigma$ -대수들의

예제 42.2.5 (여과).

무한히 긴 수업 시간에 지루해서 시간을 보내려고 공정한 동전을 던지기 시작했다고 합시다. (이에 따라 $\Omega=\{H,T\}^{\infty}$ 가 앞면 $H$ 와 뒷면 $T$ 의 무한 수열들로 이루어진다고 할 수 있습니다.) $\mathscr{F}_{n}$ 이 처음 $n$ 번의 동전 던지기 값에 의해 생성된 부분 $\sigma$ -대수를 나타낸다고 합시다. 그러면:

•

$\mathscr{F}_{0}=\{\varnothing,\Omega\}$ ,
•

$\mathscr{F}_{1}=\{\varnothing,\text{첫 번째 던지기가 $H$},\text{첫 번째 던지기가 $T$},\Omega\}$ ,
•

$\mathscr{F}_{2}=\{\varnothing,\text{첫 두 번의 던지기가 $HH$},\text{두 번째 던지기가 $T$},% \Omega,\text{첫 번째 던지기와 두 번째 던지기가 다름},\dots\}$ .
•

이런 식으로 계속되며, $\mathscr{F}_{n}$ 은 오직 처음 $n$ 번의 동전 던지기에 의해서만 ”결정되는” 가측 집합들입니다.

연습문제 42.2.6.

앞의 예시에서, 각 정수 $n$ 에 대해 크기 $|\mathscr{F}_{n}|$ 를 계산하십시오.

더 중요한 것은,

$X$ 가 $\mathscr{F}$ 에 주어진 정보에 의해서만 결정된다면 $X$ 는 $\mathscr{F}$ -가측입니다.

예제 42.2.7.

위의 예시에서, $X_{3}$ 을 세 번째 동전 던지기의 값이라고 합시다. 그러면:

•

$X_{3}$ 은 $\mathscr{F}_{2}$ -가측이 아닙니다. (즉, $X_{3}$ 은 처음 $2$ 번의 동전 던지기 정보만으로는 알 수 없습니다.)
•

하지만 이것은 $\mathscr{F}_{3}$ -가측입니다.

연습문제 42.2.8.

이를 확인하십시오! (함수는 열린집합을 가측 집합으로 끌어올릴 때 가측이라는 것을 상기하십시오. 따라서 예를 들어 $X_{3}^{\text{pre}}(\{H\})\notin\mathscr{F}_{2}$ 임을 보여야 합니다.)

따라서, 우리는 세상에 대한 부분적인 정보를 형식화할 수 있을 뿐만 아니라, 무언가가 그 부분적인 정보에만 의존한다는 것이 무엇을 의미하는지도 형식화할 수 있습니다.

42.3 조건부 기댓값

대표적인 예: $[0,1]$ 위에 분포된 $X$ 와 $Y$ 에 대한 $\mathbb{E}(X\mid X+Y)$ 입니다.

마팅게일을 정의하기 위해서는 조건부 확률의 정의가 필요하지만, 이는 놀랍게도 까다로운 것으로 밝혀집니다. 그 이유를 살펴보기 위해 다음의 간단한 예시를 고려해 봅시다.

예제 42.3.1 (고등학교 수준의 방법이 여기서 충분하지 않은 이유).

$[0,1]$ 위에 균등하게 분포된 두 개의 독립적인 확률 변수 $X$ , $Y$ 가 있다고 합시다 (그러므로 $\Omega=[0,1]^{2}$ 로 두어도 무방합니다). 다음과 같은 질문을 던져 볼 수 있습니다:

“ $X+Y=0.6$ 이라는 조건 하에서 $X$ 의 기댓값은 무엇인가”?

직관적으로, 답이 $0.3$ 이 되어야 함을 알고 있습니다. 하지만 정의를 적어 보려고 하면 곧 문제에 부딪히게 됩니다. 이상적으로는 다음과 같은 형태로 말하고 싶습니다

\mathbb{E}[X\text{주어진}X+Y=0.6]=\frac{\int_{S}X}{\int_{S}1}\text{여기서}S=\left\{% \omega\in\Omega\mid X(\omega)+Y(\omega)=0.6\right\}.

문제는 $S$ 가 측도가 0인 집합이라는 것으로, 이로 인해 곧 $\frac{0}{0}$ 에 부딪히게 되며, 이는 이러한 형태의 정의가 통하지 않는다는 것을 의미합니다.

측도론에서 이를 다루는 전형적인 방법은 우리가 정의한 부분- $\sigma$ -대수의 개념을 이용하는 것입니다.

하지만 먼저, $\mathbb{E}(X\mid X+Y)$ 가 무엇을 의미하는지 설명해야 합니다 — 왜 사건이 아니라 다른 확률 변수에 대해 조건을 거는 것일까요?

확률 변수에 대해 조건을 거는 것의 동기를 설명하기 위해 다음의 상황을 고려해 봅시다. 내일의 날씨가 오늘의 날씨와 무작위적인 변동에 의존한다고 합시다. 그러면 다음과 같은 진술을 할 수 있습니다:

	$\displaystyle\Pr(\text{내일 비가 옴}\mid\text{오늘 비가 옴})$	$\displaystyle=0.6,$
	$\displaystyle\Pr(\text{내일 비가 옴}\mid\text{오늘 비가 오지 않음})$	$\displaystyle=0.3.$

이는 표준적인 조건부 확률입니다: $\Pr(A\mid B)=\frac{\Pr(A\wedge B)}{\Pr(B)}$ .

“오늘의 날씨” 자체가 확률 변수임에 유의하십시오.

$Z$ 를 오늘 밤 일기예보가 예측한 확률이라고 하고, 이것이 위와 같이 작동한다고 합시다. 그러면 $Z$ 는 다음과 같이 정의되는 확률 실숫값 변수입니다:

	$\displaystyle Z$	$\displaystyle\colon\Omega\to\mathbb{R}$
	$\displaystyle Z(\omega)$	$\displaystyle=\Pr(\text{내일 비가 옴}\mid\text{오늘의 날씨}=\text{오늘의 날씨}(\omega))$

다음과 같이 적는 것만이 타당할 것입니다

Z=\Pr(\text{내일 비가 옴}\mid\text{오늘의 날씨}).

우리는 확률 변수에 대해 조건을 걸고 있으며, $\Pr(\cdots\mid\cdots)$ 자체가 $\mathbb{R}$ 안의 단일 값이 아니라 확률 변수인데, 이는 전혀 문제가 없습니다.

마찬가지로, $\Omega$ 가 유한하고 그 모든 부분집합이 가측이라면, 확률 실숫값 변수 $X$ 와 $Y$ 에 대해 확률 실숫값 변수 $Z=\mathbb{E}(X\mid Y)$ 를 다음과 같이 정의하는 것이 합리적일 것입니다

	$\displaystyle Z$	$\displaystyle\colon\Omega\to\mathbb{R}$
	$\displaystyle Z(\omega)$	$\displaystyle=\mathbb{E}[X\mid Y=Y(\omega)].$

예제 42.3.2.

$X$ 와 $Y$ 를 두 주사위를 굴린 결과라고 합시다. 그러면:

•

$\mathbb{E}[X\mid X+Y=3]=1.5$ 이며, 이는 쉽게 계산할 수 있습니다.
•

$\mathbb{E}(X\mid X+Y)$ 는 확률 변수로서, $X+Y=3$ 이든 아니든 모든 세계에서 값 $1.5$ 를 취할 것입니다.
•

더 일반적으로, 실제로 다음이 성립합니다

$\mathbb{E}(X\mid X+Y)=\frac{X+Y}{2}.$

확률 변수 $\mathbb{E}(X\mid X+Y)$ 가 오직 $X+Y$ 의 값에만 의존한다는 것에 주목하십시오 — 정의에 의해서 그러합니다.

물론, 앞서 설명했듯이, 이러한 소박한 시도는 연속적인 경우에 대해서는 어디서나 0으로 나누기를 야기합니다 — 그래서, 부분- $\sigma$ -대수가 등장하게 됩니다.

명제 42.3.3 (조건부 기댓값의 정의).

$X\colon\Omega\to\mathbb{R}$ 를 확률 공간 $\Omega$ 위의 절대 적분가능한 확률 변수 (즉 $\mathbb{E}[|X|]<\infty$ 를 의미합니다)라 하고, $\mathscr{F}$ 를 그 위의 부분- $\sigma$ -대수라 합시다.

그러면 다음 두 성질을 만족하는 함수 $\eta\colon\Omega\to\mathbb{R}$ 가 존재합니다:

•

$\eta$ 는 $\mathscr{F}$ -가측입니다 (즉, 함수 $(\Omega,\mathscr{F},\mu)\to\mathbb{R}$ 로서 가측입니다); 그리고
•

임의의 집합 $A\in\mathscr{F}$ 에 대해 $\mathbb{E}[\eta\cdot\mathbf{1}_{A}]=\mathbb{E}[X\cdot\mathbf{1}_{A}]$ 가 성립합니다.

더욱이, 이 확률 변수는 거의 확실하게(almost surely) 유일합니다.

증명.

생략하지만, 관련된 전문 용어로 “라돈-니코딤 도함수(Radon-Nikodym derivative)”가 사용됩니다. ∎

정의 42.3.4.

$\eta$ 를 앞의 명제에서와 같이 놓읍시다.

•

우리는 $\eta$ 를 $\mathbb{E}(X\mid\mathscr{F})$ 로 표기하고, 이를 $\mathscr{F}$ 에 대한 $X$ 의 조건부 기댓값(conditional expectation)이라 부릅니다.
•

$Y$ 가 확률 변수라면, $\mathbb{E}(X\mid Y)$ 는 $\mathbb{E}(X\mid\sigma(Y))$ 를 나타내며, 즉 $Y$ 에 의해 생성된 $\sigma$ -대수에 대한 $X$ 의 조건부 기댓값을 의미합니다.

예제 42.3.5.

예상할 수 있듯이, $\eta=\frac{X+Y}{2}$ 는 위의 $\mathbb{E}(X\mid X+Y)$ 의 조건을 만족합니다.

이 모든 것을 하는 동기를 부여하는 방법은 다음과 같습니다. 우리는 다음과 같은 것을 말할 수 있기를 원합니다:

\mathbb{E}[X\mid X+Y=0.6]=\lim_{\varepsilon\to 0}\mathbb{E}[X\mid 0.6-% \varepsilon<X+Y<0.6+\varepsilon]

안타깝게도, $\mathscr{F}$ 가 단 하나의 확률 실수 변수에 의해 생성되지 않을 수도 있는 일반적인 경우에는 이러한 설정이 작동하지 않습니다. 위의 정의가 우리에게 어떻게 도움이 되는지 살펴봅시다.

•

$A=\{\omega\in\Omega\mid 0.6-\varepsilon<X(\omega)+Y(\omega)<0.6+\varepsilon\}$ 라 하면, 이 집합은 확실히 $X+Y$ 에 의해 생성된 부분- $\sigma$ -대수에 속합니다 (왜냐하면 이는 $(X+Y)^{\text{pre}}((0.6-\varepsilon,0.6+\varepsilon))$ 이기 때문입니다).
•

$\eta$ 가 $\mathscr{F}$ -가측이라는 것은 $\eta$ 가 $\mathscr{F}=\sigma(X+Y)$ 에 있는 정보에만, 즉 $X+Y$ 에만 의존한다는 것을 의미함을 상기하십시오. 이는 이치에 맞습니다.
•

우변을 살펴봅시다:

$\mathbb{E}[X\mid 0.6-\varepsilon<X+Y<0.6+\varepsilon]=\mathbb{E}[X\cdot\mathbf% {1}_{A}].$

전체 기댓값의 법칙(law of total expectation)은 $\mathbb{E}[\mathbb{E}(X\mid Y)]=\mathbb{E}[X]$ 라고 말합니다. 따라서 직관적으로, 위의 두 번째 성질은 단순히 이 법칙이 모든 집합 $A\in\mathscr{F}$ 에 대해 성립할 것을 요구합니다.

우리의 경우, 다음과 같습니다:

$\mathbb{E}[\eta\mid 0.6-\varepsilon<X+Y<0.6+\varepsilon]=\mathbb{E}[X\mid 0.6-% \varepsilon<X+Y<0.6+\varepsilon].$

좀 더 자세한 설명:

비고 42.3.6 (이 표기법은 형편없습니다).

$\mathbb{E}(X\mid\mathscr{F})$ 라는 표기법은 인정하건대 혼란스러운데, 이는 실제로 $\mathbb{E}[X]$ 와 같은 단순한 실수가 아니라 함수 전체 $\Omega\to\mathbb{R}$ 이기 때문입니다 — 그러나 보시다시피, 나름의 장점이 있습니다. 이러한 이유로 저는 조건부 기댓값에 대해서는 대괄호가 아니라 소괄호를 사용하는 것을 잊지 않도록 조심하려 합니다; 모두가 이렇게 하는 것은 아닙니다.

표기의 남용 42.3.7.

또한, $Y=\mathbb{E}(X\mid\mathscr{F})$ 라고 쓸 때, 여기에는 어느 정도의 표기법 남용이 발생하고 있는데, 이는 $\mathbb{E}(X\mid\mathscr{F})$ 가 어느 정도 합리적인 유일성까지만(즉, 측도 0인 변화까지는 허용하여) 정의되기 때문입니다. 따라서 이는 실제로는 “ $Y$ 가 명제 42.3.3의 가정을 만족한다”는 것을 의미하지만, 이는 너무 세밀해서 아무도 신경 쓰지 않습니다.

예를 들어, 위의 예시에서 만약 $\eta$ 를 다음과 같이 바꾸면

\eta(\omega)=\begin{cases}0&\text{만약}X(\omega)+Y(\omega)=0.6\\ \frac{X(\omega)+Y(\omega)}{2}&\text{그렇지 않으면}\end{cases}

그러면 $\mathbb{E}[\eta\cdot\mathbf{1}_{A}]=\mathbb{E}[X\cdot\mathbf{1}_{A}]$ 는 모든 집합 $A$ 에 대해 여전히 성립하지만, 이제 이는 $\mathbb{E}[X\mid X+Y=0.6]=0$ 이라고 말하는 것처럼 보이지 않습니까?

그럼에도 불구하고, 우리는 측도 0인 집합을 희생해야 한다는 데 동의해야 하는데, 그렇지 않으면 다음과 같은 경우

T(\omega)=\begin{cases}1&\text{만약}Y(\omega)>0.5\text{또는}(Y(\omega)=0.5\text{그리% 고}X(\omega)\in\mathbb{Q})\\ 0&\text{그렇지 않으면}\end{cases}

그러면 이는 확실히 가측이지만(즉, 확률 변수이지만), $\mathbb{E}[T\mid Y=0.4]=0$ 이고 $\mathbb{E}[T\mid Y=0.6]=1$ 인데, $\mathbb{E}[T\mid Y=0.5]$ 는 무엇입니까? (여러분은 이것이 $0$ 이어야 한다고 주장할 수도 있지만, $\mathbb{Q}$ 가 더욱 비가측적인 어떤 것으로 바뀐다면 어떻게 되겠습니까? 게다가, 확률이 0인 집합에서만 $T$ 를 수정했을 뿐인데 조건부 기댓값이 왜 바뀌어야 합니까?)

작성 예정: 성질

42.4 슈퍼마팅게일

대표적인 예: 하우스 확률을 가정할 때, 카지노를 방문하는 것은 슈퍼마팅게일입니다.

정의 42.4.1.

$X_{0}$ , $X_{1}$ , … 를 확률 공간 $\Omega$ 위의 확률 변수의 수열이라 하고, $\mathscr{F}_{0}\subseteq\mathscr{F}_{1}\subseteq\cdots$ 를 여과라 합시다.

그러면 다음 조건들이 성립할 때 $(X_{n})_{n\geq 0}$ 는 $(\mathscr{F}_{n})_{n\geq 0}$ 에 대한 슈퍼마팅게일입니다:

•

$X_{n}$ 은 모든 $n$ 에 대해 절대 적분 가능합니다;
•

$X_{n}$ 은 $\mathscr{F}_{n}$ 에 대해 가측입니다; 그리고
•

각 $n=1,2,\dots$ 에 대해 부등식

$\mathbb{E}(X_{n}\mid\mathscr{F}_{n-1})\leq X_{n-1}$

은 모든 $\omega\in\Omega$ 에 대해 성립합니다.

서브마팅게일에서는 부등식 $\leq$ 가 $\geq$ 로 대체되며, 마팅게일에서는 $=$ 로 대체됩니다.

작성 예정: 이 용어의 어원은 무엇인가요?

표기의 남용 42.4.2 (어차피 그 여과라는 것을 쓰는 사람은 아무도 없습니다).

우리는 항상 $\mathscr{F}_{n}$ 을 이전 변수들 $X_{0}$ , $X_{1}$ , …, $X_{n-1}$ 로 생성되는 $\sigma$ -대수로 취할 것이며, 이에 대해 따로 언급하지 않겠습니다. 그럼에도 이어지는 모든 결과는 어떤 여과에 대한 슈퍼마팅게일이라는 더 일반적인 상황에서도 성립합니다.

우리는 모든 정리를 슈퍼마팅게일에 대해 증명할 것입니다; 서브마팅게일에 대한 유사한 버전은 모든 곳에서 $\leq$ 를 $\geq$ 로 대체하여 얻을 수 있고 ( $X_{n}$ 이 마팅게일인 것과 $-X_{n}$ 이 슈퍼마팅게일인 것이 동치이므로), 마팅게일에 대해서는 모든 곳에서 $\leq$ 를 $=$ 로 대체하여 얻을 수 있습니다 ( $X_{n}$ 이 마팅게일인 것과 그것이 슈퍼마팅게일이면서 동시에 서브마팅게일인 것이 동치이므로).

예시를 들어봅시다.

예제 42.4.3 (슈퍼마팅게일).

(a)

랜덤 워크: 개미 한 마리가 수직선 위의 위치 $0$ 에서 출발합니다. 매 분마다 이 개미는 공정한 동전을 던져 왼쪽으로 한 칸 걷거나 오른쪽으로 한 칸 걷습니다. $X_{t}$ 가 $t$ 번째 시각의 위치라면, $X_{t}$ 는 마팅게일인데, 그 이유는

$\mathbb{E}(X_{t}\mid X_{0},\dots,X_{t-1})=\frac{(X_{t-1}+1)+(X_{t-1}-1)}{2}=X_% {t-1}.$
(b)

카지노 게임: 이 장의 도입부에서 설명한 전략을 사용하는 도박꾼을 생각해 봅시다. 도박꾼이 거는 모든 배팅의 기댓값이 $0$ 이므로, 이는 마팅게일입니다.
(c)

독립 변수의 곱: $X_{1}$ , $X_{2}$ , … 를 (반드시 동일하게 분포하지는 않는) 평균이 $1$ 인 독립인 적분 가능 확률 변수들이라 합시다. 그러면 다음과 같이 정의되는 수열 $Y_{1}$ , $Y_{2}$ , … 는

$Y_{n}\coloneqq X_{1}X_{2}\cdots X_{n}$

$\mathbb{E}(Y_{n}\mid Y_{1},\dots,Y_{n-1})=\mathbb{E}[Y_{n}]\cdot Y_{n-1}=Y_{n-1}$ 이므로 마팅게일입니다.
(d)

반복 블랙잭: 어떤 사람이 카지노에 가서 무한히 많은 블랙잭 게임을 한다고 합시다. $X_{t}$ 가 시각 $t$ 에서의 그의 재산이라면, $X_{t}$ 는 슈퍼마팅게일입니다. 이는 각 게임의 기댓값이 음수이기 때문입니다 (하우스 엣지).

예제 42.4.4 (경박한/도발적인 예시 — 실생활은 슈퍼마팅게일이다).

$X_{t}$ 를 당신 인생의 $t$ 번째 날의 행복도라 합시다. 인생에는 오르막과 내리막이 있으므로, 모든 $t$ 에 대해 $X_{t}\leq X_{t-1}$ 인 것은 아닙니다. 예를 들어, 어느 날 복권에 당첨될 수도 있습니다.

그러나 어느 특정한 날이든 여러 가지 일이 잘못될 수 있으며 (예: 좀비 대재앙), 머피의 법칙에 따르면 이것이 일이 잘 풀리는 것보다 더 가능성이 높습니다. 또한 나이가 들수록 책임은 점점 늘어나고 건강은 점차 나빠지기 시작합니다.

따라서 다음과 같은 것이

\mathbb{E}(X_{t}\mid X_{0},\dots,X_{t-1})\leq X_{t-1}

미래에 대한 합리적인 설명으로 보입니다 — 기댓값 상으로는, 각 연속하는 날이 이전 날보다 조금씩 더 나쁩니다. (특히 죽음이 닥쳤을 때 $X_{t}=-\infty$ 로 설정한다면, 죽을 확률이 양수인 한 위에 제시된 부등식은 자명하게 참입니다.)

계속하기 전에, 증명 없이 유용한 결과 하나를 제시하겠습니다: 마르팅게일이 유계이면, 그것은 거의 확실하게 수렴합니다.

정리 42.4.5 (둡의 마르팅게일 수렴 정리).

$X_{0}$ , … 를 확률 공간 $\Omega$ 위의 상마르팅게일(supermartingale)이라 하고 다음을 만족한다고 합시다

\sup_{n\in\mathbb{Z}_{\geq 0}}\mathbb{E}\left[\left\lvert X_{n}\right\rvert% \right]<\infty.

그러면, 다음을 만족하는 확률변수 $X_{\infty}\colon\Omega\to\mathbb{R}$ 가 존재합니다

X_{n}\xrightarrow{\text{a.s.}}X_{\infty}.

42.5 선택적 정지(Optional stopping)

대표적인 예: 라스베이거스.

첫 번째 절에서 우리는 거의 확실하게 돈을 버는 방법을 설명했습니다. 도박꾼이 가진 핵심적인 이점은 원할 때 언제든지 그만둘 수 있는 능력이었습니다(이는 판돈의 크기를 조절할 수 있는 능력과 동치입니다; 영원히 $0을 거는 것은 그만두는 것과 같습니다). 정지 시간(stopping time)이라는 개념을 formalize해봅시다.

아이디어는 다음을 만족하는 함수 $\tau\colon\Omega\to\{0,1,2,\dots\}\cup\{\infty\}$ 를 정의하고자 하는 것입니다

•

$\tau(\omega)$ 는 그 이후에 마르팅게일을 정지시키는 인덱스를 지정합니다. 시각 $n$ 이후 정지할지에 대한 결정은 그 시점에 이용 가능한 정보만을 사용하여 이루어져야 함에 유의하십시오 — 즉, 필트레이션의 $\mathscr{F}_{n}$ 에 대해서만 이루어져야 합니다.
•

$X_{\tau\wedge n}$ 은 정지된 마르팅게일의 시각 $n$ 에서의 값을 나타내는 확률변수이며, 만약 $n$ 이 정지 시간 이후라면, 우리는 그것을 단지 우리가 떠난 이후의 현재 값으로 취합니다.

예를 들어, 시각 $3$ 에서 정지한 세계 $\omega$ 에서는, $X_{\tau\wedge 0}(\omega)=X_{0}(\omega)$ , $X_{\tau\wedge 1}(\omega)=X_{1}(\omega)$ , $X_{\tau\wedge 2}(\omega)=X_{2}(\omega)$ , $X_{\tau\wedge 3}(\omega)=X_{3}(\omega)$ 이지만, 그 이후에는

$X_{3}(\omega)=X_{\tau\wedge 4}(\omega)=X_{\tau\wedge 5}(\omega)=X_{\tau\wedge 6% }(\omega)=\dots$

우리가 정지했으므로 — 값이 더 이상 변하지 않습니다.
•

$X_{\tau}$ 는 정지 이후의 최종 값을 나타냅니다(또는 만약 결코 정지하지 않는다면 극한 $X_{\infty}$ 를 나타냅니다).

여기 컴파일된 기계어 코드가 있습니다.

정의 42.5.1.

$\mathscr{F}_{0}\subseteq\mathscr{F}_{1}\subseteq\cdots$ 를 확률 공간 $\Omega$ 위의 필트레이션이라 합시다.

•

정지 시간(stopping time)이란 다음과 같은 함수입니다

$\tau\colon\Omega\to\{0,1,2,\dots\}\cup\{\infty\}$

각 정수 $n$ 에 대해, 다음 집합이

$\left\{\omega\in\Omega\mid\tau(\omega)=n\right\}$

$\mathscr{F}_{n}$ -가측(즉, $\mathscr{F}_{n}$ 에 속함)이라는 성질을 갖습니다.
•

각 $n\geq 0$ 에 대해, 우리는 $X_{\tau\wedge n}\colon\Omega\to\mathbb{R}$ 를 다음과 같이 정의합니다

$X_{\tau\wedge n}(\omega)=X_{\min\left\{\tau(\omega),n\right\}}(\omega)$
•

마지막으로, 우리는 최종 결과를 다음과 같이 나타내겠습니다

$X_{\tau}(\omega)=\begin{cases}X_{\tau(\omega)}(\omega)&\tau(\omega)\neq\infty% \\ \lim_{n\to\infty}X_{n}(\omega)&\tau(\omega)=\infty\text{그리고}\lim_{n\to\infty}X% _{n}(\omega)\text{존재함}\\ \text{정의되지 않음}&\text{그렇지 않으면}.\end{cases}$

우리는 ”정의되지 않은” 경우가 오직 측도 0인 집합에 대해서만 발생하기를 요구합니다(예를 들어, 정리 42.4.5 가 적용되는 경우입니다). 그렇지 않으면 우리는 $X_{\tau}$ 가 정의되도록 허용하지 않습니다.

명제 42.5.2 (정지된 상마르팅게일은 여전히 상마르팅게일이다).

$X_{0}$ , $X_{1}$ , … 를 상마르팅게일이라 합시다. 그러면 다음 수열은

X_{\tau\wedge 0},\;X_{\tau\wedge 1},\;\dots

그 자체로 상마르팅게일입니다.

증명.

우리는 거의 어디서나 다음 부등식들을 갖습니다

	$\displaystyle\mathbb{E}\left(X_{\tau\wedge n}\mid\mathscr{F}_{n-1}\right)$	$\displaystyle=\mathbb{E}\left(X_{n-1}+\mathbf{1}_{\tau(\omega)=n-1}(X_{n}-X_{n% -1})\mid\mathscr{F}_{n-1}\right)$
		$\displaystyle=\mathbb{E}\left(X_{n-1}\mid\mathscr{F}_{n-1}\right)+\mathbb{E}% \left(\mathbf{1}_{\tau(\omega)=n-1}\cdot(X_{n}-X_{n-1})\mid\mathscr{F}_{n-1}\right)$
		$\displaystyle=X_{n-1}+\mathbf{1}_{\tau(\omega)=n-1}\cdot\mathbb{E}\left(X_{n}-% X_{n-1}\mid\mathscr{F}_{n-1}\right)\leq X_{n-1}$

$\Omega\to\mathbb{R}$ 로 가는 함수로서. ∎

정리 42.5.3 (Doob의 최적 정지 정리).

$X_{0}$ , $X_{1}$ , … 을 확률 공간 $\Omega$ 위에서, 필트레이션 $\mathscr{F}_{0}\subseteq\mathscr{F}_{1}\subseteq\cdots$ 에 대한 초마팅게일이라고 합시다. $\tau$ 를 이 필트레이션에 대한 정지 시간이라고 합시다. 어떤 상수 $C$ 에 대해 다음 가정 중 어느 것이든 성립한다고 가정합니다:

(a)

유한 시간: 거의 모든 $\omega$ 에 대해 $\tau(\omega)\leq C$ 입니다.
(b)

유한 자금: 각 $n\geq 1$ 에 대해, 거의 모든 $\omega$ 에 대해 $\left\lvert X_{\tau\wedge n}(\omega)\right\rvert\leq C$ 입니다.
(c)

유한 베팅: $\mathbb{E}[\tau]<\infty$ 이며, 각 $n\geq 1$ 에 대해 조건부 기댓값

$\mathbb{E}\left(\left\lvert X_{n}-X_{n-1}\right\rvert\mid\mathscr{F}_{n}\right)$

은 $\tau(\omega)\geq n$ 을 만족하는 거의 모든 $\omega\in\Omega$ 에 대해 최대 $C$ 의 값을 취합니다.

그러면 $X_{\tau}$ 는 거의 모든 곳에서 잘 정의되며, 더 중요하게는 다음이 성립합니다.

\mathbb{E}[X_{\tau}]\leq\mathbb{E}[X_{0}].

마지막 식은 장난스럽게 ”유일한 승리 수는 플레이하지 않는 것이다”라고 표현할 수 있습니다.

증명.

작성 예정: 오늘 밤 나중에 하기

∎

연습문제 42.5.4.

첫 절에서 설명한 전략을 가지고 라스베이거스에 가는 것은 정말 나쁜 생각이라는 것을 결론지으십시오. 무엇이 잘못되는 것입니까?

이것이 우리가 도박을 그만두게 만드는 데는 유용하지만, 무언가를 계산할 수 있게 해주지는 않습니다 — 우리는 $\mathbb{E}[X_{\tau}]$ 에 대해 그것이 $\leq\mathbb{E}[X_{0}]$ 라는 것 외에는 아무것도 알지 못합니다. 그러나:

따름정리 42.5.5.

위와 동일한 가정 하에서:

•

만약 $X_{0}$ , $X_{1}$ , … 가 준마팅게일이면, $\mathbb{E}[X_{\tau}]\geq\mathbb{E}[X_{0}]$ 입니다.
•

만약 이것이 마팅게일이면, $\mathbb{E}[X_{\tau}]=\mathbb{E}[X_{0}]$ 입니다.

증명.

만약 $X_{0}$ , $X_{1}$ , … 가 준마팅게일이면, $Y_{i}=-X_{i}$ 로 정의된 $Y_{0}$ , $Y_{1}$ , … 는 초마팅게일이며, 가정은 여전히 만족됩니다. 정리를 $Y_{\tau}$ 에 적용하면 결과를 얻습니다.

만약 $X_{0}$ , $X_{1}$ , … 가 마팅게일이면, 이것은 초마팅게일이면서 동시에 준마팅게일이므로, 결과는 즉시 따라옵니다. ∎

이로써 마침내 우리는 무언가를 계산할 수 있게 됩니다 — 만약 $\mathbb{E}[X_{0}]$ 를 계산할 수 있고 그 결과를 어떤 마팅게일에 대한 $\mathbb{E}[X_{\tau}]$ 로 쓸 수 있다면, 우리는 문제를 풀 수 있습니다!

42.6 최적 정지의 재미있는 응용 (작성 예정)

이제 우리는 지금까지 개발한 결과들의 위력을 보여주는 세 가지 문제를 제시합니다.

42.6.1 투표 문제

Alice와 Bob이 선거에서 경쟁하고 있다고 합시다. Alice는 총 $a$ 표를, Bob은 총 $b$ 표를 받았으며, $a>b$ 입니다. 표가 무작위 순서로 선택된다면, Alice가 선거 내내 Bob보다 엄격하게 앞서 있을 확률은 얼마인지 물을 수 있습니다.

그림 작성 예정: 경로

명제 42.6.1 (투표 문제).

이것은 확률 $\frac{a-b}{a+b}$ 로 발생합니다.

우리는 이것을 마팅게일로 모델링해 보아야 합니다. 이를 수행하는 자연스러운 방법은 예제 42.4.3에서와 같은 무작위 보행입니다:

	$\displaystyle X_{0}$	$\displaystyle=0$
	$\displaystyle X_{i}$	$\displaystyle=X_{i-1}+\begin{cases}1\text{확률로}\frac{1}{2}\\ -1\text{그렇지 않으면.}\end{cases}$

여기서 각 $1$ 은 앨리스가 표를 얻는 것을 나타내고, 각 $-1$ 은 밥이 표를 얻는 것을 나타냅니다.

그러면 우리는 다음을 계산해야 합니다

\Pr[X_{i}>0\text{모든 것에 대하여}1\leq i\leq a+b\mid X_{a+b}=a-b].

이것이 자연스럽기는 하지만, 확률이 $X_{a+b}=a-b$ 에 조건화되어 있다는 사실 때문에 선택적 정지 정리를 적용할 수 없습니다.

대신 다음과 같은 방법이 통합니다: 모든 표에서 시작하여, 무작위 순서로 그것들을 제거합니다.

	$\displaystyle(A_{0},B_{0})$	$\displaystyle=(a,b),$
	$\displaystyle(A_{i},B_{i})$	$\displaystyle=\begin{cases}(A_{i-1}-1,B_{i-1})\text{확률로}\frac{A_{i-1}}{A_{i-1}% +B_{i-1}}\\ (A_{i-1},B_{i-1}-1)\text{그렇지 않으면}\end{cases}\text{~{}에 대하여}1\leq i\leq a+b.$

물론 여기서 $A_{i}$ 는 앨리스에게 남은 표의 수를 나타내고, $B_{i}$ 는 밥에게 남은 표의 수를 나타냅니다.

이제 우리는 다음을 계산하기만 하면 됩니다

\Pr[A_{i}>B_{i}\text{모든 것에 대하여}0\leq i\leq a+b-1].

더 이상 조건부 기댓값이 없습니다!

다음으로 우리는 마팅게일을 구성해야 합니다. 위와 비슷하게 $X_{i}=A_{i}-B_{i}$ 로 정의해 볼 수도 있지만, 그것은 마팅게일이 되지 않습니다.

여기 요령이 있습니다: 우리는 $X_{i}$ 를 수정하여 마팅게일로 만듭니다. (확률 변수의 수열을 수정하여 마팅게일을 만드는 더 많은 예시는 문제 42A에서 찾을 수 있습니다.)

예제 42.6.2.

$a=2$ 이고 $b=1$ 이라고 합시다. 그러면:

	$\displaystyle(A_{0},B_{0})$	$\displaystyle=(2,1),$
	$\displaystyle(A_{1},B_{1})$	$\displaystyle=\begin{cases}(1,1)\text{확률로}\frac{2}{3}\\ (2,0)\text{그렇지 않으면.}\end{cases}$

그러므로 $\mathbb{E}[A_{0}-B_{0}]=1$ 인 반면 $\mathbb{E}[A_{1}-B_{1}]=\frac{2}{3}\cdot 0+\frac{1}{3}\cdot 2=\frac{2}{3}$ 이므로, 만약 우리가 $X_{i}$ 를 위와 같이 정의한다면 물론 마팅게일이 되지 않을 것입니다.

하지만 그것을 수정하여 마팅게일을 만드는 방법을 찾는 것은 어렵지 않습니다. 예를 들면:

•

만약 우리가 $X_{1}=A_{1}-B_{1}+\frac{1}{3}$ 로 정의한다면, $\mathbb{E}[X_{1}]=1$ 이 되므로 문제없습니다.
•

마찬가지로, 우리는 $X_{1}=\frac{3}{2}\cdot(A_{1}-B_{1})$ 로도 정의할 수 있습니다.
•

또는 $X_{1}=\frac{9}{4}\cdot(A_{1}-B_{1})^{2}$ 로도 정의할 수 있습니다.
•

… 기타 등등…

우리는 모든 $i$ 와 모든 $(x_{0},x_{1},\dots,x_{i-1})$ 에 대해 $\mathbb{E}[X_{i}\mid X_{0}=x_{0},X_{1}=x_{1},\dots,X_{i-1}=x_{i-1}]=x_{i-1}$ 이 되도록 만들어야 합니다. (계속 읽기 전에 어떤 수정이 통할지 스스로 알아내 보십시오.)

알고 보니, 다음과 같은 방법이 통합니다:

X_{i}=\frac{A_{i}-B_{i}}{a+b-i}\text{~{}에 대하여}0\leq i\leq a+b-1.

우리는 이것을 $i\geq a+b$ 까지 확장할 수 없지만, 그것으로 충분합니다. (걱정된다면, $i\geq a+b$ 에 대해 그냥 $X_{i}=X_{a+b-1}$ 로 정의하십시오.)

연습문제 42.6.3.

이것이 작동하는지 확인해 보십시오. (이 수학적 계산은 문제 42A의 폴야의 항아리(Pólya’s urn) 문제와 매우 유사합니다.)

정지 시간에 대해서는, 그것을 정의하는 자연스러운 방법이 하나뿐입니다: 모든 $0\leq i\leq a+b-1$ 에 대해 $X_{i}>0$ 이어서 앨리스가 밥보다 계속 앞서 있다면 $\tau$ 는 $a+b-1$ 이고, 그렇지 않다면 $\tau$ 는 $X_{i}=0$ 이 되는 가장 작은 $i$ 입니다.

그러면 선택적 정지 정리는 다음을 말해 줍니다:

\mathbb{E}[X_{\tau}]=\mathbb{E}[X_{0}].

$\mathbb{E}[X_{0}]$ 는 계산하기 쉬운데, 그것은 $\frac{A_{0}-B_{0}}{a+b}=\frac{a-b}{a+b}$ 입니다. $\mathbb{E}[X_{\tau}]$ 는 무엇일까요?

•

만약 앨리스가 밥보다 계속 앞서 있다면, $X_{\tau}=X_{a+b-1}=1$ 입니다.
•

그렇지 않으면 $X_{\tau}=0$ 입니다.

따라서 $\mathbb{E}[X_{\tau}]$ 는 정확히 우리가 계산해야 하는 확률이므로, 증명이 완료됩니다.

비고 42.6.4 (이것은 약간 반칙입니다).

다음과 같이 동등하게 쓸 수 있음에 유의하십시오

X_{i}=\frac{A_{i}-B_{i}}{A_{i}+B_{i}}.

이것이 정확히 답의 형태입니다.

즉, 답의 형태를 이미 알고 있다면 마팅게일 이론이 그것을 확인하는 데 도움이 될 수 있습니다. 하지만 모른다면…

42.6.2 ABRACADABRA

작성 예정입니다.

https://www.jeremykun.com/2014/03/03/martingales-and-the-optional-stopping-theorem/

42.6.3 USA TST 2018

작성 예정입니다.

https://aops.com/community/p9513099

42.7 생각해 볼 만한 조금 더 어려운 문제

문제 42A (마팅게일의 예시).

마팅게일의 몇 가지 예시를 더 제시하겠습니다.

(a)

(단순 확률보행) $X_{1}$ , $X_{2}$ , … 를 확률 $1/2$ 로 $+1$ 이 되고 확률 $1/2$ 로 $-1$ 이 되는 독립동일분포 확률변수라 하십시오. 다음이

$Y_{n}=\left(X_{1}+\dots+X_{n}\right)^{2}-n$

마팅게일임을 증명하십시오.
(b)

(드무아브르 마팅게일) $p,q>0$ 이고 $p+q=1$ 인 실수 $p$ 와 $q$ 를 고정하십시오. $X_{1}$ , $X_{2}$ , … 을 확률 $p$ 로 $+1$ 과 같고, 확률 $q$ 로 $-1$ 과 같은 독립 항등 분포 확률 변수라고 합시다. 다음이

$Y_{n}=\left(qp^{-1}\right)^{X_{1}+X_{2}+\dots+X_{n}}$

마팅게일임을 보이십시오.
(c)

(폴리아의 항아리) 항아리에 처음에 빨간 구슬 하나와 파란 구슬 하나가 들어 있습니다. 매분마다 항아리에서 구슬 하나를 무작위로 꺼내고, 같은 색깔의 구슬 두 개를 항아리에 더 넣습니다. 따라서 $n$ 분 후에는 항아리에 $n+2$ 개의 구슬이 있게 됩니다.

$r_{n}$ 을 빨간 구슬의 비율이라 하십시오. $r_{n}$ 이 마팅게일임을 보이십시오.

문제 42B.

카드 덱에는 $52$ 장의 카드가 있으며, 그중 $26$ 장은 빨간색이고 $26$ 장은 검은색입니다. 카드는 한 장씩 뽑혀 공개됩니다. 어느 시점에서든 덱에 카드가 최소 한 장 남아 있으면 딜러를 멈출 수 있으며, 덱의 다음 카드가 빨간색인 경우에만(그리고 그 경우에 한해) 승리합니다. 모든 카드가 다 뽑히면 패배합니다. 가능한 모든 전략 중에서, 승리할 최대 확률을 구하십시오.

힌트. 귀여운 초등적 풀이가 존재합니다. 마팅게일 기반 풀이를 위해서는, 시각 $n$ 에서 덱에 남은 빨간 카드의 비율이 마팅게일임을 보이십시오.

문제 42C (발드의 항등식).

$\mu$ 를 실수라 하십시오. $X_{1}$ , $X_{2}$ , … 를 확률 공간 $\Omega$ 위에서 정의된, 평균이 $\mu$ 인 독립 확률변수라 하십시오. 마지막으로 $\tau\colon\Omega\to\{1,2,\dots\}$ 를 $\mathbb{E}[\tau]<\infty$ 이고 사건 $\tau=n$ 이 오직 $X_{1}$ , …, $X_{n}$ 에만 의존하는 멈춤 시각이라 하십시오.

다음을 증명하십시오

\mathbb{E}[X_{1}+X_{2}+\dots+X_{\tau}]=\mu\mathbb{E}[\tau].

문제 42D (편향 없는 취객의 보행).

개미가 수직선 위의 $0$ 에서 출발하여, 확률 $1/2$ 로 왼쪽 또는 오른쪽으로 한 칸씩 이동합니다. 개미는 $-17$ 또는 $+8$ 에 도달하면 멈춥니다.

(a)

$-17$ 보다 먼저 $+8$ 에 도달할 확률을 구하십시오.
(b)

두 끝점 중 하나에 도달하는 데 걸리는 시간의 기댓값을 구하십시오.

문제 42E (편향된 취객의 걸음).

$0<p<1$ 을 실수라 하십시오. 개미가 수직선 위 $0$ 에서 출발하여, 확률 $p$ 로 좌우로 한 칸씩 걷습니다. 개미는 $-17$ 또는 $+8$ 중 하나에 도달하면 멈춥니다. 개미가 $+8$ 에 먼저 도달할 확률을 구하십시오.

힌트. 문제 42A을 사용하십시오.

문제 42F.

칠판에 숫자 $1$ 이 적혀 있습니다. 매 분마다, 칠판에 숫자 $a$ 가 적혀 있으면 그것을 지우고 구간 $[0,2.01a]$ 에서 균등하게 무작위로 선택한 실수로 대체합니다. 그 결과로 얻어지는 수열이 $0$ 에 접근할 확률은 얼마입니까?

힌트. 이는 확률 $1$ 로 발생합니다. $X_{n}$ 이 단계 $n$ 에서 판에 적힌 수이고, $\mu=\frac{1}{2.01}\int_{0}^{2.01}\log t\;dt$ 일 때, $\log(X_{n})-n\mu$ 가 마팅게일임을 보이십시오. (참고로, 큰 수의 법칙을 사용해도 될 수 있습니다.)

	$\displaystyle A$	$\displaystyle=\{\omega\mid X(\omega)=1\}$
	$\displaystyle B$	$\displaystyle=\{\omega\mid X(\omega)=2\}$
	$\displaystyle C$	$\displaystyle=\{\omega\mid X(\omega)=3\}$

장 42 정지된 마팅게일 (작성 예정)

42.1 거의 확실하게 돈을 버는 방법

예제 42.1.1 (18세기 프랑스보다도 더 탐욕스러워지기).

42.2 부분 σ-대수와 여과

정의 42.2.1.

예제 42.2.2 (부분 σ-대수의 예시).

정의 42.2.3.

정의 42.2.4.

예제 42.2.5 (여과).

연습문제 42.2.6.

예제 42.2.7.

연습문제 42.2.8.

42.3 조건부 기댓값

예제 42.3.1 (고등학교 수준의 방법이 여기서 충분하지 않은 이유).

예제 42.3.2.

명제 42.3.3 (조건부 기댓값의 정의).

증명.

정의 42.3.4.

예제 42.3.5.

비고 42.3.6 (이 표기법은 형편없습니다).

표기의 남용 42.3.7.

42.4 슈퍼마팅게일

정의 42.4.1.

표기의 남용 42.4.2 (어차피 그 여과라는 것을 쓰는 사람은 아무도 없습니다).

예제 42.4.3 (슈퍼마팅게일).

예제 42.4.4 (경박한/도발적인 예시 — 실생활은 슈퍼마팅게일이다).

정리 42.4.5 (둡의 마르팅게일 수렴 정리).

42.5 선택적 정지(Optional stopping)

정의 42.5.1.

명제 42.5.2 (정지된 상마르팅게일은 여전히 상마르팅게일이다).

증명.

정리 42.5.3 (Doob의 최적 정지 정리).

증명.

연습문제 42.5.4.

따름정리 42.5.5.

증명.

42.6 최적 정지의 재미있는 응용 (작성 예정)

42.6.1 투표 문제

명제 42.6.1 (투표 문제).

예제 42.6.2.

연습문제 42.6.3.

비고 42.6.4 (이것은 약간 반칙입니다).

42.6.2 ABRACADABRA

42.6.3 USA TST 2018

42.7 생각해 볼 만한 조금 더 어려운 문제

문제 42A (마팅게일의 예시).

문제 42B.

문제 42C (발드의 항등식).

문제 42D (편향 없는 취객의 보행).

문제 42E (편향된 취객의 걸음).

문제 42F.

42.2 부분 $\sigma$ -대수와 여과

예제 42.2.2 (부분 $\sigma$ -대수의 예시).