一：\(n\) 个随机整数 \(a_i\in[1,w]\)，且 \(a_i\neq a_j\)，求第 \(c\) 大数的期望
考虑往 \(n\) 个球之间插 \(w-n\) 个板子，则每个球和板子分别对应一个整数
第 \(c\) 个球代表的数的期望应为 \(c+w\dfrac{c}{n+1}=\dfrac{c(w+1)}{n+1}\)
二：已知序列中其中有恰好 \(i\) 个石头，\(j\) 个布，\(k\) 个剪刀的概率 \(f_{i,j,k}\)，求下一个是石头的概率
考虑序列中有 \(i+1\) 个石头，\(j\) 个布，\(k\) 个剪刀的概率 \(f_{i+1,j,k}\)，
其末尾为石头的概率为 \(\dfrac{f_{i+1,j,k}}{i+j+k+1}\)
三：有一个长度为 \(n\) 的 \(01\) 串，初始为 \(0\)，每次随机一个不与 \(1\) 相邻的 \(0\) 改为 \(1\)，无法操作时结束，求当 \(n\to\infty\) 时随机抽取一个数为 \(1\) 的概率
给每个位置赋 \(f_i\in[0,1]\)
考虑以 \(f_i\) 从小到大的顺序枚举当前位置是否可以修改为 \(1\)，
则位置 \(i\) 被修改为 \(1\) 等价于其左边和右边的极长连续下降段长度均为偶数
故其概率为：
\[\left(1-P(f_i>f_{i-1})+P(f_i>f_{i-1}>f_{i-2})-\cdots\right)^2 \]考虑先随机 \(k\) 个数在固定顺序，则 \(P(f_i>f_{i-1}>\cdots>f_{i-k})=\dfrac{f_i^k}{k!}\)
位置 \(i\) 被修改为 \(1\) 概率即为
\[p=\left(1-f_i+\frac{f_i^2}{2}-\cdots\right)^2=(e^{-f_i})^2=e^{-2f_i} \]所求即为：
\[\int_0^1e^{-2x}\mathrm dx=\frac{1}{2}-\frac{1}{2e^2} \]考虑递推，令 \(a_n\) 为最后 \(1\) 的期望个数，枚举选的位置可得：
\[a_n=\frac{2}{n}s_{n-2}+1, a_0=0, a_1=1, s_n=\sum_{i=0}^na_i \]\[\begin{aligned} na_n&=2s_{n-2}+n\\ na_n-(n-1)a_{n-1}&=2(s_{n-2}-s_{n-3})+1 \\ n(a_n-a_{n-1})&=-a_{n-1}+2a_{n-2}+1 \\ nb_n&=-b_{n-1}+a_{n-2}+1 \\ nb_n-(n-1)b_{n-1}&=-(b_{n-1}-b_{n-2})+a_{n-2}-a_{n-3} \\ n(b_n-b_{n-1})&=-2(b_{n-1}-b_{n-2}) \end{aligned}\]\[c_n=-\frac{2}{n}c_{n-1}=\frac{4}{n(n-1)}c_{n-2}=\cdots=\frac{(-2)^{n-1}}{n!} \]所求即：
\[\begin{aligned}\lim_{i\to\infty}\frac{a_i}{i}&=\lim_{i\to\infty}b_i=\sum_{i=1}^\infty c_i=\sum_{i=1}^\infty\frac{(-2)^{i-1}}{i!} \\ &=-\frac{1}{2}\sum_{i=1}^\infty\frac{(-2)^{i}}{i!}=-\frac{1}{2}(e^{-2}-1)=\frac{1}{2}-\frac{1}{2e^2}\end{aligned}\]\(a_n\) 同上，考虑
\[\mathbf{OGF}\{ia_i\}=x\frac{\mathrm d}{\mathrm dx}\mathbf{OGF}\{a_i\} \]\[\mathbf{OGF}\{s_i\}=\frac{1}{1-x}\mathbf{OGF}\{a_i\} \]\[\mathbf{OGF}\{[0,1,2,\cdots]\}=x\frac{\mathrm d}{\mathrm dx}\frac{1}{1-x}=\frac{x}{(1-x)^2} \]则设 \(y=\mathbf{OGF}\{a_i\}\)，有
\[\begin{aligned} &x\frac{\mathrm dy}{\mathrm dx}=\frac{2x^2y}{1-x}+\frac{x}{(1-x)^2} \\ &\frac{\mathrm dy}{\mathrm dx}-\frac{2xy}{1-x}=\frac{1}{(1-x)^2} \\ &\frac{\mathrm dy}{y}=\frac{2x}{1-x}\mathrm dx \\ &y=C\frac{e^{-2x}}{(1-x)^2} \\ &\frac{\mathrm dC}{\mathrm dx}\frac{e^{-2x}}{(1-x)^2}=\frac{1}{(1-x)^2} \\ &C=\frac{e^{2x}}{2}+C' \\ &y=\left(\frac{e^{2x}}{2}+C\right)\frac{e^{-2x}}{(1-x)^2} \\ &y=\frac{1}{2(1-x)^2}+\frac{Ce^{-2x}}{(1-x)^2} \end{aligned}\]易知 \(y(0)=0\)，故 \(C=-\dfrac{1}{2}\)
\[\begin{aligned} y&=\frac{1-e^{-2x}}{2(1-x)^2} \\ a_n&=\frac{1}{2}\left(n+1-\sum_{i=0}^k\sum_{j=0}^i\frac{(-2)^j}{j!}\right) \\ &=\frac{1}{2}\left(n+1-\sum_{i=0}^n\frac{(-2)^i}{i!}(n-i+1)\right) \\ \lim_{n\to\infty}\frac{a_n}{n}&=\frac{n+1}{2n}-\frac{1}{2n}\sum_{i=0}^n\frac{(-2)^i}{i!}(n-i+1) \\ &=\frac{1}{2}-\frac{1}{2n-2(n-1)}\sum_{i=0}^{n+1}\frac{(-2)^i}{i!} \\ &=\frac{1}{2}-\frac{1}{2e^2} \end{aligned}\]\(a_n\) 同上
\[\left(\frac{(-2)^{i+1}}{(i+1)!}(n-i)\right){\Large/}\left(\frac{(-2)^i}{i!}(n-i+1)\right)=\frac{-2(i-n)}{(i+1)(i-n-1)} \]\[\sum_{i=0}^n\frac{(-2)^i}{i!}(n-i+1)=(n+1)F(-n;-n-1;-2) \]\[\lim_{n\to\infty}\frac{a_n}{n}=\frac{n+1}{2n}\left(1-F(-n;-n-1;-2)\right)=\frac{1}{2}\left(1-\frac{1}{e^2}\right) \] 标签：概率,frac,dbinom,sum,2x,一些,相关,aligned,mathrm From： https://www.cnblogs.com/JerryTcl/p/17155753.html