lew@ihuxr.UUCP (08/27/83)
I sent Silvio Levy mail on this but I guess it didn't go through. So, for the record, Leo Ringwald and I independently came up with the answer that the probability of a strategy M succeeding, where strategy M is to "stick" on the highest number after drawing M numbers, is: P(M,N) = 1/N * sum i = M, N-1 of 1/i As N gets large the optimal M approaches N/e and P(M,N) -> 1/e. Leo's derivation of P(M,N) was nice and simple. He reasoned that there is a probability 1/N of the highest number being drawn on the ith turn. With i > M, there is a probability M/i-1 of the highest of the first i-1 numbers being drawn in the first M. The above formula follows immediately (with a change of dummy variable.) For N=10, the best M is 3 with a probability .398690 of succeeding. Lew Mammel, Jr. ihuxr!lew