diff options
| author | Juan Marín Noguera <juan@mnpi.eu> | 2025-05-16 22:18:44 +0200 |
|---|---|---|
| committer | Juan Marín Noguera <juan@mnpi.eu> | 2025-05-16 22:18:44 +0200 |
| commit | 4f670b750af5c11e1eac16d9cd8556455f89f46a (patch) | |
| tree | e0f8d7b33df2727d89150f799ee8628821fda80a /1.2.10.lyx | |
| parent | 16ccda6c459c0fd7ca2081e9d541124c28b0c556 (diff) | |
Changed layout for more manageable volumes
Diffstat (limited to '1.2.10.lyx')
| -rw-r--r-- | 1.2.10.lyx | 1006 |
1 files changed, 0 insertions, 1006 deletions
diff --git a/1.2.10.lyx b/1.2.10.lyx deleted file mode 100644 index a0a6bbd..0000000 --- a/1.2.10.lyx +++ /dev/null @@ -1,1006 +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 -\use_default_options true -\maintain_unincluded_children no -\language american -\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 true -\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 - -Determine the value of -\begin_inset Formula $p_{n0}$ -\end_inset - - from Eqs. - (4) and (5) and interpret this result from the standpoint of Algorithm M. -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -answer -\end_layout - -\end_inset - -For -\begin_inset Formula $n=1$ -\end_inset - -, - -\begin_inset Formula $p_{10}=1$ -\end_inset - -, - and for -\begin_inset Formula $n>1$ -\end_inset - -, - -\begin_inset Formula -\[ -p_{n0}=\frac{1}{n}p_{(n-1)(-1)}+\frac{n-1}{n}p_{(n-1)0}=\frac{n-1}{n}p_{(n-1)0}=\dots=\frac{n-1}{n}\frac{n-2}{n-1}\cdots\frac{1}{2}p_{10}=\frac{1}{n}, -\] - -\end_inset - -so in general the probability that step M4 is never run (which happens when -\begin_inset Formula $a_{n}$ -\end_inset - - is already the maximum value) is -\begin_inset Formula $p_{n0}=\frac{1}{n}$ -\end_inset - -. -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -exerc4[M10] -\end_layout - -\end_inset - -Give an explicit, - closed formula for the values of -\begin_inset Formula $p_{nk}$ -\end_inset - - in the coin-tossing experiment, - Eq. - (17). -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -answer -\end_layout - -\end_inset - - -\begin_inset Formula $p_{nk}=\binom{n}{k}p^{k}q^{n-k}$ -\end_inset - -. - To show that this derives from Eq. - (17), - we see that, - when -\begin_inset Formula $n=0$ -\end_inset - -, - -\begin_inset Formula $p_{0k}=\delta_{k0}$ -\end_inset - -, - matching the formula, - and then, - by induction, -\begin_inset Formula -\[ -p_{nk}=pp_{n-1,k-1}+qp_{n-1,k}=\binom{n-1}{k-1}p^{k}q^{n-k}+\binom{n-1}{k}p^{k}q^{n-k}=\binom{n}{k}p^{k}q^{n-k}. -\] - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -rexerc8[M20] -\end_layout - -\end_inset - -Suppose that each -\begin_inset Formula $X[k]$ -\end_inset - - is taken at random from a set of -\begin_inset Formula $M$ -\end_inset - - distinct elements, - so that each of the -\begin_inset Formula $M^{n}$ -\end_inset - - possible choices for -\begin_inset Formula $X[1],X[2],\dots,X[n]$ -\end_inset - - is considered equally likely. - What is the probability that all the -\begin_inset Formula $X[k]$ -\end_inset - - will be distinct? -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -answer -\end_layout - -\end_inset - -We need calculate the number of choices out of those -\begin_inset Formula $M^{n}$ -\end_inset - - that do not repeat numbers. - These choices can be considered as taking a subset of -\begin_inset Formula $n$ -\end_inset - - elements from those -\begin_inset Formula $M$ -\end_inset - - (if -\begin_inset Formula $n>M$ -\end_inset - - then we must necessarily repeat) and then ordering them somehow, - so the total number of choices is -\begin_inset Formula $\binom{M}{n}n!$ -\end_inset - -, - and the probability is -\begin_inset Formula -\[ -\frac{\binom{M}{n}n!}{M^{n}}=\frac{M(M-1)\cdots(M-n+1)}{M^{n}}=\frac{M^{\underline{n}}}{M^{n}}. -\] - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -rexerc11[M15] -\end_layout - -\end_inset - -What happens to the semi-invariants of a distribution if we change -\begin_inset Formula $G(z)$ -\end_inset - - to -\begin_inset Formula $F(z)=z^{n}G(z)$ -\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 $H(z)\coloneqq z^{n}$ -\end_inset - -, - then -\begin_inset Formula $h(t)\coloneqq\ln H(\text{e}^{t})=\ln\text{e}^{nt}=nt$ -\end_inset - -, - so -\begin_inset Formula $\dot{h}(t)=n$ -\end_inset - - and -\begin_inset Formula $\ddot{h}(t)=\dddot{h}(t)=\dots=0$ -\end_inset - -. - Therefore -\begin_inset Formula -\begin{align*} -\kappa_{1} & =\dot{h}(0)=n; & \kappa_{n} & =h^{(n)}(0)=0, & n & >1. -\end{align*} - -\end_inset - -Thus, - by Theorem A, - the mean increases by -\begin_inset Formula $n$ -\end_inset - - and all the other semi-invariants stay the same. -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -rexerc20[M22] -\end_layout - -\end_inset - -Suppose we want to calculate -\begin_inset Formula $\max\{|a_{1}-b_{1}|,|a_{2}-b_{2}|,\dots,|a_{n}-b_{n}|\}$ -\end_inset - - when -\begin_inset Formula $b_{1}\leq b_{2}\leq\dots\leq b_{n}$ -\end_inset - -. - Show that it is sufficient to calculate -\begin_inset Formula $\max\{m_{\text{L}},m_{\text{R}}\}$ -\end_inset - -, - where -\begin_inset Formula -\begin{align*} -m_{\text{L}} & =\max\{a_{k}-b_{k}\mid a_{k}\text{ is a left-to-right maximum of }a_{1}a_{2}\cdots a_{n}\},\\ -m_{\text{R}} & =\max\{b_{k}-a_{k}\mid a_{k}\text{ is a right-to-left minimum of }a_{1}a_{2}\cdots a_{n}\}. -\end{align*} - -\end_inset - -(Thus, - if the -\begin_inset Formula $a$ -\end_inset - -'s are in random order, - the number of -\begin_inset Formula $k$ -\end_inset - -'s for which a subtraction must be performed is only about -\begin_inset Formula $2\ln n$ -\end_inset - -.) -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -answer -\end_layout - -\end_inset - -We interpret the concepts of -\begin_inset Quotes eld -\end_inset - -directional -\begin_inset Quotes erd -\end_inset - - maximum and minimum as meaning that -\begin_inset Formula $a_{k}\geq a_{k-1},\dots,a_{1}$ -\end_inset - - or that -\begin_inset Formula $a_{k}\leq a_{k+1},\dots,a_{n}$ -\end_inset - -, - respectively. - Then, - if -\begin_inset Formula $a_{j}$ -\end_inset - - is not a left-to-right maximum, - there is a -\begin_inset Formula $k<j$ -\end_inset - - with -\begin_inset Formula $a_{k}>a_{j}$ -\end_inset - - and therefore -\begin_inset Formula $a_{k}-b_{k}>a_{j}-b_{j}$ -\end_inset - - (as -\begin_inset Formula $b_{k}\leq b_{j}$ -\end_inset - -), - so -\begin_inset Formula $a_{j}-b_{j}$ -\end_inset - - is not a maximum of -\begin_inset Formula $\{a_{k}-b_{k}\}$ -\end_inset - -. - Similarly, - if -\begin_inset Formula $a_{j}$ -\end_inset - - is not a right-to-left minimum, - there is a -\begin_inset Formula $k>j$ -\end_inset - - with -\begin_inset Formula $a_{k}<a_{j}$ -\end_inset - - and -\begin_inset Formula $b_{k}-a_{k}>b_{j}-a_{j}$ -\end_inset - -. - -\end_layout - -\begin_layout Standard -Thus -\begin_inset Formula $m_{\text{L}}=\max\{a_{k}-b_{k}\}$ -\end_inset - - and -\begin_inset Formula $m_{\text{R}}=\max\{b_{k}-a_{k}\}$ -\end_inset - -. - Since at least one of them is non-negative, - -\begin_inset Formula $\max\{m_{\text{L}},m_{\text{R}}\}$ -\end_inset - - is also non-negative and it is therefore -\begin_inset Formula $|a_{k}-b_{k}|$ -\end_inset - - for some -\begin_inset Formula $k$ -\end_inset - -, - and it is no lower than any -\begin_inset Formula $|a_{j}-b_{j}|$ -\end_inset - - as those are either -\begin_inset Formula $a_{j}-b_{j}$ -\end_inset - - or -\begin_inset Formula $b_{j}-a_{j}$ -\end_inset - -. -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -rexerc21[HM21] -\end_layout - -\end_inset - -Let -\begin_inset Formula $X$ -\end_inset - - be the number of heads that occur when a random coin is flipped -\begin_inset Formula $n$ -\end_inset - - times, - with generating function (18). - Use (25) to prove that -\begin_inset Formula -\[ -\text{Pr}(X\geq n(p+\epsilon))\leq\text{e}^{-\epsilon^{2}n/(2q)} -\] - -\end_inset - -when -\begin_inset Formula $\epsilon\geq0$ -\end_inset - -, - and obtain a similar estimate for -\begin_inset Formula $\text{Pr}(X\leq n(p-\epsilon))$ -\end_inset - -. -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -answer -\end_layout - -\end_inset - -First, - we tackle the edge cases. - If -\begin_inset Formula $n=0$ -\end_inset - -, - then -\begin_inset Formula $X=0$ -\end_inset - - and -\begin_inset Formula $\text{Pr}(X\geq0)\leq1$ -\end_inset - - trivially, - so we may consider -\begin_inset Formula $n>0$ -\end_inset - -. - If -\begin_inset Formula $p=0$ -\end_inset - -, - then -\begin_inset Formula $\text{Pr}(X=0)=1$ -\end_inset - - and -\begin_inset Formula $\text{Pr}(X\geq n\epsilon)\leq\text{e}^{-\epsilon^{2}n/2}$ -\end_inset - - trivially, - so we may consider -\begin_inset Formula $p>0$ -\end_inset - -. - Finally, - if -\begin_inset Formula $\epsilon>q$ -\end_inset - - then -\begin_inset Formula $\text{Pr}(X\geq n(p+\epsilon))=0\leq\text{e}^{-\epsilon^{2}n/(2q)}$ -\end_inset - - and if -\begin_inset Formula $\epsilon=q$ -\end_inset - - then -\begin_inset Formula $\text{Pr}(X\geq n)=p^{n}\leq(\text{e}^{-q})^{n}\leq\text{e}^{-qn/2}$ -\end_inset - -, - using the fact that -\begin_inset Formula $t\leq\text{e}^{t-1}$ -\end_inset - - for every -\begin_inset Formula $t\in\mathbb{R}$ -\end_inset - -, - so we may consider -\begin_inset Formula $\epsilon<q$ -\end_inset - - and in particular -\begin_inset Formula $q>0$ -\end_inset - -. -\end_layout - -\begin_layout Standard -Now let -\begin_inset Formula $r=n(p+\epsilon)$ -\end_inset - -. - Then -\begin_inset Formula $\text{Pr}(X\geq n(p+\epsilon))\leq x^{-n(p+\epsilon)}(q+px)^{n}$ -\end_inset - -, - and we just need to find -\begin_inset Formula $x\geq1$ -\end_inset - - such that -\begin_inset Formula -\[ -\ln(q+px)-(p+\epsilon)\ln x\leq-\frac{\epsilon^{2}}{2q}. -\] - -\end_inset - - -\begin_inset Note Greyedout -status open - -\begin_layout Plain Layout -(I had to look at the solution, - esp. - for the right value of -\begin_inset Formula $x$ -\end_inset - -.) -\end_layout - -\end_inset - - If -\begin_inset Formula $x\coloneqq\frac{p+\epsilon}{p}\frac{q}{q-\epsilon}$ -\end_inset - -, - we have -\begin_inset Formula -\begin{multline*} -\ln(q+px)-(p+\epsilon)\ln x=\ln\left(q+(p+\epsilon)\frac{q}{q-\epsilon}\right)-(p+\epsilon)\ln\left(\frac{p+\epsilon}{p}\frac{q}{q-\epsilon}\right)=\\ -=\ln q-\ln(q-\epsilon)-(p+\epsilon)(\ln q-\ln(q-\epsilon)+\ln(p+\epsilon)-\ln p)=\\ -=(q-\epsilon)\ln\frac{q}{q-\epsilon}-(p+\epsilon)\ln\frac{p+\epsilon}{p}, -\end{multline*} - -\end_inset - -where we are assuming that -\begin_inset Formula $\epsilon<q$ -\end_inset - -. - Now, - by Eq. - 1.2.9(24), - let -\begin_inset Formula $v\coloneqq\frac{\epsilon}{q}$ -\end_inset - -, -\begin_inset Formula -\begin{multline*} -(q-\epsilon)\ln\frac{q}{q-\epsilon}=q(1-v)\ln\frac{1}{1-v}=q(v-1)\ln(1-v)=\\ -=q(v-1)\sum_{k\geq1}\frac{(-1)^{k+1}}{k}(-v)^{k}=q(1-v)\sum_{k\geq1}\frac{v^{k}}{k}=q\left(\sum_{k\geq1}\frac{v^{k}}{k}-\sum_{k\geq2}\frac{v^{k}}{k-1}\right)=\\ -=q\left(v-\sum_{k\geq2}\frac{v^{k}}{k(k-1)}\right)=\epsilon-\frac{\epsilon^{2}}{2q}-\frac{\epsilon^{3}}{6q^{2}}-\frac{\epsilon^{4}}{12q^{3}}-\dots\leq\epsilon-\frac{\epsilon^{2}}{2q}. -\end{multline*} - -\end_inset - -In addition, -\begin_inset Formula -\[ --(p+\epsilon)\ln\frac{p+\epsilon}{p}=(p+\epsilon)\ln\frac{p}{p+\epsilon}=(p+\epsilon)\ln\left(1-\frac{\epsilon}{p+\epsilon}\right)\leq-\epsilon, -\] - -\end_inset - -so -\begin_inset Formula $-(p+\epsilon)\ln\frac{p+\epsilon}{p}\leq\epsilon$ -\end_inset - - and, - putting it all together, -\begin_inset Formula -\[ -\ln(q+px)-(p+\epsilon)\ln x\leq\cancel{\epsilon}-\frac{\epsilon^{2}}{2q}\cancel{-\epsilon}. -\] - -\end_inset - -For the second part, - switching the roles of heads and tails, - let -\begin_inset Formula $Y\coloneqq n-X$ -\end_inset - -, -\begin_inset Formula -\[ -\text{Pr}(X\leq n(p-\epsilon))=\text{Pr}(Y\geq n(q+\epsilon))\leq\text{e}^{-\epsilon^{2}n/(2p)}. -\] - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -rexerc22[HM22] -\end_layout - -\end_inset - -Suppose -\begin_inset Formula $X$ -\end_inset - - has the generating function -\begin_inset Formula $(q_{1}+p_{1}z)(q_{2}+p_{2}z)\cdots(q_{n}+p_{n}z)$ -\end_inset - -, - where -\begin_inset Formula $p_{k}+q_{k}=1$ -\end_inset - - for -\begin_inset Formula $1\leq k\leq n$ -\end_inset - -. - Let -\begin_inset Formula $\mu=EX=p_{1}+p_{2}+\dots+p_{n}$ -\end_inset - -. -\end_layout - -\begin_layout Enumerate -Prove that -\begin_inset Formula -\begin{align*} -\text{Pr}(X\leq\mu r) & \leq(r^{-r}\text{e}^{r-1})^{\mu}, & \text{when }0 & <r\leq1;\\ -\text{Pr}(X\geq\mu r) & \leq(r^{-r}\text{e}^{r-1})^{\mu}, & \text{when }r & \geq1. -\end{align*} - -\end_inset - - -\end_layout - -\begin_layout Enumerate -Express the right-hand sides of these estimates in convenient form when -\begin_inset Formula $r\approx1$ -\end_inset - -. -\end_layout - -\begin_layout Enumerate -Show that if -\begin_inset Formula $r$ -\end_inset - - is sufficiently large we have -\begin_inset Formula $\text{Pr}(X\geq\mu r)\leq2^{-\mu r}$ -\end_inset - -. -\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 the first equation, - using Eq. - (24) with -\begin_inset Formula $x=r$ -\end_inset - -, -\begin_inset Formula -\begin{multline*} -\text{Pr}(X\leq\mu r)\leq r^{-\mu r}(q_{1}+p_{1}r)\cdots(q_{n}+p_{n}r)=r^{-\mu r}\prod_{k}(q_{k}+p_{k}r)=\\ -=r^{-\mu r}\prod_{k}(1+p_{k}(r-1))\leq r^{-\mu r}\prod_{k}\text{e}^{p_{k}(r-1)}=r^{-\mu r}\text{e}^{\mu(r-1)}=(r^{-r}\text{e}^{r-1})^{\mu}. -\end{multline*} - -\end_inset - -For the second equation, - repeat the same steps but using Eq. - (25). -\end_layout - -\begin_layout Enumerate -When -\begin_inset Formula $r\approx1$ -\end_inset - -, - -\begin_inset Formula $r\approx\text{e}^{r-1}$ -\end_inset - -, - so -\begin_inset Formula $(r^{-r}\text{e}^{r-1})^{\mu}\approx r^{\mu(1-r)}$ -\end_inset - -. - The inequality still holds for -\begin_inset Formula $r<2$ -\end_inset - - since, - in the previous proof, - we can see that -\begin_inset Formula $1+p_{k}(r-1)\leq r^{p_{k}}$ -\end_inset - - by taking the Taylor series of the logarithms: -\begin_inset Formula -\begin{multline*} -\ln(1+p_{k}(r-1))=p_{k}(r-1)-\frac{p_{k}^{2}(r-1)^{2}}{2}+\frac{p_{k}^{3}(r-1)^{3}}{3}-\frac{p_{k}^{4}(r-1)^{4}}{4}+\dots\leq\\ -\leq p_{k}(r-1)-\frac{p_{k}(r-1)^{2}}{2}+\frac{p_{k}(r-1)^{3}}{3}-\frac{p_{k}(r-1)^{4}}{4}+\dots=p_{k}\ln r. -\end{multline*} - -\end_inset - -Using this inequality instead of the one we used gives the proper result. -\end_layout - -\begin_layout Enumerate -Clearly -\begin_inset Formula $1+p_{k}(r-1)\leq r$ -\end_inset - -, - so -\begin_inset Formula $r^{-\mu r}\prod_{k}(1+p_{k}(r-1))\leq r^{-\mu r}r^{n}$ -\end_inset - -, - and we want to see that this in turn is less than -\begin_inset Formula $2^{-\mu r}$ -\end_inset - - for large enough -\begin_inset Formula $r$ -\end_inset - -. - Now, -\begin_inset Formula -\[ -\frac{r^{n}r^{-\mu r}}{2^{-\mu r}}=r^{n}\left(\frac{2}{r}\right)^{\mu r}, -\] - -\end_inset - -and since -\begin_inset Formula $\left(\frac{2}{r}\right)^{\mu r}$ -\end_inset - - decreases faster than -\begin_inset Formula $r^{n}$ -\end_inset - - increases, - there exist -\begin_inset Formula $r_{0}$ -\end_inset - - such that, - for -\begin_inset Formula $r>r_{0}$ -\end_inset - -, - this fraction is less than 1. -\end_layout - -\end_body -\end_document |
