#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
rexerc5[M20]
\end_layout

\end_inset

Let 
\begin_inset Formula $U$
\end_inset

 be a random real number that is uniformly distributed in the interval 
\begin_inset Formula $0<U<1$
\end_inset

.
 What is the distribution of he leading digits of 
\begin_inset Formula $U$
\end_inset

?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Assume the decimal number system,
 and assume that we don't count the leading 0s.
 Then,
 with probability 
\begin_inset Formula $\frac{9}{10}$
\end_inset

,
 
\begin_inset Formula $U\geq0.1$
\end_inset

 and the leading digit will be at the first position,
 with the same probability for each digit,
 and with probability 
\begin_inset Formula $\frac{1}{10}$
\end_inset

,
 
\begin_inset Formula $U<0.1$
\end_inset

 and the leading digit is that of 
\begin_inset Formula $10U$
\end_inset

,
 which is also uniformly distributed.
 If 
\begin_inset Formula $\ell(U)\in\{1,\dots,9\}$
\end_inset

 is the leading digit of 
\begin_inset Formula $U$
\end_inset

 and 
\begin_inset Formula $k\in\{1,\dots,9\}$
\end_inset

,
 this means that 
\begin_inset Formula $P(\ell(U)=k)=\frac{9}{10}\frac{1}{9}+\frac{1}{10}P(\ell(U)=k)$
\end_inset

 and so 
\begin_inset Formula $P(\ell(U)=k)=\frac{1}{9}$
\end_inset

.
\end_layout

\begin_layout Standard
Therefore all digits have the same probability.
 In formal terms,
 if 
\begin_inset Formula $\ell(U)\in\{1,\dots,9\}$
\end_inset

 is the leading digit of 
\begin_inset Formula $U$
\end_inset

,
 for 
\begin_inset Formula $k=1,\dots,9$
\end_inset

,
\begin_inset Formula 
\begin{multline*}
P(\ell(U)=k)=P(U\geq\tfrac{1}{10})P(\ell(U)=k\mid U\geq\tfrac{1}{10})+P(U<\tfrac{1}{10})P(\ell(U)=k\mid U<\tfrac{1}{10})=\\
=\frac{9}{10}\cdot\frac{1}{9}+\frac{1}{10}\cdot P(\ell(10U)=k\mid U<0.1)=\frac{1}{10}+\frac{1}{10}P(\ell(U)=k)\implies P(\ell(U)=k)=\frac{1}{9}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc13[M20]
\end_layout

\end_inset

The floating point multiplication routine,
 Algorithm 4.2.1M,
 requires zero or one left shifts during normalization,
 depending on whether 
\begin_inset Formula $f_{u}f_{v}\geq1/b$
\end_inset

 or not.
 Assuming that the input operands are independently distributed according to the logarithmic law,
 what is the probability that no left shift is needed for normalization of the result?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

No left shift is required if,
 and only if,
 
\begin_inset Formula $f_{u}f_{v}\geq1/b$
\end_inset

.
 Now,
 
\begin_inset Formula $f_{u}$
\end_inset

 and 
\begin_inset Formula $f_{v}$
\end_inset

 are between 
\begin_inset Formula $\frac{1}{b}$
\end_inset

 and 
\begin_inset Formula $1$
\end_inset

,
 and for 
\begin_inset Formula $x\in[\frac{1}{b},1]$
\end_inset

,
 
\begin_inset Formula 
\[
P(f_{u}<x)=P(\log_{b}f_{u}<\log_{b}x)=P(\log_{b}(bf_{u})<\log_{b}(bx))=\log_{b}(bx)=1+\log_{b}x,
\]

\end_inset

and similarly for 
\begin_inset Formula $f_{v}$
\end_inset

.
 Let 
\begin_inset Formula $\varphi(x)\coloneqq1+\log_{b}x$
\end_inset

,
\begin_inset Formula 
\begin{multline*}
P(f_{u}f_{v}\geq\tfrac{1}{b})=P\big(\log_{b}(f_{u}f_{v})=\log_{b}f_{u}+\log_{b}f_{v}\geq-1\big)=\\
=\iint_{[\frac{1}{b},1]\times[\frac{1}{b},1]}[\log_{b}f_{u}+\log_{b}f_{v}\geq-1]\text{d}\varphi(f_{u})\,\text{d}\varphi(f_{v})=\\
=\iint_{[\frac{1}{b},1]\times[\frac{1}{b},1]}[\varphi f_{u}\geq1-\varphi f_{v}]\text{d}\varphi(f_{u})\,\text{d}\varphi(f_{v})=\int_{0}^{1}\int_{1-y}^{1}\text{d}x\,\text{d}y=\int_{0}^{1}y\,\text{d}y=\frac{1}{2}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc17[HM25]
\end_layout

\end_inset

(M.
 Tsuji.) Another way to define the value of 
\begin_inset Formula $\text{Pr}(S(n))$
\end_inset

 is to evaluate the quantity 
\begin_inset Formula $\lim_{n\to\infty}(H_{n}^{-1}\sum_{k=1}^{n}[S(k)]/k)$
\end_inset

;
 it can be shown that this 
\emph on
harmonic probability
\emph default
 exists and is equal to 
\begin_inset Formula $\text{Pr}(S(n))$
\end_inset

,
 whenever the latter exists according to Definition 3.5A.
 Prove that the harmonic probability of the statement 
\begin_inset Quotes eld
\end_inset


\begin_inset Formula $(\log_{10}n)\bmod1<r$
\end_inset


\begin_inset Quotes erd
\end_inset

 exists and equals 
\begin_inset Formula $r$
\end_inset

.
 (Thus,
 initial digits of integers satisfy the logarithmic law 
\emph on
exactly
\emph default
 in this sense.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Consider the integral
\begin_inset Formula 
\[
\int_{1}^{x}\frac{1}{t}\text{d}t=\left[\ln t\right]_{t=1}^{x}=\ln x.
\]

\end_inset

This means that,
 for any given 
\begin_inset Formula $\varepsilon>0$
\end_inset

,
 there is a natural number 
\begin_inset Formula $N$
\end_inset

 such that,
 if 
\begin_inset Formula $m>N$
\end_inset

,
 then
\begin_inset Formula 
\[
\left|\ln x-\sum_{10^{m}\leq k<10^{m}x}\frac{1}{10^{m}}\frac{1}{k/10^{m}}\right|=\left|\ln x-\sum_{10^{m}\leq k<10^{m}x}\frac{1}{k}\right|<\varepsilon.
\]

\end_inset

Now,
 let 
\begin_inset Formula $N$
\end_inset

 be such that the above applies for both 
\begin_inset Formula $x=1$
\end_inset

 and 
\begin_inset Formula $x=10^{r}$
\end_inset

,
 and let 
\begin_inset Formula $n=10^{p}-1$
\end_inset

 for some positive integer 
\begin_inset Formula $p>N$
\end_inset

,
 then
\begin_inset Formula 
\begin{multline*}
H_{n}^{-1}\sum_{k=1}^{n}\frac{[S(k)]}{k}=\frac{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}}{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}}=\frac{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}/p}{\sum_{0\leq m<p}\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}/p}=\\
=\frac{\sum_{0\leq m<p}(\ln10^{r}+\delta_{m})}{\sum_{0\leq m<p}(\ln10+\delta'_{m})}=\frac{\ln10^{r}+\frac{D}{p}+d_{p}}{\ln10+\frac{D'}{p}+d'_{p}},
\end{multline*}

\end_inset

where 
\begin_inset Formula $\delta_{m}\coloneqq\sum_{10^{m}\leq k<10^{m+r}}\frac{1}{k}-\ln10^{r}$
\end_inset

,
 
\begin_inset Formula $\delta'_{m}\coloneqq\sum_{10^{m}\leq k<10^{m+1}}\frac{1}{k}-\ln10$
\end_inset

,
 
\begin_inset Formula $D\coloneqq\sum_{0\leq m<N}\delta_{m}$
\end_inset

,
 
\begin_inset Formula $D'\coloneqq\sum_{0\leq m<N}\delta'_{m}$
\end_inset

,
 
\begin_inset Formula $d_{p}\coloneqq\sum_{N\leq m<p}\delta_{m}/p$
\end_inset

,
 and 
\begin_inset Formula $d'_{p}\coloneqq\sum_{N\leq m<p}\delta'_{m}/p$
\end_inset

.
 Since 
\begin_inset Formula $|d_{p}|,|d'_{p}|<\varepsilon$
\end_inset

,
 if we 
\begin_inset Formula $p$
\end_inset

 to be big enough that 
\begin_inset Formula $\left|D/p\right|,\left|D'/p\right|<\varepsilon$
\end_inset

,
 then,
 let 
\begin_inset Formula $e\coloneqq\frac{D}{p}+d_{p}$
\end_inset

 and 
\begin_inset Formula $e'\coloneqq\frac{D'}{p}+d'_{p}$
\end_inset

 (so that 
\begin_inset Formula $|e|,|e'|<2\varepsilon$
\end_inset

),
 for small enough 
\begin_inset Formula $\varepsilon$
\end_inset

,
\begin_inset Formula 
\begin{multline*}
\left|\frac{\ln10^{r}+e}{\ln10+e'}-\frac{\ln10^{r}}{\ln10}\right|\leq\left|\frac{\ln10^{r}+e}{\ln10+e'}-\frac{\ln10^{r}+e}{\ln10}\right|+\left|\frac{\ln10^{r}+e}{\ln10}-\frac{\ln10^{r}}{\ln10}\right|=\\
=\left|\ln10^{r}+e\right|\left|\frac{e'}{(\ln10+e')\ln10}\right|+\left|\frac{e}{\ln10}\right|\leq3\frac{\varepsilon}{2\ln10}+\frac{\varepsilon}{\ln10}=\frac{5}{2\ln10}\varepsilon.
\end{multline*}

\end_inset

Therefore,
 the limit for the subsequence made up of the elements where 
\begin_inset Formula $n=10^{p}-1$
\end_inset

 for some 
\begin_inset Formula $p$
\end_inset

 is precisely 
\begin_inset Formula $\frac{\ln10^{r}}{\ln10}=r$
\end_inset

.
 Note that other elements of the sequence can be written in the form
\begin_inset Formula 
\[
\frac{\sum_{0\leq m<p}(\ln10^{r}+\delta_{m})+\sum_{10^{p}\leq k\leq\min\{n,10^{p+r}+1\}}\frac{1}{k}}{\sum_{0\leq m<p}(\ln10+\delta'_{m})+\sum_{10^{p}\leq k\leq n}\frac{1}{k}},
\]

\end_inset

where 
\begin_inset Formula $10^{p}\leq n<10^{p+1}-1$
\end_inset

,
 but then,
 dividing this by the element at position 
\begin_inset Formula $10^{p}-1$
\end_inset

,
 we find that the terms in the right hand side of both sums in the numerator and denominator tend to 0,
 so the whole sequence converges to 
\begin_inset Formula $r$
\end_inset

.
\end_layout

\end_body
\end_document