ProjectEuler-436 - Unfair wager

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

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

Solution

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

首先算第一个的 pdf 。我们枚举累加器是在第 \(n\) 次累加时超过 1 ，我们计算出 \(n\) 个变量的和为 \(t\) 的 pdf \(f(x) = \frac{t^{n - 1}}{(n - 1)!}\) ，则第一个值的密度分布函数为 \[ \begin{aligned} 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{aligned} \]

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

\[ \begin{aligned} 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{aligned} \]

求出 \(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 求你的做法。