diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.aux b/Lectures_my/MC_2016/Lecture8/mchrzasz.aux index 121b992..1958261 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.aux +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.aux @@ -59,17 +59,17 @@ \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}{6}{6/7}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {6}{7}}} \pgfsyspdfmark {pgfid21}{0}{0} \pgfsyspdfmark {pgfid22}{0}{0} -\HyPL@Entry{7<>} \pgfsyspdfmark {pgfid23}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{7}{8/8}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {8}{8}}} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{7}{7/8}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {7}{8}}} \pgfsyspdfmark {pgfid24}{0}{0} \pgfsyspdfmark {pgfid25}{0}{0} \HyPL@Entry{8<>} @@ -91,11 +91,11 @@ \pgfsyspdfmark {pgfid33}{0}{0} \pgfsyspdfmark {pgfid34}{0}{0} \HyPL@Entry{11<>} -\pgfsyspdfmark {pgfid38}{23867907}{17900937} +\pgfsyspdfmark {pgfid35}{23867907}{17900937} \@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} +\pgfsyspdfmark {pgfid36}{0}{0} +\pgfsyspdfmark {pgfid37}{0}{0} \HyPL@Entry{12<>} \pgfsyspdfmark {pgfid41}{23867907}{17900937} \@writefile{nav}{\headcommand {\slideentry {0}{0}{12}{13/13}{}{0}}} @@ -156,20 +156,8 @@ \@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}}} +\@writefile{nav}{\headcommand {\beamer@partpages {1}{22}}} +\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{22}}} +\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{22}}} +\@writefile{nav}{\headcommand {\beamer@documentpages {22}}} +\@writefile{nav}{\headcommand {\def \inserttotalframenumber {20}}} diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.log b/Lectures_my/MC_2016/Lecture8/mchrzasz.log index 0122aaf..b957ad8 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) 16 APR 2016 23:37 +This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 20 APR 2016 16:38 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -2762,6 +2762,8 @@ [1 ] +LaTeX Font Info: External font `plex10' loaded for size +(Font) <14.4> on input line 268. File: images/BG_lower.png Graphic file (type QTm) Overfull \vbox (19.18185pt too high) has occurred while \output is active [] @@ -2783,7 +2785,28 @@ [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 [] + +................................................. +. 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: +................................................. + +[3 + +] +Overfull \vbox (4.50993pt too high) detected at line 326 [] File: images/BG_lower.png Graphic file (type QTm) @@ -2804,34 +2827,13 @@ . This font family consists of the following shapes: ................................................. -[3 +[4 ] 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 [] - -................................................. -. 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: -................................................. - -[4 - -] +(Font) <9> on input line 352. File: images/BG_lower.png Graphic file (type QTm) Overfull \vbox (19.18185pt too high) has occurred while \output is active [] @@ -3000,14 +3002,8 @@ [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 [] ................................................. @@ -3027,8 +3023,14 @@ [13 ] +File: images/mark.png Graphic file (type QTm) + +Overfull \hbox (4.38205pt too wide) detected at line 586 +[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3069,16 +3071,8 @@ [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 [] ................................................. @@ -3098,8 +3092,14 @@ [16 ] +File: images/mark2.png Graphic file (type QTm) + +Overfull \hbox (4.38205pt too wide) detected at line 717 +[][][] $[]$[][][][][][][][] $[]$[][][][][][][][] $[]$[][][][][][] + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3119,8 +3119,11 @@ [17 ] +Overfull \vbox (1.07576pt too high) detected at line 744 + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -3140,11 +3143,8 @@ [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 [] ................................................. @@ -3206,6 +3206,7 @@ [21 ] +\c@framenumberappendix=\count453 File: images/BG_lower.png Graphic file (type QTm) Overfull \vbox (19.18185pt too high) has occurred while \output is active [] @@ -3227,49 +3228,6 @@ [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'. @@ -3279,23 +3237,23 @@ \tf@snm=\write13 \openout13 = `mchrzasz.snm'. -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 820. -Package atveryend Info: Empty hook `AfterLastShipout' on input line 820. +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 832. +Package atveryend Info: Empty hook `AfterLastShipout' on input line 832. (./mchrzasz.aux) -Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 820. -Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 820. +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 832. +Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 832. Package logreq Info: Writing requests to 'mchrzasz.run.xml'. \openout1 = `mchrzasz.run.xml'. -Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 820. +Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 832. ) Here is how much of TeX's memory you used: - 50458 strings out of 493918 - 990204 string characters out of 6150564 + 50448 strings out of 493918 + 989928 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 + 52711 multiletter control sequences out of 15000+600000 + 37200 words of font info for 150 fonts, out of 8000000 for 9000 1144 hyphenation exceptions out of 8191 - 55i,21n,77p,10405b,1486s stack positions out of 5000i,500n,10000p,200000b,80000s + 55i,21n,77p,10405b,1483s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on mchrzasz.pdf (24 pages). +Output written on mchrzasz.pdf (22 pages). diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.nav b/Lectures_my/MC_2016/Lecture8/mchrzasz.nav index e81e84c..7327892 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.nav +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.nav @@ -10,10 +10,10 @@ \headcommand {\beamer@framepages {4}{4}} \headcommand {\slideentry {0}{0}{5}{5/5}{}{0}} \headcommand {\beamer@framepages {5}{5}} -\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}{6}{6/6}{}{0}} +\headcommand {\beamer@framepages {6}{6}} +\headcommand {\slideentry {0}{0}{7}{7/8}{}{0}} +\headcommand {\beamer@framepages {7}{8}} \headcommand {\slideentry {0}{0}{8}{9/9}{}{0}} \headcommand {\beamer@framepages {9}{9}} \headcommand {\slideentry {0}{0}{9}{10/10}{}{0}} @@ -42,12 +42,8 @@ \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}} +\headcommand {\beamer@partpages {1}{22}} +\headcommand {\beamer@subsectionpages {1}{22}} +\headcommand {\beamer@sectionpages {1}{22}} +\headcommand {\beamer@documentpages {22}} +\headcommand {\def \inserttotalframenumber {20}} diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf b/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf deleted file mode 100644 index 4567f9e..0000000 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.pdf +++ /dev/null Binary files differ diff --git a/Lectures_my/MC_2016/Lecture8/mchrzasz.tex b/Lectures_my/MC_2016/Lecture8/mchrzasz.tex index 530b2ef..38f602c 100644 --- a/Lectures_my/MC_2016/Lecture8/mchrzasz.tex +++ b/Lectures_my/MC_2016/Lecture8/mchrzasz.tex @@ -259,6 +259,15 @@ \end{frame} } +\begin{frame}\frametitle{Announcement} + +\begin{Large} +There will be no lectures and class on 19$^{th}$ of May +\end{Large} + +\end{frame} + + \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: @@ -577,7 +586,34 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\iffalse +\begin{frame}\frametitle{Neumann-Ulam dual method} +\begin{minipage}{\textwidth} +\ARROW The main problem with the Neumann-Ulam method is the fact that one has to calculate each of the $x_0^i$ separately.\\ +\ARROW The generalization works as follows: +\begin{enumerate} +\item We set randomly a \pdf~of states: $q_1,q_2,q_3,...,q_n$, such that $q_i >0$ and $\sum_{i=1}^n =1$. +\item We choose the starting point accordingly to $q_i$ probability. +\item If in the $t$ moment the point is in position $i_t$ then the with the probability $p(i_{t+1} \vert i_t)=h_{i_{t+1}, i_t}$ the points moves to the $i_{t+1}$ state. +\item For the state $0$ we assign the probability: $h_{0,i_{t}}=1-\sum_{i=1}^n h_{i,i_t}$ +\item WARNING HERE THE MATRIX IS TRANSPOSED compared to method. +\item The walk ends while you reach $0$ state. +\item For each walk/trajectory $(\gamma=(i_0,i_1,...,i_k,0))$ we assign a vector: +\begin{align*} +\overrightarrow{Y}(\gamma)=\frac{a_{i_0}}{q_{i_0}p(0\vert i_k }) \widehat{e}_{i_k} +\end{align*} +\item The final result is: $\overrightarrow{x}^0=\frac{1}{N}\sum \overrightarrow{Y}$ + +\end{enumerate}\textbf{ + + + + +\end{minipage} + +\end{frame} +\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}\frametitle{Neumann-Ulam dual method} \begin{itemize} @@ -602,7 +638,30 @@ \end{frame} \begin{frame}\frametitle{Neumann-Ulam dual method, prove} \begin{footnotesize} - +\ARROW If $Y_i(\gamma)$ is the i-th component of the $\overrightarrow{Y}(\gamma)$ vector. One needs to show: +\begin{align*} +E\lbrace Y_i(\gamma)\rbrace=x_j^0 +\end{align*} +\ARROW From definition: +\begin{align*} +Y_j(i_1,...,i_k,0)=\begin{cases} +\frac{a_{i_k}}{q_{i_0} p(0 \vert i_k)}~~~& i_k=j\\ +0 ~~~& i_k \neq j +\end{cases} +\end{align*} +\ARROW The expected value: +\begin{align*} +E \lbrace Y_j (\gamma)=\sum_{ {\rm trajectories}} \frac{a_j}{q_{i_0}p(0 \vert i_k) } P(i_1,i_2,...,i_k,0), +\end{align*} +where $P(i_1,i_2,...,i_k,0)$ is the probability of this trajectory occurring.\\ +\ARROW But by our definition the probability: +\begin{align*} +P(i_0,i_1,...,i_{k-1},j,0)=q_{i_k}h_{i_1,i_0}...h_{k,i_{k-1}}p(0 \vert j) +\end{align*} +\ARROW In the end we get: +\begin{align*} +E(Y_j(\gamma))=\sum_{k=0}^{\infty} \sum_{i_{k-1}=1}^n ... \sum_{i_{1}=1}^n \sum_{i_{0}=1}^n h_{j,i_{k-1}} h_{j,i_{k-1}} ... h_{i_2,i_1} h_{i_1,i_0} a_{i_0} +\end{align*} \end{footnotesize} @@ -658,9 +717,105 @@ \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}\frametitle{Generalization} +\ARROW Up to now we assumed that each of the matrix elements $h_{i,j} \geq 0$. Now if this is not true:\\ +\ARROW We take a probability matrix $P=p_{ij}$ such that: +\begin{align*} +p_{ij} \geq 0~~~p_{ij}=0 \Leftrightarrow h_{ij}=0,~~~~p_{i,0}=1-\sum_j p(i,j) >0. +\end{align*} +\ARROW To solve the system we construct a Markov Chain with the $P$ matrix as probabilities of transitions.\\ +\ARROW The probability of a trajectory is equal ($i_0=i$): +\begin{align*} +P(\gamma_k)=p_{i,i_1}p_{i_1,i_2}...p_{i_k,0} +\end{align*} +\ARROW The trajectory we assign the number: +\begin{align*} +X(\gamma_k)=\nu_{i,i_1} \nu_{i_1,i_2} ..., \nu_{i_{k-1},i_k} \frac{a_{i_k}}{p_{i_k,0}} +\end{align*} +where +\begin{align*} +\nu_{i,j}=\begin{cases} +h_{ij}/p_{ij},~~~& p_{ij} \neq 0\\ +1 ~~~& p_{ij} = 0 +\end{cases} +\end{align*} +\end{frame} +\begin{frame}\frametitle{Generalization, prove} +\ARROW For a $X(\gamma)$ trajectory the expected value is: +\begin{align*} +E \lbrace X(\gamma_k) = \sum_{k=0}^{\infty}\sum_{\gamma_k} X(\gamma_k)P \lbrace X(\gamma_k) \rbrace +\end{align*} +\ARROW The probability is given by the formula: +\begin{align*} +P \lbrace X(\gamma_k) \rbrace = P \lbrace X(\gamma_k)= \nu_{i,i_1} \nu_{i_1,i_2} ..., \nu_{i_{k-1},i_k} \frac{a_{i_k}}{p_{i_k,0}} \rbrace \\ = p_{i,i_1}...,p_{i_{k-1},i_k}p_{i_k,0} +\end{align*} +\ARROW However: +\begin{align*} +X(\gamma_k) P \lbrace X(\gamma_k) \rbrace=h_{i,i_1} h_{i_1,i_2} ... h_{i_{k-1},i_k} a_{i_k} +\end{align*} +so: +\begin{align*} +\sum_{\gamma_k} X(\gamma_k)P \lbrace X(\gamma_k) \rbrace = \sum_{i_1=1} ... \sum_{i_k=1} h_{i,i_1} h_{i_1,i_2} ... h_{i_{k-1}, i_k} a_{i_k} +\end{align*} + +\end{frame} + + + +\begin{frame}\frametitle{Generalization, the algorithm} +\ARROW We set the $P$ matrix in a arbitrary way.\\ +\ARROW If in the $t$ moment the point is in the $i_t$ state the with the probability $p_{i_t, i_{t+1}}$ he can go to $i_{t+1}$ state. \\ +\ARROW We stop the walk once we reach $0$.\\ +\ARROW For the given trajectory we assign the value: $X(\gamma_k)$\\ +\ARROW We repeat the procedure $N$ times and take the mean and RMS.\\ +\ARROW We repeat this also for every of the $\overrightarrow{x}^0$ vector components. + + + +\end{frame} + + + +\begin{frame}\frametitle{Wasow method} + +\begin{footnotesize} + +\ARROW The main problem with the Neumann-Ulam methods is the fact that each time we estimate only one of the part of the taylor expansion.\\ +\ARROW W.Wasow (1956) was smarter: +\begin{itemize} + +\item For the trajectory: $\gamma(i_0,i_1,...,i_k,0)$ we look at begging trajectories: +\begin{align*} +(i_0),~(i_0,i_1),~(i_0,i_1,...,i_k) +\end{align*} +and for each we associate a number: +\begin{align*} +(i_0,i_1,i_2,...,i_m),~0 \leq m \leq k +\end{align*} +we assign a number: +\begin{align*} +\nu_{i_0,i_1} \nu_{i_1,i_2}...\nu_{i_{m-1},i_m}a_{i_m} +\end{align*} + +\end{itemize} +\ARROW For the trajectory we define: +\begin{align*} +X^{\ast}(\gamma)=\sum_{m=0}^k nu_{i_1,i_2}...\nu_{i_{m-1},i_m}a_{i_m} +\end{align*} +\ARROW One can prove that: +\begin{align*} +E \lbrace X^{\ast}(\gamma) \vert i_0=i \rbrace =x_i^0 +\end{align*} + +\end{footnotesize} + +\end{frame} +