Author Topic: 最舒适的车 from WXC and generalization  (Read 15197 times)

fzy

  • Hero Member
  • *****
  • Posts: 520
最舒适的车 from WXC and generalization
« on: 五月 21, 2005, 10:17:35 am »
有三辆公共汽车可以把你带到你要去的地方。如果两辆汽车摆在你的面前,你可以知道哪辆更舒适。可是现在它们依次而来,你不知道它们的次序,你有策略提高你乘上最舒适的车的机会吗?

这个题目不难, 道理却有用。没结婚的朋友,要仔细考虑这个题目哟。

Generally, given N consecutive selections, but you have only one chance to make a decision, how to maximize your expected return? Assuming the values are 1 to N, determined by the final ranking, but not known at decision time.

My simulation says that the best strategy is to pass the first K = sqrt(N) - 1 chances, and then choose the one that is better than the best of the first K. The expected value is approximately N - K. For example, for X = 100, pass the first 9. The expected value is about 91. But I cannot prove the result.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 最舒适的车 from WXC and generalization
« Reply #1 on: 五月 21, 2005, 05:24:25 pm »
There's  an assumption need to be made when you do simulation, i.e. what do you do at the last car. If it fails the criteria, do you take it or become empty handed. The natural choice is to take the last car no matter what. With this assumption, it can be proved that sqrt(N)-1 is the best K,  I need to dig up my email about 15 year's ago. If I am lucky, I will post it in a week.

supertramp

  • Newbie
  • *
  • Posts: 18
Re: 最舒适的车 from WXC and generalization
« Reply #2 on: 五月 23, 2005, 11:18:55 am »
My simulation says that the best strategy is to pass the first K = sqrt(N) - 1 chances, and then choose the one that is better than the best of the first K. The expected value is approximately N - K. For example, for X = 100, pass the first 9. The expected value is about 91. But I cannot prove the result.

I don't see how this can be true.  If you have N = 100 and you pass the first 9, and if the next 89 choices are all worse than the best of the first 9, you will pass them.  Now the 99th choice.  If it is still worse than the best of the first 9, but better than everyone else you have seen, why would you still pass this choice when you are guaranteed to be among top 3?  The only alternative left is the last one, which could be anywhere between 1 and 100?

This problem looks like a fairly standard American option.  This common lisp code shows seem to indicate that for N = 100, the expected value is 97.39672.

(defun last-expected-score (N) (/ (1+ N) 2))

(defun inflated-score (x k N) (/ (* x (1+ N)) (1+ k)))

(defun expected-score-1 (k N)
    (if (= k N) (last-expected-score N)
        (let ((next-round (expected-score (1+ k) N)))
            (/ (loop for i from 1 to k
                sum (if (> (inflated-score i k N) next-round)
                    (inflated-score i k N)
                    next-round)) k))))

(defun expected-score (k N) (float (expected-score-1 k N)))

This code always gives you the strategy for when to exercise. Did I miss anything?



万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 最舒适的车 from WXC and generalization
« Reply #3 on: 五月 23, 2005, 11:31:50 am »
Quote
I don't see how this can be true.  If you have N = 100 and you pass the first 9, and if the next 89 choices are all worse than the best of the first 9, you will pass them.  Now the 99th choice.  If it is still worse than the best of the first 9, but better than everyone else you have seen, why would you still pass this choice when you are guaranteed to be among top 3?  The only alternative left is the last one, which could be anywhere between 1 and 100?

Very good observation. Indeed, with your adaptive algorithm, you can do much better than the simple one k decides all approach. I don't know much about lisp, but I will try to simulate your approach. To be fair to the original problem, it was asking for the one k decides all approach. Next time when someone give this problem (I've seen this problem many many times), I will ask them to be more specific.

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 最舒适的车 from WXC and generalization
« Reply #4 on: 五月 24, 2005, 09:12:42 am »

This problem looks like a fairly standard American option.  This common lisp code shows seem to indicate that for N = 100, the expected value is 97.39672.

(defun last-expected-score (N) (/ (1+ N) 2))

(defun inflated-score (x k N) (/ (* x (1+ N)) (1+ k)))

(defun expected-score-1 (k N)
   (if (= k N) (last-expected-score N)
      (let ((next-round (expected-score (1+ k) N)))
         (/ (loop for i from 1 to k
            sum (if (> (inflated-score i k N) next-round)
               (inflated-score i k N)
               next-round)) k))))

(defun expected-score (k N) (float (expected-score-1 k N)))

This code always gives you the strategy for when to exercise. Did I miss anything?


Can you explain the code? I'm afraid most people are not familiar with lisp. Also I don't know if you could spend some time to explain the relationship between this problem and Stock Options. Thanks.
« Last Edit: 五月 29, 2005, 10:44:44 am by fzy »

MW

  • Guest
Re: 最舒适的车 from WXC and generalization
« Reply #5 on: 五月 25, 2005, 05:09:01 pm »
This is a well-known problem.  I knew that the anwser is ~ N/e for the number of cars to skip if N is very big.  For N = 100, K = 37.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 最舒适的车 from WXC and generalization
« Reply #6 on: 五月 29, 2012, 10:35:29 am »
这几天在微博回答一个人的问题,又把这个问题做了一遍,结果贴在下面

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

微博别人的原题:某相亲节目,男嘉宾从24名女嘉宾中依次挑选,规定每次限见一人,一旦放过不可反悔,一旦选定则不再继续。男嘉宾该采取何种策略,才最有可能选到最漂亮的女嘉宾呢?

由于不知道女嘉宾的漂亮程度,必须要先看几个建立参照系。一个比较实用的策略是先放弃前r位, 然后从第r+1个人开始,选择第一个比前面已登场的都更漂亮的女嘉宾。问题是怎样选这个r?显然 ,r 太大会错过最好的,太小会在最好的没有到之前就选取。

数学上可以证明,对任意N个女嘉宾,最好的r是接近N/e 的整数。具体过程可见
http://www.mysanco.com/tiku/index.php?class=index&action=special_subject&tid=15018&rid=23

但是,即使取最好的r, 这个策略的成功率也不高,大约三分之一左右,也就是说有差不多三分之二的可能性要失败。很不现实。这个题的一个变种是尽可能找好的。n个人,优秀程度是1到n,与原题同样的策略,唯一需要变的是剩最后一个人时必选(不管是否符合条件),不至于空手而归。在这个要求下选什么样的r才能最大化所选人的优秀程度的期望值。

要算最大期望值,先要找出给定r 后,期望值的公式。下面我们就来推导这个公式。

假设前r 个里最大值是k ,显然k  >= r。前r 个里最大值是k的概率是

 

选到的人的值从k+1 到n均可能,平均值是(n+k+1)/2。当 k取值从r 到 n-1 时,其期望值的和是

 

这个公式可以通过下面这个组合公式化简。

 

顺便说一句,上面这个公式硬证比较麻烦,但如果用杨辉三角形来证明则很显然,只需要两句话,

注意到我们上面的期望值的和没有算k 等于n 时的期望值,因为k 等于n 时r个后面没有人符合条件,只好选最后一个。k 等于n 的概率是 r/n, 所选的人是1到n-1中的任意一个,平均值是n/2, 所以k 等于n时对期望值的贡献是r/n*(n/2) = r/2.

把这个r/2 加到上面的总和里,并化简公式(习题),我们得到给定r 后选择的人的期望值是

 

对上面的公式求极值得到 r = √n - 1

这个结果出人意料的优美。关键是k 等于n时被迫选的最后一人居然对结果的简化有帮助,没有它,结果不会这么漂亮。而且,这个算法的期望值很高。r 取 √n - 1时期望值可达91.4%. 也就是说100人里可以找到前十名。有人把算法改进了以后(比如在第99名时碰见仅次于最好的就一定要选),期望值大于97%。就是说100人里可以找到前三名。这个改进算法比较麻烦,我就不在这里写了。

« Last Edit: 五月 29, 2012, 04:22:38 pm by 万精油 »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 最舒适的车 from WXC and generalization
« Reply #7 on: 六月 07, 2012, 04:28:34 pm »
在微博贴了那个Lisp代码以后一直有人说看不懂。以前学计算机专业的人Lisp是必修课,
现在大约不是了。其实我也不懂Lisp。但想清楚道理以后,应该能猜出它的意思来。做
好事我把它翻译成MATLAB,顺便贴到这里。好像FZY说要让原帖者解释这个Lisp,希
望我这个MATLAB码能把FZY吸引过来。:)

MATLAB码我列了三种形式。第一种是忠实原意,好懂。第二种利用MATLAB向量语言
特点,简洁。第三种速度快。最快那种在我的机器上算到一亿也只需3秒钟。结果仍大
于N-3。就是说期望值在前三名以内。一亿人的前三名,选妃子也不过如此吧。:)

忠实原意翻译成MATLAB 码

Quote
p = (n+1)/2;
for i = n-1:-1:k
   q = (1:i)*(n+1)/(1+i);
   q(q<p) = p;
   p = mean(q);
end

理解了思想后化简化简成最简洁的MATLAB码

Quote
p = (n+1)/2;
for i = n-1:-1:k
    p = mean(max([p*ones(1,i); (n+1)(1:i)/(1+i)]));
end

上面那两个码都需要用到向量,n 太大时太慢。最快的是下面的MATLAB码

Quote
p = 1/2;
for i = n:-1:k+1
   r = floor(p*i);
   p = 1/2+r*(p-(r+1)/(2*i))/(i-1);
end
p = p*(n+1);


fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 最舒适的车 from WXC and generalization
« Reply #8 on: 六月 09, 2012, 10:09:29 am »
好像FZY说要让原帖者解释这个Lisp,希望我这个MATLAB码能把FZY吸引过来。:)


我一直在呀,就是没时间写字。

Lisp和Matlab都不懂。:(

不知道需要看的人数的期望值是多少?如果要看一亿人,只怕是林副主席也看不过来。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 最舒适的车 from WXC and generalization
« Reply #9 on: 六月 09, 2012, 11:22:20 am »
》 我一直在呀,就是没时间写字。

我自己都写得越来越少。我觉得是互动的。写得少,看的人就少,就写得更少。

现在的主要问题是不能开放评论。一开放评论每天有一大堆机器产生的Spam。不开放就必须注册。这年头没有足够吸引力很难有人注册。

》 Lisp和Matlab都不懂。:(

主要思想就是尽量避免被逼到最后一个选剩下的。

最后一个的期望值是(n+1)/2, 所以,倒数第二个如果比(n+1)/2好,就选它,否则放弃。这样一来,
在倒数第二个时,前(n+1)/2个放弃,后面都选。前(n+1)/2个的期望值用(n+1)/2代替。这样,我
们可以算出倒数第二个所能得到的期望值。倒数第三个如果大于倒数的二的期望值就选,否则放弃。
如此类推,一直算到K,就是这个算法所能得到的期望值。

这个算法引出一个问题,有空再谈。

》不知道需要看的人数的期望值是多少?如果要看一亿人,只怕是林副主席也看不过来。

林副主席可以搞多出同时选(当初就是这么干的)。:)

packman

  • Full Member
  • ***
  • Posts: 226
Re: 最舒适的车 from WXC and generalization
« Reply #10 on: 六月 09, 2012, 06:31:08 pm »
Give Prof. Wan some encouragement: I visit here at least a few times a day, just to see if there are any new posts. 还是少而精更好。 :-)
 加入这里都8年了。
« Last Edit: 六月 09, 2012, 06:33:04 pm by packman »
简单==完美