3.1 Random Numbers: Introduction

2 files changed, 1227 insertions, 0 deletions

diff --git a/3.1.lyx b/3.1.lyx
new file mode 100644
index 0000000..81d7d26
--- /dev/null
+++ b/3.1.lyx
@@ -0,0 +1,1204 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc1[20]
+\end_layout
+
+\end_inset
+
+Suppose that you wish to obtain a decimal digit at random,
+ not using a computer.
+ Which of the following methods would be suitable?
+\end_layout
+
+\begin_layout Enumerate
+Open a telephone directory to a random place by sticking your finger in it somewhere,
+ and use the units digit of the first number found on the selected page.
+\end_layout
+
+\begin_layout Enumerate
+Same as (a),
+ but use the units digit of the 
+\emph on
+page
+\emph default
+ number.
+\end_layout
+
+\begin_layout Enumerate
+Roll a die that is in the shape of a regular icosahedron,
+ whose twenty faces have been labeled with the digits 0,
+ 0,
+ 1,
+ 1,
+ ...,
+ 9,
+ 9.
+ Use the digit that appears on the top,
+ when the die comes to rest.
+ (A felt-covered table with a hard surface is recommended for rolling dice.)
+\end_layout
+
+\begin_layout Enumerate
+Expose a geiger counter to a source of radioactivity for one minute (shielding yourself) and use the units digit of the resulting count.
+ Assume that the geiger counter displays the number of counts in decimal notation,
+ and that the count is initially zero.
+\end_layout
+
+\begin_layout Enumerate
+Glance at your wristwatch;
+ and if the position of the second-hand is between 
+\begin_inset Formula $6n$
+\end_inset
+
+ and 
+\begin_inset Formula $6(n+1)$
+\end_inset
+
+ seconds,
+ choose the digit 
+\begin_inset Formula $n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Ask a friend to think of a random digit,
+ and use the digit he names.
+\end_layout
+
+\begin_layout Enumerate
+Ask an enemy to think of a random digit,
+ and use the digit he names.
+\end_layout
+
+\begin_layout Enumerate
+Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications.
+ Assign to these horses the digits 0 to 9,
+ in arbitrary fashion,
+ and after the race use the winner's digit.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+This would work for a typical phone book.
+ It wouldn't work if the book has,
+ say,
+ entries ordered by number with a fixed number of entries per page that is a multiple of 2 or 5.
+ And,
+ according to the official solution,
+ in some places people can choose phone numbers (presumably in the US where Knuth lives) so it wouldn't work there as people would tend to choose round numbers.
+\end_layout
+
+\begin_layout Enumerate
+This would be suitable,
+ although some adjustment would have to be made to account for the fact that left pages would have even numbers and right pages would have round numbers (say,
+ we could take the even number and divide it by two) and to avoid the last few pages if the total number is not a multiple of 20.
+\end_layout
+
+\begin_layout Enumerate
+This would work very well.
+\end_layout
+
+\begin_layout Enumerate
+This would work well assuming there are several digits between the most significant one and the units.
+\end_layout
+
+\begin_layout Enumerate
+This would work assuming you only have to do it once at a time and not at a specific time.
+\end_layout
+
+\begin_layout Enumerate
+This wouldn't work,
+ as humans are not good at mentally generating random numbers.
+\end_layout
+
+\begin_layout Enumerate
+This definitely wouldn't work,
+ as the enemy would probably be compelled to choose the number strategically instead of randomly.
+\end_layout
+
+\begin_layout Enumerate
+This could work,
+ although it would be time consuming.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc3[10]
+\end_layout
+
+\end_inset
+
+What number follows 1010101010 in the middle-square method?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $1010101010^{2}=1020304050403020100$
+\end_inset
+
+,
+ so the next number would be 3040504030.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc6[M21]
+\end_layout
+
+\end_inset
+
+Suppose that we want to generate a sequence of integers 
+\begin_inset Formula $X_{0},X_{1},X_{2},\dots$
+\end_inset
+
+,
+ in the range 
+\begin_inset Formula $0\leq X_{n}<m$
+\end_inset
+
+.
+ Let 
+\begin_inset Formula $f(x)$
+\end_inset
+
+ be any function such that 
+\begin_inset Formula $0\leq x<m$
+\end_inset
+
+ implies 
+\begin_inset Formula $0\leq f(x)<m$
+\end_inset
+
+.
+ Consider a sequence formed by the rule 
+\begin_inset Formula $X_{n+1}=f(X_{n})$
+\end_inset
+
+.
+ (Examples are the middle-square method and Algorithm K.)
+\end_layout
+
+\begin_layout Enumerate
+Show that the sequence is ultimately periodic,
+ in the sense that there exist numbers 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ and 
+\begin_inset Formula $\mu$
+\end_inset
+
+ for which the values
+\begin_inset Formula 
+\[
+X_{0},X_{1},\dots,X_{\mu},\dots,X_{\mu+\lambda-1}
+\]
+
+\end_inset
+
+are distinct,
+ but 
+\begin_inset Formula $X_{n+\lambda}=X_{n}$
+\end_inset
+
+ when 
+\begin_inset Formula $n\geq\mu$
+\end_inset
+
+.
+ Find the maximum and minimum possible values of 
+\begin_inset Formula $\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e316b"
+
+\end_inset
+
+(R.
+ W.
+ Floyd.) Show that there exists an 
+\begin_inset Formula $n>0$
+\end_inset
+
+ such that 
+\begin_inset Formula $X_{n}=X_{2n}$
+\end_inset
+
+;
+ and the smallest such value of 
+\begin_inset Formula $n$
+\end_inset
+
+ lies in the range 
+\begin_inset Formula $\mu\le n\leq\mu+\lambda$
+\end_inset
+
+.
+ Furthermore the value of 
+\begin_inset Formula $X_{n}$
+\end_inset
+
+ is unique in the sense that if 
+\begin_inset Formula $X_{n}=X_{2n}$
+\end_inset
+
+ and 
+\begin_inset Formula $X_{r}=X_{2r}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $X_{r}=X_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Use the idea of part 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "enu:e316b"
+plural "false"
+caps "false"
+noprefix "false"
+nolink "false"
+
+\end_inset
+
+ to design an algorithm that calculates 
+\begin_inset Formula $\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ for any given function 
+\begin_inset Formula $f$
+\end_inset
+
+ and any given 
+\begin_inset Formula $X_{0}$
+\end_inset
+
+,
+ using only 
+\begin_inset Formula $O(\mu+\lambda)$
+\end_inset
+
+ steps and only a bounded number of memory locations.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Assume 
+\begin_inset Formula $f:\mathbb{Z}_{m}\to\mathbb{Z}_{m}$
+\end_inset
+
+,
+ as otherwise the statements below are not necessarily true (e.g.
+ if 
+\begin_inset Formula $f:\mathbb{R}\to\mathbb{R}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $f(x)\coloneqq\frac{x}{2}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $X_{0}=\frac{m}{2}$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Enumerate
+Require that 
+\begin_inset Formula $\mu\in\mathbb{N}$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda\in\mathbb{N}^{*}$
+\end_inset
+
+,
+ as otherwise it is unclear what is meant and,
+ in particular,
+ the statement is obviously true when 
+\begin_inset Formula $\mu\in\mathbb{N}$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda=0$
+\end_inset
+
+.
+ Now,
+ since 
+\begin_inset Formula $\{X_{0},\dots,X_{m}\}\subseteq\{0,\dots,m-1\}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $|\{X_{0},\dots,X_{m}\}|\leq m$
+\end_inset
+
+ and there must be integers 
+\begin_inset Formula $i$
+\end_inset
+
+ and 
+\begin_inset Formula $j$
+\end_inset
+
+,
+ 
+\begin_inset Formula $0\leq i<j\leq m$
+\end_inset
+
+,
+ such that 
+\begin_inset Formula $X_{i}=X_{j}$
+\end_inset
+
+.
+ We choose 
+\begin_inset Formula $i$
+\end_inset
+
+ and 
+\begin_inset Formula $j$
+\end_inset
+
+ such that 
+\begin_inset Formula $j$
+\end_inset
+
+ is minimum,
+ which ensures that 
+\begin_inset Formula $X_{0},\dots,X_{j-1}$
+\end_inset
+
+ are distinct and uniquely determines 
+\begin_inset Formula $i$
+\end_inset
+
+,
+ and we set 
+\begin_inset Formula $\mu\coloneqq i$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda\coloneqq j-i$
+\end_inset
+
+;
+ then 
+\begin_inset Formula $X_{0},\dots,X_{\mu+\lambda-1=j-1}$
+\end_inset
+
+ are all distinct and,
+ for 
+\begin_inset Formula $n\geq\mu$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+X_{n+\lambda}=X_{n-i+j}=f^{n-i}(X_{j})=f^{n-i}(X_{i})=X_{n}.
+\]
+
+\end_inset
+
+It's easy to check that these values are unique:
+ 
+\begin_inset Formula $\mu+\lambda$
+\end_inset
+
+ must be the first value such that 
+\begin_inset Formula $X_{\mu+\lambda}$
+\end_inset
+
+ equals some other value earlier in the sequence,
+ and 
+\begin_inset Formula $\mu$
+\end_inset
+
+ must be the only value less than 
+\begin_inset Formula $\mu+\lambda$
+\end_inset
+
+ such that 
+\begin_inset Formula $X_{\mu}=X_{\mu+\lambda}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+As for the maximum and minimum,
+ since 
+\begin_inset Formula $0\leq i<j\leq m$
+\end_inset
+
+,
+ we have 
+\begin_inset Formula $0\leq\mu\leq m-1$
+\end_inset
+
+ and 
+\begin_inset Formula $1\leq\lambda\leq m$
+\end_inset
+
+.
+ These bounds can be reached:
+ when 
+\begin_inset Formula $f$
+\end_inset
+
+ is the identity,
+ 
+\begin_inset Formula $\mu=0$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda=1$
+\end_inset
+
+;
+ when 
+\begin_inset Formula $f(x)=(x+1)\bmod m$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\lambda=m$
+\end_inset
+
+,
+ and when 
+\begin_inset Formula $f(x)=\max\{0,x-1\}$
+\end_inset
+
+ and 
+\begin_inset Formula $X_{0}=m-1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\mu=m-1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $k\coloneqq\lceil\frac{\mu}{\lambda}\rceil$
+\end_inset
+
+ and 
+\begin_inset Formula $n\coloneqq k\lambda$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $\frac{\mu}{\lambda}\leq k\leq\frac{\mu}{\lambda}+1$
+\end_inset
+
+ and therefore 
+\begin_inset Formula $\mu\leq n\leq\mu+\lambda$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $X_{n}=X_{n+\lambda}=X_{n+2\lambda}=\dots=X_{n+k\lambda=2n}$
+\end_inset
+
+.
+ For the uniqueness,
+ let 
+\begin_inset Formula $r>0$
+\end_inset
+
+ be such that 
+\begin_inset Formula $X_{r}=X_{2r}$
+\end_inset
+
+,
+ so necessarily 
+\begin_inset Formula $2r\geq\mu+\lambda$
+\end_inset
+
+.
+ We note that,
+ for any 
+\begin_inset Formula $s\geq\mu$
+\end_inset
+
+,
+ by induction,
+ 
+\begin_inset Formula $X_{s}=X_{s-\lfloor\frac{s-\mu}{\lambda}\rfloor\lambda}=X_{\mu+((s-\mu)\bmod\lambda)}$
+\end_inset
+
+,
+ and we call 
+\begin_inset Formula $R(s)\coloneqq\mu+((s-\mu)\bmod\lambda)\in\{\mu,\dots,\mu+\lambda-1\}$
+\end_inset
+
+.
+ With this,
+ 
+\begin_inset Formula $X_{R(2r)}=X_{2r}=X_{r}$
+\end_inset
+
+,
+ so either 
+\begin_inset Formula $r=R(2r)$
+\end_inset
+
+ or 
+\begin_inset Formula $r\geq\mu+\lambda$
+\end_inset
+
+;
+ in any case 
+\begin_inset Formula $r\geq\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $X_{R(2r)}=X_{R(r)}$
+\end_inset
+
+.
+ This means 
+\begin_inset Formula $R(2r)=R(r)$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $r\equiv0\mod{\lambda}$
+\end_inset
+
+ and 
+\begin_inset Formula $R(r)=\mu+(-\mu\bmod\lambda)\equiv0\bmod\lambda$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $R(r)$
+\end_inset
+
+ is unique and 
+\begin_inset Formula $X_{r}=X_{R(r)}=X_{R(n)}=X_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+First we set 
+\begin_inset Formula $a,b\gets X_{0}$
+\end_inset
+
+ and then repeatedly set 
+\begin_inset Formula $a\gets f(a)$
+\end_inset
+
+ and 
+\begin_inset Formula $b\gets f^{2}(b)$
+\end_inset
+
+ until 
+\begin_inset Formula $a=b$
+\end_inset
+
+;
+ the number of times we do this operation is 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ and in the end 
+\begin_inset Formula $a=X_{n}$
+\end_inset
+
+.
+ Then we set 
+\begin_inset Formula $b\gets a$
+\end_inset
+
+ and repeat 
+\begin_inset Formula $b\gets f(b)$
+\end_inset
+
+ until 
+\begin_inset Formula $b=a$
+\end_inset
+
+;
+ the number of times we do this operation is 
+\begin_inset Formula $\lambda$
+\end_inset
+
+.
+ Finally,
+ since 
+\begin_inset Formula $a$
+\end_inset
+
+ is a multiple of 
+\begin_inset Formula $\lambda$
+\end_inset
+
+,
+ 
+\begin_inset Formula $X_{\mu}=X_{\mu+n}$
+\end_inset
+
+,
+ so we set 
+\begin_inset Formula $b\gets X_{0}$
+\end_inset
+
+ and repeat 
+\begin_inset Formula $b\gets f(b)$
+\end_inset
+
+ and 
+\begin_inset Formula $a\gets f(a)$
+\end_inset
+
+ until 
+\begin_inset Formula $a=b$
+\end_inset
+
+;
+ the number of times we do this operation is 
+\begin_inset Formula $\mu$
+\end_inset
+
+.
+ In total this uses two slots of memory and runs in time 
+\begin_inset Formula $O(n)+O(\lambda)+O(\mu)=O(\mu+\lambda)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc7[M21]
+\end_layout
+
+\end_inset
+
+(R.
+ P.
+ Brent,
+ 1977.) Let 
+\begin_inset Formula $\ell(n)$
+\end_inset
+
+ be the greatest power of 2 that is less than or equal to 
+\begin_inset Formula $n$
+\end_inset
+
+;
+ thus,
+ for example,
+ 
+\begin_inset Formula $\ell(15)=8$
+\end_inset
+
+ and 
+\begin_inset Formula $\ell(\ell(n))=\ell(n)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Show that,
+ in terms of the notation in exercise 6,
+ there exists an 
+\begin_inset Formula $n>0$
+\end_inset
+
+ such that 
+\begin_inset Formula $X_{n}=X_{\ell(n)-1}$
+\end_inset
+
+.
+ Find a formula that expresses the least such 
+\begin_inset Formula $n$
+\end_inset
+
+ in terms of the periodicity numbers 
+\begin_inset Formula $\mu$
+\end_inset
+
+ and 
+\begin_inset Formula $\lambda$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type 
+\begin_inset Formula $X_{n+1}=f(X_{n})$
+\end_inset
+
+,
+ to prevent it from cycling indefinitely.
+ Your algorithm should calculate the period length 
+\begin_inset Formula $\lambda$
+\end_inset
+
+,
+ and it should only use a small amount of memory space—
+you must not simply store all the computed sequence values!
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+For sufficiently large 
+\begin_inset Formula $r$
+\end_inset
+
+,
+ 
+\begin_inset Formula $n\coloneqq2^{r}-1+\lambda<2^{r+1}$
+\end_inset
+
+ and then 
+\begin_inset Formula $X_{\ell(n)-1}=X_{2^{r}-1}=X_{n}$
+\end_inset
+
+,
+ and it's easy to convince ourselves that all such 
+\begin_inset Formula $n$
+\end_inset
+
+ are of the form 
+\begin_inset Formula $2^{r}-1+k\lambda$
+\end_inset
+
+ with 
+\begin_inset Formula $r\in\mathbb{N}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\in\mathbb{N}^{*}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\lambda-1<2^{r}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $2^{r}-1\geq\mu$
+\end_inset
+
+.
+ The minimum value,
+ then,
+ happens with 
+\begin_inset Formula $k=1$
+\end_inset
+
+ and 
+\begin_inset Formula $2^{r}$
+\end_inset
+
+ is the minimum such that 
+\begin_inset Formula $\lambda,\mu+1\leq2^{r}$
+\end_inset
+
+,
+ so if 
+\begin_inset Formula $u(n)$
+\end_inset
+
+ is the lowest power of 2 that is greater than or equal to 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+n=u(\max\{\lambda,\mu+1\})+\lambda-1.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+We set 
+\begin_inset Formula $a\gets b\gets X_{0}$
+\end_inset
+
+ and 
+\begin_inset Formula $r\gets0$
+\end_inset
+
+.
+ Then repeat 
+\begin_inset Formula $b\gets f(b)$
+\end_inset
+
+ up to 
+\begin_inset Formula $2^{r}$
+\end_inset
+
+ times;
+ if at any point 
+\begin_inset Formula $b=a$
+\end_inset
+
+,
+ terminate with 
+\begin_inset Formula $\lambda$
+\end_inset
+
+ equal to the number of times that 
+\begin_inset Formula $b\gets f(b)$
+\end_inset
+
+ has been run in this iteration;
+ otherwise set 
+\begin_inset Formula $a\gets b$
+\end_inset
+
+,
+ 
+\begin_inset Formula $r\gets r+1$
+\end_inset
+
+,
+ and repeat this step.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc16[15]
+\end_layout
+
+\end_inset
+
+A sequence generated as in exercise 6 must begin to repeat after at most 
+\begin_inset Formula $m$
+\end_inset
+
+ values have been generated.
+ Suppose we generalize the method so that 
+\begin_inset Formula $X_{n+1}$
+\end_inset
+
+ depends on 
+\begin_inset Formula $X_{n-1}$
+\end_inset
+
+ as well as on 
+\begin_inset Formula $X_{n}$
+\end_inset
+
+;
+ formally,
+ let 
+\begin_inset Formula $f(x,y)$
+\end_inset
+
+ be a function such that 
+\begin_inset Formula $0\leq x,y<m$
+\end_inset
+
+ implies 
+\begin_inset Formula $0\leq f(x,y)<m$
+\end_inset
+
+.
+ The sequence is constructed by selecting 
+\begin_inset Formula $X_{0}$
+\end_inset
+
+ and 
+\begin_inset Formula $X_{1}$
+\end_inset
+
+ arbitrarily,
+ and then letting
+\begin_inset Formula 
+\begin{align*}
+X_{n+1} & =f(X_{n},X_{n-1}), & \text{for }n & >0.
+\end{align*}
+
+\end_inset
+
+What is the maximum period conceivably attainable in this case?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+See exercise 17.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc17[10]
+\end_layout
+
+\end_inset
+
+Generalize the situation in the previous exercise so that 
+\begin_inset Formula $X_{n+1}$
+\end_inset
+
+ depends on the preceding 
+\begin_inset Formula $k$
+\end_inset
+
+ values of the sequence.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+The maximum conceivable would be 
+\begin_inset Formula $m^{k}$
+\end_inset
+
+.
+ Why this is always attainable is not at all obvious.
+\end_layout
+
+\end_body
+\end_document
diff --git a/index.lyx b/index.lyx
index a60f901..1c6122d 100644
--- a/index.lyx
+++ b/index.lyx
@@ -1819,6 +1819,29 @@ Random Numbers
 Introduction
 \end_layout
 
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "3.1.lyx"
+literal "false"
+
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\family typewriter
+A10+R25+16
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
 \begin_layout Section
 Generating Uniform Random Numbers
 \end_layout