3.5 What Is a Random Sequence?

2 files changed, 1214 insertions, 0 deletions

diff --git a/3.5.lyx b/3.5.lyx
new file mode 100644
index 0000000..87a5c8a
--- /dev/null
+++ b/3.5.lyx
@@ -0,0 +1,1191 @@
+#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
+exerc1[10]
+\end_layout
+
+\end_inset
+
+Can a periodic sequence be equidistributed?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Not if it's a real sequence,
+ because the period must be finite and,
+ if 
+\begin_inset Formula $0\leq x_{1}<\dots<x_{t}\leq1$
+\end_inset
+
+ are the numbers that appear in the period,
+ then 
+\begin_inset Formula $\text{Pr}(\frac{1}{3}(2x_{1}+x_{2})\leq x<\frac{1}{3}(x_{1}+2x_{2}))=0\neq\frac{1}{3}(x_{2}-x_{1})$
+\end_inset
+
+ (a similar proof can be made for 
+\begin_inset Formula $t=1$
+\end_inset
+
+).
+ If it's an integer sequence it can happen;
+ for example for the 
+\begin_inset Formula $b$
+\end_inset
+
+-ary sequence with period 
+\begin_inset Formula $0,1,2,\dots,b-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc2[10]
+\end_layout
+
+\end_inset
+
+Consider the periodic binary sequence 0,
+ 0,
+ 1,
+ 1,
+ 0,
+ 0,
+ 1,
+ 1,
+ 
+\begin_inset Formula $\dots$
+\end_inset
+
+.
+ Is it 1-distributed?
+ Is it 2-distributed?
+ Is it 3-distributed?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+It is clearly 1-distributed and 2-distributed,
+ but not 3-distributed because 
+\begin_inset Quotes eld
+\end_inset
+
+111
+\begin_inset Quotes erd
+\end_inset
+
+ never appears.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc5[HM22]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $U_{n}=(2^{\lfloor\lg(n+1)\rfloor}/3)\bmod1$
+\end_inset
+
+.
+ What is 
+\begin_inset Formula $\text{Pr}(U_{n}<\frac{1}{2})$
+\end_inset
+
+?
+\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 $\lfloor\lg(n+1)\rfloor=0$
+\end_inset
+
+ for 
+\begin_inset Formula $n=0$
+\end_inset
+
+;
+ 1 for 
+\begin_inset Formula $n=1,2$
+\end_inset
+
+;
+ 2 for 
+\begin_inset Formula $n=3,4,5,6$
+\end_inset
+
+,
+ 3 for 
+\begin_inset Formula $n=7,\dots,14$
+\end_inset
+
+,
+ etc.,
+ so the sequence 
+\begin_inset Formula $(2^{\lfloor\lg(n+1)\rfloor})_{n}$
+\end_inset
+
+ has 1 1's,
+ followed by 2 2's,
+ 4 4's,
+ 8 8's,
+ etc.
+ It is easy to prove by induction that,
+ when 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+ is even,
+ 
+\begin_inset Formula $2^{k}\equiv1\bmod3$
+\end_inset
+
+,
+ and when it's odd,
+ 
+\begin_inset Formula $2^{k}\equiv2\bmod3$
+\end_inset
+
+,
+ and so 
+\begin_inset Formula $U_{n}<\frac{1}{2}$
+\end_inset
+
+ precisely when 
+\begin_inset Formula $\lfloor\lg(n+1)\rfloor$
+\end_inset
+
+ is even,
+ which is when 
+\begin_inset Formula $2^{k}\equiv1\bmod3$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+If 
+\begin_inset Formula $\nu(n)=|\{m\leq n\mid U_{n}<\frac{1}{2}\}|$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $\nu(n)/n$
+\end_inset
+
+ clearly increases when 
+\begin_inset Formula $n$
+\end_inset
+
+ is between 
+\begin_inset Formula $2^{2k}-1$
+\end_inset
+
+ and 
+\begin_inset Formula $2^{2k+1}-1$
+\end_inset
+
+,
+ and it decreases between 
+\begin_inset Formula $2^{2k-1}-1$
+\end_inset
+
+ and 
+\begin_inset Formula $2^{2k}-1$
+\end_inset
+
+,
+ for 
+\begin_inset Formula $k\in\mathbb{N}^{*}$
+\end_inset
+
+.
+ The limit exists if the subsequence made from these infinite local minima and the one made from these infinite local maxima both have a limit and these limits match.
+\end_layout
+
+\begin_layout Standard
+For the maxima,
+ 
+\begin_inset Formula $\nu(1)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\nu(7)=5$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\nu(31)=21$
+\end_inset
+
+,
+ etc.
+ In general,
+ 
+\begin_inset Formula 
+\[
+\nu(2^{2k+1}-1)=\sum_{i=0}^{k}2^{2k}=\frac{1-4^{k+1}}{1-4}=\frac{4^{k+1}-1}{3},
+\]
+
+\end_inset
+
+so
+\begin_inset Formula 
+\[
+\lim_{k}\frac{\nu(2^{2k+1}-1)}{2^{2k+1}-1}=\frac{\frac{4^{k+1}-1}{3}}{2\cdot4^{k}-1}=\frac{1}{3}\frac{4\cdot4^{k}-1}{2\cdot4^{k}-1}=\frac{2}{3}.
+\]
+
+\end_inset
+
+For the minima,
+ 
+\begin_inset Formula $\nu(3)=1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\nu(15)=5$
+\end_inset
+
+,
+ etc.,
+ and in general 
+\begin_inset Formula $\nu(2^{2k}-1)=\nu(2^{2k-1}-1)=\frac{4^{k}-1}{3}$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\[
+\lim_{k}\frac{\nu(2^{2k}-1)}{2^{2k}-1}=\frac{1}{3}\frac{4^{k}-1}{4^{k}-1}=\frac{1}{3}.
+\]
+
+\end_inset
+
+Since 
+\begin_inset Formula $\frac{1}{3}\neq\frac{2}{3}$
+\end_inset
+
+,
+ this probability is undefined.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc10[HM22]
+\end_layout
+
+\end_inset
+
+Where was the fact that 
+\begin_inset Formula $m$
+\end_inset
+
+ divides 
+\begin_inset Formula $q$
+\end_inset
+
+ used in the proof of Theorem C?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+This is used for the sums in the second page of proof,
+ when telling the range of 
+\begin_inset Formula $t$
+\end_inset
+
+.
+ In particular,
+ it is needed when evaluating the sum over 
+\begin_inset Formula $t$
+\end_inset
+
+ in Equation (22).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc11[M10]
+\end_layout
+
+\end_inset
+
+Use Theorem C to prove that if a sequence 
+\begin_inset Formula $\langle U_{n}\rangle$
+\end_inset
+
+ is 
+\begin_inset Formula $\infty$
+\end_inset
+
+-distributed,
+ so is the subsequence 
+\begin_inset Formula $\langle U_{2n}\rangle$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Since it's 
+\begin_inset Formula $\infty$
+\end_inset
+
+-distributed,
+ it's also 
+\begin_inset Formula $(2,2k)$
+\end_inset
+
+-distributed for all 
+\begin_inset Formula $k\in\mathbb{N}^{*}$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $\text{Pr}(u_{1}\leq U_{2n}<v_{1},\dots,u_{2k}\leq U_{2n+2k-1}<v_{2k})=(v_{1}-u_{1})\cdots(v_{k}-u_{k})$
+\end_inset
+
+ for any 
+\begin_inset Formula $u_{1},v_{1},\dots,u_{k},v_{k}\in[0,1)$
+\end_inset
+
+ with each 
+\begin_inset Formula $u_{i}<v_{i}$
+\end_inset
+
+,
+ and in particular,
+ if we let 
+\begin_inset Formula $u_{2},u_{4},\dots,u_{2k}=0$
+\end_inset
+
+ and 
+\begin_inset Formula $v_{2},v_{4},\dots,v_{2k}=1$
+\end_inset
+
+ we get the formula that shows that 
+\begin_inset Formula $\langle U_{2n}\rangle$
+\end_inset
+
+ is 
+\begin_inset Formula $k$
+\end_inset
+
+-distributed.
+ And since this 
+\begin_inset Formula $k$
+\end_inset
+
+ is arbitrary,
+ 
+\begin_inset Formula $\langle U_{2n}\rangle$
+\end_inset
+
+ is 
+\begin_inset Formula $\infty$
+\end_inset
+
+-distributed.
+ Note that this argument applies to any 
+\begin_inset Formula $\langle U_{mn+j}\rangle$
+\end_inset
+
+ with 
+\begin_inset Formula $m\in\mathbb{N}^{*}$
+\end_inset
+
+ and 
+\begin_inset Formula $j\in\mathbb{N}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc18[HM22]
+\end_layout
+
+\end_inset
+
+Prove that if 
+\begin_inset Formula $U_{0},U_{1},\dots$
+\end_inset
+
+ is 
+\begin_inset Formula $k$
+\end_inset
+
+-distributed,
+ so is the sequence 
+\begin_inset Formula $V_{0},V_{1},\dots$
+\end_inset
+
+ where 
+\begin_inset Formula $V_{n}=\lfloor nU_{n}\rfloor/n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Take any 
+\begin_inset Formula $u_{1},v_{1},\dots,u_{k},v_{k}\in[0,1)$
+\end_inset
+
+ such that each 
+\begin_inset Formula $u_{i}<v_{i}$
+\end_inset
+
+.
+ If 
+\begin_inset Formula $u_{i}\leq V_{n}<v_{i}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $u_{i}-\frac{1}{n}\leq U_{n}<v_{i}+\frac{1}{n}$
+\end_inset
+
+,
+ so if 
+\begin_inset Formula $S(n)\coloneqq\{\forall i,u_{i}\leq V_{n+i}<v_{i}\}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula 
+\begin{align*}
+\overline{\text{Pr}}(S(n)) & \leq\text{Pr}\left(\forall i,u_{i}-\frac{1}{n+i}\leq U_{n+i}<v_{i}+\frac{1}{n+i}\right)\\
+ & \leq\text{Pr}\left(\forall i,u_{i}-\frac{1}{n}\leq U_{n+i}<v_{i}+\frac{1}{n}\right)\\
+ & \leq\text{Pr}\left(\forall i,u_{i}-\frac{1}{n_{0}}\leq U_{n+i}<v_{i}+\frac{1}{n_{0}}\right)
+\end{align*}
+
+\end_inset
+
+for any 
+\begin_inset Formula $n_{0}\in\mathbb{N}$
+\end_inset
+
+,
+ since the first finitely many terms of the sequence 
+\begin_inset Quotes eld
+\end_inset
+
+don't matter,
+\begin_inset Quotes erd
+\end_inset
+
+ and since 
+\begin_inset Formula $n_{0}$
+\end_inset
+
+ is arbitrary,
+ taking limits on it we see that 
+\begin_inset Formula $\overline{\text{Pr}}(S(n))\leq\text{Pr}(\forall i,u_{i}\leq U_{n+i}<v_{i})=\prod_{i}(v_{i}-u_{i})$
+\end_inset
+
+.
+ Similarly,
+ if 
+\begin_inset Formula $u_{i}+\frac{1}{n}\leq U_{n}<v_{i}-\frac{1}{n}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $u_{i}\leq V_{n}<v_{i}$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\[
+\underline{\text{Pr}}(S(n))\geq\text{Pr}\left(\forall i,u_{i}+\frac{1}{n}\leq U_{n+i}<v_{i}+\frac{1}{n}\right)\geq\text{Pr}\left(\forall i,u_{i}+\frac{1}{n_{0}}\leq U_{n+i}<v_{i}-\frac{1}{n_{0}}\right),
+\]
+
+\end_inset
+
+this time taking 
+\begin_inset Formula $n_{0}$
+\end_inset
+
+ such that 
+\begin_inset Formula $\frac{1}{n_{0}}\leq v_{i}-u_{i}$
+\end_inset
+
+ for every 
+\begin_inset Formula $i$
+\end_inset
+
+.
+ Again we reach the conclusion that 
+\begin_inset Formula $\underline{\text{Pr}}(S(n))\geq\prod_{i}(v_{i}-u_{i})$
+\end_inset
+
+.
+ We get the result by the same argument used at the end of Theorem A.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc28[HM21]
+\end_layout
+
+\end_inset
+
+Use the sequence (11) to construct a 
+\begin_inset Formula $[0..1)$
+\end_inset
+
+ sequence that is 3-distributed,
+ for which 
+\begin_inset Formula $\text{Pr}(U_{2n}\geq\frac{1}{2})=\frac{3}{4}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $(W_{n})_{n}$
+\end_inset
+
+ be an 
+\begin_inset Formula $\infty$
+\end_inset
+
+-distributed real-valued sequence,
+ and let 
+\begin_inset Formula $(X_{n})_{n}$
+\end_inset
+
+ be the 3-distributed binary sequence from (11),
+ then 
+\begin_inset Formula $(U_{n}\coloneqq\frac{1}{2}(W_{n}+1-X_{n}))_{n}$
+\end_inset
+
+ satisfies the properties.
+ For if 
+\begin_inset Formula $0\leq u_{i}<v_{i}<1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $i\in\{1,2,3\}$
+\end_inset
+
+,
+ and if we assume that,
+ for each 
+\begin_inset Formula $i$
+\end_inset
+
+,
+ 
+\begin_inset Formula $v_{i}\geq\frac{1}{2}$
+\end_inset
+
+ implies 
+\begin_inset Formula $u_{i}\geq\frac{1}{2}$
+\end_inset
+
+ (so the 
+\begin_inset Quotes eld
+\end_inset
+
+rectangle
+\begin_inset Quotes erd
+\end_inset
+
+ is contained in one quadrant),
+ then 
+\begin_inset Formula $u_{i}\leq U_{n}<v_{i}$
+\end_inset
+
+ if,
+ and only if,
+ 
+\begin_inset Formula $\lfloor2u_{i}\rfloor=\lfloor2U_{i}\rfloor=1-X_{n}$
+\end_inset
+
+ and 
+\begin_inset Formula $2u_{i}\bmod1\leq2U_{n}\bmod1=W_{n}\leq2v_{i}$
+\end_inset
+
+.
+ Since 
+\begin_inset Formula $W_{n}$
+\end_inset
+
+ is 
+\begin_inset Formula $(16,3)$
+\end_inset
+
+-distributed,
+ the triplets 
+\begin_inset Formula $(W_{n},W_{n+1},W_{n+2})$
+\end_inset
+
+ starting at positions where 
+\begin_inset Formula $(X_{n},X_{n+1},X_{n+2})$
+\end_inset
+
+ has a given value have the same density as those starting at positions where it has any other value,
+ so 
+\begin_inset Formula 
+\begin{multline*}
+\text{Pr}(\forall i,u_{i}\leq U_{n}<v_{i})=\text{Pr}(\forall i,\lfloor2u_{i}\rfloor=1-X_{n})\text{Pr}(\forall i,2u_{i}\bmod1\leq W_{n}\leq2v_{i}\bmod1)=\\
+=\frac{1}{8}\prod_{i}(2v_{i}-2u_{i})=\prod_{i}(v_{i}-u_{i})
+\end{multline*}
+
+\end_inset
+
+and the sequence is 3-distributed (the cases where some 
+\begin_inset Formula $\lfloor2u_{i}\rfloor\neq\lfloor2v_{i}\rfloor$
+\end_inset
+
+ can be split into cases where this is not the case).
+ In addition,
+ 
+\begin_inset Formula $\text{Pr}(U_{2n}\geq\frac{1}{2})=\text{Pr}(X_{2n}=0)=\frac{3}{4}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc34[M25]
+\end_layout
+
+\end_inset
+
+Define subsequence rules 
+\begin_inset Formula ${\cal R}_{1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\cal R}_{2}$
+\end_inset
+
+,
+ 
+\begin_inset Formula ${\cal R}_{3}$
+\end_inset
+
+,
+ ...
+ such that Algorithm W can be used with these rules to give an effective algorithm to construct a 
+\begin_inset Formula $[0..1)$
+\end_inset
+
+ sequence satisfying Definition R1.
+\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.)
+\end_layout
+
+\end_inset
+
+The 
+\begin_inset Quotes eld
+\end_inset
+
+algorithm
+\begin_inset Quotes erd
+\end_inset
+
+ gives us a potentially infinite amount of sequences 
+\begin_inset Formula $\langle U_{n}\rangle{\cal R}_{k}$
+\end_inset
+
+ that are 1-distributed,
+ so we may encode the properties that we want to check for in the value 
+\begin_inset Formula $k$
+\end_inset
+
+.
+ Specifically,
+ we want to check that,
+ for an increasing sequence of bases 
+\begin_inset Formula $(b_{n})_{n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\in\mathbb{N}^{*}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $a_{1},\dots,a_{k}\in\{0,\dots,b-1\}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $U_{n-k}=a_{k},\dots,U_{n-1}=a_{1}$
+\end_inset
+
+,
+ so if,
+ for example,
+ 
+\begin_inset Formula $k=10^{b}10^{a_{1}}10^{a_{2}}1\cdots10a^{j}$
+\end_inset
+
+ with each 
+\begin_inset Formula $a_{i}<b$
+\end_inset
+
+,
+ we may set 
+\begin_inset Formula ${\cal R}_{k}(x_{0},\dots,x_{n-1})=1$
+\end_inset
+
+ if,
+ and only if,
+ 
+\begin_inset Formula $\lfloor bU_{n-1}\rfloor=a_{1}\land\dots\land\lfloor bU_{n-k}\rfloor=a_{k}$
+\end_inset
+
+.
+ For every other value of 
+\begin_inset Formula $k$
+\end_inset
+
+,
+ we may as well set 
+\begin_inset Formula ${\cal R}_{k}\equiv1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+TODO 44 (
+\begin_inset Formula $<$
+\end_inset
+
+4pp.,
+ 
+\begin_inset Formula $<$
+\end_inset
+
+1:53)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc44[16]
+\end_layout
+
+\end_inset
+
+(I.
+ J.
+ Good.) Can a valid table of random digits contain just one misprint?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Yes;
+ for example,
+ both 23456782019372837458 and 23456782019372837459 are random.
+ Of course,
+ this is not true for any misprint,
+ as then all numbers would be random.
+ For example,
+ 23456782019372828221 is random but 23456782019372828222 isn't,
+ as it contains too many 2's.
+ This has been calculated with the following (terrible) code:
+\end_layout
+
+\begin_layout Standard
+\begin_inset listings
+lstparams "language=Python,numbers=left,basicstyle={\footnotesize\ttfamily},breaklines=true"
+inline false
+status open
+
+\begin_layout Plain Layout
+
+import math
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+
+def israndom(digs):
+\end_layout
+
+\begin_layout Plain Layout
+
+    N = len(digs)
+\end_layout
+
+\begin_layout Plain Layout
+
+    dev = math.sqrt(N)
+\end_layout
+
+\begin_layout Plain Layout
+
+    for k in range(0,
+ math.floor(math.log10(N)) + 1):
+\end_layout
+
+\begin_layout Plain Layout
+
+        pos = 10**k
+\end_layout
+
+\begin_layout Plain Layout
+
+        expect = N/pos
+\end_layout
+
+\begin_layout Plain Layout
+
+        for ss in range(pos,
+ 2*pos):
+\end_layout
+
+\begin_layout Plain Layout
+
+          sb = str(ss)[1:]
+\end_layout
+
+\begin_layout Plain Layout
+
+          amt = len([n for n in range(len(digs)) if digs[n:n+k] == sb])
+\end_layout
+
+\begin_layout Plain Layout
+
+          if abs(amt-expect) > dev:
+\end_layout
+
+\begin_layout Plain Layout
+
+              print(
+\begin_inset Quotes eld
+\end_inset
+
+FAIL
+\begin_inset Quotes erd
+\end_inset
+
+,
+ digs,
+ sb)
+\end_layout
+
+\begin_layout Plain Layout
+
+              return False
+\end_layout
+
+\begin_layout Plain Layout
+
+    return True
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+
+for x in range(123456782019372800000,
+ 123456790000000000000):
+\end_layout
+
+\begin_layout Plain Layout
+
+    if israndom(str(x)[1:]):
+\end_layout
+
+\begin_layout Plain Layout
+
+        print(str(x)[1:])
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document
diff --git a/index.lyx b/index.lyx
index 3090b9f..2a79f90 100644
--- a/index.lyx
+++ b/index.lyx
@@ -2162,6 +2162,29 @@ A10+R25-16
 What Is a Random Sequence?
 \end_layout
 
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "3.5.lyx"
+literal "false"
+
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\family typewriter
+A10+R25
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
 \begin_layout Section
 Summary
 \end_layout