notes-shao2003

Unnamed repository; edit this file 'description' to name the repository.
git clone git://pcardenasb.com/notes-shao2003.git
Log | Files | Refs

commit 1486f2708ad30565f0f41503451ba09f2dcb2345
Author: Pablo Cárdenas <pablo.cardenas@impa.br>
Date:   Sun, 26 Jul 2026 20:52:57 -0300

Initial commit

Diffstat:
Aanki.pl | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adocument.tex | 20++++++++++++++++++++
Amacros.tex | 643+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atex/chapter_01.tex | 751+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 1522 insertions(+), 0 deletions(-)

diff --git a/anki.pl b/anki.pl @@ -0,0 +1,108 @@ +#!/usr/bin/env perl +use strict; +use warnings; + +my $deck_name = "shao2003"; + +print "#separator:Comma\n"; +print "#html:true\n"; +print "#deck:notes::$deck_name\n"; +print "#notetype:Basic\n"; +print "#columns:Front,Back,Tags\n"; + +sub quote_csv { + my $s = shift; + $s =~ s/"/""/g; + return qq{"$s"}; +} + +sub escape_html { + my $s = shift; + $s =~ s/&/&amp;/g; + $s =~ s/</&lt;/g; + $s =~ s/>/&gt;/g; + return $s; +} + +sub latex_to_html_fast { + my $s = shift; + $s =~ s/^\t+//mg; + + $s = escape_html($s); + $s =~ s{\\emph\{([^{}]*)\}}{<em>$1</em>}g; + + $s =~ s{ + \\begin\{(align\*?|equation\*?|gather\*?)\} + (.*?) + \\end\{\1\} + }{\\[\\begin{$1}$2\\end{$1}\\]}gxs; + + 1 while $s =~ s{ + \\begin\{itemize\} + ((?:(?!\\begin\{itemize\}|\\end\{itemize\}).)*) + \\end\{itemize\} + }{ + my @items = grep { /\S/ } split /\\item\b/, $1; + "<ul>" . join("", map { + my $x = $_; + $x =~ s/^\s+|\s+$//g; + $x =~ s/\n\s*\n/\n/g; + "<li>$x</li>" + } @items) . "</ul>"; + }egxs; + + my @blocks = grep { /\S/ } split /\n\s*\n/, $s; + return join "\n", map { + /^<ul>/ ? $_ : "<p>$_</p>" + } @blocks; +} + + + +my $style = " +<style> +.card { + font-family: serif; + text-align: left; + margin-inline: auto; + max-width: 36em; +} +</style> +"; + +for my $file (glob("tex/chapter_*.tex")) { + (my $lecture_num = $file) =~ s{^.*/chapter_(\d\d)\.tex$}{$1}; + + open my $fh, "<", $file or die $!; + my ($lecture_title) = (<$fh> =~ /\\title\s+(.*)/); + my $tex = do { local $/; <$fh> }; + + my @lecture_block_titles; + while ( + $tex =~ / + ^\\begin\{(?<env>[^}]*)\} + \{(?<id>.*?)\}\{(?<name>.*?)\}\R + (?<body>.*?) + ^\\end\{\k<env>\} + /smgx + ) { + my $env = $+{env}; + my $id = $+{id}; + my $name = $+{name}; + my $body = $+{body}; + + my $title = sprintf("%s %s: %s", $id, $env, $name); + push @lecture_block_titles, $title; + + my $back = latex_to_html_fast($body); + my $front = $style . $title; + my $tags = "${deck_name}::lecture::$lecture_num ${deck_name}::env::$env"; + + print quote_csv($front), ",", quote_csv("\n" . $back), ",", quote_csv($tags), "\n"; + } + + my $front = $style . "$lecture_num.99 Index"; + my $back = "<strong>$lecture_title</strong>\n" . join("\n", map { "<div>$_</div>" } @lecture_block_titles); + my $tags = "${deck_name}::lecture::$lecture_num ${deck_name}::env::index"; + print quote_csv($front), ",", quote_csv("\n" . $back), ",", quote_csv($tags), "\n"; +} diff --git a/document.tex b/document.tex @@ -0,0 +1,20 @@ +\input macros + +\def\definition#1#2{\breakbox{0.5 0.5 0.5} Definition #1: #2} +\def\theorem#1#2{\breakbox{0.5 0.5 0.5} Theorem #1: #2} +\def\paragraph#1#2{\breakbox{0.5 0.5 0.5} Paragraph #1: #2} +\def\lemma#1#2{\breakbox{0.5 0.5 0.5} Lemma #1: #2} +\def\example#1#2{\breakbox{0.5 0.5 0.5} Example #1: #2} +\def\proposition#1#2{\breakbox{0.5 0.5 0.5} Proposition #1: #2} +\def\proof#1#2{\breakbox{0.5 0.5 0.5} Proof #1: #2} + +\def\enddefinition{\endbreakbox} +\def\endtheorem{\endbreakbox} +\def\endparagraph{\endbreakbox} +\def\endlemma{\endbreakbox} +\def\endexample{\endbreakbox} +\def\endproposition{\endbreakbox} +\def\endproof{\endbreakbox} + +\input tex/chapter_01 +\bye diff --git a/macros.tex b/macros.tex @@ -0,0 +1,643 @@ +\baselineskip=12pt +\lineskiplimit=0pt +\lineskip=0pt +\parindent=0pt +\parskip=0pt +\topskip=0pt +\maxdepth=0pt +\jot=3pt +\abovedisplayskip=3pt +\belowdisplayskip=3pt +\abovedisplayshortskip=0pt +\belowdisplayshortskip=0pt +\predisplaypenalty=0 + +% \pretolerance=-1 +% \tolerance=9999 +% \emergencystretch=8pt +\overfullrule=5mm +\showboxdepth=100 +\showboxbreadth=1000 + +\def\capitalize#1#2{\uppercase{#1}#2} + +% UTF8 {{{ +\catcode`\^^c2=13 +\catcode`\^^c3=13 + +\def\UTFviii#1#2{% + \expandafter\ifx\csname utf8-#1-\number`#2\endcsname\relax + \errmessage{Unsupported UTF-8 character}% + \else + \csname utf8-#1-\number`#2\endcsname + \fi +} + +\def^^c2#1{\UTFviii{c2}{#1}} +\def^^c3#1{\UTFviii{c3}{#1}} + +% C2 block +\expandafter\def\csname utf8-c2-161\endcsname{!`} % ¡ +\expandafter\def\csname utf8-c2-191\endcsname{?`} % ¿ + +% Uppercase A: À Á Â Ã Ä Å +\expandafter\def\csname utf8-c3-128\endcsname{\`A} +\expandafter\def\csname utf8-c3-129\endcsname{\'A} +\expandafter\def\csname utf8-c3-130\endcsname{\^A} +\expandafter\def\csname utf8-c3-131\endcsname{\~A} +\expandafter\def\csname utf8-c3-132\endcsname{\"A} +\expandafter\def\csname utf8-c3-133\endcsname{\AA} + +% Ç +\expandafter\def\csname utf8-c3-135\endcsname{\c C} + +% Uppercase E: È É Ê Ë +\expandafter\def\csname utf8-c3-136\endcsname{\`E} +\expandafter\def\csname utf8-c3-137\endcsname{\'E} +\expandafter\def\csname utf8-c3-138\endcsname{\^E} +\expandafter\def\csname utf8-c3-139\endcsname{\"E} + +% Uppercase I: Ì Í Î Ï +\expandafter\def\csname utf8-c3-140\endcsname{\`I} +\expandafter\def\csname utf8-c3-141\endcsname{\'I} +\expandafter\def\csname utf8-c3-142\endcsname{\^I} +\expandafter\def\csname utf8-c3-143\endcsname{\"I} + +% Ñ +\expandafter\def\csname utf8-c3-145\endcsname{\~N} + +% Uppercase O: Ò Ó Ô Õ Ö +\expandafter\def\csname utf8-c3-146\endcsname{\`O} +\expandafter\def\csname utf8-c3-147\endcsname{\'O} +\expandafter\def\csname utf8-c3-148\endcsname{\^O} +\expandafter\def\csname utf8-c3-149\endcsname{\~O} +\expandafter\def\csname utf8-c3-150\endcsname{\"O} + +% Uppercase U: Ù Ú Û Ü +\expandafter\def\csname utf8-c3-153\endcsname{\`U} +\expandafter\def\csname utf8-c3-154\endcsname{\'U} +\expandafter\def\csname utf8-c3-155\endcsname{\^U} +\expandafter\def\csname utf8-c3-156\endcsname{\"U} + +% Lowercase a: à á â ã ä å +\expandafter\def\csname utf8-c3-160\endcsname{\`a} +\expandafter\def\csname utf8-c3-161\endcsname{\'a} +\expandafter\def\csname utf8-c3-162\endcsname{\^a} +\expandafter\def\csname utf8-c3-163\endcsname{\~a} +\expandafter\def\csname utf8-c3-164\endcsname{\"a} +\expandafter\def\csname utf8-c3-165\endcsname{\aa} + +% ç +\expandafter\def\csname utf8-c3-167\endcsname{\c c} + +% Lowercase e: è é ê ë +\expandafter\def\csname utf8-c3-168\endcsname{\`e} +\expandafter\def\csname utf8-c3-169\endcsname{\'e} +\expandafter\def\csname utf8-c3-170\endcsname{\^e} +\expandafter\def\csname utf8-c3-171\endcsname{\"e} + +% Lowercase i: ì í î ï +\expandafter\def\csname utf8-c3-172\endcsname{\`\i} +\expandafter\def\csname utf8-c3-173\endcsname{\'\i} +\expandafter\def\csname utf8-c3-174\endcsname{\^\i} +\expandafter\def\csname utf8-c3-175\endcsname{\"\i} + +% ñ +\expandafter\def\csname utf8-c3-177\endcsname{\~n} + +% Lowercase o: ò ó ô õ ö +\expandafter\def\csname utf8-c3-178\endcsname{\`o} +\expandafter\def\csname utf8-c3-179\endcsname{\'o} +\expandafter\def\csname utf8-c3-180\endcsname{\^o} +\expandafter\def\csname utf8-c3-181\endcsname{\~o} +\expandafter\def\csname utf8-c3-182\endcsname{\"o} + +% Lowercase u: ù ú û ü +\expandafter\def\csname utf8-c3-185\endcsname{\`u} +\expandafter\def\csname utf8-c3-186\endcsname{\'u} +\expandafter\def\csname utf8-c3-187\endcsname{\^u} +\expandafter\def\csname utf8-c3-188\endcsname{\"u} +% }}} + +% breakbox environment {{{1 +\newbox\innerbox +\newbox\innerboxi +\newbox\lineboxcheck +\newdimen\bgh +\newdimen\bgw +\newdimen\heightremaining +\newdimen\fboxsep +\newdimen\fboxrule +\newif\ifstart +\newif\ifend + +\fboxsep=2mm +\fboxrule=1.5pt + +\immediate\pdfobj{<< /Type /ExtGState /ca 0.03 >>} +\edef\TransparentState{\number\pdflastobj} +\pdfpageresources\expanded{{/ExtGState << /TransparentBoxGS \TransparentState\space 0 R >>}} + +\def\breakbox#1{ + \global\def\breakboxcolori{#1} + \setbox\innerbox=\vbox\bgroup% + \advance\hsize by-2\fboxsep% + \advance\hsize by-2\fboxrule% + \ifx\documentclass\undefined\else + \linewidth=\hsize + \textwidth=\hsize + \fi + \penalty0% + \noindent\strut\ignorespaces +} + +\def\endbreakbox{% + \egroup + + \splitmaxdepth=0pt + \splittopskip=0pt + + \starttrue + \endfalse + \loop + \heightremaining=\pagegoal + \ifdim\heightremaining=\maxdimen + \heightremaining=\vsize + \fi + \advance\heightremaining by-\pagetotal + \advance\heightremaining by-2\fboxsep + \advance\heightremaining by-2\fboxrule + \vbadness=10000 + \setbox\innerboxi=\vsplit\innerbox to\heightremaining + \vbadness=1000 + \setbox0=\vbox{ + \unvcopy\innerboxi + \unskip\unpenalty\unskip\unpenalty + \global\setbox\lineboxcheck=\lastbox + } + \ifvoid\lineboxcheck\else + \ifvoid\innerbox\endtrue\fi + % fcolorbox {{{ + \setbox0=\vbox{\kern\fboxsep\unvbox\innerboxi\kern\fboxsep} + \dimen0=\hsize + \advance\dimen0 by-2\fboxrule + \advance\dimen0 by-2\fboxsep + \wd0=\dimen0 + \bgh=\ht0 + \bgw=\wd0 + \advance\bgw by 2\fboxsep + \pdfliteral direct {q}% + \ifstart + \pdfliteral direct {\breakboxcolori\space rg}% + \hrule height\fboxrule + \else + \pdfliteral direct {/TransparentBoxGS gs}% + \pdfliteral direct {\breakboxcolori\space rg}% + \hrule height\fboxrule + \fi + \pdfliteral direct {Q}% + \hbox{% + \pdfliteral direct {q}% + \pdfliteral direct {\breakboxcolori\space rg}% + \vrule width\fboxrule + \pdfliteral direct {/TransparentBoxGS gs}% + \pdfliteral direct {\breakboxcolori\space rg}% + \vrule width\bgw height\bgh depth0pt + \pdfliteral direct {Q}% + \kern-\bgw + \kern\fboxsep + \box0 + \kern\fboxsep + \pdfliteral direct {q}% + \pdfliteral direct {\breakboxcolori\space rg}% + \vrule width\fboxrule + \pdfliteral direct {Q}% + } + \pdfliteral direct {q}% + \ifend + \pdfliteral direct {\breakboxcolori\space rg}% + \hrule height\fboxrule + \else + \pdfliteral direct {/TransparentBoxGS gs}% + \pdfliteral direct {\breakboxcolori\space rg}% + \hrule height\fboxrule + \fi + \pdfliteral direct {Q}% + % }}} + \startfalse + \fi + \unless\ifvoid\innerbox + \eject + \repeat + \vskip8pt +} +% }}}1 + +% Theorems {{{1 +\newcount\thmnum +\thmnum=0 +\def\newthm#1#2{ + % \theorem + \expandafter\def\csname #2\endcsname{% + \global\advance\thmnum by1 + \def\tmp{\futurelet\next}% + \expandafter\tmp\csname #2i\endcsname + } + + % \theoremi + \expandafter\def\csname #2i\endcsname{% + \let\thmname=\relax + \def\tmpi[####1]{\def\thmname{####1}\csname #2ii\endcsname}% + \ifx\next[ + \expandafter\tmpi + \else + \csname #2ii\endcsname + \fi + } + + % \theoremii + \expandafter\def\csname #2ii\endcsname{% + \breakbox{#1} + {\bf \capitalize#2 \number\thmnum.} \ifx\thmname\relax\else{\bf(\thmname)}\fi% + } + + % \endtheorem + \expandafter\def\csname end#2\endcsname{% + \endbreakbox + } +} + + +\def\xthm#1#2,{ + \if\relax\detokenize{#2}\relax\else + \newthm{#1}{#2} + \def\tmpxthm{\xthm{#1}} + \expandafter\tmpxthm + \fi +} + +\newbox\noxthmbox +\def\newnoxthm#1{ + % \theorem + \expandafter\def\csname #1\endcsname{% + \global\advance\thmnum by1 + \def\tmp{\futurelet\next}% + \expandafter\tmp\csname #1i\endcsname + } + + % \theoremi + \expandafter\def\csname #1i\endcsname{% + \def\tmpi[####1]{\csname #1ii\endcsname}% + \ifx\next[ + \expandafter\tmpi + \else + \csname #1ii\endcsname + \fi + } + + % \theoremii + \expandafter\def\csname #1ii\endcsname{% + \setbox\noxthmbox=\vbox\bgroup + } + + % \endtheorem + \expandafter\def\csname end#1\endcsname{% + \egroup + } +} + +\def\noxthm#1#2,{ + \if\relax\detokenize{#2}\relax\else + \newnoxthm{#2} + \def\tmpnoxthm{\noxthm{#1}} + \expandafter\tmpnoxthm + \fi +} +\xthm{0.00 0.66 0.00}theorem,lemma,corollary,proposition,, +\xthm{1.00 0.35 0.00}definition,, +\xthm{1.00 0.00 1.00}example,problem,, +\xthm{0.00 0.58 1.00}question,paragraph,summary,observation,, +\xthm{0.63 0.56 0.45}proof,, + +%\noxthm{0.00 0.66 0.00}theorem,lemma,corollary,proposition,, +%\noxthm{1.00 0.35 0.00}definition,, +%\noxthm{1.00 0.00 1.00}example,problem,, +%\noxthm{0.00 0.58 1.00}question,paragraph,summary,observation,, +%\noxthm{0.63 0.56 0.45}proof,, +% }}}1 + +% jobname {{{1 +\edef\twocolumn{\detokenize{twocolumn}} +\edef\threecolumnL{\detokenize{threecolumnL}} +\edef\threecolumnP{\detokenize{threecolumnP}} +\edef\fourcolumn{\detokenize{fourcolumn}} +\edef\slides{\detokenize{slides}} +\edef\slidesfour{\detokenize{slidesfour}} +\edef\xjobname{\jobname} + +\newcount\numcol +\ifx\xjobname\twocolumn + \numcol=2 + \pdfpageheight=297mm + \pdfpagewidth=210mm +\else\ifx\xjobname\threecolumnL + \numcol=3 + \pdfpageheight=220.161mm + \pdfpagewidth=311.371mm + \mag=954 +\else\ifx\xjobname\threecolumnP + \numcol=3 + \pdfpageheight=452.461mm + \pdfpagewidth=319.922mm + \mag=656 +\else\ifx\xjobname\fourcolumn + \numcol=4 + \pdfpageheight=297mm + \pdfpagewidth=420mm + \mag=707 +\else\ifx\xjobname\slides + \numcol=2 + \pdfpageheight=118.125mm + \pdfpagewidth=210mm + \mag=762 +\else\ifx\xjobname\slidesfour + \numcol=4 + \pdfpageheight=236.25mm + \pdfpagewidth=420mm + \mag=707 +\else + \numcol=1 + \pdfpageheight=282mm + \pdfpagewidth=100mm +\fi\fi\fi\fi\fi\fi + +\ifx\xjobname\slides + \vsize=108.125mm +\else\ifx\xjobname\slidesfour + \vsize=220mm +\else\ifx\xjobname\threecolumnL + \vsize=203.387mm +\else\ifx\xjobname\threecolumnP + \vsize=428.086mm +\else + \vsize=281mm +\fi\fi\fi\fi +\hsize=97.5mm + +\hoffset=-1in +\voffset=-1in +% }}}1 + +% myoutput {{{1 +\countdef\pageno=0 +\pageno=1 +\newcount\curcol +\newcount\colbox +\newcount\firstbox +\firstbox=100 +\curcol=0 +\def\myoutput{% + \global\advance\curcol by1 + {% + \advance\curcol by\firstbox + \global\setbox\curcol=\box255 + \global\wd\curcol=\hsize + }% + \ifnum\curcol=\numcol + \shipout\vbox to \pdfpageheight {% + \vfil + \hbox to \pdfpagewidth {% + \colbox=0 + \hfil + \loop\ifnum\colbox<\numcol + \advance\colbox by1 + {% + \hfil + \advance\colbox by\firstbox + \box\colbox + }% + \repeat + \hfil\hfil + }% + \vfil + }% + \global\advance\pageno by1 + \global\curcol=0 + \fi +} + +\output{\myoutput}% +% }}}1 + +% if latex {{{1 +\newbox\tablebox +\newbox\tablerow +\newbox\tableshifted +\newdimen\tableskip +\newdimen\tablelastskip +\ifx\documentclass\undefined + % latex {{{2 + \def\textbf#1{{\bf #1}} + \def\textit#1{{\it #1}} + \def\mathrm#1{{\rm #1}} + \def\mathcal#1{{\cal#1}} + \def\frac#1#2{{#1\over#2}} + \def\emph#1{{\it#1}} + \def\:{\,\,} + \let\plainend=\end + \def\begin#1{\csname #1\endcsname} + \def\end#1{\csname end#1\endcsname} + \def\bye{\par\vfill\supereject\plainend} + \let\plainitem=\item + % \def\item{\parindent=20pt\plainitem{$\circ$}} + + \def\itemize{\bgroup\def\item{\parindent=20pt\plainitem{$\circ$}}\def\itemize{\bgroup\def\item{\parindent=40pt\plainitem{$\circ$}}}} + \def\enditemize{\par\egroup} + % }}}2 + + % amsmath {{{2 + \def\coloneqq{\mathrel{\mathop:}=} + \def\mathclap#1{\hbox to 0pt{\hss$#1$\hss}} + \def\mathllap{} + + \catcode`@=11 + \def\align{% + \bgroup + \openup\jot + \m@th + \def\\{\cr} + \setbox\tablebox=\vbox\bgroup\ialign\bgroup% + \strut$\hfil\displaystyle{##}$\tabskip=0pt&$\displaystyle{{}##}$\hfil\tabskip=0pt\crcr + } + \def\endalign{% + \crcr\egroup\egroup% + \tableskip=\hsize + \advance\tableskip by-\wd\tablebox + \divide\tableskip by2 + \ifdim\tableskip<0pt + \tableskip=0pt + \fi + \setbox\tableshifted=\vbox{}% + \setbox\tablebox=\vbox{% + \unvbox\tablebox + \loop + \tablelastskip=\lastskip + \unskip + \setbox\tablerow=\lastbox + \unless\ifvoid\tablerow + \setbox\tableshifted=\vbox{% + \hskip\tableskip\box\tablerow + \vskip\tablelastskip + \unvbox\tableshifted + }% + \repeat + \unvbox\tableshifted + }% + \vskip\abovedisplayskip + \unvbox\tablebox + \vskip\belowdisplayskip + \egroup + } + \catcode`@=12 + + \expandafter\let\csname align*\endcsname=\align + \expandafter\let\csname endalign*\endcsname=\endalign + \expandafter\let\csname gather*\endcsname=\align + \expandafter\let\csname endgather*\endcsname=\endalign + + \def\text#1{\hbox{#1}} + \def\operatorname#1{\mathop{\mathrm{#1}}} + + \def\overset#1#2{\mathop{#2}\limits^{#1}} + \def\underset#1#2{\mathop{#2}\limits_{#1}} + \def\binom#1#2{{#1\choose#2}} + + \def\lvert{|} + \def\rvert{|} + \def\lVert{\|} + \def\rVert{\|} + + \def\implies{\Longrightarrow} + \def\tag#1{\eqno(#1)} + + \def\({$} + \def\){$} + + \def\[{$$} + \def\]{$$} + + \def\xrightarrow#1{\mathrel{\buildrel #1\over\longrightarrow}} + + \font\sevenex=cmex7 + \scriptfont3=\sevenex + + \catcode`@=11 + \def\pmatrix{% + \bgroup + \left(% + \vcenter\bgroup + \normalbaselines + \m@th + \def\\{\cr}% + \ialign\bgroup + \hfil$##$\hfil&&\quad\hfil$##$\hfil\crcr + } + \def\endpmatrix{% + \crcr + \egroup + \egroup + \right)% + \egroup + } + \catcode`@=12 + % }}}2 + + % amssymb {{{2 + \font\tenbb=msbm10 + \font\sevenbb=msbm7 + \font\fivebb=msbm5 + + \newfam\bbfam + \textfont\bbfam=\tenbb + \scriptfont\bbfam=\sevenbb + \scriptscriptfont\bbfam=\fivebb + + \def\mathbb#1{\ifx1#11\hskip-4pt 1\else{\fam\bbfam#1}\fi} + % }}}2 + +\else % {{{2 + \AtBeginDocument{ + \baselineskip=12pt + \abovedisplayskip=1pt + \belowdisplayskip=1pt + \abovedisplayshortskip=2pt + \belowdisplayshortskip=2pt + \output{\myoutput}% + \overfullrule=5mm + + \ifx\xjobname\twocolumn + \pdfpageheight=297mm + \pdfpagewidth=210mm + \else\ifx\xjobname\fourcolumn + \pdfpageheight=297mm + \pdfpagewidth=420mm + \mag=707 + \else\ifx\xjobname\slides + \pdfpageheight=118.125mm + \pdfpagewidth=210mm + \mag=762 + \else + \pdfpageheight=282mm + \pdfpagewidth=100mm + \fi\fi\fi + + \ifx\xjobname\slides + \vsize=108.125mm + \else + \vsize=281mm + \fi + \hsize=97.5mm + \textwidth=97.5mm + \linewidth=97.5mm + } + + \AtEndDocument{ + \loop\ifnum\curcol>0 + \par\vbox{}\break + \repeat + } + + % list + \catcode`\@=11 + \def\@listi{\leftmargin\leftmargini + \parsep=0pt + \topsep=0pt + \itemsep=0pt + \partopsep=0pt} + \let\@listI\@listi + %\@listi + \def\@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep} + \def\@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep} + \def\@listiv {\leftmargin\leftmarginiv + \labelwidth\leftmarginiv + \advance\labelwidth-\labelsep} + \def\@listv {\leftmargin\leftmarginv + \labelwidth\leftmarginv + \advance\labelwidth-\labelsep} + \def\@listvi {\leftmargin\leftmarginvi + \labelwidth\leftmarginvi + \advance\labelwidth-\labelsep} + + \def\labelitemi{$\circ$} + \catcode`\@=12 + % }}}2 +\fi +% }}}1 + +\def\title#1\par{\breakbox{0.0 0 0}\tolerance=2000\bf#1\endbreakbox} + +% vim: fen fdm=marker ft=plaintex diff --git a/tex/chapter_01.tex b/tex/chapter_01.tex @@ -0,0 +1,751 @@ +\title Probability Theory + +\begin{paragraph}{1.4}{Why Conditional Expectations Are Needed} + In elementary probability, the conditional probability of an event \(B\) given an event \(A\) is defined as + \[ + P(B\mid A)=\frac{P(A\cap B)}{P(A)}, + \] + provided that \(P(A)>0\). In probability and statistics, however, we sometimes need a notion of conditional probability even for events \(A\) with \(P(A)=0\); for example, \(A=\{Y=c\}\), where \(c\in\mathbb{R}\) and \(Y\) is a random variable having a continuous c.d.f. +\end{paragraph} + +\begin{paragraph}{1.4}{Scope of Conditional Probability} + General definitions of conditional probability, expectation, and distribution are introduced in this section, and they are shown to agree with those defined in elementary probability in special cases. +\end{paragraph} + +\begin{definition}{1.6}{Conditional Expectation and Probability} + Let \(X\) be an integrable random variable on \((\Omega,\mathcal{F},P)\). + + \begin{itemize} + \item Let \(\mathcal{A}\) be a sub-\(\sigma\)-field of \(\mathcal{F}\). The conditional expectation of \(X\) given \(\mathcal{A}\), denoted by \(E(X\mid\mathcal{A})\), is the a.s.-unique random variable satisfying: + \begin{itemize} + \item \(E(X\mid\mathcal{A})\) is measurable from \((\Omega,\mathcal{A})\) to \((\mathbb{R},\mathcal{B})\); + \item \(\int_A E(X\mid\mathcal{A})\,dP=\int_A X\,dP\) for every \(A\in\mathcal{A}\). + \end{itemize} + The existence of \(E(X\mid\mathcal{A})\) follows from Theorem~1.4. + + \item Let \(B\in\mathcal{F}\). The conditional probability of \(B\) given \(\mathcal{A}\) is \(P(B\mid\mathcal{A})=E(I_B\mid\mathcal{A})\). + + \item Let \(Y\) be measurable from \((\Omega,\mathcal{F},P)\) to \((\Lambda,\mathcal{G})\). The conditional expectation of \(X\) given \(Y\) is + \[ + E(X\mid Y)=E[X\mid\sigma(Y)]. + \] + \end{itemize} +\end{definition} + +\begin{paragraph}{1.4.1}{Information in a Random Element} + Essentially, the \(\sigma\)-field \(\sigma(Y)\) contains ``the information in \(Y\).'' Hence, \(E(X\mid Y)\) is the expectation of \(X\) given the information provided by \(\sigma(Y)\). +\end{paragraph} + +\begin{paragraph}{1.4.1}{Representing Conditional Expectations} + The following useful result shows that there is a Borel function \(h\), defined on the range of \(Y\), such that \(E(X\mid Y)=h\circ Y\). +\end{paragraph} + +\begin{lemma}{1.2}{Measurable Functions of a Random Element} + Let \(Y\) be measurable from \((\Omega,\mathcal{F})\) to \((\Lambda,\mathcal{G})\), and let \(Z\) be a function from \((\Omega,\mathcal{F})\) to \((\mathbb{R}^k,\mathcal{B}^k)\). Then \(Z\) is measurable from \((\Omega,\sigma(Y))\) to \((\mathbb{R}^k,\mathcal{B}^k)\) if and only if there is a measurable function \(h\) from \((\Lambda,\mathcal{G})\) to \((\mathbb{R}^k,\mathcal{B}^k)\) such that \(Z=h\circ Y\). +\end{lemma} + +\begin{paragraph}{1.4.1}{Conditioning on a Value} + The function \(h\) in \(E(X\mid Y)=h\circ Y\) is a Borel function on \((\Lambda,\mathcal{G})\). For \(y\in\Lambda\), define + \[ + E(X\mid Y=y)=h(y). + \] + Thus \(h(y)\) is a function on \(\Lambda\), whereas \(h\circ Y=E(X\mid Y)\) is a function on \(\Omega\). +\end{paragraph} + +\begin{paragraph}{1.4.1}{Conditional Expectation of a Vector} + For a random vector \(X\), \(E(X\mid\mathcal{A})\) is defined as the vector of conditional expectations of the components of \(X\). +\end{paragraph} + +\begin{example}{1.21}{Conditioning on a Countable Partition} + Let \(X\) be an integrable random variable on \((\Omega,\mathcal{F},P)\). Let \(A_1,A_2,\ldots\) be disjoint events such that \(\bigcup_i A_i=\Omega\) and \(P(A_i)>0\) for every \(i\), and let \(a_1,a_2,\ldots\) be distinct real numbers. Define + \[ + Y=\sum_{i=1}^{\infty}a_iI_{A_i}. + \] + Then + \[ + E(X\mid Y) + = + \sum_{i=1}^{\infty} + \frac{\int_{A_i}X\,dP}{P(A_i)}I_{A_i}. + \tag{1.59} + \] + + We verify the two conditions in Definition~1.6 with \(\mathcal{A}=\sigma(Y)\). Since \(\sigma(Y)=\sigma(\{A_1,A_2,\ldots\})\), the right-hand side of (1.59) is measurable on \((\Omega,\sigma(Y))\). For every \(B\in\mathcal{B}\), + \[ + Y^{-1}(B)=\bigcup_{i:a_i\in B}A_i. + \] + Using properties of integrals, + \begin{align*} + \int_{Y^{-1}(B)}X\,dP + & =\sum_{i:a_i\in B}\int_{A_i}X\,dP \\ + & =\sum_{i=1}^{\infty} + \frac{\int_{A_i}X\,dP}{P(A_i)} + P\bigl(A_i\cap Y^{-1}(B)\bigr) \\ + & =\int_{Y^{-1}(B)} + \left[ + \sum_{i=1}^{\infty} + \frac{\int_{A_i}X\,dP}{P(A_i)}I_{A_i} + \right]dP. + \end{align*} + This verifies the second condition and proves (1.59). + + Let \(h\) be a Borel function on \(\mathbb{R}\) satisfying + \[ + h(a_i)=\frac{\int_{A_i}X\,dP}{P(A_i)}. + \] + Then \(E(X\mid Y)=h\circ Y\) and \(E(X\mid Y=y)=h(y)\). + + If \(A\in\mathcal{F}\) and \(X=I_A\), then + \[ + P(A\mid Y)=E(X\mid Y) + =\sum_{i=1}^{\infty}\frac{P(A\cap A_i)}{P(A_i)}I_{A_i}. + \] + For \(\omega\in A_i\), this equals \(P(A\cap A_i)/P(A_i)=P(A\mid A_i)\). Hence Definition~1.6 agrees with the elementary definition of conditional probability. +\end{example} + +\begin{proposition}{1.9}{Conditional Expectation from a Joint Density} + Let \(X\) be a random \(n\)-vector and \(Y\) a random \(m\)-vector. Suppose that \((X,Y)\) has a joint p.d.f. \(f(x,y)\) with respect to \(\nu\times\lambda\), where \(\nu\) and \(\lambda\) are \(\sigma\)-finite measures on \((\mathbb{R}^n,\mathcal{B}^n)\) and \((\mathbb{R}^m,\mathcal{B}^m)\), respectively. Let \(g(x,y)\) be a Borel function on \(\mathbb{R}^{n+m}\) for which \(E|g(X,Y)|<\infty\). Then + \[ + E[g(X,Y)\mid Y] + = + \frac{\int g(x,Y)f(x,Y)\,d\nu(x)} + {\int f(x,Y)\,d\nu(x)} + \quad\text{a.s.} + \tag{1.60} + \] +\end{proposition} + +\begin{proof}{1.9}{Proof via Fubini's Theorem} + Denote the right-hand side of (1.60) by \(h(Y)\). By Fubini's theorem, \(h\) is Borel, and Lemma~1.2 implies that \(h(Y)\) is Borel on \((\Omega,\sigma(Y))\). Also, + \[ + f_Y(y)=\int f(x,y)\,d\nu(x) + \] + is the p.d.f. of \(Y\) with respect to \(\lambda\). For \(B\in\mathcal{B}^m\), + \begin{align*} + \int_{Y^{-1}(B)}h(Y)\,dP + & =\int_B h(y)\,dP_Y(y) \\ + & =\int_B + \frac{\int g(x,y)f(x,y)\,d\nu(x)} + {\int f(x,y)\,d\nu(x)} + f_Y(y)\,d\lambda(y) \\ + & =\int_{\mathbb{R}^n\times B}g(x,y)f(x,y)\,d(\nu\times\lambda) \\ + & =\int_{\mathbb{R}^n\times B}g(x,y)\,dP_{(X,Y)} \\ + & =\int_{Y^{-1}(B)}g(X,Y)\,dP. + \end{align*} + The first and last equalities follow from Theorem~1.2, the second and fourth from the definitions of \(h\) and p.d.f.'s, and the third from Fubini's theorem. +\end{proof} + +\begin{definition}{1.4.1}{Conditional Density} + For a random vector \((X,Y)\) with joint p.d.f. \(f(x,y)\) with respect to \(\nu\times\lambda\), define the conditional p.d.f. of \(X\) given \(Y=y\) by + \[ + f_{X\mid Y}(x\mid y)=\frac{f(x,y)}{f_Y(y)}, + \tag{1.61} + \] + where + \[ + f_Y(y)=\int f(x,y)\,d\nu(x) + \] + is the marginal p.d.f. of \(Y\) with respect to \(\lambda\). For every fixed \(y\) with \(f_Y(y)>0\), \(f_{X\mid Y}(x\mid y)\) is a p.d.f. with respect to \(\nu\). +\end{definition} + +\begin{paragraph}{1.4.1}{Expectation under a Conditional Density} + Equation~(1.60) can be rewritten as + \[ + E[g(X,Y)\mid Y] + = + \int g(x,Y)f_{X\mid Y}(x\mid Y)\,d\nu(x). + \] + Thus the conditional expectation of \(g(X,Y)\) given \(Y\) equals its expectation with respect to the conditional p.d.f. of \(X\) given \(Y\), agreeing with elementary probability. +\end{paragraph} + +\begin{proposition}{1.10}{Properties of Conditional Expectations} + Let \(X,Y,X_1,X_2,\ldots\) be integrable random variables on \((\Omega,\mathcal{F},P)\), and let \(\mathcal{A}\) be a sub-\(\sigma\)-field of \(\mathcal{F}\). + + \begin{itemize} + \item If \(X=c\) a.s., where \(c\in\mathbb{R}\), then \(E(X\mid\mathcal{A})=c\) a.s. + \item If \(X\le Y\) a.s., then \(E(X\mid\mathcal{A})\le E(Y\mid\mathcal{A})\) a.s. + \item For \(a,b\in\mathbb{R}\), + \[ + E(aX+bY\mid\mathcal{A}) + =aE(X\mid\mathcal{A})+bE(Y\mid\mathcal{A}) + \quad\text{a.s.} + \] + \item \(E[E(X\mid\mathcal{A})]=EX\). + \item If \(\mathcal{A}_0\subset\mathcal{A}\), then + \begin{align*} + E[E(X\mid\mathcal{A})\mid\mathcal{A}_0] + & =E(X\mid\mathcal{A}_0) \\ + & =E[E(X\mid\mathcal{A}_0)\mid\mathcal{A}] + \quad\text{a.s.} + \end{align*} + + \item If \(\sigma(Y)\subset\mathcal{A}\) and \(E|XY|<\infty\), then + \[ + E(XY\mid\mathcal{A})=YE(X\mid\mathcal{A}) + \quad\text{a.s.} + \] + \item If \(X\) and \(Y\) are independent and \(E|g(X,Y)|<\infty\) for a Borel function \(g\), then + \[ + E[g(X,Y)\mid Y=y]=E[g(X,y)] + \quad\text{a.s. }P_Y. + \] + \item If \(EX^2<\infty\), then + \[ + [E(X\mid\mathcal{A})]^2\le E(X^2\mid\mathcal{A}) + \quad\text{a.s.} + \] + \item If \(X_n\ge0\), then the conditional Fatou lemma gives + \[ + E\left(\liminf_n X_n\mid\mathcal{A}\right) + \le\liminf_n E(X_n\mid\mathcal{A}) + \quad\text{a.s.} + \] + \item If \(|X_n|\le Y\) and \(X_n\to X\) a.s., then the conditional dominated convergence theorem gives + \[ + E(X_n\mid\mathcal{A})\to E(X\mid\mathcal{A}) + \quad\text{a.s.} + \] + + \end{itemize} +\end{proposition} + +\begin{paragraph}{1.4.1}{Further Convergence Properties} + Part (vii) of Proposition~1.10 follows from the more general Theorem~1.7(i). Since \(E(X\mid\mathcal{A})\) is defined only for integrable \(X\), conditional monotone convergence---if \(0\le X_1\le X_2\le\cdots\) and \(X_n\to X\) a.s., then \(E(X_n\mid\mathcal{A})\to E(X\mid\mathcal{A})\) a.s.---is a special case of Proposition~1.10(x). +\end{paragraph} + +\begin{paragraph}{1.4.1}{Conditional Inequalities} + Holder's inequality (1.40), Liapounov's inequality (1.42), Minkowski's inequality (1.43), and Jensen's inequality (1.47) also hold a.s. when \(E\) is replaced by \(E(\,\cdot\mid\mathcal{A})\). +\end{paragraph} + +\begin{example}{1.22}{Conditional Expectation as Best Predictor} + Let \(X\) be a random variable on \((\Omega,\mathcal{F},P)\) with \(EX^2<\infty\), and let \(Y\) be measurable from \((\Omega,\mathcal{F},P)\) to \((\Lambda,\mathcal{G})\). We wish to predict \(X\) from an observed value of \(Y\). Let + \[ + \mathcal{H} + = + \{g:\ g\text{ is Borel and }E[g(Y)^2]<\infty\}. + \] + A predictor \(g(Y)\) is assessed by its mean squared prediction error \(E[X-g(Y)]^2\). Then \(E(X\mid Y)\) is the best predictor: + \[ + E[X-E(X\mid Y)]^2 + = + \min_{g\in\mathcal{H}}E[X-g(Y)]^2. + \tag{1.62} + \] + + Proposition~1.10(viii) implies \(E(X\mid Y)\in\mathcal{H}\). For every \(g\in\mathcal{H}\), + \begin{align*} + E & [X-g(Y)]^2 = \\ + & =E[X-E(X\mid Y)+E(X\mid Y)-g(Y)]^2 \\ + & =E[X-E(X\mid Y)]^2+E[E(X\mid Y)-g(Y)]^2 \\ + & \quad+2E\{[X-E(X\mid Y)][E(X\mid Y)-g(Y)]\} \\ + & =E[X-E(X\mid Y)]^2+E[E(X\mid Y)-g(Y)]^2 \\ + & \quad+2E\!\left(E\{[X-E(X\mid Y)][E(X\mid Y)-g(Y)]\mid Y\}\right) \\ + & =E[X-E(X\mid Y)]^2+E[E(X\mid Y)-g(Y)]^2 \\ + & \quad+2E\{[E(X\mid Y)-g(Y)]E[X-E(X\mid Y)\mid Y]\} \\ + & =E[X-E(X\mid Y)]^2+E[E(X\mid Y)-g(Y)]^2 \\ + & \ge E[X-E(X\mid Y)]^2. + \end{align*} + The third equality follows from Proposition~1.10(iv), the fourth from Proposition~1.10(vi), and the last equality before the inequality from Proposition~1.10(i), (iii), and (vi). +\end{example} + +\begin{definition}{1.7}{Independence} + Let \((\Omega,\mathcal{F},P)\) be a probability space. + + \begin{itemize} + \item Let \(\mathcal{C}\) be a collection of sets in \(\mathcal{F}\). Events in \(\mathcal{C}\) are independent if and only if, for every positive integer \(n\) and distinct \(A_1,\ldots,A_n\in\mathcal{C}\), + \[ + P(A_1\cap\cdots\cap A_n)=P(A_1)\cdots P(A_n). + \] + \item Collections \(\mathcal{C}_i\subset\mathcal{F}\), \(i\in I\), are independent if and only if the events in every collection \(\{A_i\in\mathcal{C}_i:i\in I\}\) are independent. + \item Random elements \(X_i\), \(i\in I\), are independent if and only if the \(\sigma\)-fields \(\sigma(X_i)\), \(i\in I\), are independent. + \end{itemize} +\end{definition} + +\begin{paragraph}{1.4.2}{Checking Independence} + The following result is useful for checking the independence of \(\sigma\)-fields. +\end{paragraph} + +\begin{lemma}{1.3}{Independence of Generated Sigma-fields} + Let \(\mathcal{C}_i\), \(i\in I\), be independent collections of events. Suppose that every \(\mathcal{C}_i\) is closed under intersections: if \(A,B\in\mathcal{C}_i\), then \(A\cap B\in\mathcal{C}_i\). Then the \(\sigma\)-fields \(\sigma(\mathcal{C}_i)\), \(i\in I\), are independent. +\end{lemma} + +\begin{paragraph}{1.4.2}{Independence and Joint Distributions} + Lemma~1.3 immediately shows that random variables \(X_i\), \(i=1,\ldots,k\), are independent according to Definition~1.7 if and only if (1.7) holds, with \(F\) the joint c.d.f. of \((X_1,\ldots,X_k)\) and \(F_i\) the marginal c.d.f. of \(X_i\). Thus Definition~1.7(iii) agrees with the notion of independence in Section~1.3.1. +\end{paragraph} + +\begin{paragraph}{1.4.2}{Functions Preserve Independence} + Definition~1.7 also shows that if \(X\) and \(Y\) are independent random vectors, then \(g(X)\) and \(h(Y)\) are independent for every pair of Borel functions \(g\) and \(h\). This gives a simple proof of Lemma~1.1. +\end{paragraph} + +\begin{paragraph}{1.4.2}{Independence as No Information} + For events \(A\) and \(B\) with \(P(A)>0\), they are independent if and only if \(P(B\mid A)=P(B)\). Thus \(A\) provides no information about the probability that \(B\) occurs. The next proposition extends this fact. +\end{paragraph} + +\begin{proposition}{1.11}{Conditioning with Independent Information} + Let \(X\) be a random variable with \(E|X|<\infty\), and let \(Y_i\) be random \(k_i\)-vectors, \(i=1,2\). If \((X,Y_1)\) and \(Y_2\) are independent, then + \[ + E[X\mid(Y_1,Y_2)]=E(X\mid Y_1) + \quad\text{a.s.} + \] +\end{proposition} + +\begin{proof}{1.11}{Proof on Generating Rectangles} + First, \(E(X\mid Y_1)\) is Borel on \((\Omega,\sigma(Y_1,Y_2))\), since \(\sigma(Y_1)\subset\sigma(Y_1,Y_2)\). It remains to show that, for every \(B\in\mathcal{B}^{k_1+k_2}\), + \[ + \int_{(Y_1,Y_2)^{-1}(B)}X\,dP + = + \int_{(Y_1,Y_2)^{-1}(B)}E(X\mid Y_1)\,dP. + \tag{1.63} + \] + If \(B=B_1\times B_2\), with \(B_i\in\mathcal{B}^{k_i}\), then + \[ + (Y_1,Y_2)^{-1}(B)=Y_1^{-1}(B_1)\cap Y_2^{-1}(B_2) + \] + and + \begin{align*} + & \int_{Y_1^{-1}(B_1)\cap Y_2^{-1}(B_2)}E(X\mid Y_1)\,dP \\ + & \quad=\int I_{Y_1^{-1}(B_1)}I_{Y_2^{-1}(B_2)}E(X\mid Y_1)\,dP \\ + & \quad=\left[\int I_{Y_1^{-1}(B_1)}E(X\mid Y_1)\,dP\right] + \left[\int I_{Y_2^{-1}(B_2)}\,dP\right] \\ + & \quad=\left[\int I_{Y_1^{-1}(B_1)}X\,dP\right] + \left[\int I_{Y_2^{-1}(B_2)}\,dP\right] \\ + & \quad=\int I_{Y_1^{-1}(B_1)}I_{Y_2^{-1}(B_2)}X\,dP \\ + & \quad=\int_{Y_1^{-1}(B_1)\cap Y_2^{-1}(B_2)}X\,dP. + \end{align*} + The second and fourth equalities use (1.38) and the independence of \((X,Y_1)\) and \(Y_2\); the third uses the definition of \(E(X\mid Y_1)\). + + Thus (1.63) holds for rectangles. The collection + \[ + \mathcal{H} + = + \{B\subset\mathbb{R}^{k_1+k_2}:B\text{ satisfies (1.63)}\} + \] + is a \(\sigma\)-field. Since + \[ + \mathcal{B}^{k_1}\times\mathcal{B}^{k_2}\subset\mathcal{H}, + \] + we have + \[ + \mathcal{B}^{k_1+k_2} + = + \sigma(\mathcal{B}^{k_1}\times\mathcal{B}^{k_2}) + \subset\mathcal{H}, + \] + which proves the result. +\end{proof} + +\begin{paragraph}{1.4.2}{Conditional Probabilities under Independence} + Proposition~1.11 remains true with \(X\) replaced by \(h(X)\) for any Borel \(h\). Consequently, if \((X,Y_1)\) and \(Y_2\) are independent, then + \[ + P(A\mid Y_1,Y_2)=P(A\mid Y_1) + \quad\text{a.s. for every }A\in\sigma(X). + \tag{1.64} + \] + If \(Y_1\) is constant and \(Y=Y_2\), this becomes \(P(A\mid Y)=P(A)\) a.s. for every \(A\in\sigma(X)\). Thus \(\sigma(Y)\) supplies no additional information about the stochastic behavior of \(X\), giving another equivalent and more intuitive definition of independence. +\end{paragraph} + +\begin{paragraph}{1.4.2}{Conditional Independence} + For nonconstant \(Y_1\), \(X\) and \(Y_2\) are conditionally independent given \(Y_1\) if and only if (1.64) holds. Proposition~1.11 therefore says that if \(Y_2\) and \((X,Y_1)\) are independent, then \(X\) and \(Y_2\) are conditionally independent given \(Y_1\). The proposition may fail if \(Y_2\) is independent of \(X\) but not of \((X,Y_1)\); see Exercise~96. +\end{paragraph} + +\begin{paragraph}{1.4.3}{Conditional Distributions without Densities} + The conditional p.d.f. was introduced in Section~1.4.1 for random variables having p.d.f.'s with respect to specified measures. We now consider conditional distributions when no p.d.f. need exist. +\end{paragraph} + +\begin{paragraph}{1.4.3}{Need for a Regular Version} + For random vectors \(X\) and \(Y\) on a common probability space, it is natural to consider \(P[X^{-1}(B)\mid Y=y]\) as the conditional distribution of \(X\) given \(Y=y\). Since conditional probability is defined only almost surely, however, for a fixed \(y\) this expression need not be a probability measure. The next theorem gives a version that is a probability measure for every fixed \(y\). A proof is given in Billingsley (1986, pp.~460--461). +\end{paragraph} + +\begin{theorem}{1.7}{Existence of Conditional Distributions} + \begin{itemize} + \item Let \(X\) be a random \(n\)-vector on \((\Omega,\mathcal{F},P)\), and let \(\mathcal{A}\) be a sub-\(\sigma\)-field of \(\mathcal{F}\). There is a function \(P(B,\omega)\) on \(\mathcal{B}^n\times\Omega\) such that: + \begin{itemize} + \item \(P(B,\omega)=P[X^{-1}(B)\mid\mathcal{A}]\) a.s. for every fixed \(B\in\mathcal{B}^n\); + \item \(P(\,\cdot,\omega)\) is a probability measure on \((\mathbb{R}^n,\mathcal{B}^n)\) for every fixed \(\omega\in\Omega\). + \end{itemize} + + If \(Y\) is measurable from \((\Omega,\mathcal{F},P)\) to \((\Lambda,\mathcal{G})\), there is a function \(P_{X\mid Y}(B\mid y)\) such that: + \begin{itemize} + \item \(P_{X\mid Y}(B\mid y)=P[X^{-1}(B)\mid Y=y]\) a.s. \(P_Y\) for every fixed \(B\in\mathcal{B}^n\); + \item \(P_{X\mid Y}(\,\cdot\mid y)\) is a probability measure on \((\mathbb{R}^n,\mathcal{B}^n)\) for every fixed \(y\in\Lambda\). + \end{itemize} + + Furthermore, if \(g\) is Borel and \(E|g(X,Y)|<\infty\), then + \begin{align*} + E[g(X,Y)&\mid Y=y] = \\ + & =E[g(X,y)\mid Y=y] \\ + & =\int_{\mathbb{R}^n}g(x,y)\,dP_{X\mid Y}(x\mid y) + \quad\text{a.s. }P_Y. + \end{align*} + + \item Let \((\Lambda,\mathcal{G},P_1)\) be a probability space. Suppose \(P_2\) is a function from \(\mathcal{B}^n\times\Lambda\) to \(\mathbb{R}\) such that \(P_2(\,\cdot,y)\) is a probability measure on \((\mathbb{R}^n,\mathcal{B}^n)\) for every \(y\), and \(P_2(B,\,\cdot)\) is Borel for every \(B\in\mathcal{B}^n\). Then there is a unique probability measure \(P\) on \((\mathbb{R}^n\times\Lambda,\sigma(\mathcal{B}^n\times\mathcal{G}))\) such that + \[ + P(B\times C)=\int_C P_2(B,y)\,dP_1(y) + \tag{1.65} + \] + for \(B\in\mathcal{B}^n\) and \(C\in\mathcal{G}\). + + \hangindent\parindent If \((\Lambda,\mathcal{G})=(\mathbb{R}^m,\mathcal{B}^m)\), and \(X(x,y)=x\) and \(Y(x,y)=y\) are the coordinate random vectors, then \(P_Y=P_1\), \(P_{X\mid Y}(\,\cdot\mid y)=P_2(\,\cdot,y)\), and (1.65) defines the joint distribution of \((X,Y)\). Its joint c.d.f. is + + \begin{align*} + F(x,y) & = \int_{(-\infty,y]} P_{X\mid Y}\bigl((-\infty,x]\mid z\bigr)\,dP_Y(z) \ \ (1.66) \\ + & x\in\mathbb{R}^n,\ y\in\mathbb{R}^m. + \end{align*} + Here \((-\infty,a]=(-\infty,a_1]\times\cdots\times(-\infty,a_k]\) for \(a=(a_1,\ldots,a_k)\). + \end{itemize} +\end{theorem} + +\begin{definition}{1.4.3}{Conditional Distribution} + For fixed \(y\), + \[ + P_{X\mid Y=y}=P_{X\mid Y}(\,\cdot\mid y) + \] + is called the conditional distribution of \(X\) given \(Y=y\). Under Theorem~1.7(i), if \(Y\) is an \(m\)-vector and \((X,Y)\) has a p.d.f. with respect to \(\nu\times\lambda\), then \(f_{X\mid Y}(x\mid y)\) from (1.61) is the p.d.f. of \(P_{X\mid Y=y}\) with respect to \(\nu\). +\end{definition} + +\begin{paragraph}{1.4.3}{The Two-stage Experiment Theorem} + Theorem~1.7(ii) says that a distribution on one space and conditional distributions on a second space determine a joint distribution on the product space. If \(Y\in\mathbb{R}^m\) is selected in stage one according to \(P_Y=P_1\), and \(X\) is then selected according to \(P_2(\,\cdot,y)\), the combined experiment produces a jointly distributed pair \((X,Y)\) whose distribution is given by (1.65), with \(P_{X\mid Y=y}=P_2(\,\cdot,y)\). This gives a way to generate dependent random variables. +\end{paragraph} + +\begin{example}{1.23}{A Market Survey} + A mail survey asks \(N\) randomly selected customers whether a new product is better than the old one. A response is \(1\) if the new product is preferred and \(0\) otherwise; some customers do not respond. Let \(X\) be the number of ones among the returned questionnaires. + + If every customer responds, then \(X\) has the binomial distribution \(\operatorname{Bi}(p,N)\), assuming independent responses, where \(p\in(0,1)\) is the overall preference rate. Let \(Y\) be the number who respond. Suppose customers respond independently with probability \(\pi\in(0,1)\). Then + \[ + Y\sim\operatorname{Bi}(\pi,N). + \] + Given \(Y=y\), \(P_{X\mid Y=y}\) is \(\operatorname{Bi}(p,y)\) for \(y\ge1\), and is point mass at \(0\) for \(y=0\). + + Using (1.66) and counting measure, the joint c.d.f. is + \begin{align*} + F(x,y) + & =\sum_{k=0}^{y} + P_{X\mid Y=k}((-\infty,x]) + \binom Nk\pi^k(1-\pi)^{N-k} \\ + & =\sum_{k=0}^{y}\sum_{j=0}^{\min\{x,k\}} + \binom kjp^j(1-p)^{k-j} + \binom Nk\pi^k(1-\pi)^{N-k}, + \end{align*} + for \(x=0,1,\ldots,y\) and \(y=0,1,\ldots,N\). + + The marginal c.d.f. is \(F_X(x)=F(x,\infty)=F(x,N)\). Its p.d.f. with respect to counting measure is + \begin{align*} + f_X(x) + & =\sum_{k=x}^{N} + \binom{k}{x}p^x(1-p)^{k-x} + \binom Nk\pi^k(1-\pi)^{N-k} \\ + & =\binom Nx(\pi p)^x(1-\pi p)^{N-x}, + \end{align*} + for \(x=0,1,\ldots,N\). Thus \(X\sim\operatorname{Bi}(\pi p,N)\). +\end{example} + +\begin{paragraph}{1.4.1}{Conditional Expectations from Densities} + The next result generalizes Example~1.21 to conditional expectations of random variables having p.d.f.'s. +\end{paragraph} + +\begin{paragraph}{1.4.4}{Dependent Sequences} + As applications of conditional expectations, we introduce two important types of dependent sequences: Markov chains and martingales. +\end{paragraph} + +\begin{definition}{1.4.4}{Markov Chain} + A sequence of random vectors \(\{X_n:n=1,2,\ldots\}\) is a Markov chain, or Markov process, if and only if + \[ + P(B\mid X_1,\ldots,X_n)=P(B\mid X_n) + \quad\text{a.s.}, + \quad + B\in\sigma(X_{n+1}),\ n=2,3,\ldots. + \tag{1.67} + \] +\end{definition} + +\begin{paragraph}{1.4.4}{The Markov Property} + Comparing (1.67) with (1.64), \(X_{n+1}\), representing tomorrow, is conditionally independent of \((X_1,\ldots,X_{n-1})\), representing the past, given \(X_n\), representing today. However, \((X_1,\ldots,X_{n-1})\) need not be independent of \((X_n,X_{n+1})\). +\end{paragraph} + +\begin{paragraph}{1.4.4}{Independent Sequences Are Markov} + Every sequence of independent random vectors is a Markov chain: Proposition~1.11 shows that both sides of (1.67) equal \(P(B)\). The next example gives dependent Markov processes. +\end{paragraph} + +\begin{example}{1.24}{First-order Autoregressive Processes} + Let \(\varepsilon_1,\varepsilon_2,\ldots\) be independent random variables, let \(X_1=\varepsilon_1\), and define + \[ + X_{n+1}=\rho X_n+\varepsilon_{n+1}, + \quad n=1,2,\ldots, + \] + where \(\rho\in\mathbb{R}\). This is a first-order autoregressive process. For \(B\in\mathcal{B}\), + \begin{align*} + P(X_{n+1}\in B\mid X_1,\ldots,X_n) + & =P_{\varepsilon_{n+1}}(B-\rho X_n) \\ + & =P(X_{n+1}\in B\mid X_n) + \quad\text{a.s.}, + \end{align*} + where \(B-y=\{x\in\mathbb{R}:x+y\in B\}\); hence \(\{X_n\}\) is a Markov chain. + + For \(y\in\mathbb{R}\), + \[ + P_{\varepsilon_{n+1}}(B-y) + =P(\varepsilon_{n+1}+y\in B) + =\int I_B(x+y)\,dP_{\varepsilon_{n+1}}(x). + \] + Fubini's theorem implies that this is Borel in \(y\). Therefore \(P_{\varepsilon_{n+1}}(B-\rho X_n)\) is Borel with respect to \(\sigma(X_n)\), and hence with respect to \(\sigma(X_1,\ldots,X_n)\). + + Let \(B_j\in\mathcal{B}\), \(j=1,\ldots,n\), and + \[ + A=\bigcap_{j=1}^n X_j^{-1}(B_j). + \] + Since \(X_{n+1}=\varepsilon_{n+1}+\rho X_n\) and \(\varepsilon_{n+1}\) is independent of \((X_1,\ldots,X_n)\), Theorem~1.2 and Fubini's theorem give + \begin{align*} + \int_A & P_{\varepsilon_{n+1}}(B-\rho X_n)\,dP= \\ + & =\int_{x_j\in B_j,\ j=1,\ldots,n,t\in B-\rho x_n} + dP_{\varepsilon_{n+1}}(t)\,dP_X(x) \\ + & =\int_{x_j\in B_j,\ j=1,\ldots,n,x_{n+1}\in B} + dP_{(X,\varepsilon_{n+1})}(x,t) \\ + & =P\bigl(A\cap X_{n+1}^{-1}(B)\bigr), + \end{align*} + where \(X=(X_1,\ldots,X_n)\), \(x=(x_1,\ldots,x_n)\), and \(x_{n+1}=\rho x_n+t\). The final argument in the proof of Proposition~1.11 now gives + \[ + P(X_{n+1}\in B\mid X_1,\ldots,X_n) + =P_{\varepsilon_{n+1}}(B-\rho X_n) + \quad\text{a.s.} + \] + The proof that the latter equals \(P(X_{n+1}\in B\mid X_n)\) a.s. is similar and simpler. +\end{example} + +\begin{proposition}{1.12}{Characterizations of Markov Chains} + A sequence \(\{X_n\}\) is a Markov chain if and only if any one of the following conditions holds: + + \begin{itemize} + \item For every \(n\ge2\) and every integrable \(h(X_{n+1})\), with \(h\) Borel, + \[ + E[h(X_{n+1})\mid X_1,\ldots,X_n] + =E[h(X_{n+1})\mid X_n] + \quad\text{a.s.} + \] + \item For every \(n\ge1\) and \(B\in\sigma(X_{n+1},X_{n+2},\ldots)\), + \[ + P(B\mid X_1,\ldots,X_n)=P(B\mid X_n) + \quad\text{a.s.} + \] + \item For every \(n\ge2\), \(A\in\sigma(X_1,\ldots,X_n)\), and \(B\in\sigma(X_{n+1},X_{n+2},\ldots)\), + \[ + P(A\cap B\mid X_n) + =P(A\mid X_n)P(B\mid X_n) + \quad\text{a.s.} + \] + \end{itemize} +\end{proposition} + +\begin{proof}{1.12}{Proof of the Characterizations} + First, condition (a) clearly implies (1.67). Conversely, (1.67) implies (a) for simple \(h\) by Proposition~1.10(iii). For nonnegative \(h\), choose nonnegative simple functions \(h_1\le h_2\le\cdots\le h\) with \(h_j\to h\), and apply Proposition~1.10(iii) and (x). The general case follows from \(h=h^+-h^-\). + + Condition (b) clearly implies (1.67). Conversely, + \[ + \sigma(X_{n+1},X_{n+2},\ldots) + = + \sigma\left(\bigcup_{j=1}^{\infty}\sigma(X_{n+1},\ldots,X_{n+j})\right). + \] + It therefore suffices to prove (b) for \(B\in\sigma(X_{n+1},\ldots,X_{n+j})\), by induction on \(j\). The case \(j=1\) is (1.67). The induction hypothesis also gives + \begin{align*} + E[h(X_{n+1},\ldots,X_{n+j})&\mid X_1,\ldots,X_n] = \\ + & =E[h(X_{n+1},\ldots,X_{n+j})\mid X_n] \ \ (1.68) + \end{align*} + for every Borel \(h\). + + For \(B_1\in\sigma(X_{n+j+1})\) and \(B_2\in\sigma(X_{n+1},\ldots,X_{n+j})\), + \begin{align*} + E & (I_{B_1}I_{B_2}\mid X_1,\ldots,X_n)= \\ + & =E[E(I_{B_1}I_{B_2}\mid X_1,\ldots,X_{n+j})\mid X_1,\ldots,X_n] \\ + & =E[I_{B_2}E(I_{B_1}\mid X_1,\ldots,X_{n+j})\mid X_1,\ldots,X_n] \\ + & =E[I_{B_2}E(I_{B_1}\mid X_{n+j})\mid X_1,\ldots,X_n] \\ + & =E[I_{B_2}E(I_{B_1}\mid X_{n+j})\mid X_n] \\ + & =E[I_{B_2}E(I_{B_1}\mid X_n,\ldots,X_{n+j})\mid X_n] \\ + & =E[E(I_{B_1}I_{B_2}\mid X_n,\ldots,X_{n+j})\mid X_n] \\ + & =E(I_{B_1}I_{B_2}\mid X_n) + \quad\text{a.s.} + \end{align*} + Here the first and last equalities use Proposition~1.10(v), the second and sixth use Proposition~1.10(vi), the third and fifth use (1.67), and the fourth uses (1.68). This completes the induction. + + If (b) holds, then for \(A\in\sigma(X_1,\ldots,X_n)\) and \(B\) in the future \(\sigma\)-field, + \begin{align*} + E(I_AI_B\mid X_n) + & =E[E(I_AI_B\mid X_1,\ldots,X_n)\mid X_n] \\ + & =E[I_AE(I_B\mid X_1,\ldots,X_n)\mid X_n] \\ + & =E[I_AE(I_B\mid X_n)\mid X_n] \\ + & =E(I_A\mid X_n)E(I_B\mid X_n), + \end{align*} + which is (c). + + Conversely, assume (c). Let \(A_1\in\sigma(X_n)\), \(A_2\in\sigma(X_1,\ldots,X_{n-1})\), and \(B\in\sigma(X_{n+1},X_{n+2},\ldots)\). Then + \begin{align*} + \int_{A_1\cap A_2}E(I_B\mid X_n)\,dP + & =\int_{A_1}I_{A_2}E(I_B\mid X_n)\,dP \\ + & =\int_{A_1}E[I_{A_2}E(I_B\mid X_n)\mid X_n]\,dP \\ + & =\int_{A_1}E(I_{A_2}\mid X_n)E(I_B\mid X_n)\,dP \\ + & =\int_{A_1}E(I_{A_2}I_B\mid X_n)\,dP \\ + & =P(A_1\cap A_2\cap B). + \end{align*} + Disjoint unions of events \(A_1\cap A_2\) generate \(\sigma(X_1,\ldots,X_n)\), so \(E(I_B\mid X_n)=E(I_B\mid X_1,\ldots,X_n)\) a.s., proving (b). +\end{proof} + +\begin{paragraph}{1.4.4}{Past and Future Given the Present} + Condition (b) of Proposition~1.12 says that the past and future are conditionally independent given the present. This is a property of every Markov chain. More discussion and applications appear in Section~4.1.4. +\end{paragraph} + +\begin{definition}{1.4.4}{Martingales} + Let \(\{X_n\}\) be integrable random variables on \((\Omega,\mathcal{F},P)\), and let + \[ + \mathcal{F}_1\subset\mathcal{F}_2\subset\cdots\subset\mathcal{F} + \] + with \(\sigma(X_n)\subset\mathcal{F}_n\). The sequence \(\{X_n,\mathcal{F}_n:n=1,2,\ldots\}\) is a martingale if and only if + \[ + E(X_{n+1}\mid\mathcal{F}_n)=X_n + \quad\text{a.s.},\quad n=1,2,\ldots. + \tag{1.69} + \] + It is a submartingale if equality is replaced by \(\ge\), and a supermartingale if equality is replaced by \(\le\). The sequence \(\{X_n\}\) itself is called a martingale, submartingale, or supermartingale when the filtration is \(\sigma(X_1,\ldots,X_n)\). Proposition~1.10(v) shows that if \(\{X_n,\mathcal{F}_n\}\) has one of these properties, then so does \(\{X_n\}\). +\end{definition} + +\begin{paragraph}{1.4.4}{Basic Martingale Properties} + For a martingale \(\{X_n,\mathcal{F}_n\}\), + \[ + E(X_{n+j}\mid\mathcal{F}_n)=X_n + \quad\text{and}\quad + EX_1=EX_j. + \] + For a submartingale the corresponding statements are + \[ + E(X_{n+j}\mid\mathcal{F}_n)\ge X_n + \quad\text{and}\quad + EX_1\le EX_2\le\cdots. + \] + These hold for every \(j=1,2,\ldots\). +\end{paragraph} + +\begin{paragraph}{1.4.4}{Constructing Martingales} + Given \(\mathcal{F}_1\subset\mathcal{F}_2\subset\cdots\subset\mathcal{F}\) and an integrable \(Y\), the sequence \(\{E(Y\mid\mathcal{F}_n)\}\) is a martingale. Another construction uses independent integrable random variables \(\{\varepsilon_n\}\) and + \[ + X_n=\varepsilon_1+\cdots+\varepsilon_n. + \] + Since + \[ + E(X_{n+1}\mid X_1,\ldots,X_n) + =X_n+E\varepsilon_{n+1} + \quad\text{a.s.}, + \] + \(\{X_n\}\) is a martingale if \(E\varepsilon_n=0\), a submartingale if \(E\varepsilon_n\ge0\), and a supermartingale if \(E\varepsilon_n\le0\), for every \(n\). Example~1.24 with \(\rho=1\) also shows that \(\{X_n\}\) is a Markov chain. +\end{paragraph} + +\begin{paragraph}{1.4.4}{Another Martingale Example} + The next example gives another construction of martingales. +\end{paragraph} + +\begin{example}{1.25}{Likelihood Ratio Martingale} + Let \((\Omega,\mathcal{F},P)\) be a probability space, let \(Q\) be another probability measure on \(\mathcal{F}\), and let \(\mathcal{F}_1\subset\mathcal{F}_2\subset\cdots\subset\mathcal{F}\). Write \(P_n\) and \(Q_n\) for the restrictions of \(P\) and \(Q\) to \(\mathcal{F}_n\). If \(Q_n\ll P_n\) for every \(n\), then + \[ + X_n=\frac{dQ_n}{dP_n} + \] + defines a martingale \(\{X_n,\mathcal{F}_n\}\). + + Now suppose \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\), and there is a \(\sigma\)-finite measure \(\nu_n\) on \(\mathcal{F}_n\) such that \(P_n\ll\nu_n\ll P_n\). Define + \[ + p_n(Y_1,\ldots,Y_n)=\frac{dP_n}{d\nu_n}, + \qquad + q_n(Y_1,\ldots,Y_n)=\frac{dQ_n}{d\nu_n}. + \] + By Proposition~1.7(iii), + \[ + X_n + = + \frac{q_n(Y_1,\ldots,Y_n)} + {p_n(Y_1,\ldots,Y_n)}, + \] + which is called a likelihood ratio in statistics. +\end{example} + +\begin{paragraph}{1.4.4}{Functions of Martingales} + The following results give useful properties of martingales and submartingales. +\end{paragraph} + +\begin{proposition}{1.13}{Convex Functions of Martingales} + Let \(\phi\) be convex on \(\mathbb{R}\). + + \begin{itemize} + \item If \(\{X_n,\mathcal{F}_n\}\) is a martingale and \(\phi(X_n)\) is integrable for every \(n\), then \(\{\phi(X_n),\mathcal{F}_n\}\) is a submartingale. + \item If \(\{X_n,\mathcal{F}_n\}\) is a submartingale, \(\phi(X_n)\) is integrable for every \(n\), and \(\phi\) is nondecreasing, then \(\{\phi(X_n),\mathcal{F}_n\}\) is a submartingale. + \end{itemize} +\end{proposition} + +\begin{proof}{1.13}{Proof by Conditional Jensen} + For the first part, + \[ + \phi(X_n) + =\phi(E(X_{n+1}\mid\mathcal{F}_n)) + \le E[\phi(X_{n+1})\mid\mathcal{F}_n] + \quad\text{a.s.} + \] + by Jensen's inequality for conditional expectations. For the second, monotonicity and the submartingale property give + \[ + \phi(X_n) + \le\phi(E(X_{n+1}\mid\mathcal{F}_n)) + \le E[\phi(X_{n+1})\mid\mathcal{F}_n] + \quad\text{a.s.} + \] +\end{proof} + +\begin{paragraph}{1.4.4}{Examples of Convex Transformations} + Proposition~1.13 shows that if \(\{X_n,\mathcal{F}_n\}\) is a submartingale, then so is \(\{X_n^+,\mathcal{F}_n\}\). If it is a martingale, then \(\{|X_n|,\mathcal{F}_n\}\), \(\{|X_n|^p,\mathcal{F}_n\}\) for \(p>1\), and \(\{|X_n|(\log|X_n|)^+,\mathcal{F}_n\}\) are submartingales whenever the displayed random variables are integrable. +\end{paragraph} + +\begin{proposition}{1.14}{Doob's Decomposition} + Let \(\{X_n,\mathcal{F}_n\}\) be a submartingale. Then + \[ + X_n=Y_n+Z_n,\quad n=1,2,\ldots, + \] + where \(\{Y_n,\mathcal{F}_n\}\) is a martingale, + \[ + 0=Z_1\le Z_2\le\cdots, + \] + and \(EZ_n<\infty\) for every \(n\). If \(\sup_nE|X_n|<\infty\), then + \[ + \sup_nE|Y_n|<\infty + \quad\text{and}\quad + \sup_nEZ_n<\infty. + \] +\end{proposition} + +\begin{proof}{1.14}{Proof of Doob's Decomposition} + Define + \[ + \eta_1=X_1,\qquad \zeta_1=0, + \] + and, for \(n\ge2\), + \begin{align*} + \eta_n & =X_n-X_{n-1}-E(X_n-X_{n-1}\mid\mathcal{F}_{n-1}) \\ + \zeta_n & =E(X_n-X_{n-1}\mid\mathcal{F}_{n-1}). + \end{align*} + Then + \[ + Y_n=\sum_{i=1}^n\eta_i, + \qquad + Z_n=\sum_{i=1}^n\zeta_i + \] + satisfy \(X_n=Y_n+Z_n\) and the required conditions. + + If \(\sup_nE|X_n|<\infty\), then \(EY_1=EY_n\) and \(Z_n\le|X_n|-Y_n\), so + \[ + EZ_n\le E|X_n|-EY_1. + \] + Hence \(\sup_nEZ_n<\infty\). Since \(|Y_n|\le|X_n|+Z_n\), it also follows that \(\sup_nE|Y_n|<\infty\). +\end{proof} + +\begin{paragraph}{1.4.4}{Doob's Convergence Theorem} + The following martingale convergence theorem, due to Doob, has many applications; see, for example, Example~1.27 in Section~1.5.1. A proof is given in Billingsley (1986, pp.~490--491). +\end{paragraph} + +\begin{proposition}{1.15}{Martingale Convergence} + Let \(\{X_n,\mathcal{F}_n\}\) be a submartingale. If + \[ + c=\sup_nE|X_n|<\infty, + \] + then \(X_n\to X\) a.s. for a random variable \(X\) satisfying \(E|X|\le c\). +\end{proposition}