Changed layout for more manageable volumes

1 files changed, 0 insertions, 1383 deletions

diff --git a/3.3.3.lyx b/3.3.3.lyx
deleted file mode 100644
index d03c773..0000000
--- a/3.3.3.lyx
+++ /dev/null
@@ -1,1383 +0,0 @@
-#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 Subsubsection
-First Set
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc1[M10]
-\end_layout
-
-\end_inset
-
-Express 
-\begin_inset Formula $x\bmod y$
-\end_inset
-
- in terms of the sawtooth and 
-\begin_inset Formula $\delta$
-\end_inset
-
- functions.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-We have 
-\begin_inset Formula $((x))-\frac{1}{2}\delta(x)=x-\lfloor x\rfloor-\frac{1}{2}$
-\end_inset
-
-,
- so 
-\begin_inset Formula $\lfloor x\rfloor=x-((x))+\tfrac{1}{2}(\delta(x)-1)$
-\end_inset
-
-.
- Therefore
-\begin_inset Formula 
-\begin{multline*}
-x\bmod y=x-y\left\lfloor \frac{x}{y}\right\rfloor =x-y\left(\frac{x}{y}-\left(\left(\frac{x}{y}\right)\right)+\frac{1}{2}\left(\delta(\tfrac{x}{y})-1\right)\right)=\\
-=\left(\left(\left(\frac{x}{y}\right)\right)+\frac{1-\delta(\frac{x}{y})}{2}\right)y.
-\end{multline*}
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc4[M19]
-\end_layout
-
-\end_inset
-
-If 
-\begin_inset Formula $m=10^{10}$
-\end_inset
-
-,
- what is the highest possible value of 
-\begin_inset Formula $d$
-\end_inset
-
- (in the notation of Theorem P),
- given that the potency of the generator is 10?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-It's 
-\begin_inset Formula $d=2\cdot5^{10}$
-\end_inset
-
-.
- First,
- we note that 
-\begin_inset Formula 
-\[
-(2\cdot5^{10})^{9}\bmod10^{10}=2^{9}5^{90}\bmod2^{10}5^{10}=2^{9}5^{10}(5^{80}\bmod2)=m/2\neq0,
-\]
-
-\end_inset
-
- and that 
-\begin_inset Formula $(2\cdot5^{10})^{10}\bmod10^{10}=2^{10}5^{100}\bmod2^{10}5^{10}=0$
-\end_inset
-
-,
- so if 
-\begin_inset Formula $b=d$
-\end_inset
-
- we have potency 10.
- Second,
- we note that,
- since 
-\begin_inset Formula $d\mid m$
-\end_inset
-
-,
- and any divisor of 
-\begin_inset Formula $m$
-\end_inset
-
- greater that 
-\begin_inset Formula $2\cdot5^{10}$
-\end_inset
-
- has to be a multiple at least of 
-\begin_inset Formula $2^{2}$
-\end_inset
-
- and of 
-\begin_inset Formula $5^{2}$
-\end_inset
-
-,
- and therefore of 100,
- then 
-\begin_inset Formula $b$
-\end_inset
-
- would have to be a multiple of 100 and the potency would be at most 5.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc7[M24]
-\end_layout
-
-\end_inset
-
-Give a proof of the reciprocity law (19),
- when 
-\begin_inset Formula $c=0$
-\end_inset
-
-,
- by using the general reciprocity law of exercise 1.2.4–45.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Note Greyedout
-status open
-
-\begin_layout Plain Layout
-(I had to look up the solution,
- obviously.)
-\end_layout
-
-\end_inset
-
-In this case,
- the law reduces to
-\begin_inset Formula 
-\begin{multline*}
-\sigma(h,k,0)+\sigma(k,h,0)=\\
-=12\sum_{0\leq j<k}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj}{k}\right)\right)+12\sum_{0\leq j<h}\left(\left(\frac{j}{h}\right)\right)\left(\left(\frac{kj}{h}\right)\right)=\frac{h}{k}+\frac{k}{h}+\frac{1}{hk}-3.
-\end{multline*}
-
-\end_inset
-
-where 
-\begin_inset Formula $0<h\leq k$
-\end_inset
-
- are coprime integers.
- The last equation from exercise 1.2.4–45 with 
-\begin_inset Formula $k=2$
-\end_inset
-
- tells us that
-\begin_inset Formula 
-\[
-\sum_{1\leq j<n}\left\lfloor \frac{mj}{n}\right\rfloor \left(\left\lfloor \frac{mj}{n}\right\rfloor +1\right)+2\sum_{1\leq j<m}j\left\lceil \frac{jn}{m}\right\rceil =nm(m-1)
-\]
-
-\end_inset
-
-for 
-\begin_inset Formula $m,n\in\mathbb{N}$
-\end_inset
-
-,
- where we multiply by 2 and then set the lower bound of the sums to 1 because terms with 
-\begin_inset Formula $j=0$
-\end_inset
-
- evaluate to 0.
- Now,
- since 
-\begin_inset Formula $h$
-\end_inset
-
- and 
-\begin_inset Formula $k$
-\end_inset
-
- are coprime,
- for 
-\begin_inset Formula $j\in\{1,\dots,k-1\}$
-\end_inset
-
-,
-\begin_inset Formula 
-\begin{align*}
-\left(\left(\frac{hj}{k}\right)\right) & =\frac{hj}{k}-\left\lfloor \frac{hj}{k}\right\rfloor -\frac{1}{2}=\frac{hj}{k}-\left\lceil \frac{hj}{k}\right\rceil +\frac{1}{2},
-\end{align*}
-
-\end_inset
-
-so substituting above,
-\begin_inset Formula 
-\begin{multline*}
-S\coloneqq kh(h-1)=\\
-=\sum_{j=1}^{k-1}\left(\frac{hj}{k}-\left(\left(\frac{hj}{k}\right)\right)-\frac{1}{2}\right)\left(\frac{hj}{k}-\left(\left(\frac{hj}{k}\right)\right)+\frac{1}{2}\right)+\\
-+2\sum_{j=1}^{h-1}j\left(\frac{kj}{h}-\left(\left(\frac{kj}{h}\right)\right)+\frac{1}{2}\right)=\\
-=\frac{h^{2}}{k^{2}}\sum_{j=1}^{k-1}j^{2}-\frac{2h}{k}\sum_{j=1}^{k-1}j\left(\left(\frac{hj}{k}\right)\right)+\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right)^{2}-\frac{k-1}{4}+\frac{2k}{h}\sum_{j=1}^{h-1}j^{2}-\\
--2\sum_{j=1}^{h-1}j\left(\left(\frac{kj}{h}\right)\right)+\frac{h^{2}-h}{2}.
-\end{multline*}
-
-\end_inset
-
-Now,
-\begin_inset Formula 
-\begin{align*}
-\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right) & =\sum_{j=1}^{k-1}\left(\left(\frac{j}{k}\right)\right)=\sum_{j=1}^{k-1}\left(\frac{j}{k}-\frac{1}{2}\right)=\frac{k(k-1)}{2k}-\frac{k-1}{2}=0,
-\end{align*}
-
-\end_inset
-
-so
-\begin_inset Formula 
-\begin{multline*}
-\sigma(h,k,0)=12\sum_{j=0}^{k-1}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj}{k}\right)\right)=12\sum_{j=1}^{k-1}\left(\frac{j}{k}-\frac{1}{2}\right)\left(\left(\frac{hj}{k}\right)\right)=\\
-=12\sum_{j=1}^{k-1}\frac{j}{k}\left(\left(\frac{hj}{k}\right)\right).
-\end{multline*}
-
-\end_inset
-
-In addition,
-\begin_inset Formula 
-\[
-\sum_{j=1}^{k-1}j^{2}=\frac{(k-1)k(2k-1)}{6}=\frac{k}{6}(2k^{2}-3k+1)=\frac{k^{3}}{3}-\frac{k^{2}}{2}+\frac{k}{6},
-\]
-
-\end_inset
-
-and in particular
-\begin_inset Formula 
-\begin{align*}
-\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right)^{2} & =\sum_{j=1}^{k-1}\left(\left(\frac{j}{k}\right)\right)^{2}\\
- & =\sum_{j=1}^{k-1}\frac{j^{2}}{k^{2}}-\sum_{j=1}^{k-1}\frac{j}{k}+\frac{k-1}{4}=\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{2}+\frac{k-1}{4}\\
- & =\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{4},
-\end{align*}
-
-\end_inset
-
-so finally
-\begin_inset Formula 
-\begin{align*}
-S= & \frac{kh^{2}}{3}-\frac{h^{2}}{2}+\frac{h^{2}}{6k}-\frac{h}{6}\sigma(h,k,0)+\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{2}+\frac{2kh^{2}}{3}-kh+\\
- & +\frac{k}{3}-\frac{h}{6}\sigma(k,h,0)+\frac{h^{2}}{2}-\frac{h}{2}\\
-= & kh(h-1)-\frac{h}{2}+\frac{h^{2}}{6k}+\frac{k}{6}+\frac{1}{6k}-\frac{h}{6}\sigma(h,k,0)-\frac{h}{6}\sigma(k,h,0).
-\end{align*}
-
-\end_inset
-
-With this,
-\begin_inset Formula 
-\[
-\sigma(h,k,0)+\sigma(k,h,0)=-3+\frac{h}{k}+\frac{k}{h}+\frac{1}{hk}.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc14[M20]
-\end_layout
-
-\end_inset
-
-The linear congruential generator that has 
-\begin_inset Formula $m=2^{35}$
-\end_inset
-
-,
- 
-\begin_inset Formula $a=2^{18}+1$
-\end_inset
-
-,
- 
-\begin_inset Formula $c=1$
-\end_inset
-
-,
- was given the serial correlation test on three batches of 1000 consecutive numbers,
- and the result was a very high correlation,
- between 
-\begin_inset Formula $0.2$
-\end_inset
-
- and 
-\begin_inset Formula $0.3$
-\end_inset
-
-,
- in each case.
- What is the serial correlation of this generator,
- taken over all 
-\begin_inset Formula $2^{35}$
-\end_inset
-
- numbers of the period?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-The generator has full period by 3.2.1.2–A,
- and 
-\begin_inset Formula $x'\coloneqq2^{18}-1$
-\end_inset
-
- gives us 
-\begin_inset Formula $S(x')=0$
-\end_inset
-
-.
- Thus,
- by (17),
- 
-\begin_inset Formula $C=(2^{35}\sigma(2^{18}+1,2^{35},1)-3+6(2^{35}-2^{18}))/(2^{70}-1)$
-\end_inset
-
-.
- Now we calculate the Dedekind coefficient by Theorem D.
-\begin_inset Formula 
-\begin{align*}
-2^{35} & =(2^{17}-1)(2^{18}+1)+(2^{17}+1), & 1 & =0(2^{18}+1)+1;\\
-2^{18}+1 & =1(2^{17}+1)+2^{17}, & 1 & =0(2^{17}+1)+1;\\
-2^{17}+1 & =1\cdot2^{17}+1 & 1 & =0(2^{17})+1;\\
-2^{17} & =2^{17}\cdot1+0, & 1 & =1\cdot1+0.
-\end{align*}
-
-\end_inset
-
-The number 
-\begin_inset Formula $h'\coloneqq2^{35}-2^{18}+1$
-\end_inset
-
- gives us 
-\begin_inset Formula $(2^{18}+1)h'\equiv1\pmod{2^{35}}$
-\end_inset
-
-,
- so
-\begin_inset Formula 
-\begin{multline*}
-\sigma(2^{18}+1,2^{35},1)=\frac{(\cancel{2^{18}}+1)+(2^{35}\cancel{-2^{18}}+1)}{2^{35}}+\left((2^{17}-1)-6\cdot0+6\frac{1^{2}}{2^{35}(2^{18}+1)}\right)-\\
--\left(1-6\cdot0+\frac{6\cdot1^{2}}{(2^{18}+1)(2^{17}+1)}\right)+\left(1-6\cdot0+6\frac{1^{2}}{(2^{17}+1)2^{17}}\right)-\left(2^{17}-6\cdot1+6\frac{1^{2}}{2^{17}}\right)\\
-\\-3-2+1=\\
-=\cancel{1}+\frac{2}{2^{35}}\cancel{+2^{17}}\cancel{-1}+\frac{6}{2^{53}+2^{35}}\cancel{-1}-\frac{6}{2^{35}+2^{18}+2^{17}+1}\cancel{+1}+\frac{6}{2^{34}+2^{17}}\cancel{-2^{17}}+6-\frac{6}{2^{17}}-4=\\
-=2+\frac{1}{2^{34}}+6\left(\frac{1}{2^{53}+2^{35}}-\frac{1}{2^{35}+3\cdot2^{17}+1}+\frac{1}{2^{34}+2^{17}}-\frac{1}{2^{17}}\right)=\\
-=2+\frac{1}{2^{34}}+6\frac{2^{17}+1-2^{35}\cancel{+2^{36}+2^{18}}-2^{53}\cancel{-2^{36}}-2^{35}\cancel{-2^{18}}}{2^{35}(2^{18}+1)(2^{17}+1)}=\\
-=2+\frac{1}{2^{34}}+3\frac{(-2^{36}+1)\cancel{(2^{17}+1)}}{2^{34}(2^{18}+1)\cancel{(2^{17}+1)}}=2+\frac{1}{2^{34}}-3\frac{2^{18}-1}{2^{34}}=2-\frac{3\cdot2^{18}-4}{2^{34}}=\\
-=2-\frac{3\cdot2^{16}-1}{2^{32}}=\frac{2^{33}-2^{17}-2^{16}+1}{2^{32}}=\frac{(2^{17}-1)(2^{16}-1)}{2^{32}}.
-\end{multline*}
-
-\end_inset
-
-Thus,
-\begin_inset Formula 
-\begin{multline*}
-C=\frac{8(2^{17}-1)(2^{16}-1)-3+6\cdot2^{18}(2^{17}-1)}{2^{70}-1}=\frac{91624920407}{393530540239137101141}\cong\\
-\cong2.33\cdot10^{-10}.
-\end{multline*}
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc18[M23]
-\end_layout
-
-\end_inset
-
-(U.
- Dieter.) Given positive integers 
-\begin_inset Formula $h$
-\end_inset
-
-,
- 
-\begin_inset Formula $k$
-\end_inset
-
-,
- 
-\begin_inset Formula $z$
-\end_inset
-
-,
- let
-\begin_inset Formula 
-\[
-S(h,k,c,z)=\sum_{0\leq j<z}\left(\left(\frac{hj+c}{k}\right)\right).
-\]
-
-\end_inset
-
-Show that this sum can be evaluated in closed form,
- in terms of the generalized Dedekind sums and the sawtooth function.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $S_{j}\coloneqq\left(\left(\frac{hj+c}{k}\right)\right)$
-\end_inset
-
- and note that 
-\begin_inset Formula $S_{j}=S_{j+k}$
-\end_inset
-
- for all 
-\begin_inset Formula $j$
-\end_inset
-
-.
- Thus,
- if 
-\begin_inset Formula $z>k$
-\end_inset
-
-,
-\begin_inset Formula 
-\[
-\sum_{0\leq j<z}\left(\left(\frac{hj+c}{k}\right)\right)=\left\lfloor \frac{z}{k}\right\rfloor \sum_{0\leq j<k}\left(\left(\frac{hj+c}{k}\right)\right)+\sum_{0\leq j<z\bmod k}\left(\left(\frac{hj+c}{k}\right)\right),
-\]
-
-\end_inset
-
-so we may assume 
-\begin_inset Formula $z\leq k$
-\end_inset
-
- from now on.
- Now,
- 
-\begin_inset Formula $\left\lfloor \frac{j}{k}\right\rfloor -\left\lfloor \frac{j-z}{k}\right\rfloor $
-\end_inset
-
- is 1 when 
-\begin_inset Formula $0\leq j<z$
-\end_inset
-
- and 0 when 
-\begin_inset Formula $z\leq j<k$
-\end_inset
-
-,
- so
-\begin_inset Formula 
-\begin{multline*}
-S(h,k,c,z)=\sum_{0\leq j<k}\left(\left\lfloor \frac{j}{k}\right\rfloor -\left\lfloor \frac{j-z}{k}\right\rfloor \right)\left(\left(\frac{hj+c}{k}\right)\right)=\\
-=\sum_{0\leq j<k}\left(\cancel{\frac{j}{k}}-\left(\left(\frac{j}{k}\right)\right)\cancel{-\frac{1}{2}}-\frac{\cancel{j}-z}{k}+\left(\left(\frac{j-z}{k}\right)\right)\cancel{+\frac{1}{2}}\right)\left(\left(\frac{hj+c}{k}\right)\right)+\\
-+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right)=\\
-=\sum_{0\leq j<k}\left(\left(\left(\frac{j-z}{k}\right)\right)+\frac{z}{k}-\left(\left(\frac{j}{k}\right)\right)\right)\left(\left(\frac{hj+c}{k}\right)\right)+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right).
-\end{multline*}
-
-\end_inset
-
-Let's evaluate the sum term by term.
- Clearly the term 
-\begin_inset Formula $-\left(\left(\frac{j}{k}\right)\right)$
-\end_inset
-
- sums to 
-\begin_inset Formula $-\frac{1}{12}\sigma(h,k,c)$
-\end_inset
-
-.
- For the term with 
-\begin_inset Formula $\frac{z}{k}$
-\end_inset
-
-,
- which is constant,
- we use the argument used to derive Eq.
- (13) in the text with 
-\begin_inset Formula $d\coloneqq\gcd\{h,k\}$
-\end_inset
-
-.
- Finally,
-\begin_inset Formula 
-\begin{multline*}
-\sum_{0\leq j<k}\left(\left(\frac{j-z}{k}\right)\right)\left(\left(\frac{hj+c}{k}\right)\right)=\sum_{-z\leq j<k-z}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj+c+hz}{k}\right)\right)=\\
-=\frac{1}{12}\sigma(h,k,c+hz).
-\end{multline*}
-
-\end_inset
-
-Putting it all together,
-\begin_inset Formula 
-\[
-S(h,k,c,z)=\frac{1}{12}\sigma(h,k,c+hz)-\frac{1}{12}\sigma(h,k,c)+\frac{zd}{k}\left(\left(\frac{c}{d}\right)\right)+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right).
-\]
-
-\end_inset
-
-For 
-\begin_inset Formula $z=k$
-\end_inset
-
-,
- this simplifies to 
-\begin_inset Formula $d\left(\left(\frac{c}{d}\right)\right)$
-\end_inset
-
-,
- and since 
-\begin_inset Formula $\left\lfloor \frac{z}{k}\right\rfloor +\frac{z\bmod k}{k}=\frac{z}{k}$
-\end_inset
-
-,
- it's easy to check that this formula still applies when 
-\begin_inset Formula $z>k$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc19[M23]
-\end_layout
-
-\end_inset
-
-Show that the 
-\emph on
-serial test
-\emph default
- can be analyzed over the full period,
- in terms of generalized Dedekind sums,
- by finding a formula for the probability that 
-\begin_inset Formula $\alpha\leq X_{n}<\beta$
-\end_inset
-
- and 
-\begin_inset Formula $\alpha'\leq X_{n+1}<\beta'$
-\end_inset
-
-,
- when 
-\begin_inset Formula $\alpha$
-\end_inset
-
-,
- 
-\begin_inset Formula $\beta$
-\end_inset
-
-,
- 
-\begin_inset Formula $\alpha'$
-\end_inset
-
-,
- and 
-\begin_inset Formula $\beta'$
-\end_inset
-
- are given integers with 
-\begin_inset Formula $0\leq\alpha<\beta\leq m$
-\end_inset
-
- and 
-\begin_inset Formula $0\leq\alpha'<\beta'\leq m$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Formula $P(x)\coloneqq\left\lfloor \frac{x-\alpha}{m}\right\rfloor -\left\lfloor \frac{x-\beta}{m}\right\rfloor $
-\end_inset
-
- is 1 precisely when 
-\begin_inset Formula $x\in[\alpha,\beta)$
-\end_inset
-
- and 0 for any other 
-\begin_inset Formula $x\in[0,1)$
-\end_inset
-
-.
- 
-\begin_inset Formula $Q(x)\coloneqq\left\lfloor \frac{x-\alpha'}{m}\right\rfloor -\left\lfloor \frac{x-\beta'}{m}\right\rfloor $
-\end_inset
-
- works in an analogous manner.
- For a linear congruential sequence given by 
-\begin_inset Formula $S(x)\coloneqq(ax+c)\bmod m$
-\end_inset
-
- that has maximum period,
- the probability that 
-\begin_inset Formula $x_{n}\in[\alpha,\beta)\land x_{n+1}\in[\alpha',\beta')$
-\end_inset
-
- is
-\begin_inset Formula 
-\begin{multline*}
-\frac{1}{m}\sum_{0\leq x<m}P(x)Q(ax+c)=\\
-=\frac{1}{m}\sum_{0\leq x<m}\left(\left\lfloor \frac{x-\alpha}{m}\right\rfloor -\left\lfloor \frac{x-\beta}{m}\right\rfloor \right)\left(\left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor -\left\lfloor \frac{S(x)-\beta'}{m}\right\rfloor \right)
-\end{multline*}
-
-\end_inset
-
-Now,
-\begin_inset Formula 
-\begin{align*}
-\left\lfloor \frac{x-\alpha}{m}\right\rfloor  & =\frac{x}{m}-\frac{\alpha}{m}-\frac{1}{2}-\left(\left(\frac{x-\alpha}{m}\right)\right)+\frac{1}{2}\delta_{x,\alpha},\\
-\left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor  & =\frac{(ax+c)\bmod m-\alpha'}{m}-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{1}{2}+\frac{1}{2}\delta_{S(x)\alpha'}=\\
- & =\left(\left(\frac{ax+c}{m}\right)\right)-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{\alpha'}{m}+\frac{1}{2}(\delta_{S(x)\alpha'}-\delta_{S(x)0}).
-\end{align*}
-
-\end_inset
-
-Thus,
- 
-\begin_inset Formula 
-\begin{multline*}
-\sum_{0\leq x<m}\left\lfloor \frac{x-\alpha}{m}\right\rfloor \left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor =\\
-=\sum_{0\leq x<m}\left(\left(\frac{x}{m}-\frac{1}{2}\right)-\frac{\alpha}{m}-\left(\left(\frac{x-\alpha}{m}\right)\right)\right)\\
-\left(\left(\left(\frac{ax+c}{m}\right)\right)-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{\alpha'}{m}\right)+\\
-+\frac{1}{2}\left(\left\lfloor \frac{S(\alpha)-\alpha'}{m}\right\rfloor +\left\lfloor \frac{S^{-1}(\alpha')-\alpha}{m}\right\rfloor -\left\lfloor \frac{S^{-1}(0)-\alpha}{m}\right\rfloor \right)+\frac{1}{4}([S(\alpha)=\alpha']-[S(\alpha)=0]).
-\end{multline*}
-
-\end_inset
-
-The terms outside this last sum can be calculated directly.
- Inside the sum,
- we have a product of two sums with three terms each,
- which we may expand into 9 terms.
- For these,
- note that 
-\begin_inset Formula $\frac{x}{m}-\frac{1}{2}=\left(\left(\frac{x}{m}\right)\right)-\frac{1}{2}[x=0]$
-\end_inset
-
-,
- so for example
-\begin_inset Formula 
-\[
-\sum_{0\leq x<m}\left(\frac{x}{m}-\frac{1}{2}\right)\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)=\frac{1}{12}\delta(a,m,c-\alpha')-\left(\left(\frac{c-\alpha'}{m}\right)\right),
-\]
-
-\end_inset
-
-and similarly,
-\begin_inset Formula 
-\begin{multline*}
-\sum_{0\leq x<m}\left(\left(\frac{x-\alpha}{m}\right)\right)\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)=\\
-=\sum_{-\alpha\leq x<m-\alpha}\left(\left(\frac{x}{m}\right)\right)\left(\left(\frac{ax+c-\alpha'+\alpha}{m}\right)\right)=\frac{1}{12}\sigma(a,m,c-\alpha'+\alpha).
-\end{multline*}
-
-\end_inset
-
-The other terms do not include sawtooth functions and can be expanded mechanically using that 
-\begin_inset Formula $\sum_{0\leq x<m}x=\frac{m(m-1)}{2}$
-\end_inset
-
-.
- Then we can compute the initial sum as the sum of 4 of these sums.
-\end_layout
-
-\begin_layout Subsubsection
-Second Set
-\end_layout
-
-\begin_layout Standard
-In many cases,
- exact computations with integers are quite difficult to carry out,
- but we can attempt to study the probabilities that arise when we take the average real values of 
-\begin_inset Formula $x$
-\end_inset
-
- instead of restricting the calculation to integer values.
- Although these results are only approximate,
- they shed some light on the subject.
-\end_layout
-
-\begin_layout Standard
-It is convenient to deal with numbers 
-\begin_inset Formula $U_{n}$
-\end_inset
-
- between zero and one;
- for linear congruential sequences,
- 
-\begin_inset Formula $U_{n}=X_{n}/m$
-\end_inset
-
-,
- and we have 
-\begin_inset Formula $U_{n+1}=\{aU_{n}+\theta\}$
-\end_inset
-
-,
- where 
-\begin_inset Formula $\theta=c/m$
-\end_inset
-
- and 
-\begin_inset Formula $\{x\}$
-\end_inset
-
- denotes 
-\begin_inset Formula $x\bmod1$
-\end_inset
-
-.
- For example,
- the formula for serial correlation now becomes
-\begin_inset Formula 
-\[
-C=\left(\int_{0}^{1}x\{ax+\theta\}\text{d}x-\left(\int_{0}^{1}x\text{d}x\right)^{2}\right)\biggg/\left(\int_{0}^{1}x^{2}\text{d}x-\left(\int_{0}^{1}x\text{d}x\right)^{2}\right).
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc21[HM23]
-\end_layout
-
-\end_inset
-
-(R.
- R.
- Coveyou.) What is the value of 
-\begin_inset Formula $C$
-\end_inset
-
- in the formula just given?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-We have
-\begin_inset Formula 
-\begin{align*}
-\int_{0}^{1}x\text{d}x & =\left.\frac{x^{2}}{2}\right|_{x=0}^{1}=\frac{1}{2}, & \int_{0}^{1}x^{2}\text{d}x & =\left.\frac{x^{3}}{3}\right|_{x=0}^{1}=\frac{1}{3},
-\end{align*}
-
-\end_inset
-
-and we just need to calculate the more complex integral.
- Assume 
-\begin_inset Formula $a>0$
-\end_inset
-
-.
- Then the graph for 
-\begin_inset Formula $\{ax+\theta\}$
-\end_inset
-
- is a sequence of lines.
- The first goes from 
-\begin_inset Formula $(0,\theta)$
-\end_inset
-
- to 
-\begin_inset Formula $(\frac{1-\theta}{a},1)$
-\end_inset
-
-,
- the next one from 
-\begin_inset Formula $(\frac{1-\theta}{a},0)$
-\end_inset
-
- to 
-\begin_inset Formula $(\frac{2-\theta}{a},1)$
-\end_inset
-
-,
- etc.,
- and the last one goes from 
-\begin_inset Formula $(1-\tfrac{\theta}{a},0)$
-\end_inset
-
- to 
-\begin_inset Formula $(1,\theta)$
-\end_inset
-
- (we used that 
-\begin_inset Formula $a$
-\end_inset
-
- is an integer to calculate this).
- Thus
-\begin_inset Formula 
-\[
-\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{k=1}^{a-1}\int_{\frac{k-\theta}{a}}^{\frac{k+1-\theta}{a}}x(ax+\theta-k)\text{d}x+\int_{0}^{\frac{1-\theta}{a}}x(ax+\theta)\text{d}x+\int_{1-\frac{\theta}{a}}^{1}x(ax+\theta-a)\text{d}x.
-\]
-
-\end_inset
-
-Now,
-\begin_inset Formula 
-\[
-\int x(ax+\theta-k)\text{d}x=\frac{a}{3}x^{3}+\frac{\theta-k}{2}x^{2}+C,
-\]
-
-\end_inset
-
-so if we call 
-\begin_inset Formula $x_{k}\coloneqq\frac{k-\theta}{a}$
-\end_inset
-
- except that 
-\begin_inset Formula $x_{0}\coloneqq0$
-\end_inset
-
- and 
-\begin_inset Formula $x_{a+1}\coloneqq1$
-\end_inset
-
-,
- we have
-\begin_inset Formula 
-\begin{multline*}
-\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{0\leq k\leq a}\int_{x_{k}}^{x_{k+1}}x(ax+\theta-k)\text{d}x=\\
-=\sum_{0\leq k\leq a}\left(\frac{a}{3}x_{k+1}^{3}+\frac{\theta-k}{2}x_{k+1}^{2}-\frac{a}{3}x_{k}^{3}-\frac{\theta-k}{2}x_{k}^{2}\right)=\frac{a}{3}+\frac{\theta-a}{2}+\sum_{0<k\leq a}\frac{1}{2}x_{k}^{2}=\\
-=\frac{a}{3}+\frac{\theta-a}{2}+\frac{1}{2a^{2}}\sum_{k=1}^{a}(k^{2}-2k\theta+\theta^{2})=\frac{\theta}{2}-\frac{a}{6}+\frac{(a+1)(2a+1)}{12a}-\frac{(a+1)\theta}{2a}+\frac{\theta^{2}}{2a}=\\
-=\frac{\theta(\theta-1)}{2a}+\frac{1}{12a}+\frac{1}{4}.
-\end{multline*}
-
-\end_inset
-
-Putting it all together,
-\begin_inset Formula 
-\[
-C=\left(\frac{\theta(\theta-1)}{2a}+\frac{1}{12a}+\frac{1}{4}-\frac{1}{4}\right)\biggg/\left(\frac{1}{3}-\frac{1}{4}\right)=\frac{6\theta(\theta-1)+1}{a}.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc22[M22]
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $a$
-\end_inset
-
- be an integer,
- and let 
-\begin_inset Formula $0\leq\theta<1$
-\end_inset
-
-.
- If 
-\begin_inset Formula $x$
-\end_inset
-
- is a random real number,
- uniformly distributed between 0 and 1,
- and if 
-\begin_inset Formula $s(x)=\{ax+\theta\}$
-\end_inset
-
-,
- what is the probability that 
-\begin_inset Formula $s(x)<x$
-\end_inset
-
-?
- (This is the 
-\begin_inset Quotes eld
-\end_inset
-
-real number
-\begin_inset Quotes erd
-\end_inset
-
- analog of Theorem P.)
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-As in the previous exercise,
- let 
-\begin_inset Formula $x_{0}\coloneqq0$
-\end_inset
-
-,
- 
-\begin_inset Formula $x_{k}\coloneqq\frac{k-\theta}{a}$
-\end_inset
-
- for 
-\begin_inset Formula $k\in\{1,\dots,a\}$
-\end_inset
-
-,
- and 
-\begin_inset Formula $x_{a+1}\coloneqq1$
-\end_inset
-
-,
- for 
-\begin_inset Formula $k\in\{0,\dots,a\}$
-\end_inset
-
- and 
-\begin_inset Formula $x\in[x_{k},x_{k+1})$
-\end_inset
-
- we have 
-\begin_inset Formula $\lfloor ax+\theta\rfloor=k$
-\end_inset
-
- and
-\begin_inset Formula 
-\[
-s(x)=ax+\theta-\lfloor ax+\theta\rfloor<x\iff(a-1)x<\lfloor ax+\theta\rfloor-\theta=k-\theta\iff x<\frac{k-\theta}{a-1},
-\]
-
-\end_inset
-
-so in particular 
-\begin_inset Formula $s(x)\geq x$
-\end_inset
-
- for 
-\begin_inset Formula $x<x_{1}$
-\end_inset
-
- and the probability is
-\begin_inset Formula 
-\begin{multline*}
-\int_{0}^{1}[s(x)<x]\text{d}x=\sum_{k=1}^{a}\int_{x_{k}}^{x_{k+1}}[x<\tfrac{k-\theta}{a-1}]\text{d}x=\sum_{k=1}^{a-1}\left(\frac{k-\theta}{a-1}-\frac{k-\theta}{a}\right)+1-\frac{a-\theta}{a}=\\
-=\sum_{k=1}^{a-1}\frac{k-\theta}{a(a-1)}+\frac{\theta}{a}=\left(\frac{1}{2}-\frac{\theta}{a}\right)+\frac{\theta}{a}=\frac{1}{2}.
-\end{multline*}
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc25[M25]
-\end_layout
-
-\end_inset
-
-Let 
-\begin_inset Formula $\alpha$
-\end_inset
-
-,
- 
-\begin_inset Formula $\beta$
-\end_inset
-
-,
- 
-\begin_inset Formula $\alpha'$
-\end_inset
-
-,
- 
-\begin_inset Formula $\beta'$
-\end_inset
-
- be real numbers with 
-\begin_inset Formula $0\leq\alpha<\beta\leq1$
-\end_inset
-
-,
- 
-\begin_inset Formula $0\leq\alpha'<\beta'\leq1$
-\end_inset
-
-.
- Under the assumptions of exercise 22,
- what is the probability that 
-\begin_inset Formula $\alpha\leq x<\beta$
-\end_inset
-
- and 
-\begin_inset Formula $\alpha'\leq s(x)<\beta'$
-\end_inset
-
-?
- (This is the 
-\begin_inset Quotes eld
-\end_inset
-
-real number
-\begin_inset Quotes erd
-\end_inset
-
- analog of exercise 19.)
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-In the notation of the answer to exercise 22,
- assume that 
-\begin_inset Formula $\alpha\in[x_{p},x_{p+1})$
-\end_inset
-
- and 
-\begin_inset Formula $\beta\in[x_{q},x_{q+1})$
-\end_inset
-
-,
- with 
-\begin_inset Formula $0\leq p\leq q\leq a$
-\end_inset
-
-.
- For 
-\begin_inset Formula $x\in[x_{k},x_{k+1})$
-\end_inset
-
-,
-\begin_inset Formula 
-\[
-\alpha'\leq s(x)<\beta'\iff\alpha'\leq ax+\theta-k<\beta'\iff x\in\left[\frac{\alpha'+k-\theta}{a},\frac{\beta'+k-\theta}{a}\right).
-\]
-
-\end_inset
-
-Note that,
- since 
-\begin_inset Formula $s(x)$
-\end_inset
-
- goes from 0 to 1 when 
-\begin_inset Formula $x$
-\end_inset
-
- goes from 
-\begin_inset Formula $x_{k}$
-\end_inset
-
- to 
-\begin_inset Formula $x_{k+1}$
-\end_inset
-
-,
- each of these intervals has 
-\begin_inset Formula $s(x)$
-\end_inset
-
- enter and exit 
-\begin_inset Formula $[\alpha',\beta')$
-\end_inset
-
- and fully contains the interval above.
- Let 
-\begin_inset Formula $s_{k}^{-1}(y)\coloneqq\frac{y+k-\theta}{a}$
-\end_inset
-
-.
- If 
-\begin_inset Formula $p=q$
-\end_inset
-
-,
- the probability is
-\begin_inset Formula 
-\[
-\int_{\alpha}^{\beta}[\alpha'\leq s(x)<\beta']\text{d}x=\max\left\{ 0,\min\{\beta,s_{p}^{-1}(\beta')\}-\max\{\alpha,s_{p}^{-1}(\alpha')\}\right\} .
-\]
-
-\end_inset
-
-If 
-\begin_inset Formula $p\neq q$
-\end_inset
-
-,
- we have to consider the two extremes and the 
-\begin_inset Formula $q-p-1$
-\end_inset
-
- intervals in the middle,
- each of which contributes 
-\begin_inset Formula $\frac{\beta'-\alpha'}{a}$
-\end_inset
-
-,
- so the probability in this case is
-\begin_inset Formula 
-\begin{multline*}
-\max\left\{ 0,s_{p}^{-1}(\beta')-\max\{\alpha,s_{p}^{-1}(\alpha')\}\right\} +(q-p-1)\frac{\beta'-\alpha'}{a}+\\
-+\max\left\{ 0,\min\{\beta,s_{q}^{-1}(\beta')\}-s_{q}^{-1}(\alpha')\right\} .
-\end{multline*}
-
-\end_inset
-
-Note that this last formula is still valid when 
-\begin_inset Formula $p=q$
-\end_inset
-
-.
-\end_layout
-
-\end_body
-\end_document