Some good links:
http://mathforum.org/probstat/probstat.html
http://www.mathpages.com/home/iprobabi.htm
Here is an interesting example:
-----------------------------------------------------------------
Optimizing Your Wife -----------------------------------------------------------------
If a man can expect to meet exactly N eligible women in his life,
what strategy should he use to maximize his chances of choosing
the very best one? We typically make some idealized assumptions
when solving this type of problem, namely, that he meets the women
in random order of "goodness", that there is an unambiguous
ordering of the women, and that the man is concerned ONLY to
maximize his chances of choosing the VERY best of the N candidates,
placing no value at all on choosing the second-best versus the
worst.
Under these conditions the man's strategy can obviously never be
to select a candidate that isn't the best he has met so far. Also,
at each stage his only information is (1) how many women he has
evaluated so far, and (2) whether the current women is the best
so far. At some stage, his strategy must be to select the current
woman if she is the best so far, and clearly if he has reached this
stage the optimum strategy can't subsequently be to pass on a
"best so far" candidate. Thus, his optimum strategy for selecting
the very best of a sequence of N candidates is to pass on the first
j-1 candidates (where j is a number to be determined), and then
select the next "best so far" that he encounters. This strategy
will result in choosing the very best woman if and only if there
is one and only one "best so far" in the sequence from j to N.
Of course, the probability that the overall best woman is the kth
woman in the sequence is just 1/N. Also, the probability that that
best woman of the first k-1 women would be one of the first j-1
women is (j-1)/(k-1). Hence, the probability of selecting the
optimum woman at the kth round, for k in the range j to N based on
some particular value of j, equals the product
/ 1 \ / j-1 P{N,j} = ( --- )( ----- )
\ N / \ k-1 /
So, for this value of j, the probability of selecting the optimum
woman out of all N candidates based on this strategy (pass on the
first j-1, then choose the next "best so far") is the sum of the
above expression for k ranging from j to N. Thus we have
/j-1\ N / 1 P{N,j} = ( --- ) SUM ( ----- )
\ N / k=j \ k-1 /
If N is fairly large, the summation on the right is a large span of
the simple harmonic series, i.e., sum of the inverses of consecutive
integers. Recalling that the sum of 1/m for m=1 to s is asymptotically
equal to ln(s) + gamma (where gamma=0.57 is Euler constant) it follows
that the above probability approaches
/j-1\ / N P{N,j} = ( --- ) ln( ----- )
\ N / \ j-2 /
as N and j increase. To maximize this probability, we differentiate
with respect to j and set the result to zero, which gives
j-1 / N --- = ln( ----- )
j-2 \ j-2 /
Thus, as j increases, the left side approaches 1, and we can take
the exponential of both sides to give
N
e = ---
j-2
Consequently, for a large number of candidates, the optimum strategy
for maximizing the chances of selecting the very best woman from N
sequential candidates is to pass on the first N/e women (approximately)
and then select the next "best so far" that is encountered. With
this strategy the probability of success approaches 1/e.
(Incidentally, it's been called to my attention that the above formula
could, in certain circumstances, be used in a Bayesian way to estimate
the number N of candidates that a man could have expected to encounter
over his entire life, based on knowledge of having already met the
very best woman. The "Amanda Rule" states that if a man knows, by some
means, that the kth woman he has encountered is actually the very
best, then a Bayesian estimate for the number N of women he would have
expected to meet overall is roughly e*k. Of course, if he has already
determined that the kth woman is the very best, he presumably has no
interest in the remaining k(e-1) candidates, so the formula is of
only academic interest.)
The above is the traditional answer, and it gives a surprisingly good
probability of finding the single best woman from N candidates even
as N increases without limit. However, as noted previously, this
solution essentially treats the second best woman as no more suitable
than the least suitable. In other words, the strategy is entirely
focused on maximizing the probability of selecting the very best
candidate, without distinguishing between the utilities of any other
outcomes. A more pragmatic criterion for choosing a strategy might
be to maximize the expected "goodness" of the selection based on
some weighting of the outcomes. This certainly affects the answer,
as can be seen in the case of N=5 with a linear weighting where 0
is the worst and 4 is the best. The results for a strategy of
"passing" on the first k candidates and then choosing the next
"best so far" (or the last candidate if necessary) are as shown
below
probability expected
of selecting goodness of
the best the selected
k candidate candidate
---- ----------- --------------
0 24/120 240/120 = 2.000
1 50/120 348/120 = 2.900
2 52/120 336/120 = 2.800
3 41/120 297/120 = 2.475
4 24/120 240/120 = 2.000
This shows that to maximize your chances of selecting the very
best candidate you should "pass" on the first two, whereas to
maximize the expected goodness of the selected candidate you
should only "pass" on the first one.
By the way, the numerators of the exact probabilities of selecting
the best of N candidates using a strategy of k "passes" are as
shown below, based on denominators of N!.
N k
--- --------------------------------
3 2 3 2
4 6 11 10 6
5 24 50 52 41 24
6 120 274 308 271 206 120
7 720 1764 2088 1950 1640 1237 720
Is there is simple way of generating more rows of this table (aside
from just counting permutations)? Do these coefficients have any
other applications?
