Re: [math-fun] Expected time to get any of several hits
Oops, it has been kindly pointed out to me that Bernie's questions is about sampling *without* replacement, which I somehow managed to miss. Sorry about that. In this case I don't think there's any neat closed formula for the expected number of trials before first choosing one of the M items out of N. It's just E(M;N) = E(# trials to the first success) = 1*[1]*(M/N) + 2*[(1-(M/N))]*(M/(N-1)) + 3*[(1-(M/N)*(1-M/(N-1))]*(M/(N-2)]+. . . + (N-M+1)*[(1-(M/N))*(1-M/(N-1))*...*(1-M/(N-M+1))]*(M/(N-(N-M)) where the last fraction is of course = 1. ----------------------------------------- There might be an interesting asymptotic formula for E(k*M;k*N) as k -> oo. (My guess, however, is that this just approaches the expectation for sampling *with* replacement, i.e., N/M.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
On 25 Jan 2008 at 0:00, Dan Asimov wrote:
Oops, it has been kindly pointed out to me that Bernie's questions ,.. is about sampling *without* replacement, which I somehow managed to ... miss. Sorry about that. ] It isn't what I'm thinking about, but one way to see the question I'm asking is: you have M ciphers using the same ciphersystem with a keyspace of size N. If you have to brute-force the key, trying each test-case against each of the M ciphertexts in turn, how far on average do you have to through the keyspace to decode one of the messages? To decode all of them?
There might be an interesting asymptotic formula for E(k*M;k*N) as k -> oo.
(My guess, however, is that this just approaches the expectation for sampling ... *with* replacement, i.e., N/M.)
As I said, my guess is pretty much that. If you assume that the M 'targets' are uniformly distributed across the sample space, then you'd think it'd take about N/(M+1) probes before you run into the first one and N*M/(M+1) probes before you get all of 'em. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
participants (2)
-
Bernie Cosell -
Dan Asimov