SPECODER's Blog

越然独立，卓而胜己!
最佳止步问题（optimal stopping）[2]
调和级数与欧拉常数

最佳止步问题（optimal stopping）[3]

SPECODER posted @ Oct 15, 2011 08:13:23 PM in string maths() with tags 最佳止步 optimal stopping , 2279 readers

 

退而求其次:

如果你把眼光稍为放低一点， 能够选中第一名或第二名就好的话，那么你应该采取怎样的手段?

很自然地，一开始你仍应按以前的办法进行，自第 r 位起，等候第一个临时第一名。但是如果等了一段时间，还未出现，这是会有疑虑: 是不是第一名已成漏网之鱼? (已经在最前面r -1位中出现了)。所以你应该自第s位( s > r )起，首次碰到临时第一名或临时第二名时，你都一把抓住，因为临时第二名也可能会是实际第二名。我们也可以证明，最好的手段，就在这一类里，不过我也不证明了。我再简写如下：

\[M_{r,s}\] :自第 r 位起，选择临时第一。自第 s 位起,(如果以前尚未选定)，一遇到临时的第一或第二，就马上选择。

我们现在来算\[M_{r,s}\]的成功机率。符号及其意义如上一篇中所述。

\setcounter{equation}{5}\begin{eqnarray} P(M_{r,s})&=&\sum^n_{k=r}P(S_{k},x_k=1\,or\, 2)\nonumber\\ {}&=&\sum^n_{k=r}\Big[P(S_k,x_k=1)+P(S_k,x_k=2)\Big] \end{eqnarray}

  1)     \[r\leq k<s\]: \[$P(S_k\vert x_k=1)=\frac{(r-1)}{(k-1)}, P(S_k,x_k=1)=\frac{(r-1)}{n(k-1 )}$\]。(理由见上篇日志)

  2)     \[r\leq k<s\]: \[P(S_k,x_k=2)=P(S_k,x_k=2\]且第一名出现在第 k 位之后)。

(因为如果第k位是第二名，而第一名出现在先，则按照上述办法，第k位根本不会被选到)。

现在:

  •    \[P(x_k = 2 \]且第一名出现在后\[)=\frac{(n-k)(n-2)}{n!}=\frac{(n-k)}{n(n-1)}\]

理解上式其实也并不难：

首先，我们有 n 个位置，其中一个要给第一名，还有一个要给第二名，所以就有P_{2}^{1}C_{2}^{n}个情况，

而给第二名的是第 k 个位置,给第一名的是后 n-k 个位置中的一个。所以就有：\[\frac{n-k}{P_{2}^{1}C_{n}^{2}}=\frac{(n-k)}{n(n-1)}\]

  •     \[P(S_k|x_k = 2\]且第一名出现在后\[)=\frac{(r-1)}{(k-1)}\]
\begin{displaymath}\begin{split}P(S_k,x_k = 2)=&\frac{r-1}{k-1} \cdot \frac{(n-1)-(k-1)}{n(n-1)} \\ =&\frac{r-1}{n(k-1)} - \frac{r-1}{n(n-1)}\end{split}\end{displaymath}
 
  3)     \[s\leq k\]: \[P(S_k|x_k = 1) = \frac{r-1}{k-1} \cdot \frac{s-2}{k-2}\]，因为这时第 k 位要被选中，一定是如下情况:
 
事件 a: 前k -1位中最好的要在前r -1位里（否则会在\[[r,k-1]\]之间做出选择），而且
事件 b :前k -1位中次好的要在前s -1位中（否则会在\[[s,k-1]\]之间做出选择）。
注：两件事件的条件都是在\[x_k=1\]的情况下。
 
注意：\[ \frac{r-1}{k-1} \cdot \frac{s-2}{k-2}\] 其实就是\[P(a,b)\]。
 
所以：
\begin{displaymath} P(S_k,x_k=1)=\frac{1}{n}\cdot\frac{r-1}{k-1}\cdot\frac{s-2}{k-2} \end{displaymath}
 
  4)     \[s\leq k\]: 与 3) 中的理由一样，我们得到：

\begin{displaymath} P(S_k,x_k=2)=\frac{1}{n}\cdot\frac{r-1}{k-1}\cdot\frac{s-2}{k-2} \end{displaymath}

把所有上面结果放进(6)式里，我们就有：

\setcounter{equation}{6}\begin{eqnarray}P(M_{r,s})&=&\sum_{k=r}^{n} P(S_k,x_k =1\,or\,2) = \sum_{k=r}^{s-1}P(S_k,x_k =1\,or\,2) + \sum_{k=s}^{n}P(S_k,x_k =1\,or\,2)\nonumber\\&=&\frac{2(r-1)}{n}\sum_{k=r}^{s-1}\frac{1}{k-1}-\frac{(s-r)(r-1)}{n(n-1)}+\frac{2(r-1)(s-2)}{n}\sum_{k=s}^{n}(\frac{1}{k-2}-\frac{1}{k-1})\nonumber\\&=&\frac{2(r-1)}{n}\sum_{k=r}^{s-1}\frac{1}{k-1}-\frac{(s-r)(r-1)}{n(n-1)}+\frac{2(r-1)}{n}-\frac{2(r-1)(s-2)}{n(n-1)} \end{eqnarray}

 

我们再讨论，当n很大时，最好的 r 和 s（= r * , s *）以及 \[P(M_{r^*,s^*})\]该是多少。因为(7)式较复杂，最快的方法，就是将这个非连续变量的式子，用连续变量的式子来取代，（discrete $\rightarrow$continous，这是一般应用数学中的惯技），然后再用微分的方法。这里我只得向一般中学同学们作个道歉，这也是不得已的事。如前一篇日志里一样，用微分的方法，可以很快得到，至少可以省去了整页的篇幅。

我们令：

\begin{displaymath} x=\frac{r}{n},\qquad y=\frac{s}{n} \end{displaymath}

根据前面的经验，当n很大时，r *和s *也应该很大。因此如果 ( r , s )在( r * , s * )附近的话，r和s也都很大，所以：

\begin{displaymath} \sum^{s-1}_{k=r}\,\frac{1}{k-1}\approx\ln{\frac{s}{r}}=\ln{\frac{y}{x}} \end{displaymath}

你若稍为观察，可见(7)式右方与下式相近：

\setcounter{equation}{7}\begin{eqnarray} f(x,y)=2x\ln{\frac{y}{x}}-x(y-x)+2x-2xy \end{eqnarray}

其实（7）式的化简形式是别有用意的，有意的让 n 的一次式出现在分母，而让于 r, s 有关的一次式出现在分子上，上下次数统一，这样一来，很容易进行取近似的操作，而且很合理。

现在我就当x , y为连续变数，求f ( x , y )的最大点( x * , y * )。根据微分的方法，( x *, y * )应是下面两式的解:

\begin{displaymath} \frac{\partial f}{\partial x}=0,\quad \frac{\partial f}{\partial y}=0 \end{displaymath}

计算这两个偏微分，分别得到：

\begin{displaymath} -2x+3y=2\ln{\frac{y}{x}},\quad \frac{2x}{y}=3x \end{displaymath}

由此我们得到 $y^*=\frac{2}{3}$ 以及：

\setcounter{equation}{8}\begin{eqnarray} -\ln x=1+\ln (\frac{3}{2})-x \approx 1.405 -x \end{eqnarray}

这是个“超越方程”，x *是(9)式在(0,1) 间的解。x *的近似值并不难求，见图（9）。你如有个小型计算机,不需要花多少时间,

此处，我们可以运用牛顿法来解超越方程：

step1: 先构造 \[f(x)=1+\ln(3/2)-x+\ln(x)\]

step2: 利用迭代 \begin{displaymath}\left\{\begin{array}{l}x_{k+1}=x_{k}-\frac{f(x_k)}{f^\prime(x_k)}\\x_0=x^\prime_0 \end{array}\right.\end{displaymath} ,即\begin{displaymath}\left\{\begin{array}{l}x_{k+1}=x_{k}-\frac{1+\ln(3/2)-x_k+ln(x_k)}{-1+1/x_k}\\x_0=0.5 \end{array}\right.\end{displaymath}

其实牛顿法的运用和起始值有很密切的关系，这里我们已知在 \[[ 0, 1]\]之间有一个解，而显然不能取，0 或 1，所以取\[( 0, 1)\]即可。

理论上，\[x_0\]如果与解很接近的话，迭代会很快趋向于解。

在很多计算机上，都有 ans（answer） 键，在此基础上，先输入0.5，在按 “=”键，此时，就把0.5存入了ans，之后在输入上式中的时候，\[x_k\]用ans代替，之后不断按 “=”4到5次之后便会趋向于正解。

 

 

 

就可以找出 $x^*\approx 0.347$。再从(8)和(9),你就得到 

\begin{displaymath} f(x^*,y^*)=x^*(2-x^*)\approx 0.574 \end{displaymath}

所以我们新策略的答案是 

\begin{displaymath} r^*\approx 0.347n,s^*\approx \frac{2}{3} n ,P(M_{r^*,s^*})\approx 0.574 \end{displaymath}

补充说明：也许有对:
\setcounter{equation}{7}\begin{eqnarray} f(x,y)=2x\ln{\frac{y}{x}}-x(y-x)+2x-2xy \end{eqnarray}
有疑问，说为什么求出的极值一定就是最大值呢？这一点在很多高数书都有一张篇幅是说多元函数求极值的，具体如下，证明从略：

设函数\[z=f(x,y)\]在点\[(x_0,y_0)\]的某邻域内连续,且有一阶及二阶连续的偏导数,又 \[f_x(x_0,y_0)=f_y(x_0,y_0)=0\] ,记

\[A=f_{xx}(x_0,y_0)\] , \[B=f_{xy}(x_0,y_0)\] , \[C=f_{yy}(x_0,y_0)\]

则函数在\[(x_0,y_0)\]处是否取得极值的条件如下

(1)、\[AC-B^2 > 0\]时具有极值,且当时有极大值,当时有极小值；

(2)、\[AC-B^2 < 0\]时没有极值；

(3)、\[AC-B^2 = 0\]时可能有极值,也可能没有极值,需另作判定。

对于（8）式极值就是最大值的证明读者可自行证明，纯粹是计算，笔者在此，允许我偷个懒。

不管你算了还是没有算，反正我是算过了。他是正确的，真是个奇迹！ （- -）Y。
 
至此，这个新策略让你有超过过一半以上的机会，可以选中第一名或第二名！这和随意乱选一个的成功机会 \[\frac{2}{n}\],真是天渊之别，你还坚持数学无用吗？
这类问题多有实用的背景。例如在作统计调查工作时，常会遭遇到需要你作抉择的时候：多作观察的话，你要付出代价，但少作观察的话，你对最所面临的问题恐怕又了解得不够，什么时候停止观察最为有利?这与上面相亲问题当然不尽相同，但也类似。
 
下面，双手献上这一方面的参考书，虽然只是一般性的介绍，与君共享：
 
 
1.Breiman,〈Stopping rule problems〉,in 《Applied Combinatorial Mathematics》, John Wiley,1964.

止步问题有时也很复杂。通常对某个问题，你会有好像很好的止步法， 但要证明它是最好的办法，有时也很困难。上述问题(只要第一名的)， 曾在《Scientific American》中被提出作为问题征答。以后同样的问题又出现在《Amer. Math. Monthly》的问题栏内。见

2.Moser and Pounder,〈solution in "Mathematical Games"〉,《Scientific American》, March 1960.
 
3.Bosch,〈solution to Problem 5086〉,Amer.Math.Monthly,71(1964),329-330.

上面两答案均未证明M r *的确最好。要想证明M r * , M r * , s * 是最好，可以用“Dynamic programming”的想法，见

4.Lindley, 〈Dynamic programming and decision theory〉,《J.Royal Stat.Soc.》 C,10(1961),39-51.
 
5.Gilbert and Mosteller,〈Recognizing the maximum of a sequence〉, 《Amer.Stat.Assoc.》61(1966),35-73.

此类问题也有用「马尔科夫链」的想法处理的，见

6.Rozanov, 《Introduction to Probability Theory》, Prentice-Hall, 1969 (见p.28-29,86-87,139-142).
 
7.Dynkin and Yushkevich,《Markov Processes, Theorems and Problems》, Plenum Press, 1969.
 
8.Chow,Robbins and Siegmund,《Great Expectations,The Theory of Optimal Stopping》，Houghton Mifflin,1972.

 

Small_feed Comments (3)
1
[Reply]
Fadden said:
Apr 02, 2019 07:41:59 AM

Optimal timing of the question in the term of the logically depends while catching the new part from the all formulas. We have to stop this formula about to buy assignment australia that will not be competing with the all long subject to objective terms.

2
[Reply]
AAA said:
May 14, 2022 09:13:56 PM

What would many of us do devoid of the brilliant suggestions you share on this web site? Who else has got the perseverance to cope with important topics in the interest of ordinary subscribers like me? My spouse and i and my guys are really lucky to have your website among the ones we typically visit. We hope you know how a great deal we take pleasure in your efforts! Much luck coming from us all. North American Bancard

 

==============================

 

Hi there, I discovered your website by way of Google while searching for a comparable topic, your website came up, it looks good. I’ve bookmarked it in my google bookmarks. Selling Credit Card Processing

3
[Reply]
AAA said:
May 16, 2022 10:49:36 PM

You have a gift for words I will give you that. If only I had the same gift 日本精品


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter