均匀分布下的最优寻宝策略

2019-02-09  本文已影响0人  张矩阵

源起

2018年9月入职阿里，午饭时和入职半年的同事钱导闲聊说到了这道面试题。题目是钱导2010年面试阿里时面试官出的题目。近十年了，因缘际会，加上之前并未在面试书中见过这道题目，于是将钱导和我的讨论结果记为此文。

问题

现有一条数轴，有一宝藏位于原点到坐标L的线段上。寻宝人需要从原点的位置出发，找到宝藏后将宝藏带回原点。

寻宝人在行走路上需要消耗粮食，每走1个单位的距离需要消耗粮食量C
在原点处有粮食站可供寻宝人取粮食。

寻宝人可以一次性带足粮食；也可以第一次只带部分粮食、当走了一定距离仍无法找到宝藏时就折返回原点补充粮食、再开始第二次寻宝，以此类推。（注意返程路上也是需要消耗粮食的，不可以到了断粮时才开始返程。而是应该在粮食恰好只够返程、且依然未能寻到宝时返程）

若宝藏位置符合均匀分布，寻宝人使用怎样的寻宝策略，可以使得从粮食站取的粮食量的期望值最小？

猜测

建模

这道题目的关键，是用合适的数学语言进行刻画。当建模完成后，后面的代数运算都是自然的。

在连续型概率下，单点的概率为0，但宝藏依然有可能位于坐标0和坐标L（概率测度为0仅为不可能事件的必要不充分条件）

为了讨论的方便（主要为了能够引入无限步策略，对于原问题其实无所谓），我们假设宝藏不会位于坐标0和坐标L，这不影响问题的实质。

有限步策略

现假设一个策略恰使用了n次取粮，每次取粮走的距离为严格递增序列 a_1, ..., a_n
其中a_n=L，因为必须保证该策略一定能寻宝成功。
注意每次寻宝人会在粮食恰好只够返程、且依然未能寻到宝时返程补粮

为了后续推导记号的便捷性，我们记a_0=0
则一个有限步策略由严格递增序列a_0, a_1, ..., a_n构成，其中a_0=0,a_n=L

宝藏位置随机变量X为 [0, L] 上的均匀分布，即 X \sim U(0,L)
当X=x时，设 i 恰使得a_i <= x < a_{i+1}
则取走的粮食为f(x) = \Sigma^{i+1}_{k=0}2Ca_k
因此，取走的粮食的数学期望为
\begin{split} E(f(X))&=\int_0^{L}p(x)f(x)dx \\ &= \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)f(x)dx\\ &= \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)(\Sigma^{i+1}_{k=0}2Ca_k)dx \\ &= \Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}2Ca_k\int_{a_i}^{a_{i+1}}p(x)dx \\ &= \frac{2C}{L}\Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k \end{split} \tag 1

考察项\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k，得
\begin{split} \Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k &=\Sigma^{i+1}_{k=0}a_{i+1}a_k - \Sigma^{i+1}_{k=0}a_ia_k \\ &= (a_{i+1}^2 + a_{i+1}a_i + \Sigma^{i-1}_{k=0}a_{i+1}a_k) - (a_{i+1}a_i + a_i^2 + \Sigma^{i-1}_{k=0}a_{i}a_k) \\ &= (a_{i+1}^2 - a_i^2) + (a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k \end{split} \tag 2

当i \ge 2时，因a_0, a_1, ..., a_n是严格递增序列且a_1>0
所以(a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k > 0, \quad i\ge2 \tag 3

因此，当n \ge 3时，将 (3) 代回 (1) 可得
E(f(X)) > \frac{2C}{L}\Sigma_{i=0}^{n-1}(a_{i+1}^2 - a_i^2) = \frac{2C}{L}a_n^2 = 2CL

而当n=1 或 n=2 时，由 (1)易得 E(f(X)) = 2CL，为最小期望
当n=1时还有Var(f(X))=0为最小方差

无限步策略

对于一个无限步的策略，我们沿用在有限步策略中使用的记号和公式。
实际上，一个无限步策略是逐渐逼近坐标L的，为使一个无限步策略是合法的，易知a_i<L对任意i成立且 \lim_{n \to \infty} a_n= L

与有限步策略的情形类似，只要任取n>3可得
E(f(X))=\int_0^{L}p(x)f(x)dx \gt \Sigma_{i=0}^{n-1}\int_{a_i}^{a_{i+1}}p(x)f(x)dx \gt 2CL

更进一步：期望是否可能无穷

由前面有限步策略、无限步策略的讨论，实际上我们已经得到了原问题的答案。这里我们更深入的讨论：一个不好的策略是否可能会导致取粮的数学期望太大（例如正无穷）

我们继续使用前面的记号，将(2)代回(1)得到
\begin{split} E(f(X)) &= \frac{2C}{L}\Sigma_{i=0}^{n-1}\Sigma^{i+1}_{k=0}(a_{i+1}-a_i)a_k \\ &= \frac{2C}{L}\Sigma_{i=0}^{n-1}[(a_{i+1}^2 - a_i^2) + (a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-1}[(a_{i+1}-a_i)\Sigma^{i-1}_{k=0}a_k] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-1}(a_{i+1}\Sigma_{k=0}^{i-1}a_k - a_i\Sigma_{k=0}^{i-1}a_k) \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - (\Sigma_{i=0}^{n-1}a_{i}\Sigma_{k=0}^{i-1}a_k) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - (\Sigma_{i=0}^{n-2}a_{i+1}\Sigma_{k=0}^{i}a_k) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}[(\Sigma_{i=0}^{n-1}a_{i+1}\Sigma_{k=0}^{i-1}a_k) - \Sigma_{i=0}^{n-2}a_{i+1}(\Sigma_{k=0}^{i-1}a_k + a_i) ] \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}(a_n\Sigma_{k=0}^{n-2}a_k - \Sigma_{i=0}^{n-2}a_{i+1}a_{i}) \\ &= \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \\ \end{split} \tag 4

有限步策略是否可能取粮期望过大

由(4)式，有限步策略的期望总是有限的。
因此，我们考虑的问题为：对于任意给定的正数A，是否总存在足够差的策略使E(f(X))>A

考虑一个“试探型”的n步策略，对于i=1,2,...,n, 有a_i = i\frac{L}{n}
我们用\Theta(n^p)表示与n^p为同阶无穷大
则
\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= \Sigma_{i=0}^{n-2}i\frac{L}{n}[L-(i+1)\frac{L}{n}]\\ &= \frac{L^2}{n^2}\Sigma_{i=0}^{n-2}[in-(i+1)i] \\ &= \frac{L^2}{n^2}[(n-1)\Sigma_{i=0}^{n-2}i-\Sigma_{i=0}^{n-2}i^2 ]\\ &= \frac{L^2}{n^2}[\frac{1}{2}(n-1)^2(n-2) - \frac{1}{6}(n-2)(n-1)(2n-3) ]\\ &= \frac{L^2}{n^2}\Theta(n^3)\\ &= L^2\Theta(n)\\ \end{split}
代回(4)式得E(f(X))=2CL + 2CL\Theta(n)
当n \rightarrow \infty 时，有E(f(X)) \rightarrow \infty （注意这个表述并不代表无限步的策略）
即对于任意给定的正数A，总存在足够大的n使得E(f(X))>A

无限步策略是否可能取粮期望过大

当策略为无限步时，我们考虑：此时的期望是有限还是无限？
注意(4)式在无限步策略下的写法略有不同：
\begin{split} E(f(X)) &= \lim_{n \to +\infty} \frac{2C}{L}a_n^2 + \frac{2C}{L}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \\ &= 2CL + \frac{2C}{L}\lim_{n \to +\infty}\Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) \end{split} \tag{5}

调和级数

考虑一个无限步的策略：对于i=1,2,... 有a_i = L(1-\frac{1}{i})
易证这是一个合法的寻宝策略。
则
\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= L^2\Sigma_{i=0}^{n-2}(1-\frac{1}{i})(-\frac{1}{n}+\frac{1}{i+1})\\ &=L^2(-\Sigma_{i=0}^{n-2}\frac{1}{n} + \Sigma_{i=0}^{n-2}\frac{1}{i+1} + \Sigma_{i=0}^{n-2}\frac{1}{ni} - \Sigma_{i=0}^{n-2}\frac{1}{i(i+1)}) \end{split}
其中，
\Sigma_{i=0}^{n-2}\frac{1}{i+1}为调和级数，当n \rightarrow \infty 时趋于正无穷。其余三项均易证n \rightarrow \infty有有限极限值。
因此由(5)式知此时 E(f(X))=+\infty

几何级数

考虑一个无限步的策略：对于i=1,2,... 有a_i = L(1-\frac{1}{2^i})
易证这是一个合法的寻宝策略。
则
\begin{split} \Sigma_{i=0}^{n-2}a_i(a_{n} - a_{i+1}) &= L^2\Sigma_{i=0}^{n-2}(1-\frac{1}{2^i})(-\frac{1}{2^n}+\frac{1}{2^{i+1}})\\ &=L^2(-\Sigma_{i=0}^{n-2}\frac{1}{2^n} + \Sigma_{i=0}^{n-2}\frac{1}{2^{i+1}} + \Sigma_{i=0}^{n-2}\frac{1}{2^i2^n} - \Sigma_{i=0}^{n-2}\frac{1}{2^i2^{i+1}}) \end{split}
由几何级数的性质，易证上式四项级数均有有限极限
因此由(5)式知此时 E(f(X)) 为有限值

结论

  1. 有两种策略可以使得提取粮食的期望值最小
  1. 不好的策略

继续扩展的方向

在写这篇文章时，我的大部分精力实际上花在了没有写出来的部分——针对一般概率分布的讨论。最初，我考虑了常见的连续型分布，但解析形式的复杂性（例如正态分布无原函数等）让我转而研究较为简化的分段均匀分布的性质。实际上，由于分段均匀分布可以分任意多段，可以任意逼近一般的概率分布（想象一下直方图），因此如果能研究好这类分布，对一般的概率分布也能有一个大致的认识。

但即使在这种情形下，我依然没有得出较有价值的结论。推出的表达式复杂，且试了一些具体数值后发现结果依赖于具体的参数设置，这使得整个问题的分类讨论更加繁复。最终我只推出了某些无关痛痒的性质（例如如果临近原点处概率极高的话可以先试探等显而易见的结论），对最优策略的推导并无显著帮助。

这个问题如果继续扩展，一般的概率分布确是一个方向。但未必会得出比较精巧的结果。实际上在原问题的讨论中我们也已经发现，很多不等号放缩都很“松”、很随意。

感兴趣的同学可以继续研究。

一点唠叨

上一篇下一篇

猜你喜欢

热点阅读