选中最大数的策略

lulijie

策略（N) 获取最大数的概率 P(N) =(N-1)/m   *    ∑ 1/i    （ ∑中的 i 从N-1到 m-1）
那么  P(N+1) =N/m   *    ∑ 1/i    （ ∑中的 i 从N到 m-1）
所以   △P= P(N+1)- P(N) =1/m   *   [ ∑ 1/i   -1]      （ ∑中的 i 从N到 m-1）       概率增值公式
N=1时， ∑ 1/i  大于1，   N=m-1时  ∑ 1/i  =1/（m-1），小于1
因为  ∑ 1/i   是个递减数列  从大于1 递减至   1/（m-1）      （  i从1至m-1）
所以  △P也是递减数列，从大于0  递减至  小于0，
所以概率P(N)  先是递增数列，后变为递减数列，
所以P(N) 有个最大值，当△P第一次变为负值时的N就是所求的最大值的自变量。
那么N等于多少， △P 第一次小于0呢？  
------------------------------------------------------------------------------------
第一：设    C(k)=∑ 1/i -ln(k+1)     （ ∑中的 i 从1到k ）           C(k)是个递增数列
                         K趋向无穷大时， C(k)的极限  就是欧拉常数C=0.57721566490153286060651209
那么  C(N-1)=∑ 1/i -ln(N)       （ ∑中的 i 从1到N-1）
        C(m-1)=∑ 1/i -ln(m)       （ ∑中的 i 从1到m-1）
   因为    m* △P=(∑ 1/i  -1)         （ ∑中的 i 从N到m-1）
       所以 m* △P=C(m-1)+ln(m) -C(N-1)-ln(N)-1  =ln(m/N)-1   +    C(m-1)-C(N-1)
     m* △P=ln(m/Ne)  +    C(m-1)-C(N-1)

为C(k)是个递增数列，C(m-1)-C(N-1)大于0，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
     那么  m/Ne>=M/N
当N取M值时，m/Ne>= M/N=1
     m* △P=ln(m/ne)  +    C(m-1)-C(N-1) >=ln1 +    C(m-1)-C(N-1) >0
   所以N<=M 时，△P都大于0，所以P(N)取最大值时，N 必定>=M+1 。
-----------------------------------------------------------------------------
第二：同样：
设    C'(k)=∑ 1/i -ln(k)     （ ∑中的 i 从1到k ）              C'(k)是个递减数列
                         K趋向无穷大时， C’(k)的极限  就是欧拉常数C=0.57721566490153286060651209
那么  C'(N-1)=∑ 1/i -ln(N-1)       （ ∑中的 i 从1到N-1）
        C’(m-1)=∑ 1/i -ln(m-1)       （ ∑中的 i 从1到m-1）
   因为    m* △P=(∑ 1/i  -1)         （ ∑中的 i 从N到m-1）
       所以 m* △P=C’(m-1)+ln(m-1) -C'(N-1)-ln(N-1)-1  =ln[(m-1)/(N-1)]-1   +    C'(m-1)-C'(N-1)
     m* △P=ln[(m-1/(N-1)e] +    C'(m-1)-C'(N)

因为C‘(k)是个递减数列，C'(m-1)-C'(N)小于0，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
     (m-1)/(N-1)e<(m-1)/m   *   (M+1)/(N-1)
当N取M+2值时， (m-1)/(N-1)e<(m-1)/m   *   (M+1)/(N-1)=(m-1)/m  <1
                m* △P=ln[(m-1)/ (N-1)e]  +    C'(m-1)-C'(N) <ln1 +    C'(m-1)-C'(N)<0
   所以N>=M+2 时，△P都小于0，所以P(N)取最大值时，N 必定<=M+2 。
-------------------------------------------------------------
综合第一和第二，得出，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
那么，P(N)取最大值时，M+1<=N<=M+2
所以结论1得证。

[ 本帖最后由 lulijie 于 2009-3-2 01:43 编辑 ]

lulijie

△=0.858时，计算公式可以在m<1000时，正确率达到100%，但是m再增大时，计算公式的正确率却远远不如其他修正值△。
比如m<30000时，△=0.858时，计算公式     m=2818，5539，8260，10981，13702，16423，19144，21865，23322，26043，28764，出现偏差，
所以才认为修正值0.858不如8591好。

[ 本帖最后由 lulijie 于 2009-3-1 23:44 编辑 ]

lulijie

结论1证明了，结论2就好证明了。
              P(M1) =(M1-1)/m   *    ∑ 1/i    （ ∑中的 i 从M1-1到 m-1）
      因为   ∑ 1/i   =ln(m/(M1-1))  +    C(m-1)-C(M1-1)  
   因为m趋向于无穷大，所以   m/e  趋向于无穷大，所以M1-1也趋向于无穷大
    所以C(m-1)-C(M1-1)  趋向于C-C=0                 C欧拉常数。
    m/(M1-1)趋向于e，ln(m/(M1-1))  趋向于1，
    P(M1)的极限就=1/e  *1=1/e。

lulijie

题目：有m个实数，两两不等，每次只显示一个数给你看，你可以选择获取它或放过它看下一个数。你的目标是得到最大的数。
      那么如何安排策略，才能使得获取最大数的概率最高？
策略（n)  ：放过前面的n个数，从第N=n+1个数开始，若与前面的所有数相比是最大的，就选择该数，否则放过，看下一个数，一直到所看的数与前面的所有数相比是最大为止，选择该数。若看到了最后一个数，就只能选择最后一个。

假设：  q是  不比 m/e  大的最大整数，即q=int(m/e) 或q<=m/e<q+1       int是取整函数， e为自然对数，=2.718281828……
那么：
     结论1：策略（n) 获取最大数的概率
              P(n) =n/m   *    ∑ 1/i    （ ∑中的 i 从n到 m-1）       n>0   
              P(n) =1/m                                               n=0
     结论2：使得概率P最大的n值必等于q或q+1。      
     结论3：m趋向于无穷大时，P(q) 或P(q+1)的极限等于1/e 。
           也就是说m很大时，最优策略获取最大数的概率等于1/e。
证明：结论1：最大数出现在被看的轮次是随机的，所以出现在任何轮次的概率都是1/m。
           最大数若出现在前n轮次，由于策略(n)的缘故，已被放弃，所以不可能被选中了。最大数出现在n+1次以后，比如第i轮次（i>n），根据策略，被选中的条件是i-1轮次之前出现的所有i-1个数中最大的数出现在第n轮次之前（包括第n轮次），因为若出现在n轮次之后，根据策略，它必备选中，从而不可能获得最大数。所以最大数出现第i轮次且被选中的概率=1/m  *  n/(i-1)=n/m * 1/(i-1),所以策略（n) 获取最大数的概率
          P(n)=n/m * ∑1/(i-1),  (∑中的i=n+1 to m)   
     即   P(n)=n/m * ∑ 1/i ，   （ ∑中的i从n到 m-1）
    所以结论1得证。
     结论2 ：思路：  
               1.首先证明  数列P(n) 是个先递增后递减的数列。头尾的数列值相等，都等于1/m，所以中间有最大值。
                          前后两个数列的差值△P= P(n+1)- P(n) =1/m   *   [ ∑ 1/i   -1]      （ ∑中的 i 从n+1 到 m-1）
                                                  即  m*△P= [ ∑ 1/i   -1]      （ ∑中的 i 从n+1 到 m-1）
                          从上面式子可看出△P是个递减数列，从大于0，逐渐减至小于0. 当第一次变为负值时的n就是所求的最大值的自变量。
               2.构造两个新的数列：C(k)=∑ 1/i -ln(k+1)     （ ∑中的 i 从1到k ）           C(k)是个递增数列
                                                 C'(k)=∑ 1/i -ln(k)         （ ∑中的 i 从1到k ）           C'(k)是个递减数列
                      这两个数列的极限值都相等，都等于欧拉常数C=0.57721566490153286060651209
               3.将概率△P用C(k)或C'(k)来表示：m* △P=ln(m/(n+1)) + C(m-1)-C(n) -1                式子1
                                                                    m* △P=ln[(m-1)/n] +  C'(m-1)-C'(n+1) -1           式子2
                       当n=q-1时，用式子1判断△P>0,所以P(n)取最大值时，n 必定>=q
                       当n=q+1时，用式子2判断△P<0,所以P(n)取最大值时，n 必定<=q+1
                  所以就得出P(n)取最大值，q<=n<=q+1,结论2得证。
    结论3：P(q) =q/m   *    ∑ 1/i    （ ∑中的 i 从q到 m-1）   
                因为 ∑ 1/i   =ln(m/q)  +    C(m-1)-C(q-1)  
               所以 P(q) =q/m * [ln(m/q)+ C(m-1)-C(q-1)]
                因为m趋向无穷大，所以q=int(m/e)也趋向无穷大，m/q趋向e, q/m 趋向1/e, C(m-1)-C(q-1)]趋向C-C=0，
               所以 P(q) 趋向1/e * (lne+0)=1/e.
               所以结论3得证。   
-------------------------------------------------------------------
下面证明结论2：
            C(n)=∑ 1/i -ln(n+1)       （ ∑中的 i 从1到n）                 式子a
            C(m-1)=∑ 1/i -ln(m)       （ ∑中的 i 从1到m-1）             式子b
             因为m*△P=[ ∑ 1/i   -1]     （ ∑中的 i 从n+1 到 m-1）
             所以  式子b-式子a   得到   ∑ 1/i   =ln m/(n+1) +  C(m-1)- C(n)      （ ∑中的 i 从n+1 到 m-1）
             所以  m*△P=ln m/(n+1) +  C(m-1)- C(n)-1
             n取q-1值时，m*△P=ln m/q +  C(m-1)- C(q)-1
             因为q<=m/e<q+1,所以m/q>=e,  因为C(k)是个递增数列，所以C(m-1)- C(q)>0.
             所以m*△P >lne+0-1>0.  
             因此 n取q-1值时，△P>0
             -----------------------------
             C'(n)=∑ 1/i -ln(n)       （ ∑中的 i 从1到n）
             C’(m-1)=∑ 1/i -ln(m-1)       （ ∑中的 i 从1到m-1）
             因为 m* △P=(∑ 1/i  -1)         （ ∑中的 i 从n+1到m-1）
             所以 m* △P=C’(m-1)+ln(m-1) -C'(n)-ln(n)-1  =ln[(m-1)/n] + C'(m-1)-C'(n)-1
             n取q+1值时，m*△P=ln (m-1)/(q+1) +  C'(m-1)- C'(q+1)-1
             因为q<=m/e<q+1,所以(m-1)/(q+1)< m/(q+1)<e,  因为C'(k)是个递减数列，所以C'(m-1)- C'(q+1)<0.
             所以m*△P <lne+0-1<0,
             因此n取q+1值时，△P<0。
         所以结论2得证。

[ 本帖最后由 lulijie 于 2009-3-2 21:01 编辑 ]

lulijie

模拟计算公式
N=int[(m+△)/e] +1        int为取整函数。 △为修正值，e为自然对数。e=2.71828182845905
因为放过的个数n=N-1，
   所以概率取最大值时，n=int( m/e+△')       模拟计算公式    (△'=△/e)
用  △'来修正n是很有道理的。
   因为 int( m/e)=q   ,n不是等于q，就是等于q+1
    当 0<△'<1时  q=  int( m/e)<= int( m/e+△')   <= int( m/e)+1=q+1
     所以  int( m/e+△')  不是等于q，就是等于q+1。只要△'选的适当，完全可以用来代替n值。正确率可以很高。
    若△' 等于0时，nt( m/e+△') 只能等于q， 不可能等于q+1，所以等于q+1的这部分n就不能正确求出，所以用△' 等于0，错误率很高。
   △' 等于1时，nt( m/e+△') 只能等于q+1， 不可能等于q，所以等于q的这部分n就不能正确求出，所以用△' 等于1，错误率也很高。
  所以，修正值△' 应该在0和1之间。

ggglgq

　　
  
  
    嗯，楼主的题目很好，楼主 和 金眼睛 对问题的分析研究很透彻！
  
    自然对数 e 的科学应用很广呀！ 这使我想起 N 为底的对数的概率应用：
  
    在 N 进制中，首位数为 m 的自然数的概率 （ N 为大于 1 的自然数）
  
    http://bbs.mf8-china.com/viewthread.php?tid=2153　　
　　　　
　　可惜无暇去证明，不知各位高手能否抽空去证明一下呢？谢谢了！