diff --git a/Lectures_my/MC_2016/Lecture7/mchrzasz.log b/Lectures_my/MC_2016/Lecture7/mchrzasz.log index f4a4acc..57f0f6c 100644 --- a/Lectures_my/MC_2016/Lecture7/mchrzasz.log +++ b/Lectures_my/MC_2016/Lecture7/mchrzasz.log @@ -1,4 +1,4 @@ -This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 13 APR 2016 11:56 +This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 15 APR 2016 22:48 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -3232,12 +3232,12 @@ Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 704. ) Here is how much of TeX's memory you used: - 50440 strings out of 493918 - 989704 string characters out of 6150564 + 50415 strings out of 493918 + 988964 string characters out of 6150564 1340103 words of memory out of 5000000 - 52700 multiletter control sequences out of 15000+600000 + 52675 multiletter control sequences out of 15000+600000 37184 words of font info for 148 fonts, out of 8000000 for 9000 1144 hyphenation exceptions out of 8191 - 55i,19n,77p,10405b,1477s stack positions out of 5000i,500n,10000p,200000b,80000s + 55i,19n,77p,10405b,1480s stack positions out of 5000i,500n,10000p,200000b,80000s Output written on mchrzasz.pdf (21 pages). diff --git a/Lectures_my/MC_2016/Lecture7/mchrzasz.pdf b/Lectures_my/MC_2016/Lecture7/mchrzasz.pdf index fd28d42..6b83833 100644 --- a/Lectures_my/MC_2016/Lecture7/mchrzasz.pdf +++ b/Lectures_my/MC_2016/Lecture7/mchrzasz.pdf Binary files differ diff --git a/Lectures_my/MC_2016/Lecture7/mchrzasz.synctex.gz b/Lectures_my/MC_2016/Lecture7/mchrzasz.synctex.gz index 8ec1578..187b545 100644 --- a/Lectures_my/MC_2016/Lecture7/mchrzasz.synctex.gz +++ b/Lectures_my/MC_2016/Lecture7/mchrzasz.synctex.gz Binary files differ diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.aux b/Lectures_my/MC_2016/Lecture8/mchrzasz.aux index 55cf10a..121b992 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.aux +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.aux @@ -59,78 +59,117 @@ \pgfsyspdfmark {pgfid16}{0}{0} \HyPL@Entry{5<>} \pgfsyspdfmark {pgfid17}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{6}{6/6}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {6}{6}}} \pgfsyspdfmark {pgfid18}{0}{0} \pgfsyspdfmark {pgfid19}{0}{0} -\HyPL@Entry{6<>} \pgfsyspdfmark {pgfid20}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{7}{7/7}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {7}{7}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{6}{6/7}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {6}{7}}} \pgfsyspdfmark {pgfid21}{0}{0} \pgfsyspdfmark {pgfid22}{0}{0} -\HyPL@Entry{7<>} +\HyPL@Entry{7<>} \pgfsyspdfmark {pgfid23}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{8}{8/8}{}{0}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{7}{8/8}{}{0}}} \@writefile{nav}{\headcommand {\beamer@framepages {8}{8}}} \pgfsyspdfmark {pgfid24}{0}{0} \pgfsyspdfmark {pgfid25}{0}{0} -\HyPL@Entry{8<>} +\HyPL@Entry{8<>} \pgfsyspdfmark {pgfid26}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{9}{9/9}{}{0}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{8}{9/9}{}{0}}} \@writefile{nav}{\headcommand {\beamer@framepages {9}{9}}} \pgfsyspdfmark {pgfid27}{0}{0} \pgfsyspdfmark {pgfid28}{0}{0} -\HyPL@Entry{9<>} +\HyPL@Entry{9<>} \pgfsyspdfmark {pgfid29}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{10}{10/10}{}{0}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{9}{10/10}{}{0}}} \@writefile{nav}{\headcommand {\beamer@framepages {10}{10}}} \pgfsyspdfmark {pgfid30}{0}{0} \pgfsyspdfmark {pgfid31}{0}{0} -\HyPL@Entry{10<>} +\HyPL@Entry{10<>} \pgfsyspdfmark {pgfid32}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{11}{11/11}{}{0}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{10}{11/11}{}{0}}} \@writefile{nav}{\headcommand {\beamer@framepages {11}{11}}} \pgfsyspdfmark {pgfid33}{0}{0} \pgfsyspdfmark {pgfid34}{0}{0} -\HyPL@Entry{11<>} -\pgfsyspdfmark {pgfid35}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{12}{12/12}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {12}{12}}} -\pgfsyspdfmark {pgfid36}{0}{0} -\pgfsyspdfmark {pgfid37}{0}{0} -\HyPL@Entry{12<>} +\HyPL@Entry{11<>} \pgfsyspdfmark {pgfid38}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{13}{13/13}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {13}{13}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{11}{12/12}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {12}{12}}} \pgfsyspdfmark {pgfid39}{0}{0} \pgfsyspdfmark {pgfid40}{0}{0} -\HyPL@Entry{13<>} +\HyPL@Entry{12<>} \pgfsyspdfmark {pgfid41}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{14}{14/14}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {14}{14}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{12}{13/13}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {13}{13}}} \pgfsyspdfmark {pgfid42}{0}{0} \pgfsyspdfmark {pgfid43}{0}{0} -\HyPL@Entry{14<>} +\HyPL@Entry{13<>} \pgfsyspdfmark {pgfid44}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{15}{15/15}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {15}{15}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{13}{14/14}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {14}{14}}} \pgfsyspdfmark {pgfid45}{0}{0} \pgfsyspdfmark {pgfid46}{0}{0} -\HyPL@Entry{15<>} +\HyPL@Entry{14<>} \pgfsyspdfmark {pgfid47}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{16}{16/16}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {16}{16}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{14}{15/15}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {15}{15}}} \pgfsyspdfmark {pgfid48}{0}{0} \pgfsyspdfmark {pgfid49}{0}{0} -\HyPL@Entry{16<>} +\HyPL@Entry{15<>} \pgfsyspdfmark {pgfid50}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{17}{17/17}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {17}{17}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{15}{16/16}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {16}{16}}} \pgfsyspdfmark {pgfid51}{0}{0} \pgfsyspdfmark {pgfid52}{0}{0} -\@writefile{nav}{\headcommand {\beamer@partpages {1}{17}}} -\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{17}}} -\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{17}}} -\@writefile{nav}{\headcommand {\beamer@documentpages {17}}} -\@writefile{nav}{\headcommand {\def \inserttotalframenumber {16}}} +\HyPL@Entry{16<>} +\pgfsyspdfmark {pgfid53}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{16}{17/17}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {17}{17}}} +\pgfsyspdfmark {pgfid54}{0}{0} +\pgfsyspdfmark {pgfid55}{0}{0} +\HyPL@Entry{17<>} +\pgfsyspdfmark {pgfid56}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{17}{18/18}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {18}{18}}} +\pgfsyspdfmark {pgfid57}{0}{0} +\pgfsyspdfmark {pgfid58}{0}{0} +\HyPL@Entry{18<>} +\pgfsyspdfmark {pgfid59}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{18}{19/19}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {19}{19}}} +\pgfsyspdfmark {pgfid60}{0}{0} +\pgfsyspdfmark {pgfid61}{0}{0} +\HyPL@Entry{19<>} +\pgfsyspdfmark {pgfid62}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{19}{20/20}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {20}{20}}} +\pgfsyspdfmark {pgfid63}{0}{0} +\pgfsyspdfmark {pgfid64}{0}{0} +\HyPL@Entry{20<>} +\pgfsyspdfmark {pgfid65}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{20}{21/21}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {21}{21}}} +\pgfsyspdfmark {pgfid66}{0}{0} +\pgfsyspdfmark {pgfid67}{0}{0} +\HyPL@Entry{21<>} +\pgfsyspdfmark {pgfid68}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{21}{22/22}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {22}{22}}} +\pgfsyspdfmark {pgfid69}{0}{0} +\pgfsyspdfmark {pgfid70}{0}{0} +\HyPL@Entry{22<>} +\pgfsyspdfmark {pgfid71}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{22}{23/23}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {23}{23}}} +\pgfsyspdfmark {pgfid72}{0}{0} +\pgfsyspdfmark {pgfid73}{0}{0} +\HyPL@Entry{23<>} +\pgfsyspdfmark {pgfid74}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{23}{24/24}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {24}{24}}} +\pgfsyspdfmark {pgfid75}{0}{0} +\pgfsyspdfmark {pgfid76}{0}{0} +\@writefile{nav}{\headcommand {\beamer@partpages {1}{24}}} +\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{24}}} +\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{24}}} +\@writefile{nav}{\headcommand {\beamer@documentpages {24}}} +\@writefile{nav}{\headcommand {\def \inserttotalframenumber {22}}} diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.log b/Lectures_my/MC_2016/Lecture8/mchrzasz.log index e55ef39..0122aaf 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.log +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.log @@ -1,4 +1,4 @@ -This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 26 NOV 2015 11:03 +This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 16 APR 2016 23:37 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -2396,7 +2396,11 @@ ))) Package hyperref Warning: Token not allowed in a PDF string (Unicode): -(hyperref) removing `\fontspec' on input line 207. +(hyperref) removing `\fontspec' on input line 212. + + +Package hyperref Warning: Token not allowed in a PDF string (Unicode): +(hyperref) removing `\fontspec' on input line 219. Package biblatex Info: Trying to load language 'english'... Package biblatex Info: ... file 'english.lbx' found. @@ -2416,40 +2420,40 @@ (./mchrzasz.aux) \openout1 = `mchrzasz.aux'. -LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for PU/pdf/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for OT4/cmr/m/n on input line 213. -LaTeX Font Info: Try loading font information for OT4+cmr on input line 213. +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for PU/pdf/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for OT4/cmr/m/n on input line 225. +LaTeX Font Info: Try loading font information for OT4+cmr on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/polski/ot4cmr.fd File: ot4cmr.fd 2008/02/24 v1.2.1 Font defs for fonts PL (MW) ) -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for LY1/ptm/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for EU1/lmr/m/n on input line 213. -LaTeX Font Info: ... okay on input line 213. -LaTeX Font Info: Checking defaults for T3/cmr/m/n on input line 213. -LaTeX Font Info: Try loading font information for T3+cmr on input line 213. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for LY1/ptm/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for EU1/lmr/m/n on input line 225. +LaTeX Font Info: ... okay on input line 225. +LaTeX Font Info: Checking defaults for T3/cmr/m/n on input line 225. +LaTeX Font Info: Try loading font information for T3+cmr on input line 225. (/usr/share/texmf/tex/latex/tipa/t3cmr.fd File: t3cmr.fd 2001/12/31 TIPA font definitions ) -LaTeX Font Info: ... okay on input line 213. +LaTeX Font Info: ... okay on input line 225. *geometry* driver: auto-detecting *geometry* detected driver: xetex @@ -2487,7 +2491,7 @@ ABD: EveryShipout initializing macros \AtBeginShipoutBox=\box119 -Package hyperref Info: Link coloring OFF on input line 213. +Package hyperref Info: Link coloring OFF on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/hyperref/nameref.sty Package: nameref 2012/10/27 v2.43 Cross-referencing by name of section @@ -2497,9 +2501,9 @@ ) \c@section@level=\count448 ) -LaTeX Info: Redefining \ref on input line 213. -LaTeX Info: Redefining \pageref on input line 213. -LaTeX Info: Redefining \nameref on input line 213. +LaTeX Info: Redefining \ref on input line 225. +LaTeX Info: Redefining \pageref on input line 225. +LaTeX Info: Redefining \nameref on input line 225. (./mchrzasz.out) (./mchrzasz.out) \@outlinefile=\write10 @@ -2530,7 +2534,7 @@ tionary/translator-theorem-dictionary-English.dict Dictionary: translator-theorem-dictionary, Language: English ) -LaTeX Info: Redefining \includegraphics on input line 213. +LaTeX Info: Redefining \includegraphics on input line 225. *** you should *not* be loading the inputenc package *** XeTeX expects the source to be in UTF8 encoding @@ -2627,8 +2631,8 @@ Package biblatex Info: Trying to load bibliographic data... Package biblatex Info: ... file 'mchrzasz.bbl' not found. No file mchrzasz.bbl. -Package biblatex Info: Reference section=0 on input line 213. -Package biblatex Info: Reference segment=0 on input line 213. +Package biblatex Info: Reference section=0 on input line 225. +Package biblatex Info: Reference segment=0 on input line 225. (./mchrzasz.nav) ................................................. . fontspec info: "no-scripts" @@ -2656,53 +2660,53 @@ . * 'bold italic' with NFSS spec.: . <->"Trebuchet MS/BI/ICU:mapping=tex-text;" ................................................. -LaTeX Font Info: Try loading font information for OML+plm on input line 213. +LaTeX Font Info: Try loading font information for OML+plm on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/polski/omlplm.fd File: omlplm.fd 2008/02/24 v1.2.1 Font defs for fonts PL (MW) ) -LaTeX Font Info: Try loading font information for OMS+plsy on input line 213 +LaTeX Font Info: Try loading font information for OMS+plsy on input line 225 . (/usr/share/texlive/texmf-dist/tex/latex/polski/omsplsy.fd File: omsplsy.fd 2008/02/24 v1.2.1 Font defs for fonts PL (MW) ) -LaTeX Font Info: Try loading font information for OMX+plex on input line 213 +LaTeX Font Info: Try loading font information for OMX+plex on input line 225 . (/usr/share/texlive/texmf-dist/tex/latex/polski/omxplex.fd File: omxplex.fd 2008/02/24 v1.2.1 Font defs for fonts PL (MW) ) LaTeX Font Info: External font `plex10' loaded for size -(Font) <10> on input line 213. +(Font) <10> on input line 225. LaTeX Font Info: External font `plex10' loaded for size -(Font) <7> on input line 213. +(Font) <7> on input line 225. LaTeX Font Info: External font `plex10' loaded for size -(Font) <5> on input line 213. -LaTeX Font Info: Try loading font information for U+msa on input line 213. +(Font) <5> on input line 225. +LaTeX Font Info: Try loading font information for U+msa on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd File: umsa.fd 2013/01/14 v3.01 AMS symbols A ) -LaTeX Font Info: Try loading font information for U+msb on input line 213. +LaTeX Font Info: Try loading font information for U+msb on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd File: umsb.fd 2013/01/14 v3.01 AMS symbols B ) -LaTeX Font Info: Try loading font information for U+rsfs on input line 213. +LaTeX Font Info: Try loading font information for U+rsfs on input line 225. (/usr/share/texlive/texmf-dist/tex/latex/jknapltx/ursfs.fd File: ursfs.fd 1998/03/24 rsfs font definition file (jk) ) \c__siunitx_mathsf_int=\count451 LaTeX Font Info: External font `plex10' loaded for size -(Font) <10.95> on input line 213. +(Font) <10.95> on input line 225. LaTeX Font Info: External font `plex10' loaded for size -(Font) <8> on input line 213. +(Font) <8> on input line 225. LaTeX Font Info: External font `plex10' loaded for size -(Font) <6> on input line 213. +(Font) <6> on input line 225. \c__siunitx_mathtt_int=\count452 -LaTeX Font Info: Try loading font information for OT4+cmtt on input line 213 +LaTeX Font Info: Try loading font information for OT4+cmtt on input line 225 . (/usr/share/texlive/texmf-dist/tex/latex/polski/ot4cmtt.fd @@ -2779,8 +2783,11 @@ [2 ] +Overfull \vbox (4.50993pt too high) detected at line 317 + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -2800,6 +2807,10 @@ [3 ] +File: images/walk.png Graphic file (type QTm) + +LaTeX Font Info: External font `plex10' loaded for size +(Font) <9> on input line 343. File: images/BG_lower.png Graphic file (type QTm) Overfull \vbox (19.18185pt too high) has occurred while \output is active [] @@ -2821,15 +2832,8 @@ [4 ] -Overfull \hbox (17.33817pt too wide) detected at line 356 -\OML/plm/m/it/10.95 x[] \OT4/cmr/m/n/10.95 = \OML/plm/m/it/10.95 a[] \OT4/cmr/m -/n/10.95 + [] \OML/plm/m/it/10.95 h[]a[] \OT4/cmr/m/n/10.95 + [] [] \OML/plm/m/ -it/10.95 h[]h[]a[] \OT4/cmr/m/n/10.95 + [] [] [] \OML/plm/m/it/10.95 h[]h[]h[]a -[] \OT4/cmr/m/n/10.95 + \OML/plm/m/it/10.95 ::: - [] - File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -2870,16 +2874,8 @@ [6 ] -File: images/mark.png Graphic file (type QTm) - -Overfull \hbox (4.38205pt too wide) detected at line 429 -[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] - [] - -LaTeX Font Info: External font `plex10' loaded for size -(Font) <14.4> on input line 429. File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -2920,14 +2916,8 @@ [8 ] -File: images/mark2.png Graphic file (type QTm) - -Overfull \hbox (4.38205pt too wide) detected at line 506 -[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] - [] - File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -2989,11 +2979,8 @@ [11 ] -Overfull \vbox (6.34827pt too high) detected at line 584 - [] - File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3013,8 +3000,14 @@ [12 ] +File: images/mark.png Graphic file (type QTm) + +Overfull \hbox (4.38205pt too wide) detected at line 577 +[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3076,8 +3069,16 @@ [15 ] +File: images/mark2.png Graphic file (type QTm) + +Overfull \hbox (4.38205pt too wide) detected at line 658 +[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] + [] + +LaTeX Font Info: External font `plex10' loaded for size +(Font) <14.4> on input line 658. File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3097,7 +3098,6 @@ [16 ] -\c@framenumberappendix=\count453 File: images/BG_lower.png Graphic file (type QTm) Overfull \vbox (19.18185pt too high) has occurred while \output is active [] @@ -3119,6 +3119,157 @@ [17 ] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[18 + +] +Overfull \vbox (6.34827pt too high) detected at line 736 + [] + +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[19 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[20 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[21 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[22 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[23 + +] +\c@framenumberappendix=\count453 +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[24 + +] \tf@nav=\write11 \openout11 = `mchrzasz.nav'. @@ -3128,23 +3279,23 @@ \tf@snm=\write13 \openout13 = `mchrzasz.snm'. -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 668. -Package atveryend Info: Empty hook `AfterLastShipout' on input line 668. +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 820. +Package atveryend Info: Empty hook `AfterLastShipout' on input line 820. (./mchrzasz.aux) -Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 668. -Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 668. +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 820. +Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 820. Package logreq Info: Writing requests to 'mchrzasz.run.xml'. \openout1 = `mchrzasz.run.xml'. -Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 668. +Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 820. ) Here is how much of TeX's memory you used: - 50345 strings out of 493918 - 987476 string characters out of 6150564 - 1343064 words of memory out of 5000000 - 52620 multiletter control sequences out of 15000+600000 - 33267 words of font info for 134 fonts, out of 8000000 for 9000 + 50458 strings out of 493918 + 990204 string characters out of 6150564 + 1344164 words of memory out of 5000000 + 52720 multiletter control sequences out of 15000+600000 + 37208 words of font info for 151 fonts, out of 8000000 for 9000 1144 hyphenation exceptions out of 8191 - 55i,17n,77p,10405b,1468s stack positions out of 5000i,500n,10000p,200000b,80000s + 55i,21n,77p,10405b,1486s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on mchrzasz.pdf (17 pages). +Output written on mchrzasz.pdf (24 pages). diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.nav b/Lectures_my/MC_2016/Lecture8/mchrzasz.nav index 0f2bda2..e81e84c 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.nav +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.nav @@ -10,32 +10,44 @@ \headcommand {\beamer@framepages {4}{4}} \headcommand {\slideentry {0}{0}{5}{5/5}{}{0}} \headcommand {\beamer@framepages {5}{5}} -\headcommand {\slideentry {0}{0}{6}{6/6}{}{0}} -\headcommand {\beamer@framepages {6}{6}} -\headcommand {\slideentry {0}{0}{7}{7/7}{}{0}} -\headcommand {\beamer@framepages {7}{7}} -\headcommand {\slideentry {0}{0}{8}{8/8}{}{0}} +\headcommand {\slideentry {0}{0}{6}{6/7}{}{0}} +\headcommand {\beamer@framepages {6}{7}} +\headcommand {\slideentry {0}{0}{7}{8/8}{}{0}} \headcommand {\beamer@framepages {8}{8}} -\headcommand {\slideentry {0}{0}{9}{9/9}{}{0}} +\headcommand {\slideentry {0}{0}{8}{9/9}{}{0}} \headcommand {\beamer@framepages {9}{9}} -\headcommand {\slideentry {0}{0}{10}{10/10}{}{0}} +\headcommand {\slideentry {0}{0}{9}{10/10}{}{0}} \headcommand {\beamer@framepages {10}{10}} -\headcommand {\slideentry {0}{0}{11}{11/11}{}{0}} +\headcommand {\slideentry {0}{0}{10}{11/11}{}{0}} \headcommand {\beamer@framepages {11}{11}} -\headcommand {\slideentry {0}{0}{12}{12/12}{}{0}} +\headcommand {\slideentry {0}{0}{11}{12/12}{}{0}} \headcommand {\beamer@framepages {12}{12}} -\headcommand {\slideentry {0}{0}{13}{13/13}{}{0}} +\headcommand {\slideentry {0}{0}{12}{13/13}{}{0}} \headcommand {\beamer@framepages {13}{13}} -\headcommand {\slideentry {0}{0}{14}{14/14}{}{0}} +\headcommand {\slideentry {0}{0}{13}{14/14}{}{0}} \headcommand {\beamer@framepages {14}{14}} -\headcommand {\slideentry {0}{0}{15}{15/15}{}{0}} +\headcommand {\slideentry {0}{0}{14}{15/15}{}{0}} \headcommand {\beamer@framepages {15}{15}} -\headcommand {\slideentry {0}{0}{16}{16/16}{}{0}} +\headcommand {\slideentry {0}{0}{15}{16/16}{}{0}} \headcommand {\beamer@framepages {16}{16}} -\headcommand {\slideentry {0}{0}{17}{17/17}{}{0}} +\headcommand {\slideentry {0}{0}{16}{17/17}{}{0}} \headcommand {\beamer@framepages {17}{17}} -\headcommand {\beamer@partpages {1}{17}} -\headcommand {\beamer@subsectionpages {1}{17}} -\headcommand {\beamer@sectionpages {1}{17}} -\headcommand {\beamer@documentpages {17}} -\headcommand {\def \inserttotalframenumber {16}} +\headcommand {\slideentry {0}{0}{17}{18/18}{}{0}} +\headcommand {\beamer@framepages {18}{18}} +\headcommand {\slideentry {0}{0}{18}{19/19}{}{0}} +\headcommand {\beamer@framepages {19}{19}} +\headcommand {\slideentry {0}{0}{19}{20/20}{}{0}} +\headcommand {\beamer@framepages {20}{20}} +\headcommand {\slideentry {0}{0}{20}{21/21}{}{0}} +\headcommand {\beamer@framepages {21}{21}} +\headcommand {\slideentry {0}{0}{21}{22/22}{}{0}} +\headcommand {\beamer@framepages {22}{22}} +\headcommand {\slideentry {0}{0}{22}{23/23}{}{0}} +\headcommand {\beamer@framepages {23}{23}} +\headcommand {\slideentry {0}{0}{23}{24/24}{}{0}} +\headcommand {\beamer@framepages {24}{24}} +\headcommand {\beamer@partpages {1}{24}} +\headcommand {\beamer@subsectionpages {1}{24}} +\headcommand {\beamer@sectionpages {1}{24}} +\headcommand {\beamer@documentpages {24}} +\headcommand {\def \inserttotalframenumber {22}} diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf b/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf index 2ef368f..4567f9e 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf Binary files differ diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.tex b/Lectures_my/MC_2016/Lecture8/mchrzasz.tex index d936aca..530b2ef 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.tex +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.tex @@ -173,6 +173,8 @@ %\hypersetup{colorlinks,linkcolor=,urlcolor=links} % For shapo's formulas: + +% For shapo's formulas: \def\lsi{\raise0.3ex\hbox{$<$\kern-0.75em\raise-1.1ex\hbox{$\sim$}}} \def\gsi{\raise0.3ex\hbox{$>$\kern-0.75em\raise-1.1ex\hbox{$\sim$}}} \newcommand{\lsim}{\mathop{\lsi}} @@ -203,10 +205,20 @@ \def\fixme{{\color{red} FIXME!}} \def\mc{{\color{Magenta}{MC}}} \def\pdf{{\rm p.d.f.}} +\def\cdf{{\rm c.d.f.}} +\def\ARROW{{\color{JungleGreen}{$\Rrightarrow$}}\xspace} +\def\ARROWR{{\color{WildStrawberry}{$\Rrightarrow$}}\xspace} \author{ {\fontspec{Trebuchet MS}Marcin Chrz\k{a}szcz} (Universit\"{a}t Z\"{u}rich)} \institute{UZH} -\title[Random number generators and application]{Random number generators and application} +\title[Specific \pdf~generation]{Specific \pdf~generation} +\date{\fixme} +\newcommand*{\QEDA}{\hfill\ensuremath{\blacksquare}}% +\newcommand*{\QEDB}{\hfill\ensuremath{\square}}% + +\author{ {\fontspec{Trebuchet MS}Marcin Chrz\k{a}szcz} (Universit\"{a}t Z\"{u}rich)} +\institute{UZH} +\title[Solving linear equation systems with Markov Chain MC]{Solving linear equation systems with Markov Chain MC} \date{\fixme} @@ -220,7 +232,7 @@ \begin{center} \begin{columns} \begin{column}{0.9\textwidth} - \flushright\fontspec{Trebuchet MS}\bfseries \Huge {Applications of Monte Carlo methods} + \flushright\fontspec{Trebuchet MS}\bfseries \Huge {Solving linear equation systems with Markov Chain MC} \end{column} \begin{column}{0.2\textwidth} %\includegraphics[width=\textwidth]{SHiP-2} @@ -242,40 +254,41 @@ \vspace{1em} % \footnotesize\textcolor{gray}{With N. Serra, B. Storaci\\Thanks to the theory support from M. Shaposhnikov, D. Gorbunov}\normalsize\\ \vspace{0.5em} - \textcolor{normal text.fg!50!Comment}{Experimental Methods in Particle Physics, \\ 26 November, 2015} + \textcolor{normal text.fg!50!Comment}{Monte Carlo methods, \\ 21 April, 2016} \end{center} \end{frame} } - - - - -\begin{frame}\frametitle{Markov Chain MC} +\begin{frame}\frametitle{Trivial example} +\begin{minipage}{\textwidth} +\ARROW Lets start with a TRIVIAL example: we want to calculate $S=A+B$. We can rewrite it in: +\begin{align*} +A=p \frac{A}{p}+(1-p) \frac{B}{1-p} +\end{align*} +and one can interpret the sum as expected value of: +\begin{align*} +W=\begin{cases} +\frac{A}{p}~~{ \rm with~propability~} p \\ +\frac{A}{1p}~~{ \rm with~propability~} 1-p +\end{cases} +\end{align*} +\ARROW The algorithm: \begin{itemize} -\item Consider a finite possible states: $S_1$, $S_2$, ... -\item And the time steps of time, labelled as $1$, $2$, ... -\item At time $t$ the state is denoted $X_t$. -\item The conditional probability is defined as: +\item We generate a random variable $W$ and calculate: +\begin{align*} +\hat{S}=\frac{1}{N}\sum_{i=1}^N W_i +\end{align*} +\ARROW The $\hat{S}$ is an unbias estimator of $S$. \end{itemize} -\begin{equation} -P(X_t=S_j \vert X_{t-1}=S_{j-1},..., X_{1}=S_{1}) \nonumber -\end{equation} -\begin{itemize} -\item The Markov chain is then if the probability depends only on previous step. -\end{itemize} -\begin{equation} -P(X_t=S_j \vert X_{t-1}=S_{j-1},..., X_{1}=S_{1}) = P(X_t=S_j \vert X_{t-1}=S_{j-1} )\nonumber -\end{equation} -\begin{itemize} -\item For this reason this reason MCMC is also knows as drunk sailor walk. -\item Very powerful method. Used to solve linear eq. systems, invert matrix, solve differential equations, etc. -\end{itemize} + + + +\end{minipage} + \end{frame} - - -\begin{frame}\frametitle{Linear Equations} +\begin{frame}\frametitle{Trivial example2 } +\begin{minipage}{\textwidth} \begin{itemize} \item Lets say we have a linear equation system: \end{itemize} @@ -299,64 +312,125 @@ \hat{X} = \dfrac{1}{N}\sum_{i=1} W_i{~}{~}{~}{~}{~} \hat{\sigma_X}=\dfrac{1}{\sqrt{N-1}}\sqrt{\dfrac{1}{N} \sum_{i=1}^N W_i^2-\hat{X}^2} \nonumber \end{equation} +\end{minipage} + \end{frame} -\begin{frame}\frametitle{Neumann-Ulam method} + + + +\begin{frame}\frametitle{Random walk} +\begin{minipage}{\textwidth} +\begin{footnotesize} + +\begin{center} +\includegraphics[width=0.8\textwidth]{images/walk.png} +\end{center} +\ARROW We are in the point $x$ and we walk accordingly to the following rules: \begin{itemize} -\item Let's try apply the basic MCMC method to solve a simple linear equation system: +\item From point $x$ we walk with probability $p$ to point $y$ or with $1-p$ to $a$. +\item From point $y$ we walk with probability $q$ to point $x$ and with $1-Q$ to $b$. +\item The walks ends when you end up in $a$ or $b$. +\item You get a ''reward'' $A$ if you end up in point $a$ and $B$ if you end up in $b$. +\item $X$ is expected ''reward'' when you start the walk from $x$, $Y$ when you start from $y$. +\end{itemize} +\ARROW The algorithm above is so-called random walk on the set $\lbrace a,x,y,b \rbrace$\\ +\ARROW The described walked can solve the linear equation system that we discussed above. + +\end{footnotesize} + +\end{minipage} +\end{frame} + +\begin{frame}\frametitle{Markov Chain MC} +\begin{footnotesize} +\begin{itemize} + +\item Consider a finite (or Countable set) possible states: $S_1$, $S_2$, ... +\item The $X_t$ is the state of the system in the time $t$ +\item We are looking at discrete time steps: $1,2,3,...$ + + +\item At time $t$ the state is denoted $X_t$. +\item The conditional probability is defined as: \end{itemize} \begin{equation} -A \overrightarrow{x} = \overrightarrow{b} \nonumber +P(X_t=S_j \vert X_{t-1}=S_{j-1},..., X_{1}=S_{1}) \nonumber \end{equation} \begin{itemize} -\item The above system can be (always, see linear algebra lecture) translated into system: +\item The Markov chain is then if the probability depends only on previous step. \end{itemize} \begin{equation} -\overrightarrow{x} = \overrightarrow{a} + H \overrightarrow{x} \nonumber +P(X_t=S_j \vert X_{t-1}=S_{j-1},..., X_{1}=S_{1}) = P(X_t=S_j \vert X_{t-1}=S_{j-1} )\nonumber \end{equation} \begin{itemize} -\item For this method we assume that the norm of the matrix is: +\item For this reason this reason MCMC is also knows as drunk sailor walk. +\item Very powerful method. Used to solve linear eq. systems, invert matrix, solve differential equations, etc. +\item Also used in physics problems: Brown motions, diffusion, etc. \end{itemize} -\begin{equation} -\Vert H \Vert = \underset{1 \leq i \leq n}{max} \sum_{j=1}^n \vert h_{ij} \vert <1 \nonumber \end{equation} -\begin{itemize} -\item Which we can write in a form: -\end{itemize} -\begin{equation} -(1 -H)\overrightarrow{x}=\overrightarrow{a} \nonumber -\end{equation} + + +\end{footnotesize} \end{frame} -\begin{frame}\frametitle{Neumann-Ulam method} -\begin{itemize} -\item The solution would be then: -\end{itemize} -\begin{equation} -\overrightarrow{x}_0=(1 -H)^{-1}\overrightarrow{a} \nonumber -\end{equation} -\begin{itemize} -\item We can Taylor expend this: -\end{itemize} -\begin{equation} -\overrightarrow{x}_0=(1 -H)^{-1}\overrightarrow{a} = \overrightarrow{a} + H \overrightarrow{a} + H^2 \overrightarrow{a} + H^3 \overrightarrow{a} +.... \nonumber -\end{equation} -\begin{itemize} -\item For the $i$-th component of the $\overrightarrow{x}$ vector: -\end{itemize} -\begin{equation} -x_0^i= a_i + \sum_{j=1}^n h_{ij} a_{j_1} + \sum_{j_1=1}^n \sum_{j_2=1}^n h_{ij_1} h_{ij_2} a_{j_2} + \sum_{j_1=1}^n \sum_{j_2=1}^n \sum_{j_3=1}^n h_{ij_1} h_{ij_2} h_{ij_3} a_{j_3} + ...\nonumber -\end{equation} -\begin{itemize} -\item One can construct probabilistic behaviour of a system that follows the path of equation above. -\end{itemize} +\begin{frame}\frametitle{Linear equations system} +\begin{footnotesize} +\ARROW Lets start from a linear equation system: +\begin{align*} +\textbf{A} \overrightarrow{x}=\overrightarrow{b},~~~~~\det \textbf{A} \neq 0, +\end{align*} +where $\textbf{A}=(a_{ij},i,j=1,2,...,n$ -matrix, $\overrightarrow{b}=(b_1,b_2,...,b_n)$-vector, $\overrightarrow{x}=(x_1,x_2,...,x_n)$ - vector of unknowns.\\ +\ARROW The solution we mark as $\overrightarrow{x}^0 = (x_1^0, x_2^0,..., x_n^0)$\\ +\ARROW The above system can be transformed into the iterative representation: +\begin{align*} + \overrightarrow{x}=\overrightarrow{a} + \textbf{H} \overrightarrow{x} +\end{align*} +where $\textbf{H}$ is a matrix, $\overrightarrow{a}$ is a vector.\\ +\ARROW We assume that the matrix norm: +\begin{align*} +\Vert H \Vert= \max_{1 \leq i \leq n} \sum_{j=1}^n \vert h_{h_{ij}} \vert <1 +\end{align*} +\pause +\ARROW We can always change transform every system to the iteration form: $\textbf{A}=\textbf{V}-\textbf{W}$. +\begin{align*} +(\textbf{V} - \textbf{W} )\overrightarrow{x} = \overrightarrow{b}~~~~ \mapsto ~~~~ \overrightarrow{x} = \textbf{V}^{-1} \overrightarrow{b} + \textbf{V}^{-1} \textbf{W} \overrightarrow{x} +\end{align*} +\end{footnotesize} \end{frame} +\begin{frame}\frametitle{Linear equations system} +\begin{footnotesize} +\ARROW Now we further modify the equation system: +\begin{align*} +\overrightarrow{x}=\overrightarrow{a} + \textbf{H} \overrightarrow{x} \Rightarrow (\textbf{I} - \textbf{H})\overrightarrow{x}=\overrightarrow{a} +\end{align*} +where $\textbf{I}=\delta_{ij}$ - unit matrix, $\delta_{ij}$ is the Kronecker delta. +\ARROW What one can do is to represent the solution in terns of Neumann series: +\begin{align*} +\overrightarrow{x}^0=(\textbf{I}-\textbf{H})^{-1}\overrightarrow{a}= \overrightarrow{a} \textbf{H} \overrightarrow{a} + \textbf{H}^2 \overrightarrow{a}+ \textbf{H}^3 \overrightarrow{a}+ ... +\end{align*} +\ARROW So for the $i^{th}$ component we have: +\begin{align*} +x_i^0=a_i+\sum_{j=1}^nh_{ij} a_j + \sum_{j_1 =1}^n \sum_{j_2 =1}^n h_{ij_1} h_{ij_2} a_{j_2} \\ ++...+\sum_{j_1 =1}^n ...\sum_{j_n =1}^n h_{ij_1}... h_{ij_n} a_{j_n} +\end{align*} +\ARROW We will construct a probabilistic interpretation using MCMC and then we show that the expected value is equal to the above formula. +\end{footnotesize} +\end{frame} + + + + + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}\frametitle{Neumann-Ulam method} +\begin{footnotesize} + \begin{itemize} \item To do so we add to our matrix an additional column of the matrix: \end{itemize} @@ -365,23 +439,97 @@ \end{equation} \begin{itemize} \item The system has states: $\lbrace 0,1,2...,n\rbrace$ -\item State at $t$ time is denoted as $i_t$. +\item State at $t$ time is denoted as $i_t(i_t=0,1,2,...,n;t=0,1,....)$ \item We make a random walk accordingly to to the following rules: \begin{itemize} \item At the begging of the walk ($t=0$) we are at $i_0$. \item In the $t$ moment we are in the $i_t$ position then in $t+1$ time stamp we move to state $i_{t+1}$ with the probability $h_{i_t i_{t+1}}$. \item We stop walking if we are in state $0$. \end{itemize} -\item The path $X(\gamma) = (i_0, i_1, i_2, ..., i_k, 0)$ is called trajectory. -\item It can be proven that $x_i^0 =E \lbrace X (\gamma) \vert i_0=j \rbrace$. +\item The path $\gamma = (i_0, i_1, i_2, ..., i_k, 0)$ is called trajectory. +\item For each trajectory we assign a number: +\begin{align*} +X(\gamma)=X(i_0, i_1, i_2, ..., i_k, 0)=\frac{a_{i_k}}{h_{i_k 0}} +\end{align*} \end{itemize} +\end{footnotesize} \end{frame} + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}\frametitle{Neumann-Ulam method, $\rm \color{RubineRed}{Lecture3/Markov}$} +\begin{frame}\frametitle{Neumann-Ulam method} +\begin{footnotesize} +\ARROW The $X(\gamma)$ variable is a random variable from: $\lbrace a_1/h_{1,0},a_2/h_{2,0},...,a_n/h_{n,0} \rbrace$. The probability that $X(\gamma) a_j/h_{j,0}$ is equal to the probability that the last non zero state of the $\gamma$ trajectory is $j$.\\ +\ARROW The expected value of the $X(\gamma)$ trajectory if the trajectory begins from $i_0=s$ is: +\begin{align*} +E \lbrace X(\gamma) \vert i_0=s \rbrace=\sum_{k=0}^{\infty} \sum_{ \lbrace \gamma_k \rbrace} X(\gamma) P(\gamma) +\end{align*} +where $\gamma_k$ is a trajectory of length $k$, which starts in $i_0=s$ and $P(\gamma)$ is the probability of occurrence of this trajectory. +\ARROW Yes you guest it lets do Taylor expansion: +\begin{align*} +E \lbrace X(\gamma) \vert i_0=s \rbrace= \sum_{\gamma_0}X(\gamma)P(\gamma) + \sum_{\gamma_1}X(\gamma)P(\gamma)+...+ \sum_{\gamma_k}X(\gamma)P(\gamma) +\end{align*} +\ARROW Now let's examine the elements of the above series. + +\end{footnotesize} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}\frametitle{Neumann-Ulam method} +\begin{footnotesize} +$\lbrace \gamma_0 \rbrace$: One trajectory: $\gamma_0=(i_0=s \vert 0)$, $P(\gamma_0)=h_{s,0}$ and $X(\gamma_0)=a_s/h_{s,0}$. So: +\begin{align*} +\sum_{\gamma_1}X(\gamma)P(\gamma) = \frac{a_s}{h_{s,0}} h_{s,0}=a_s +\end{align*} +$\lbrace \gamma_1 \rbrace$: Trajectories: $\gamma_1=(i_0,i_1=s \vert 0),~i_1 \neq 0$, $P(\gamma_1)= P(s,i_1,0)=h_{s,i_1}h_{i_1,0} $ and $X(\gamma_1)=a_{i_1}/h_{i_1,0}$. So: +\begin{align*} +\sum_{\gamma_1}X(\gamma)P(\gamma) = \sum_{i_1=1}^n \frac{a_{i_1}}{h_{i_1,0}} h_{s,i_1} h_{i_1,0}= \sum_{i=1}^n h_{s,i_1}a_{i_1} +\end{align*} + + +$\lbrace \gamma_2 \rbrace$: Trajectories: $\gamma_2=(i_0,i_1,i_2=s \vert 0),~i_1,i_2 \neq 0$, $P(\gamma_2)= P(s,i_1, i_2,0)=h_{s,i_1}h_{i_1,i_2}h_{i_1,0} $ and $X(\gamma_2)=a_{i_2}/h_{i_2,0}$. So: +\begin{align*} +\sum_{\gamma_2}X(\gamma)P(\gamma) = \sum_{i_1=1}^n \sum_{i_2=1}^n \frac{a_{i_2}}{h_{i_2,0}} h_{s,i_1} h_{i_1,i_2} h_{i_1,0}= \sum_{i_1=1}^n \sum_{i_2=1}^n h_{s,i_1} h_{i_1,i_2} a_{i_2} +\end{align*} + +\ARROW etc... + +\end{footnotesize} + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}\frametitle{Neumann-Ulam method} +\begin{footnotesize} +\ARROW After summing up: +\begin{align*} +E \lbrace X(\gamma) \vert i_0=s \rbrace= a_s+ \sum_{i_1 =1}^n h_{s,i_1} a_{i_1}+ \sum_{i_1 =1}^n \sum_{i_2 =1}^n h_{s,i_1} h_{i_1,i_2} a_{i_2}+....\\ + \sum_{i_1 =1}^n \sum_{i_2 =1}^n ... \sum_{i_k =1}^n h_{s,i_1} h_{i_1,i_2}... h_{i_{k-1},i_k}+... +\end{align*} +\ARROW If you compare this expression with the Neumann series we will they are the same so: +\begin{align*} +x_i^0=E \lbrace X(\gamma) \vert i_0=i \rbrace +\end{align*} + +\begin{exampleblock}{To sum up:} +We have proven that solving a linear system can be represented by an expectation value of the random variable $X(\gamma)$. The error is computed using standard deviation equation. +\end{exampleblock} +\end{footnotesize} + +\end{frame} + + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}\frametitle{Neumann-Ulam method} \begin{itemize} \item For example lets try to solve this equation system: \end{itemize} @@ -452,11 +600,15 @@ \end{frame} +\begin{frame}\frametitle{Neumann-Ulam dual method, prove} +\begin{footnotesize} +\end{footnotesize} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}\frametitle{Neumann-Ulam dual method, $\rm \color{RubineRed}{Lecture3/Markov2}$} +\begin{frame}\frametitle{Neumann-Ulam dual method} \begin{itemize} \item Let's try to solve the equation system: \end{itemize} @@ -508,149 +660,6 @@ -\begin{frame}\frametitle{Look elsewhere effect, $\rm \color{RubineRed}{Lecture3/LEE}$} -\begin{itemize} -\item Look elsewhere effect addresses the following problem: -\begin{itemize} -\item Imagine you observed a $3\sigma$ deviation in one of the observable that you measured. -\item Before you get excited one needs to understand if given the fact that you had so many measurements this might happen! -\end{itemize} -\item Example: Let's say we have measured 50 observables. What is the probability to observed 1 that is $3\sigma$ away from theory prediction? -\item Let's simulate 50 Gaussian distribution centred at 0 and width of 1. We count how simulations where at least one of the 50 numbers have the absolute value $>3$. -\item More complicated example: what if you observed 3 in a row $2\sigma$ fluctuations among 50 measurements? -\item This kind of studies are the best solvable by MC simulations. -\end{itemize} - - -\end{frame} - - - - - - -\begin{frame}\frametitle{Travelling Salesman Problem} -\begin{itemize} -\item Salesman starting from his base has to visit $n-1$ other locations and return to base headquarters. The problem is to find the shortest way. -\item For large $n$ the problem can't be solver by brutal force as the complexity of the problem is $(n-1)!$ -\item There exist simplified numerical solutions assuming factorizations. Unfortunately even those require anonymous computing power. -\item Can MC help? YES :) -\item The minimum distance $l$ has to depend on 2 factors: $P$ the area of the city the Salesman is travelling and the density of places he wants to visit: $\dfrac{n}{P}$ -\item Form this we can assume: -\end{itemize} -\begin{equation} -l \sim P^a (\dfrac{n}{P})^b=P^{a-b}n^b. \nonumber -\end{equation} - -\end{frame} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - - - - - -\begin{frame}\frametitle{Traveling Salesman Problem} -\begin{itemize} -\item From dimension analysis: -\end{itemize} -\begin{equation} -a-b=\dfrac{1}{2}. \nonumber -\end{equation} -\begin{itemize} -\item To get $l$ we need square root of area. -\item From this it's obvious: -\end{itemize} -\begin{equation} -l \sim P^a (\dfrac{n}{P})^b=P^{0.5}n^{a-0.5}. \nonumber -\end{equation} -\begin{itemize} -\item Now we can multiply the area by alpha factor that keeps the density constant then: -\end{itemize} -\begin{equation} -l \sim \alpha^0.5 \alpha6{a-0.5} = \alpha^a \nonumber -\end{equation} -\begin{itemize} -\item In this case the distance between the clients will not change, but the number of clients will increase by $\alpha$ so: -\end{itemize} -\begin{equation} -l \sim \alpha \nonumber -\end{equation} -\begin{itemize} -\item In the end we get: $a=1$ -\end{itemize} -\end{frame} - - - -\begin{frame}\frametitle{Traveling Salesman Problem} -\begin{itemize} -\item In total: -\end{itemize} -\begin{equation} -l \sim k (nP)^{0.5}\nonumber -\end{equation} -\begin{itemize} -\item Of course the k depends on the shape of the area and locations of client. However for large $n$ the k starts loosing the dependency. It's an asymptotically free estimator. -\item To use the above formula we need to somehow calculate k. -\item How to estimate this? Well make a TOY MC: take a square put uniformly $n$ points. Then we can calculate $l$. Then it's trivial: -\end{itemize} -\begin{equation} -k= l(nP)^{-0.5} \nonumber -\end{equation} -\end{frame} - - -\begin{frame}\frametitle{Traveling Salesman Problem} -\begin{itemize} -\item This kind of MC experiment might require large CPU power and time. The adventage is that once we solve the problem we can use the obtained k for other cases (it's universal constant!). -\item It turns out that: -\end{itemize} -\begin{equation} -k \sim \dfrac{3}{4} \nonumber -\end{equation} -\begin{itemize} -\item Ok, but in this case we can calculate $l$ but not the actual shortest way! Why the hell we did this exercise?! -\item Turns out that for most of the problems we are looking for the solution that is close to smallest $l$ not the exact minimum. -\end{itemize} -\end{frame} - -\begin{frame}\frametitle{War Games} - -\begin{itemize} -\item S. Andersoon 1966 simulated for Swedish government how would a tank battle look like. -\item Each of the sides has 15 tanks. that they allocate on the battle field. -\item The battle is done in time steps. -\item Each tank has 5 states: -\begin{itemize} -\item OK -\item Tank can only shoot -\item Tank can only move -\item Tank is destroyed -\item Temporary states -\end{itemize} -\item This models made possible to check different fighting strategies. - -\end{itemize} -\end{frame} - - - -\begin{frame} - -\begin{center} -\begin{Huge} - Q \& A -\end{Huge} -\end{center} - - -\end{frame} - - -