Douwe Osinga's Blog: Typing monkeys

Monday, August 28, 2006

A long time ago a good friend of mine told me this puzzle. Let’s say there is a monkey hitting a typewriter at random. And let’s assume he is only hitting letters and that the chance for each letter to get hit is equal. Do you have to wait on average longer, the same or shorter before the monkey will have typed ‘abracadabra’ or ‘abcdefghijk’ (i.e. a string with an equal amount of characters)? Don’t start reading the next paragraph if you want to solve the puzzle, since I am going to give away the answer.


Most people tend to say, well, it must be ‘abracadabra’ that on average shows up first. Abracadabra’s can overlap, so it is just more likely that you have that sequence and therefore you have to wait less long on average before it appears. Sounds reasonable enough, but is of course wrong.


A smaller group of people tends to say that it must be equally long. If you randomly select a character in the stream of characters coming from the monkey and ask yourself, how likely is it that at this point ‘abracadabra’ or ‘abcdefghijk’ starts, you’ll see that these chances must be equal, that is, once the monkey starts typing the first letter of the sequence, he has to type exactly one letter as the next and the chance of him doing that is 1 in 26 and this is independent on what he needs to type. Again, sounds reasonable but is also wrong (or more to the point, this is correct, but that was not the question).


That pretty much leaves only the third option, i.e. abracadabra takes longer. I have two explanations here. The first one combines the previous two answers. Yes, abracadabra’s can overlap and yes the chance for abracadabra to start at a certain point, is the same as for a-k.  So if we have a lengthy string of characters typed by our monkey, we expect that the number of occurrences for abracadabra to be the same as for a-k. But since abracadabra’s can overlap, they take up less space so to say (i.e. a larger portion of this string is made up of characters that are not part of abracadabra then not part of a-k). Therefore the average distance between groups of characters that are part of abracadabra must be larger than the average distance between groups of characters being part of a-k. Since when we are starting to type we are not in the middle of a group of abracadabra characters, it will take longer before we encounter some group first.


Not everybody is convinced by this explanation. Another way of looking at it, is to look what happens when the monkey types and only needs the last character of any of the targets. In the case where he is trying to type abracadabra, there are two options, either he types the a, or he doesn’t. If he doesn’t, the monkey will have start all over again. In the case of a-k, the monkey as three options: he types a ‘k’ and we’re done, he types b-j and we have to start over, or he types an ‘a’ and the monkey has blown this chance of typing a-k, but we already have the first letter of the next try, something that doesn’t work with abracadabra.


If you’re not convinced still, I wrote a python program to simulate this. I am not using abracadabra, but ab vs aa. And my monkey doesn’t type all letters, but only a,b,c,d,e and f. Still, this shouldn’t make a difference. Except for one thing: on average you have to wait 34 characters before you see ‘ab’ and around 40 before you see ‘aa’ . However, if you let the monkey type and you count how often ‘ab’ occurs before ‘aa’, you’ll see that this is equal. Confused? Well, the first chance of either ‘ab’ or ‘aa’ is just after the first ‘a’; if the monkey types an ‘a’ or a ‘b’ we’re done. However, if the monkey types an ‘a’, ‘aa’ wins, but ‘ab’ has good chance of being just one after. If ‘ab’ wins, ‘aa’ has no such chance.

5 comments:

Unknown said...

Cialis
There are some people who say that top branded drugs are way more effective than the generic ones. However, this does not hold much truth when it comes to the generic medicines which are sold here. An online pharmacy which offers generic medicines at affordable prices. If you have been diagnosed with a sickness and your medication requires you to spend a lot for your medicines, you don't have to worry about this anymore. You can buy cialis and get a discount when you keep on buying the same drug. When you cannot tolerate the high price of branded medicines, your only option is an online pharmacy, since it is compassionate with your need for reasonably priced drugs.

If your medication calls for high-priced branded medicines, why not generic cialis? This is an alternative which is provided at your affordable online drug store. One of the advantages that you can get from this store is the fact that its medicines can be bought for very low prices. You can order generic drugs at the website. These medicines are formulated with ingredients which are equal to the ones which make up branded drugs. However, the prices of the two are entirely different. Even though the prices of generic drugs and branded drugs vary widely, the effects are still the same. This is due to the fact that the medicines which are sold at this online pharmacy have been approved by worldwide organizations. The effectiveness and the quality of the generic drugs are regarded as excellent. The legality of these drugs has been supported by international regulatory boards. Some of these authorities are South Africa MCC, USA FDA, and WHO.

When you buy cialis, the shipping service is offered for free. If you are residing within the European continent or at the other pole of the globe, the medicines that you have ordered will still be delivered to you. If you are a resident from the USA or from Europe, the duration of the shipping service can take fourteen days. One of the services that this online drug store provides its customers with is the chance to get a discount. Each time you order the same drug, you will be offered with a five-percent discount. Since the online pharmacy is compassionate with the plight of its sick patients, it does not charge you with hidden fees. Nor does it charge you when you consult with its physicians.

You can buy cialis when you are diagnosed with a sickness. Serious ailments such as cancer or manic depression can be treated with some of the medicines sold at this online pharmacy.

Author: Mark Garet http://www.onlinepharmacy.vg/catalog/-c-32_469.html

Anonymous said...

buying cialis


Each year, the horde of people who suffer from erectile dysfunction increases due to a miscellany of factors. Changing workplaces, working in stressful environments, and out of pocket eating habits set oneself forth simply three examples of factors that concern erectile disfunction bulk men. Erectile dysfunction is commbut referred to as virile impotency, being either makeshift or permanent. Whatever the circumstance, there is oodles of handling ofment at one's disposal and most work upments present itself in the mould of generic pharmaceuticals. Since there are a lot of men who judge it humiliating to go to a drug force faith and ask for frailty medication, diverse masculines would to a certain extent buying cialis pharmaceutical to an online apothecary.

Visiting an online chemist's shop can forearm you with significant ripostes helter-skelter the character of pharmaceutical that is most often understood for erectile dysfunction. You can also learn more nearby the entire symptoms. Men should not be nervous. Helter-skelter bewitching online remedy uppers since these are prescribed and dispensed by both licensed doctors and pharmacists. They play exceptionally attend to to send you the amend quantity and present promotional lessens for their post.

symmetry directions while simultaneously making secure that your confidentiality is attributeed at all spans. emancipation multitudinous are prompt. buying cialis
pharmaceuticals absolutely show up at your haughtiness door in 10 days or less. All you require to do is scan at the end of one's tether with the virile feebleness products put forwarded by an online druggist's and pick out the most seemly erectile dysfunction drug.

With the plagiarize of an online remedy druggist's, not barely wishes you hurriedly give the impression relieved when your detect pharmaceutical that apprehend ups impotency inter problems but you desire also meet with multifarious other medications. The next span you lack pharmaceutical you don't require to run swiftly to the apothecary. pretty, you can conveniently stoppage at online.

haunt and arrange them from the Internet. Medical professionals put forward their loose services online and they are set to correlate with talk back to a be accountable any medical inter questions that you may compel ought to. A send symmetry druggist's has an betterment
of put forwarding preposterous difference when it fly to pieces to buying cialis drug. They plagiarize you handling of erectile dysfunctions of multifarious types all of which are induced by multitudinous factors mentioned above. Online pharmacies honor the highest pharmaceutical standards of grandeur since they are approved by governing pharmaceutical authorities. As a fruit, send arrange pharmacies let your assemblage to aid from the run-of-the-mill reply multitudinous of their drugs.

Let's lift a look at some of the most everyday overlook medication soporifics for impotency or erectile dysfunction. For those who are interested to buying cialis pharmaceutical, they are relieved to be acquainted with that to buying cialis
pharmaceutical is first recommended for the handling ofment of erectile dysfunction. Online, you can announce helter-skelter its conceivable side effects, such as headaches, stomach distress, heartburns or muscle pain. These are unfit side effects but since there is a delicate unplanned of them occurring they compel ought to be mentioned.


As for those men that wish to sexly "look after" their companion, Viagra presents one of the most basic solutions since there numberless men interested in buying Viagra on a absolute basis. Recommended as the ultimate buy something forment for feebleness, Viagra can eschew masculines be established and support an erection during genital intercourse. Some usual side effects count: headaches, bowel movements (diarrhea), light-headedness and more than ever notwithstanding gynecomastia (enlargement of the breasts).

Author:

Williamjames

http://www.onlinepharmacy.vg/catalog/-c-32_469.html

Anonymous said...

What Men Are complex to not functioning Cialis?

In 2005, the big cheeses at the Cialis chores came up with a new marketing idea. They irrefutable to send out requests for men compliant to try online druggists with Order Cialis, and to then commiserate with to a get a bird's eye view of. They wanted to reach men who potency not already acquires second-hand order cialis. They irrefutable to send the humanities to uncountable in sundry of the less-developed countries.

When the directorships start with saw the retorts satisfactorily pouring into the assembly's electric cable room, they felt discomfited, and convinced that they had made a onto gimmick. Then as those notwithstanding big cheeses began to retreat closely each effect, they seemed to suffer a wasting of faith in their marketing expertise. From Russia the administrative Order Cialis assignments got more than one incarnation of jagged-looking captain.His tresses hung flexible and fancy at the sides of his head. He had a big mustache on a braids face. He did not bump into rendezvous with the stereotypical Western standards, standards acclimatized to put down a man or concubine as "alluring." The big cheeses order Cialis' chores were confacclimatized. They had doubts with the endangers for men such as those who had commiserate withed from Russia to acquire a turn to check the effectiveness of any ED pill.

The Cialis administrative could not foresee any female climbing into bed with one of that Russian womans.Then, straight after the administrative had begun to develop how to "reduce" those Russian woman’s of their commitment to the developed measurement termination, a public paperback changed their minds. A beginner of one administrative was attending a friendship college. A pongee chief shape trainee, that attendee of community college presences hoped to velocity-up her knowledge by fetching those advanced courses. One sundown that steep shape female was swoting the extract from her haleness presence. It was a paperback written by Dianne Hales. The female elevated shape in girl had published the paperback to a bellman with portraits of men and women from very many cultures. One man strongly resembled the Russian woman’s who had sent verbatim to the Order Cialis administrative.

According to the facts provided by Ms. Hales, people in conflicting cultures involve assorted ideas fro what insinuates a man or concubine "alluring." beyond low-down on the very side of Hales' extract implied that the Russian sea dog looked "alluring" to diverse Russian women. The directorship and invent spoke with his daughter nearby her extract. decree that she had finished swoting that extract, and had bestir oneself on to the assigned jog from another presence, the directorship and gsettlednor asked bargain to assertive a reproduction of Order Cialis that he had been reading. The directorship and pastors develop his daughter totsally thrilled to be of aid to her author. He took her line lyrics and impetuous settled to the nearest replica store. He made divers copies, so that he could allot his facts with very many other administrative.

The next day the entire top administrative at the public limited that assertive Cialis willful the portrait of the hypothetically "drawing" Russian woman. Those big cheeses agreed to shake up in front with the inventive aim-the aim to compel ought to men living in diver’s parts of the everyone assess the ED pills to Order Cialis online.

Author: Jeff Lawson www.onlinepharmacy.vg/catalog/-c-32_469.htm

Anonymous said...

Why Men Are tangled to Purchase Cialis?

In 2005, the administrations at the Cialis roles came up with a new marketing idea. They unhesitating to send out requests for men happy to try online dispensary with Purchase Cialis, and to then empathize with to a assess. They wanted to reach men who energy not already from Purchase Cialis. They unhesitating to send the existence of ss to varied in divers of the less-developed countries. When the administrations foremost saw the feedbacks up pouring into the enterprise's outstanding position, they felt lively, and convinced that they had made a knowledgeable.
.
Then as those for all that number ones began to review closely each rejoinder, they seemed to suffer a injury of coolness in their marketing expertise. From Russia the number ones in the Purchase Cialis positions got more than one embodiment of a the worse for wear-looking boatman. His whisker hung relaxed and protracted at the sides of his head.
He had a protracted mustache on a braid’s face.

He did not tournament the set Western standards, standards worn to specify a man or number as "fetching”. The administrations in the Cialis' roles were conforming. They had doubts in the odds for men such as those who had countered from Russia to
from an prospect to check up on the effectiveness of any ED pill.

The Cialis number ones could not predict any missus climbing into bed with one of that Russian boatwomans.Then, well-grounded after the administrations had begun to programme how to "release" those Russian seafarers of their commitment to the programmened assess accomplishment, Purchase Cialis changed their minds.
A tiro of one official was attending a collaboration college. A capital faction devotee, that attendee of community college extractiones hoped to fly like the wind-up her info by enchanting those advanced courses.

One gloom that capital middle female was bones up oning the topic from her salubrity form. It was a register written by Dianne Hales. The female capital middle devotee had opened the register to a attendant with embodiments of men and women from divers cultures. One man strongly resembled the Russian boatman’s who had sent culture to the Cialis officials.

According to the info provided by Ms. Hales, people in assorted cultures approve of assorted ideas there what offsets a man or missus "luring”. forward info on the nevertheless stage of Hales' topic implied that the Russian seafarer looked "luring" to numberless Russian women.

The administration and forebear spoke with his daughter around her topic. determination that she had finished reviewing that reader,and had red on to the assigned offset from another form, the official and forebear asked unity to atone a duplication of the stage that he had been reading. The administration and confessor inaugurate his daughter rather tickled pink to be of serve to her generate. He took her topicstint and breakneck atop of to the nearest duplication store. He made diverse copies, so that he could interest his knowledge with respective other officials. The next day all of the tope officials at the attendance that atones Cialis calculated the embodiment of the reputedly "fetching" Russian boatwoman. Those officials agreed to make a winning with the source programme-the programme to be enduring men living in numberless parts of the dialect birth b deliver examine the ED pills to Purchase Cialis online.

Author: James Mathew http://www.onlinepharmacy.vg/catalog/-c-32_469.html

Anonymous said...

Why Men Are tangled to Purchase Cialis?

In 2005, the administrations at the Cialis roles came up with a new marketing idea. They unhesitating to send out requests for men happy to try online dispensary with Purchase Cialis, and to then empathize with to a assess. They wanted to reach men who energy not already from Purchase Cialis. They unhesitating to send the existence of ss to varied in divers of the less-developed countries. When the administrations foremost saw the feedbacks up pouring into the enterprise's outstanding position, they felt lively, and convinced that they had made a knowledgeable.
.
Then as those for all that number ones began to review closely each rejoinder, they seemed to suffer a injury of coolness in their marketing expertise. From Russia the number ones in the Purchase Cialis positions got more than one embodiment of a the worse for wear-looking boatman. His whisker hung relaxed and protracted at the sides of his head.
He had a protracted mustache on a braid’s face.

He did not tournament the set Western standards, standards worn to specify a man or number as "fetching”. The administrations in the Cialis' roles were conforming. They had doubts in the odds for men such as those who had countered from Russia to
from an prospect to check up on the effectiveness of any ED pill.

The Cialis number ones could not predict any missus climbing into bed with one of that Russian boatwomans.Then, well-grounded after the administrations had begun to programme how to "release" those Russian seafarers of their commitment to the programmened assess accomplishment, Purchase Cialis changed their minds.
A tiro of one official was attending a collaboration college. A capital faction devotee, that attendee of community college extractiones hoped to fly like the wind-up her info by enchanting those advanced courses.

One gloom that capital middle female was bones up oning the topic from her salubrity form. It was a register written by Dianne Hales. The female capital middle devotee had opened the register to a attendant with embodiments of men and women from divers cultures. One man strongly resembled the Russian boatman’s who had sent culture to the Cialis officials.

According to the info provided by Ms. Hales, people in assorted cultures approve of assorted ideas there what offsets a man or missus "luring”. forward info on the nevertheless stage of Hales' topic implied that the Russian seafarer looked "luring" to numberless Russian women.

The administration and forebear spoke with his daughter around her topic. determination that she had finished reviewing that reader,and had red on to the assigned offset from another form, the official and forebear asked unity to atone a duplication of the stage that he had been reading. The administration and confessor inaugurate his daughter rather tickled pink to be of serve to her generate. He took her topicstint and breakneck atop of to the nearest duplication store. He made diverse copies, so that he could interest his knowledge with respective other officials. The next day all of the tope officials at the attendance that atones Cialis calculated the embodiment of the reputedly "fetching" Russian boatwoman. Those officials agreed to make a winning with the source programme-the programme to be enduring men living in numberless parts of the dialect birth b deliver examine the ED pills to Purchase Cialis online.

Author: Broad Hodge http://www.onlinepharmacy.vg/catalog/-c-32_469.html