Blog E

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

2024WF游记

好像能进 9 月哈萨克斯坦的 World Final 了,这学期没怎么训,假期打算开始复健,于是打算先写个游记占坑。 7.1 有场 div 1+2,因为大号 @ethan_enhe 三月刚上红,不太敢动。遂创小号 @_furina 开打。没想到打得还不错,rnk 99,猛加 867 rating。 发现法国 cf 不太行,于是把小号地址设到了法国(符合原著),打算看看能不能打到前三。至高无上的水神陛下即将抵达自己忠实的枫丹! 7.7 拿小号去div2炸鱼了,题都会,可惜差一题没写出来, rnk 5。 这比赛怎么这么多猜结论题。。。

LSPN论文调研

终于把大研的中期报告胡过去了,听说没有人看,于是就写的简单点。 正好也好久没发博客,就把文献调研部分拿出来发一个,记录一下这学期读的部分文章。因为大研报告的提交平台的富文本编辑器不支持公式,所以这里也就都没有用 latex,凑合看吧[doge] 研究问题 Learing Parity with Noise 的问题描述如下: 有一个隐藏的,长度为 n 的 0/1 向量 s, 目标是找出它 我们可以对数据库进行若干次询问,每次询问,会得到如下的回答: 一个长度为 n 的随机 0/1 向量 y x dot y mod 2 的结果(但是会以 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...

Probability and Computing 第八章部分习题


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...

Probability and Computing 第七章部分习题

算不动了

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

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...

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; ...

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]...

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])]$ 定理 \(\...

icon