Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site ulysses.UUCP
Path: utzoo!linus!decvax!harpo!eagle!mhuxt!mhuxi!mhuxa!ulysses!egs
From: egs@ulysses.UUCP
Newsgroups: net.math
Subject: Re: Another counterintuitive stat problem
Message-ID: <577@ulysses.UUCP>
Date: Sun, 28-Aug-83 05:01:08 EDT
Article-I.D.: ulysses.577
Posted: Sun Aug 28 05:01:08 1983
Date-Received: Tue, 30-Aug-83 05:18:21 EDT
Organization: Bell Labs, Murray Hill
Lines: 37

Regarding Silvio's problem. I think, but have not been able to prove yet, that
the optimal strategy is of the form:

	let M numbers go by, and choose the first of the remaining
	numbers that is greater than the first M.

What I get as the optimal value of M (if there are N numbers) is the value of M
that maximizes the function:

	F(N,M) = 1/N * sum over k=M,N-1 of (M/k),

(assign the ratio 0/0 the value of 1 to handle the case of M=0) which is a
reduced form of:

	F(N,M) = 1/N! * sum over k=M,N-1 of (C(N-1,k)*M*(k-1)!*(N-1-k)!),

which I get by counting the number of times the M-strategy picks the highest
number and dividing by the total number of permutations.

You can approximate F(N,M) as:

	F'(M,N) = M/N * (integral from M to N of 1/x dx) = M*(ln(N)-ln(M))/N.

Finding the maximum value of F' with respect to M yields:

	max of F'(N,M) = 1/e at M = N/e,

with the rather neat result that a fairly close approximation of the likelihood
for guessing the highest number when following the optimal strategy is
approximately 0.03679.

As it turns out, for N=10, the best choice is M=3 with a 0.3987 chance of
getting the highest number. For N=100, the best choice is M=37, with a 0.3710
chance. For N=1000, M=368, and chance is 0.3682.

							Ed Sheppard
							BTL @ MH