- 程序有所改变。发帖如还有问题请报告
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】问道概率题 -- baiqi
家园 【原创】问道概率题 1.有100个人，每个人的身高不同，他们随机排成一列，你从第一个走到最后一个，不能回头，只能向前走，你经过了20个，再往前走，遇到第一个比前面 20个都要高的人，你就把他选出来，如果直到100个都没有比前20个要高的，你就挑第100个，游戏结束。
问：这样做你选出的人是前5高的概率是多少？
2.你的目的是选出前5高的人，那么有没有一个最恰当的人数x,你经过x个人后，再往前走，遇到第一个比前面x个都要高的人，就选他（如果直到 100个都没有就选第100个），而选出的人是前5高的概率最高。
家园 Ignatov's Theorem Google: Ignatov's Theorem
k-record values of discrete random variables
家园 some comments Consider the tallest one amount the first 20 persons, and name him "X". let's call the shortest one the 1'st person, and the tallest one the 100'th person.
X is the x'th person. Obviously, x could be any number between 20 and 100.
Next, we will pick up an "Y", while we go through the original line. This Y is the y'th person in height. Apparently, the range of y is [x + 1, 100].
The question is:
What is the probability of y being 96 - 100?
The desired consequence is comprised by two events, event A and event B. Event A is the combination of the first 20 persons, and Event B is picking up a "good" person from the rest of the line. For example:
event A event B
------- -------
1) x = 20 96'th - 100'th got picked
2) x = 21 96'th - 100'th got picked
.
.
.
77) x = 96 97'th - 100'the got picked
.
.
The final answer should be the summation of the probability of each row. The probability of each row should be the multiple of the probabilities of event A and event B in that row.
The probability of event B in each row is comparatively easy. For instance, P(B) of row 1 should be 5 / (100 - 20).
The calculation of column A is complicated. Taking the first row as an example, the point is that the first 20 persons you encountered are indeed the first 20 persons regarding to their height. The order between these 20 persons is not important (any combination is allowed).
need some more work...
家园 随便说说 如果我们把题目改成选出最高的，似乎可以简化一些，不过也还没得到简单的结果。
首先把这100人由低到高编号为1到100。
就前二十个人来说，其中最高者可能在所有人中排第20位，21位，......，100位（event A)。比如说前二十人中最高的是30号，那么剩下的80人里面，必然有70（＝100－30）人的编号大于30，其余10（＝80－70＝30－20）人编号大于30。
这100人自由排列的方法总数为100！＝(100,20)*P(80,70)*P(10,10).
对于后面80人，我们希望编号为100的那个人排在其中大于30号的70人的第一位（event B)，加上这个要求，排法为C(80,70)*（70－1）!*10!。下面再说event A的排列方法。我们先要在1到29号里选出19个，然后加上30号，这二十个人在前二十个位置上自由排列，方法数为C(29,19)*20!。我觉得如何选这19个人和后面80人的排法无关，所以可以用乘法原理。这样，如果前二十人里最高的是第30号，共有C(29,19)*20!*C(80,70)*69!*10!种排法，它的概率就是这个数除以100！。利用上面对100！的分解，可以稍微化简一下。类似的办法可以分析其它可能的event A，然后求和。
原题是找前五名，好像要复杂不少。
- 复 随便说说
家园 谢谢你量化出这个分析 同意你的分析。如果把要求从第100号，扩大到100号和99号，会发生什么呢：
事件A不受影响。
事件B中，以30为例，方程C(80,70)*（70－1）!*10!似乎还应该加上所有99号排第一的情况。这似乎就是乘以2？
是不是？我感觉棘手的是在100号出现在前20个的时候，规定要选取队列末尾，作为结果。
家园 基本同意 如果目的是选99或100号，确实是要乘以2。
100号出现在前二十名似乎也没什么，只要要求99号出现在队尾即可，事件B的排列方式共有79！种。这只是特殊情况。
我觉得困难在于，即使只寻找100号，对所有可能求和的时候得不到简单的表达式。我也没时间用mathematica试试，不过凭我记忆中的几个简单公式，化简不了那个数列求和。这样对于第二问就有困难了。没有一个足够简单的表达式，没有办法求最大值。
当然了，可以硬算，反正最多是80项求和，现在的计算机根本不在乎。不过我们在西西河图的是个乐趣，所以还是想追求一下解析表达式。
本帖一共被 1 帖 引用 (帖内工具实现)
家园 I don't think so. The probability of event B in each row is comparatively easy. For instance, P(B) of row 1 should be 5 / (100 - 20).
===========
I don't think so.
what if I run into the height smaller than top5 but larger than all the previous 20?
家园 Yes, 1/16 is only for row 1 Yes, you are right.
Event B is actually a series of events. In the expression 5 / (100 - 20), the number "20" should be replaced in each different row.
For example, in the second row, the tallest one amount the first 20 persons is the 21'st guy in height. Therefore, (100 - 21) persons MAY be picked, but only 5 of them are desired. The probability of event B in this case/row is 5 / (100 - 21).
家园 no, you misundertood me. 我是说：在20个人之后，top5之前如果遇到比前20个都要大但是比top5都要小的，则这个也是不成的。
你再考虑一下吧，你那个想法不单不完整，也是不对的。
