公司网站建设需要哪些内容,成品短视频app的优势,用jsp sqlserver做的购物网站,自己有域名如何做网站前言
本文是三国杀中的概率学问题系列文章中的一篇#xff0c;将详细讨论王荣吉占的期望摸牌数问题。并加上连续情形作为拓展。
值得说明的是#xff0c;本文的思路受到了一篇文章的启发#xff0c;在此特别鸣谢#xff0c;这是文章的链接。
王荣吉占的期望摸牌数 王荣的…前言
本文是三国杀中的概率学问题系列文章中的一篇将详细讨论王荣吉占的期望摸牌数问题。并加上连续情形作为拓展。
值得说明的是本文的思路受到了一篇文章的启发在此特别鸣谢这是文章的链接。
王荣吉占的期望摸牌数 王荣的二技能吉占很有意思展示牌堆顶的一张牌然后猜测下一张牌比这张牌大还是比这张牌小猜对了就继续猜直到猜错为止然后最终可以获得展示的所有牌。所以即便第一次就猜错也能拿到2张牌第一张展示的牌和猜错的这张牌。为了能够摸更多的牌我们需要采取贪心的猜牌策略保证自己这次猜对的概率最大。也就是说在展示的牌为1-6时我们选择猜大8-13时猜小7的时候由于猜大和猜小的概率一样所以猜大猜小都可以。
离散情形
为了使得模型更一般化将13种不同的点数改为n种不同的点数。那么问题可以重新描述如下 问题牌有1~n这n种点数我们先亮出第一张牌然后猜测下一张牌跟这一张牌的大小关系然后亮出下一张牌若猜对则继续猜猜错就停止。求在最优策略下平均能亮出几张牌。 由于牌堆为理想牌堆不管怎么拿牌每种点数的牌的张数都是一样的所以最优策略即为若当前牌的点数小于等于 n 1 2 \frac{n1}{2} 2n1就猜大否则猜小。
我们令 f ( x ) f(x) f(x)表示当前牌的点数为 x x x时后面会亮出的牌数的数学期望。那么我们可以得到下面的公式 f ( x ) { ∑ i x 1 n 1 n f ( i ) 1 0 ≤ x ≤ n 1 2 ∑ i 1 x − 1 1 n f ( i ) 1 n 1 2 x ≤ 1 f(x)\begin{cases} \sum_{ix1}^n{\frac{1}{n}f(i)1} 0\leq x\leq\frac{n1}{2} \\ \sum_{i1}^{x-1}{\frac{1}{n}f(i)1} \frac{n1}{2}x\leq 1 \end{cases} f(x){∑ix1nn1f(i)1∑i1x−1n1f(i)10≤x≤2n12n1x≤1
解释一下这个公式当前牌的点数为 x x x时首先会亮出下一张牌这是1的含义。然后下一张牌是每个点数的概率都是 1 n \frac{1}{n} n1把猜对了能亮出的牌数乘以概率累加起来就是猜对了之后期望亮出的牌数。分成两段也仅仅是因为猜测策略的原因。
我们要求的是平均能亮出几张牌假设这个数量为 E E E那么 E 1 n ∑ i 1 n f ( i ) 1 E\frac{1}{n}\sum_{i1}^n{f(i)}1 En1∑i1nf(i)1
首先先亮出一张牌然后这张牌的点数有n种可能性即有 1 n \frac{1}{n} n1的概率为i。如果第一张牌是i的话则期望亮出的牌数就是 f ( i ) f(i) f(i)。于是我们把概率乘以亮出牌数累加起来就是接下来会亮出的牌数即 1 n ∑ i 1 n f ( i ) \frac{1}{n}\sum_{i1}^n{f(i)} n1∑i1nf(i)。再加上第一张亮出的牌就是 1 n ∑ i 1 n f ( i ) 1 \frac{1}{n}\sum_{i1}^n{f(i)}1 n1∑i1nf(i)1了。 E E E就是我们想求的答案。
接下来我们来算出 f ( x ) f(x) f(x)的具体值。
我们设出 f ( x ) f(x) f(x)的前缀和。令 F ( x ) ∑ i 1 n f ( i ) F(x)\sum_{i1}^n{f(i)} F(x)∑i1nf(i)
当 n 1 2 x ≤ 1 \frac{n1}{2}x\leq 1 2n1x≤1时 f ( x ) 1 n F ( x − 1 ) 1 f(x)\frac{1}{n}F(x-1)1 f(x)n1F(x−1)1 F ( x − 1 ) n f ( x ) n F(x-1)nf(x)n F(x−1)nf(x)n
将 x 1 x1 x1代入 x x x得 F ( x ) n f ( x 1 ) n F(x)nf(x1)n F(x)nf(x1)n
两式相减得 f ( x ) n f ( x 1 ) − n f ( x ) f(x)nf(x1)-nf(x) f(x)nf(x1)−nf(x)
于是得到了 f ( x ) f(x) f(x)的递推式 f ( x 1 ) n 1 n f ( x ) f(x1)\frac{n1}{n}f(x) f(x1)nn1f(x)
由于 n n n为常数于是我们发现在 n 1 2 x ≤ 1 \frac{n1}{2}x\leq 1 2n1x≤1上 f ( x ) f(x) f(x)是等比数列。
类似地在 0 ≤ x ≤ n 1 2 0\leq x\leq\frac{n1}{2} 0≤x≤2n1上求得 f ( x 1 ) n n 1 f ( x ) f(x1)\frac{n}{n1}f(x) f(x1)n1nf(x)
可以发现 f ( x ) f(x) f(x)是一列以 n 1 2 \frac{n1}{2} 2n1为对称轴先递减后递增的两段等比数列公比分别为 n n 1 \frac{n}{n1} n1n和 n 1 n \frac{n1}{n} nn1。
等比数列的求和公式为 S a 1 ∗ q n − 1 q − 1 Sa_1*\frac{q^n-1}{q-1} Sa1∗q−1qn−1现在公比已经知道了所以要求首项。 f ( n 1 2 ) f(\frac{n1}{2}) f(2n1)位于两段的连接处可以让它作为两段等比数列的首项。现在我们来求 f ( n 1 2 ) f(\frac{n1}{2}) f(2n1)。
我们不妨假设 n n n为奇数这样 x n 1 2 x\frac{n1}{2} x2n1在公式的两段上都可以成立。于是有 f ( n 1 2 ) ∑ i n 3 2 n 1 n f ( i ) 1 ∑ i 1 n − 1 2 1 n f ( i ) 1 f(\frac{n1}{2})\sum_{i\frac{n3}{2}}^n{\frac{1}{n}f(i)1}\sum_{i1}^{\frac{n-1}{2}}{\frac{1}{n}f(i)1} f(2n1)∑i2n3nn1f(i)1∑i12n−1n1f(i)1 ( 2 1 n ) f ( n 1 2 ) 1 n F ( n ) 2 (2\frac{1}{n})f(\frac{n1}{2})\frac{1}{n}F(n)2 (2n1)f(2n1)n1F(n)2 f ( n 1 2 ) 1 2 n 1 F ( n ) 2 n 2 n 1 f(\frac{n1}{2})\frac{1}{2n1}F(n)\frac{2n}{2n1} f(2n1)2n11F(n)2n12n
利用 f ( x ) f(x) f(x)的对称性以及等比数列求和公式有 F ( n ) ∑ i 1 n − 1 2 f ( i ) ∑ i n 1 2 n f ( i ) ∑ i n 3 2 n f ( i ) ∑ i n 1 2 n f ( i ) n 1 n f ( n 1 2 ) ( n 1 n ) n − 1 2 − 1 n 1 n − 1 f ( n 1 2 ) ( n 1 n ) n 1 2 − 1 n 1 n − 1 [ 2 n ( n 1 n ) n 1 2 − 2 n − 1 ] f ( n 1 2 ) F(n)\sum_{i1}^{\frac{n-1}{2}}{f(i)}\sum_{i\frac{n1}{2}}^n{f(i)}\sum_{i\frac{n3}{2}}^n{f(i)}\sum_{i\frac{n1}{2}}^n{f(i)}\frac{n1}{n}f(\frac{n1}{2})\frac{(\frac{n1}{n})^{\frac{n-1}{2}}-1}{\frac{n1}{n}-1}f(\frac{n1}{2})\frac{(\frac{n1}{n})^{\frac{n1}{2}}-1}{\frac{n1}{n}-1}[2n(\frac{n1}{n})^{\frac{n1}{2}}-2n-1]f(\frac{n1}{2}) F(n)∑i12n−1f(i)∑i2n1nf(i)∑i2n3nf(i)∑i2n1nf(i)nn1f(2n1)nn1−1(nn1)2n−1−1f(2n1)nn1−1(nn1)2n1−1[2n(nn1)2n1−2n−1]f(2n1)
联立两式 { f ( n 1 2 ) 1 2 n 1 F ( n ) 2 n 2 n 1 F ( n ) [ 2 n ( n 1 n ) n 1 2 − 2 n − 1 ] f ( n 1 2 ) \begin{cases} f(\frac{n1}{2})\frac{1}{2n1}F(n)\frac{2n}{2n1}\\ F(n)[2n(\frac{n1}{n})^{\frac{n1}{2}}-2n-1]f(\frac{n1}{2}) \end{cases} {f(2n1)2n11F(n)2n12nF(n)[2n(nn1)2n1−2n−1]f(2n1)
解得 { f ( n 1 2 ) n 2 n 1 − n ( n 1 n ) n 1 2 F ( n ) n [ 2 n 2 n 1 ( n 1 n ) n 1 2 − 1 ] 1 − n 2 n 1 ( n 1 n ) n 1 2 \begin{cases} f(\frac{n1}{2})\frac{n}{2n1-n(\frac{n1}{n})^{\frac{n1}{2}}}\\ F(n)\frac{n[\frac{2n}{2n1}(\frac{n1}{n})^{\frac{n1}{2}}-1]}{1-\frac{n}{2n1}(\frac{n1}{n})^{\frac{n1}{2}}} \end{cases} ⎩ ⎨ ⎧f(2n1)2n1−n(nn1)2n1nF(n)1−2n1n(nn1)2n1n[2n12n(nn1)2n1−1]
于是可以得到 E ∑ i 1 n 1 n f ( i ) 1 1 n F ( n ) 1 1 2 n 1 n ( n n 1 ) n 1 2 − 1 E\sum_{i1}^{n}\frac{1}{n}f(i)1\frac{1}{n}F(n)1\frac{1}{\frac{2n1}{n}(\frac{n}{n1})^\frac{n1}{2}-1} E∑i1nn1f(i)1n1F(n)1n2n1(n1n)2n1−11
当 n 13 n13 n13时 E ≈ 4.232 E\approx4.232 E≈4.232
当 n → ∞ n\to\infty n→∞时 l i m n → ∞ E l i m n → ∞ 1 2 ( 1 − 1 n 1 ) n 1 2 − 1 1 2 e − 1 2 − 1 ≈ 4.69 lim_{n\to\infty}Elim_{n\to\infty}\frac{1}{2(1-\frac{1}{n1})^{\frac{n1}{2}}-1}\frac{1}{2e^{-\frac{1}{2}}-1}\approx4.69 limn→∞Elimn→∞2(1−n11)2n1−112e−21−11≈4.69
至此原题就解出来了。
连续情形
我们再做一点点扩展看看在 n n n趋于无穷时的情况。现在我们把问题转化为连续的情况。 问题在[0,1]区间上的均匀分布总体进行依次采样约定若采样得到的随机数小于 1 2 \frac{1}{2} 21则猜测下一次采得的随机数会更大若采样得到的随机数大于 1 2 \frac{1}{2} 21则猜测下一次采得的随机数会更小。若猜测正确则继续猜若猜测错误则采样终止。求采样次数的数学期望。 设 f ( x ) f(x) f(x)表示当前点为 x x x时继续猜测的次数。给出 f ( x ) f(x) f(x)的表达式如下 f ( x ) { ∫ x 1 f ( t ) d t 1 0 ≤ x ≤ 1 2 ∫ 0 x f ( t ) d t 1 1 2 x ≤ 1 f(x)\begin{cases} \int_x^1{f(t)dt}1 0\leq x\leq\frac{1}{2} \\ \int_0^x{f(t)dt}1 \frac{1}{2}x\leq 1 \end{cases} f(x){∫x1f(t)dt1∫0xf(t)dt10≤x≤2121x≤1 值得说明的是 x 1 2 x\frac{1}{2} x21的情况对于两个公式都成立。这个式子是怎么得出来的呢现在的点是 x x x我们先要按上述规则进行一次猜测这是1的含义。如果猜错了我们就失去了继续猜测的机会。如果猜对了那么我们可以继续猜测。假设下一个点是 t t t这样的概率为 d t dt dt继续猜测的次数为 f ( t ) f(t) f(t)。这样做一个积分可以理解为加权平均就能得到 f ( x ) f(x) f(x)的表达式了。
假设 E E E为采样次数的数学期望那么 E ∫ 0 1 f ( t ) d t 1 E\int_0^1{f(t)dt}1 E∫01f(t)dt1
这个式子的含义是先随机出现一个点这是1的含义再按照这个点的值进行加权平均也就是积分的含义。 E E E就是在连续情形下王荣的摸牌数。
接下来我们开始解这个函数。
首先发现一个很简单的事实 f ( 0 ) f ( 1 ) E f(0)f(1)E f(0)f(1)E
显然这个函数关于 x 1 2 x\frac{1}{2} x21是对称的。那么我们来求一下 f ( 1 2 ) f(\frac{1}{2}) f(21)的值。 f ( 1 2 ) ∫ 1 2 1 f ( t ) d t 1 ∫ 0 1 2 f ( t ) d t 1 f(\frac{1}{2})\int_\frac{1}{2}^1{f(t)dt}1\int_0^\frac{1}{2}{f(t)dt}1 f(21)∫211f(t)dt1∫021f(t)dt1 2 f ( 1 2 ) ∫ 0 1 f ( t ) d t 2 E 2 2f(\frac{1}{2})\int_0^1{f(t)dt}2E2 2f(21)∫01f(t)dt2E2 f ( 1 2 ) 1 2 E 1 2 f(\frac{1}{2})\frac{1}{2}E\frac{1}{2} f(21)21E21
当 0 ≤ x ≤ 1 2 0\leq x\leq \frac{1}{2} 0≤x≤21时我们对 f ( x ) ∫ x 1 f ( t ) d t 1 f(x)\int_x^1{f(t)dt}1 f(x)∫x1f(t)dt1两边求导得 f ′ − f f-f f′−f
这是一个比较简单的常微分方程接下来需要一点点常微分方程的知识。 d f d x − f \frac{df}{dx}-f dxdf−f d f f − d x \frac{df}{f}-dx fdf−dx d l n f − d x dlnf-dx dlnf−dx l n f − x C 1 lnf-xC_1 lnf−xC1 f e − x C 1 C e − x fe^{-xC_1}Ce^{-x} fe−xC1Ce−x
于是我们解得 f C e − x fCe^{-x} fCe−x
代入 x 0 x0 x0和 x 1 2 x\frac{1}{2} x21得 { C e 0 E C e − 1 2 1 2 E 1 2 \begin{cases} Ce^0E \\ Ce^{-\frac{1}{2}}\frac{1}{2}E\frac{1}{2} \end{cases} {Ce0ECe−2121E21
解得 C E 1 2 e − 1 2 − 1 CE\frac{1}{2e^{-\frac{1}{2}}-1} CE2e−21−11
于是得到当 0 ≤ x ≤ 1 2 0\leq x\leq \frac{1}{2} 0≤x≤21时 f ( x ) e − x 2 e − 1 2 − 1 f(x)\frac{e^{-x}}{2e^{-\frac{1}{2}}-1} f(x)2e−21−1e−x
由于 f ( x ) f(x) f(x)关于 x 1 2 x\frac{1}{2} x21对称可对称地写出 1 2 x ≤ 1 \frac{1}{2}x\leq 1 21x≤1的情况。于是我们可以得到 f ( x ) f(x) f(x)的表达式。 f ( x ) { e − x 2 e − 1 2 − 1 0 ≤ x ≤ 1 2 e x − 1 2 e − 1 2 − 1 1 2 x ≤ 1 f(x)\begin{cases} \frac{e^{-x}}{2e^{-\frac{1}{2}}-1} 0\leq x\leq\frac{1}{2} \\ \frac{e^{x-1}}{2e^{-\frac{1}{2}}-1} \frac{1}{2}x\leq 1 \end{cases} f(x)⎩ ⎨ ⎧2e−21−1e−x2e−21−1ex−10≤x≤2121x≤1 E 1 2 e − 1 2 − 1 ≈ 4.69 E\frac{1}{2e^{-\frac{1}{2}}-1}\approx4.69 E2e−21−11≈4.69即为我们所求的答案。
可以发现连续情形就是离散情形在 n → ∞ n\to\infty n→∞时的情况。而指数函数在离散情形下对应的其实就是等比数列。
总结
本文先将问题作为离散情形进行处理将问题中的n13推广到了n为任意奇数的情况偶数情形略有不同也可以做但是没有什么意义笔者就没有单独列出了。并且将问题推广到了 n n n为 ∞ \infty ∞的情形即连续情形。从而彻底解出了王荣吉占背后的数学模型。
