概率论杂题

发表于 更新于 本文字数： 3.2k 阅读时长 ≈ 3 分钟

收录一点看到过的趣题。

一张 nn 个点的无向图，上面进行随机游走，同时点 ii 有 pip_i 的概率离开这张图，否则均匀随机走一条出边，对于每对 (i,j)(i,j) 求出，从 ii 出发，最后在 jj 离开图的概率。

n≤500n\le 500

注意到每次经过一个点 ii 的时候都有概率离开，设 fif_i 表示 ii 被经过次数的期望，那么容易发现 ii 的答案就是 fi×pif_i\times p_i。

列一下方程，就是每个点有相邻点的 ff​ 乘上概率的和。

fx=[x 是起点]+∑(fy−py)/dyf_x=[\text{x 是起点}]+\sum (f_y-p_y)/d_y

这样高斯消元就可以得到一个 ii，所有 jj 的答案了。

注意到每次是在右边选一个点加个常数，因此可以类似矩阵求逆，把每个 jj 的答案用每个点是否是起点表示出来，总复杂度 O(n3)O(n^3) 。

有一个盒子，初始有 mm 个白球和 mm 个黑球，进行以下操作 nn 次：

第 ii 轮，均匀随机在盒子里面取出一个球，如果为黑球，记录 ai=−1a_i=-1，否则 ai=1a_i=1​ ，然后放入一个黑球一个白球。

求 E[∣∑i=1nai∣]\mathbb E[|\sum_{i=1}^n a_i|]。

n≤106n\le 10^6​ 。

首先设 A=∑i=1n[ai=1],B=∑i=1n[ai=−1]A=\sum_{i=1}^n[a_i=1],B=\sum_{i=1}^n [a_i=-1]，那么要求的就是 E[∣A−B∣]\mathbb E[|A-B|]。

注意到这个绝对值非常阴间，换成 ∣A−B∣=(A−B)2|A-B|=\sqrt{(A-B)^2}，因此只需要求出 E[A2],E[AB]\mathbb E[A^2],\mathbb E[AB] 即可。

考虑先给所有白球标个号，在第 i−1i-1 轮加入的白球标号为 ii，黑球同理，这样记录拿出的球的标号。

如果只记录拿出的 nn 个比较麻烦，经典做法是改成取 2n2n 次，排成长度为 2n2n 的序列，因为我们只关心前面 nn 个球的黑白数量，所以后面怎么放其实无关，因此得到一个长度为 2n2n 的排列。

考虑一个排列怎样是合法的，显然是标号为 ii 的球放的位置 ≥i\ge i。

然后会发现所有合法排列出现概率相同，这个考虑每次取球，可以取的球的相对顺序，排第一个的概率就是满足均匀分布。

因此只需要数，钦定一个地方必须放一个值，合法排列的方案数。

先考虑不钦定咋做，相当于一个数可以放一个后缀，这个是经典，答案是：

∏i=1n(n−i+2)(n−i+1)\prod_{i=1}^n (n-i+2)(n-i+1)

就是从后往前确定。

那么考虑确定一个值，假设钦定 ar=la_r=l，那么 [l,r][l,r] 中的数相当于可以选的位置减少了 11，方案数相应改变。

直接 dp，因为是选一个区间，设 fi,0/1/2f_{i,0/1/2} 表示前 ii 个方案，当前在区间左边，中间还是右边，轻松转移做到 O(n)O(n)，这个是 E[A]\mathbb E[A]。

E[A2]\mathbb E[A^2] 是类似的，只不过是选了两个区间，类似的 dp 即可。

随机选择两个数 x,y∈Nx,y\in \mathbb N，求他们互质的概率。

经典题了，但是不太会做。

题目相当于是要求

lim⁡N→∞∑i=1n∑j=1n[gcd⁡(i,j)=1]N2\lim_{N\to \infty} \sum_{i=1}^n \sum_{j=1}^n \frac{[\gcd(i,j)=1]}{N^2}

先莫反一下：

lim⁡N→∞∑i=1nμ(i)1i2\lim_{N\to \infty} \sum_{i=1}^n \mu(i)\frac{1}{i^2}

考虑一下 μ\mu 的意义，就是多一个质因子就乘一个 −1-1，得到：

∏p∈P(1−1p2)\prod_{p\in \mathbb P} (1-\frac{1}{p^2})

就是直接考虑每个质因子选或者不选，然后我就不会下一步推导了/dk 。

乘法很难以计算，因此考虑转化为加法，但是 p2−1p2\frac{p^2-1}{p^2} 也不太好搞。

此时很妙的一步，注意到 1−x1-x 这个东西放在分母是可以展开的，因此直接式子取倒数，得到：

∏p∈P11−1p2=∏p∈P(∑k=1∞1p2k)=∑i=1∞1i2=π26\prod_{p\in \mathbb P} \frac{1}{1-\frac{1}{p^2}}=\prod_{p\in \mathbb P}(\sum_{k=1}^{\infty} \frac{1}{p^{2k}})=\sum_{i=1}^{\infty}\frac{1}{i^2}=\frac{\pi^2}{6}

中间一步是唯一分解定理，最后一步是经典。

因此

∏p∈P(1−1p2)=6π2≈0.607927\prod_{p\in \mathbb P} (1-\frac{1}{p^2})=\frac{6}{\pi^2}\approx 0.607927

笑点解析，这个题 mathematica 不会做。

对于任意大小为 nn 的正整数集合 SS，证明，必定存在一个大小为 n/3n/3 的子集 TT 满足不存在 a,b,c∈T,a+b=ca,b,c\in T,a+b=c 。

先挖个概率方法的坑。

这个东西感觉本质和鸽巢原理其实一样，只不过用概率分析有些时候会更加简单。

先守旧派，用非概率方法做一下。

先随便构造一个一个子集，我们取出所有 [l,r]∩S,2l≥r[l,r] \cap S,2l\ge r，容易发现肯定合法。

但是发现这个作用好像不大，想了一会儿，并不会做。

做法很高妙啊，选一个质数 p=3k+2p=3k+2，然后把 x∈Sx\in S 变成 x mod px\bmod p，在这个取模意义下满足条件比原来更强。

类似得找一个区间满足一定合法，发现 [k+1,2k+1][k+1,2k+1] 一定合法。

只选一个区间里面的数容易寄，多选几个合法的集合 TT，然后去证明 ∣T∩S∣≥n/3|T\cap S|\ge n/3 。

由于是模质数域下，显然把一个集合所有元素全部乘以一个数 xx 还是合法。

那么 xx 总共有 pp 种选法，由于 pp 为质数，所以 sxsx 一定两两不同。

那么

∑x=0p−1∑s∈S[s∈[k+1,2k+1]]=∣S∣(k+1)\sum_{x=0}^{p-1} \sum_{s\in S} [s\in [k+1,2k+1]]=|S|(k+1)

相当于这么多个球放到 pp 个盒子里面去，那么至少有一个盒子有：

⌈∣S∣(k+1)3k+2⌉≥∣S∣3\left\lceil \frac{|S|(k+1)}{3k+2} \right \rceil\ge \frac{|S|}{3}