commit 7733817ef7d7744ed46cd0d784d0b4983aff41aa
parent 70b027f318947199a3ac6a544669a0792f579c13
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sat, 9 Oct 2021 17:39:24 -0500
Add 1.2.10 and 1.2.11
Diffstat:
| M | README.org | | | 210 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- |
1 file changed, 209 insertions(+), 1 deletion(-)
diff --git a/README.org b/README.org
@@ -70,6 +70,9 @@ Ah Stirling's appproximation.
2nd equality in (20): just a sign trick.
+***** 18
+
+***** 20
**** 1.2.6
Note how the \(r\) in \({r \choose k} = \frac{r^{\underline{k}}}{k!}\) is real.
@@ -272,7 +275,7 @@ Alternatively, this can also from rewriting (9) with \(a_{jk} = x_{j}\).
In (38), note that
\begin{align*}
- e^{S_{k}z^{k} / k}
+ \E^{S_{k}z^{k} / k}
&= \sum_{l \geq 0} \frac{1}{l!}(S_{k}z^{k} / k)^{l}\\
&= \sum_{l \geq 0} \frac{1}{l!}S_{k}^{l}z^{lk}k^{l},
\end{align*}
@@ -334,6 +337,211 @@ Thus, we have
&= \sum_{n \geq 0, n \mod m = r}a_{n}z^{n}.
\end{align*}
+**** 1.2.10
+Notation for (4) is a bit confusing at first. We scan from back to the front, so if \(x_{1}\) is the \(n\)-th (largest), we would make the last update there, leaving \(k - 1\) updates when we go from \(x_{n}\) to \(x_{2}\) (\(P_{(n - 1)(k - 1)}\)). If \(x_{1}\) is not the largest, we would have made all \(k\) updates before we go to it (\(P_{(n - 1)k}\)).
+
+To get (7), we rewrite \(G_{n}(z)\) using (4):
+\begin{align*}
+ G_{n}(z)
+ &= \sum_{k}p_{nk}z^{k}\\
+ &= \sum_{k}(\frac{1}{n}p_{(n - 1)(k - 1)} + \frac{n - 1}{n}p_{(n - 1)k})z^{k}\\
+ &= \frac{z}{n} \sum_{k}p_{(n - 1)(k - 1)}z^{k - 1} + \frac{n - 1}{n}\sum_{k}p_{(n - 1)k}z^{k}\\
+ &= \frac{z}{n} G_{n - 1}(z) + \frac{n - 1}{n}G_{n - 1}(z)\\
+ &= \frac{z + n - 1}{n} G_{n - 1}(z).
+\end{align*}
+Similarly applying this to (17) we get
+\begin{align*}
+ G_{n}(z)
+ &= \sum_{k}p_{nk}z^{k}\\
+ &= \sum_{k}(pp_{(n - 1)(k - 1)} + q p_{(n - 1)k})z^{k}\\
+ &= pz\sum_{k}pp_{(n - 1)(k - 1)}z^{k - 1} + q \sum_{k}p_{(n - 1)k}z^{k}\\
+ &= (q + pz)G_{n - 1}(z).
+\end{align*}
+
+Taylor's expansion for (20) reads
+\begin{align*}
+ G(1 + z)
+ &= \frac{1}{n} \frac{(1 + z)^{n + 1} - 1 - z}{z}\\
+ &= \frac{1}{n} \frac{\sum_{k = 0}^{n + 1}{n + 1\choose k}z^{k} - 1 - z}{z}\\
+ &= \frac{1}{n} (\sum_{k = 1}^{n + 1}{n + 1\choose k}z^{k - 1} - 1)\\
+ &= \frac{1}{n} (n + \sum_{k = 2}^{n + 1}{n + 1\choose k}z^{k - 1})\\
+ &= 1 + \frac{1}{n}\sum_{k = 1}^{n}{n + 1\choose k + 1}z^{k}\\
+ &= 1 + \frac{1}{n}{n + 1\choose 2}z + \frac{1}{n}{n + 1 \choose 3}z^{2} + \cdots\\
+ &= 1 + \frac{n + 1}{2}z + \frac{(n + 1)(n - 1)}{6}z^{2} + \cdots.
+\end{align*}
+
+Didn't realize that \(\ev[X]\) can be read as expected value of \([X]\). Guess it does make sense to use \(\ev(X)\) or \(\ev X\) then.
+
+***** DONE 2
+CLOSED: [2021-10-09 Sat 07:38]
+Since
+\begin{align*}
+ G''(z)
+ &= \sum_{k}k(k - 1)p_{k}z^{k - 1}\\
+ &= \sum_{k}k^{2}p_{k}z^{k - 1} - \sum_{k}kp_{k}z^{k - 1}\\
+ &= \sum_{k}k^{2}p_{k}z^{k - 1} - G'(z),
+\end{align*}
+it's easy to see that
+\begin{align*}
+ \var(G)
+ &= \sum_{k}k^{2}p_{k} - (\sum_{k}kp_{k})^{2}\\
+ &= G''(1) + G'(1) - (G'(1))^{2}.
+\end{align*}
+
+***** INACTIVE 13
+***** INACTIVE 14
+***** INACTIVE 21
+***** INACTIVE 22
+***** INACTIVE 23
+**** 1.2.11.1
+(10) seems useful. Also note the customary meaning of \(z\) being in the neighborhood of \(0\).
+***** INACTIVE 8
+***** INACTIVE 11
+***** INACTIVE 12
+**** 1.2.11.2
+To get (2), note that in \([k, k + 1)\), \(\{x\} = x - k\):
+\begin{align*}
+ \int_{k}^{k + 1}(\{x\} - \frac{1}{2})f'(x)\dd x
+ &= (\{x\} - \frac{1}{2})f(x)|_{x = k}^{k + 1} - \int_{k}^{k + 1}f(x) \dd (\{x\} - \frac{1}{2})\\
+ &= (x - k - \frac{1}{2})f(x)|_{x = k}^{k + 1} - \int_{k}^{k + 1}f(x) \dd x.
+\end{align*}
+
+
+By no discontinuities it meant that \(B_{m}(\{x\}) = B_{m}\) at all \([t, t+1]\) boundary points with \(t \geq 1\). The integration by parts results can then be simplified as:
+\begin{align*}
+ \frac{1}{m!} \int_{1}^{n}B_{m}(\{x\})f^{(m)}(x)\dd x
+ &= \frac{1}{(m + 1)!} \int_{1}^{n}f^{(m)}(x)\dd B_{m + 1}(\{x\})\\
+ &= \frac{1}{(m + 1)!} (B_{m + 1}(\{x\})f^{m}(x))|_{x = 1}^{n} - \frac{1}{(m + 1)!} \int_{1}^{n}B_{m + 1}(\{x\}) f^{(m + 1)}(x)\dd x\\
+ &= \frac{B_{m + 1}}{(m + 1)!}(f^{m}(n) - f^{m}(1)) - \frac{1}{(m + 1)!} \int_{1}^{n}B_{m + 1}(\{x\}) f^{(m + 1)}(x)\dd x.
+\end{align*}
+
+
+See Concrete Mathematics 9.5 for proof of (12). Also note how we get Stiring's approximation and Euler's constant from (10)!
+
+\(\E^{\sigma} = \sqrt{2\pi}\) is another interesting fact. The most common form of Stirling's approximation is probably with \(m = 1\)
+\begin{align*}
+ \ln n!
+ &= (n + \frac{1}{2})\ln n - n + \sigma + O(\frac{1}{n}),\\
+ n!
+ &= \E^{\sigma}\sqrt{n}(\frac{n}{\E})^{n} + O(\frac{1}{n})\\
+ &= \sqrt{2\pi n}(\frac{n}{\E})^{n} + O(\frac{1}{n}).
+\end{align*}
+
+***** DONE 1
+CLOSED: [2021-10-09 Sat 09:12]
+To get (7), multiply (4) by \(\E^{z} - 1\):
+\begin{align*}
+ z
+ &= \sum_{n \geq 0}\delta_{n1}z^{n}\\
+ &= (\E^{z} - 1)\sum_{k \geq 0}\frac{B_{k}z^{k}}{k!}\\
+ &= (\sum_{j \geq 0}\frac{z^{j}}{j!} - 1)\sum_{k \geq 0}\frac{B_{k}z^{k}}{k!}\\
+ &= \sum_{n \geq 0}z^{n}(\sum_{0 \leq k \leq n}\frac{B_{k}}{k!(n-k)!} - \frac{B_{n}}{n!}).
+\end{align*}
+Equating the coefficients we get
+\begin{align*}
+ \sum_{0 \leq k \leq n}\frac{B_{k}}{k!(n-k)!} - \frac{B_{n}}{n!}
+ &= \delta_{n1},\\
+ \sum_{k}{n\choose k}B_{k}
+ &= B_{n} + n!\denta_{n1}\\
+ &= B_{n} + 1!\denta_{n1}\\
+ &= B_{n} + \denta_{n1}.
+\end{align*}
+
+***** INACTIVE 3
+***** INACTIVE 5
+***** INACTIVE 6
+**** 1.2.11.3
+
+Note that
+\begin{align*}
+ \Gamm(x + 1)
+ &= \int_{0}^{\infty}\E^{-t}t^{x}\dd t,
+\end{align*}
+thus the following
+\begin{align*}
+ \frac{1}{\Gamma(x + 1)}\int_{0}^{x + y}\E^{-t}t^{x}\dd t
+ &= \frac{1}{\Gamma(x + 1)}(\Gamma(x + 1) - \int_{x}^{\infty}\E^{-t}t^{x}\dd t + \int_{x}^{x + y}\E^{-t}t^{x}\dd t)\\
+ &= 1 - \frac{1}{\Gamma(x + 1)}\int_{x}^{\infty}\E^{-t}t^{x}\dd t + \frac{1}{\Gamma(x + 1)}\int_{x}^{x + y}\E^{-t}t^{x}\dd t).
+\end{align*}
+
+For the expansion after (11), we can write
+\begin{align*}
+ 1 - \frac{2}{3}u + \frac{1}{2}u^{2} - \frac{2}{5}u^{3} + \cdots
+ &= (\sum_{i = 0}^{\infty}a_{i}u^{i})^{2}\\
+ &= \sum_{i = 0}^{\infity}u^{i}\sum_{j = 0}^{i}a_{j}a_{i-j}.
+\end{align*}
+We can then solve the first few terms
+\begin{align*}
+ \begin{cases}
+ 1
+ &= a_{0}^{2},\\
+ -\frac{2}{3}
+ &= 2a_{0}a_{1}\\
+ \frac{1}{2}
+ &= 2a_{0}a_{2} + a_{1}^{2},\\
+ -\frac{2}{5}
+ &= 2a_{0}a_{3} + 2a_{1}a_{2},\\
+ \cdots,
+ \end{cases}
+\end{align*}
+and we get
+\begin{align*}
+ a_{0}
+ &= \sqrt(1)\\
+ &= 1,\\
+ a_{1}
+ &= \frac{-\frac{2}{3}}{2a_{0}}\\
+ &= -\frac{1}{3},\\
+ a_{2}
+ &= \frac{\frac{1}{2} - a_{1}^{2}}{2a_{0}}\\
+ &= \frac{1}{2}(\frac{1}{2} - \frac{1}{9})\\
+ &= \frac{7}{36},\\
+ a_{3}
+ &= \frac{1}{a_{0}}(-\frac{1}{5} + a_{1}a_{2})\\
+ &= -\frac{1}{5} - (-\frac{1}{3})\frac{7}{36}\\
+ &= - \frac{73}{540},\\
+ &\cdots.
+\end{align*}
+To express \(u\) in \(w\), we just try to cancel one term at a time using the polynomial form, which would probably go something like the above, and there's probably some easier pattern that allows us to write things out easier. Guess we'll find out in 4.7.
+
+Change of variable in (14) is \(q = xv\). Recall that
+\begin{align*}
+ \Gamma(1 + n)
+ &= n!,\\
+ \Gamma(\frac{1}{2} + n)
+ &= \frac{(2n)!}{n^{n}n!}\sqrt(\pi),
+\end{align*}
+for (15).
+
+For Taylor expansion after (16), we only need to keep terms up to \(x^{-2}\):
+\begin{align*}
+ \exp(\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))
+ &= 1 + (\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3})) + \frac{1}{2}(\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))^{2} + O(x^{-3})\\
+ &= 1 - \frac{u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + \frac{u^{4}}{8x^{2}} + O(x^{-3}).
+\end{align*}
+Then we can just do the integration term by term
+\begin{align*}
+ \int_{0}^{y}\E^{-u}(1 + \frac{u}{x})^{x}\dd u
+ &= \int_{0}^{y}(1 - \frac{u^{2}}{2x} + \frac{u^{4}}{8x^{2}} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))\dd u\\
+ &= (u - \frac{u^{3}}{6x} + \frac{u^{5}}{40x^{2}} + \frac{u^{4}}{12x^{2}} + uO(x^{-3}))|_{u = 0}^{y}\\
+ &= y - \frac{y^{3}}{6}x + (\frac{y^{5}}{40} + \frac{y^{4}}{12})x^{-2} + O(x^{-3}).
+\end{align*}
+
+For (18) we use Stirling's approximation in exponential form (above 1.2.11.2 (19)).
+
+Third term in (21) gets absorbed by \(O(n^{n}\E^{-n})\) in (22).
+
+Try Ramanujan's treatment for \(Q(n)\)!
+
+***** 2
+***** 3
+***** 4
+***** 5
+***** 6
+***** 14
+***** 19
+Watson's lemma! o7
+***** 20
** TODO Chapter 2: Information structures
**** 2.3.4.4
***** INACTIVE 29