Monkey and a poet's work ?
in [General Programming]
|
From: Noob on 8 Mar 2010 07:35 Richard Heathfield wrote: > Let's assume that we have *one* monkey, then, hitting *one* typewriter > *once* per second, purely at random. The typewriter has *two* keys, 0 > and 1. (When we install the MonkeyBrain XII later on, we can soup up the > speed a bit.) > > Here is a Shakespeare sonnetette: 10010111. We want to know whether, if > we'd installed our monkey attadawnatime, he would have a reasonable > probability of having produced this sonnetette by now. Of course, we'd > like to be more general than that. > > Attadawnatime, they say, was 14,000,000,000 years ago. That's about > 441504000000000000 seconds, which we'll double (in case the scientists > got it wrong, which is not exactly unheard of), giving us a million > million million seconds to work with. Bags of time. > > Now, the first seven times our monkey hits the keys, he can't possibly > produce the sonnetette. But the eighth time, he *may* have produced a > sonnetette. That is, if the bit length of the target text T is L, then > we have to produce at least L bits. > > The probability of the first L bits producing T is 1/(2^L). More > specifically, for L=8 it's 1/256 = 0.00390625 = p (probability of > matching L bits of data against all L bits of text, in a given position > in the bitstream). > > Now if we produce *more* bits, it gets a bit(sigh) more interesting. > Let's assume we produce 9 bits. We now have two stabs at the T cherry: a > match of T against the first 8 bits of the 9, and a match against the > last 8 bits of the 9. Any one match will do, so both matches have to > fail for the monkey to fail. We calculate this failure probability F by > raising (1-p) to the power of the number of match attempts: > > F = (1-p)^2 = 0.99609375^2 = 0.9922027587890625 I don't think so. The two attempts are not independent.
From: jellybean stonerfish on 8 Mar 2010 09:44 On Mon, 08 Mar 2010 01:56:54 -0800, Nick Keighley wrote: > shakespere didn't generate his plays by random means. It was random that there even was a Shakespeare.
From: Richard Heathfield on 8 Mar 2010 18:44 Noob wrote: > Richard Heathfield wrote: <snip> >> We calculate this failure probability F by >> raising (1-p) to the power of the number of match attempts: >> >> F = (1-p)^2 = 0.99609375^2 = 0.9922027587890625 > > I don't think so. The two attempts are not independent. It's a fair cop. Perhaps you could explain how to perform the calculation correctly? -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: mike on 9 Mar 2010 16:02 In article <yKWdnfd7BvIrFgjWnZ2dnUVZ8txi4p2d(a)bt.com>, rjh(a)see.sig.invalid says... > Noob wrote: > > Richard Heathfield wrote: > > <snip> > > >> We calculate this failure probability F by > >> raising (1-p) to the power of the number of match attempts: > >> > >> F = (1-p)^2 = 0.99609375^2 = 0.9922027587890625 > > > > I don't think so. The two attempts are not independent. > > It's a fair cop. Perhaps you could explain how to perform the > calculation correctly? > Unfortunately, the calculation depends on the specific text*. So for your binary version of Hamlet (or was it Othello) there is no simple answer. * to prove this, imagine that the works of Shakespeare can be expressed as a two character binary string (maybe the Condendsed Books version) and the random monkey has typed three symbols. If the condensed string is '00' then there is a 5/8 chance that it will not appear in a random three character string, but if the string is '01' then there is a 1/2 chance it will not be found in a random three character string. Mike
From: rossum on 9 Mar 2010 18:01
On Sun, 07 Mar 2010 15:14:30 -0500, Stefan Monnier <monnier(a)iro.umontreal.ca> wrote: >>> For another take on this have a look at the story "The Library >>> of Babel" by Jorge Luis Borges http://jubal.westnet.com/hyperdiscordia/library_of_babel.html >>>(who was, BTW, the model for >>> the blind librarian in Eco's "The Name of the Rose"). > >You might like the "Pierre Menard, Author of the Quixote" as well, for >a different take on it. http://www.coldbacon.com/writing/borges-quixote.html And for a third suggestion by the same author try "The Book of Sand" http://artificeeternity.com/bookofsand/ which compresses the entire library into a single book (though it does have quite a few pages). rossum > > > Stefan |