0%

Project-Euler-436

\(\newcommand{\D}[0]{\mathrm{d}}\) 卡着第 50 名过……

谁来教教我如何用微积分算期望啊,我算着简直要疯了。。

solution

其实只要算出这两个随机变量的 pdf 就好了。但是我觉得算起来特别恶心……主要是对这货不熟吧,时不时就卡住了。

首先算第一个的 pdf 。我们枚举累加器是在第 \(n\) 次累加时超过 1 ,我们计算出 \(n\) 个变量的和为 \(t\) 的 pdf \(f(x) = \frac{t^{n - 1}}{(n - 1)!}\) ,则第一个值的密度分布函数为 \[ \begin{array}{rl} & P(x) \\ = & \sum_{n = 1}^\infty \int_{1 - x}^{1} f(t) \D{t} \\ = & \sum_{n = 1}^\infty \int_{1 - x}^{1} \frac{t^{n - 1}}{(n - 1)!} \D{t} \\ = & \sum_{n = 1}^\infty \frac{1 - (1 - x)^n}{n!} \\ = & \sum_{n = 1}^\infty \frac{1}{n!} - \sum_{n = 1}^\infty \frac{(1 - x)^n}{n!} \\ = & (e - 1) - (e^{1 - x} - 1) \\ = & e - e^{1 - x} \\ \end{array} \]

第二个值的 pdf 就比较恶心了。还是同样的思想,我们令 \(g_n(x)\) 表示 \(n\) 个 0 到 1 的变量的和为 \(1 + x\) 的 pdf ,可以得到 \(g_1(x) = 0\) 。可以求出 \(g_n (x)\) 递推式:

\[ \begin{array}{rl} & g_{n+1}(x) \\ = & \int_{0}^x g_n(t) \D{t} + \int_{x}^1 f(t) \D{t} \\ = & \int_{0}^x g_n(t) \D{t} + \frac{1 - x^n}{n!} \\ \end{array} \]

求出 \(g_n(x)\) 通项似乎是比较困难的,但是注意,第二个值的 pdf 我们只关心 \(\sum_{n=1}^\infty g_n(x)\)

对于递推式 \(v_{n+1}(x) = \int_0^x v_n(t) \D{t}, v_{0}(x) = 1\) ,我们可以得到 \(v_n(x) = \frac{x^n}{n!}\) ,则 \(\sum_{n=0}^\infty v_n(x) = e^x\)

我们考虑 \(g_{n+1}(x) = \int_0^x g_n(t) \D{t} + \frac{1 - x^n}{n!}\) 里面的 \(\frac{1}{n!}\) 。这个数会被连续积分无数次,最后对 \(\sum_{n = 1}^\infty g_n (x)\) 的贡献是 \(\frac{e^x}{n!}\)\(\frac{x^n}{n!}\) 也会被积分无数次,注意到对于 \(k\) 来说,所有 \(x \leq k\)\(\frac{x^n}{n!}\) 积分时都会得到过一个 \(\frac{x^k}{k!}\) ,所以这部分对于和的贡献是 \(\sum_{k = 1}^\infty k \frac{x^k}{k!} = x e^x\) 。所以我们有: \[\sum_{n = 1}^\infty g_n(x) = \sum_{n = 1}^\infty \frac{e^x}{n!} - x e^x = e^x (e - 1 - x)\]

现在要开始求第二个值的 pdf 了。令 pdf 为 \(Q(x)\) ,则有 : \[Q(x) = \int_{1-x}^1 e^x(e-1-x)\D{x}\]

知道了 \(P(x)\)\(Q(x)\) ,答案就是:

\[ans = \int_{0}^1 Q(x) \int_0^x P(y) \D{y} \D{x}\]

\(Q(x)\)\(ans\) 的具体表达式我用的 sage 暴力算的,就没写出来了。

nonsense

看着 forum 里面各种高大上的积分感觉被虐傻了。

@dyh 求你的做法。