Originally posted by Ernest Friedman-Hill:
[QB]
You always read the whole file, and you perform this procedure for every fortune. The first fortune thus has up to N-1 chances to be replaced -- if it's not replaced by the second one, it may be replaced by the third one, or fourth one, and so on. And once the first one is replaced, the replacement can itself be replaced, as can that replacement. So the probability of the first fortune being selected is 1/2 - 1/3 - 1/4 - 1/5 - 1/6 ... - 1/N, which is equal to, as it turns out, 1/N.QB]
I get it. The idea is that for the first fortune to survive, it would have to be outside of the probabilities that we calculate. Consider the case in which we have 5 fortunes.
1 always gets placed in F.
2 will be placed in F 1/2 of the time. Therefore, 1 survives 1/2 of the time.
3 will be placed in F 1/3 of the time. Therefore, if 1 survived the last replacement, it would survive this replacement 2/3 of the time.
4 will be placed in F 1/4 of the time. Therefore, if 1 survived the previous replacements, it would survive this replacement 3/4 of the time.
5 will be placed in F 1/5 of the time, Therefore, if 1 survived the previous replacements, it would survive 4/5 of the time.
So the probability of 1 surviving is 1/2 * 2/3 * 3/4 * 4/5 = 1/5
Very nice programming. Kudos to the original fortune programmers, and thanks to those who responded so quickly to my question. I apologize for the late reply, but I have really sporadic Internet access.
I probably will go towards the index methodology, to get the constant space/time factor, but this was a great insight. Thank you, Mr. F-H!