Blog E

路漫漫其修远兮，吾将上下而求索。

Probability and Computing 第九章笔记

单变量正态分布 Moment Generating Function \[M_X(t)=e^{t^2\sigma^2/2+\mu t}\] Chernoff bound \[\Pr(\|\frac{X-\mu}{\sigma}\|\ge a)\le 2e^{-a^2/2}\] 中心极限定理 二项分布的极限 n 充分大时，$B(n,p)$ 的概率分布趋近于与其同方差与均值的正态分布。 中心极限定理 $X_1,X_2\cdots X_n$ 独立同分布，则： \[\lim_{n\rightarrow \infty}\Pr(a\le \frac{\overline X-\mu...

Posted by ethan-zhou on February 11, 2024

Probability and Computing 第八章部分习题

Posted by ethan-zhou on February 3, 2024

Probability and Computing 第八章笔记

泊松过程——最独立的一集

这一章节前面不少内容偏概念，和概统课讲的一样，下面主要记录泊松过程和连续马尔可夫过程分布的一些性质，泊松分布给我的直观感受就是，什么统计量之间都是独立的。 Balls and bins with feedback 两个 bin，分别有 x，y 个球的时候，再来一个球，以 $\frac {x^p}{x^p+y^p}$ 的概率进入第一个 bin，剩下概率进入第二个 bin。初始 $x=y=1$ $p=1$ 时，n 轮之后 x 均匀分布 $p>1$ 时，with probability 1 there exist a number c such that one...

Posted by ethan-zhou on February 3, 2024

Probability and Computing 第七章部分习题

算不动了

写了部分习题, upd. 最后一题的放缩问了个同学，现在会了，大致是把递推式放缩成 $i(f_i-f_{i-1})\le (n-i)(f_{i+1}-f_i)$，后面懒得写了。

Posted by ethan-zhou on February 1, 2024

Probability and Computing 第七章笔记

突然发现，上次发博客还是上次了，因此，我打算打算一下，简单写个笔记记录一下这章内容。 Notation $r^t_{i,j}$: 从i开始走，t时刻恰好第一次到j的概率 $h_{i,j}$: 从i开始走，第一次到j的期望步数 Definition 略 Classification of States 连通性 accessible: $\exist n,\text{ s.t.} P^n_{i,j}>0$ communicate: i,j 双向联通 若整个链是一个 communicating class / 对应的图强连通，则称其 irreducible...

Posted by ethan-zhou on January 4, 2024

Probability and Computing 第五章作业题

题目 模拟代码（第二问） bool f[MXN]; #define ls(x) ((x) << 1) #define rs(x) (((x) << 1) | 1) #define bro(x) ((x) ^ 1) #define fa(x) ((x) >> 1) queue<ll> q; ll n, cnt; ll chk(ll r) { ll cnt = (ll)f[r] + f[ls(r)] + f[rs(r)]; if (cnt == 2) { if (!f[r]) return r; ...

Posted by ethan-zhou on September 7, 2023

Probability and Computing 第四章笔记

Moment Generating Functions \[M_X(t)=\mathbb{E}[e^{tX}]\] 性质 $M_X^{(n)}(0)=\mathbb{E}[X^n]$ X,Y 独立,则 $M_{X+Y}(t)=M_X(t)M_Y(t)$ Chernoff Bounds 根据上述生成函数和马尔可夫不等式 可以得到: $\Pr(X\ge a)\le \min_{t>0}\frac{\mathbb{E}[e^tX]}{e^{ta}}$ $\Pr(X\le a)\le \min_{t<0}\frac{\mathbb{E}[e^tX]...

Posted by ethan-zhou on August 3, 2023

Probability and Computing 第三章笔记

Markov’s Inequality 若 X 恒大于0,则: \[\Pr(x\ge a)\le \frac{\mathbb{E}[x]}a\] Moments 定义 kth moment of a random variable X is $\mathbb{E}[x^k]$ variance $\mathrm{Var}[X]=\mathbb{E}[X^2]-(\mathbb{E}[X])^2$ covariance $\mathrm{Cov}(X,Y)=\mathrm{E}[(X-\mathrm{E}[X])(Y-\mathrm{E}[Y])]$ 定理 \(\...

Posted by ethan-zhou on August 3, 2023

Probability and Computing 第二章笔记

Linearity of Expectations (不要求独立) \[\mathbb{E}[\sum X_i]=\sum \mathbb{E}[X_i]\] 琴生不等式 $f(x)$为凸函数,则$\mathbb{E}[f(x)]>f(\mathbb{E}[x])$,利用泰勒展开证明即可. binomial random variable \(\Pr(X=j)=\binom n j p^j (1-p)^{n-j}\) 性质 $\mathbb{E}[X]=np$ 应用 考虑一个函数 S.每次调用它,S 都会递归调用 X 次自己.其中 X 是二项式概率分布的变量...

Posted by ethan-zhou on July 26, 2023

Probability and Computing 第一章笔记

最近看 Probability and Computing, 在此记录一些重要结论和有趣算法. Polynomial Identities 多项式次数为d,则x在[0,100d]随机取值,仅有$\frac{1}{100}$概率错误(根据代数基本定理,f-g最多有d个根). 一些基本定义和引理: 概率定义 容斥原理 事件的独立性 条件概率 $\Pr(E|F)=\frac{\Pr(E\cap F)}{\Pr(F)}$ Veryfying Matrix Multiplication 给定三个方阵 A,B,C 快速验证 $A\times B=C$? 随机算法 随机...

Posted by ethan-zhou on July 21, 2023

FRIENDS

ABOUT ME

avatar

一个 OIer ICPCer，喜欢弹吉他，踢球，爱好编程

✉️ zehzhou [at] mail [dot] ustc [dot] edu [dot] cn

FEATURED TAGS

算法 游记 前端 线段树 题解 USACO dp 随机算法
icon