### 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.

#### 万精油

• 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?

#### 万精油

• 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.&nbsp; 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.&nbsp; Now the 99th choice.&nbsp; 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?&nbsp; 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.&nbsp; 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)
&nbsp; &nbsp;(if (= k N) (last-expected-score N)
&nbsp; &nbsp; &nbsp; (let ((next-round (expected-score (1+ k) N)))
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(/ (loop for i from 1 to k
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum (if (> (inflated-score i k N) next-round)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(inflated-score i k N)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;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.

#### 万精油

• Hero Member
• Posts: 1831
##### Re: 最舒适的车 from WXC and generalization
« Reply #6 on: 五月 29, 2012, 10:35:29 am »

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

http://www.mysanco.com/tiku/index.php?class=index&action=special_subject&tid=15018&rid=23

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

#### 万精油

• Hero Member
• Posts: 1831
##### Re: 最舒适的车 from WXC and generalization
« Reply #7 on: 六月 07, 2012, 04:28:34 pm »

MATLAB码我列了三种形式。第一种是忠实原意，好懂。第二种利用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

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

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 »

Lisp和Matlab都不懂。:(

#### 万精油

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

》 Lisp和Matlab都不懂。:(

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

#### 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 »