Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A monkey is sitting at a simplified keyboard that only includes the keys "a", "b", and "c". The monkey presses the keys at random. Let X be the number of keys pressed until the money has passed all the different keys at least once. For example, if the monkey typed "accaacbcaaac.." then X would equal 7 whereas if the money typed "cbaccaabbcab.." then X would equal 3.

a.) What is the probability X >= 10?

b.) Prove that for an random variable Z taking values in the range {1,2,3,...}, E(Z) = Summation from i = 1 to infinity of P(Z >= i).

c.) What's the expected value of X?

First, is this a binomial distribution or a geometric distribution? I believe it is a binomial but my other friends says that it is geometric. As for the questions above, for a can I just do 1 - P(X = 9) or 1 - P(X < 9), but I don't know how I will calculate X < 9, I would know how to calculate P(X = 9), I don't know how to do b or c.

share|improve this question
Remember the legend of Procrustes and do not try and force-fit this problem into the categories of binomial or geometric distributions: the forcible application of one or the other will kill any hopes of getting to the right answer. Instead, think first about what is being asked. Try a simpler problem: What is $P\{X = 10\}$ if the keyboard had only "a" and "b" and the monkey pressed them with probabilities $p$ and $1-p$ respectively? It is the probability of seeing either "aaaaaaaaab" or "bbbbbbbbba", right? The sum of two geometric probabilities but not a geometric distribution, right? –  Dilip Sarwate Mar 10 '14 at 14:18
@DilipSarwate Yes, that makes sense. But what are you trying to get at? –  user125627 Mar 10 '14 at 14:21

2 Answers 2

up vote 1 down vote accepted

We solve only the expectation part, in order to introduce an idea. But to make what the monkey types more interesting, Let us assume that the monkey has $5$ letters available.

Let $X_1$ be the waiting time (the number of key presses) until the first "new" letter. Of course $X=1$.

Let $X_2$ be the waiting time between the first new letter, and the second. Let $X_3$ be the waiting time between the second new letter and the third. Define $X_4$ and $X_5$ similarly.

Then the total waiting time $W$ is given by $W=X_1+X_2+X_3+X_4+X_5$. By the linearity of expectation we have $$E(W)=E(X_1)+E(X_2)+\cdots+E(X_5).$$

Clearly $E(X_1)=1$.

Once we have $1$ letter, the probability that a key press produces a new letter is $\frac{4}{5}$. So by a standard result about the geometric distribution, $E(X_2)=\frac{5}{4}$.

Once we have obtained $2$ letters, the probability that a letter is new is $\frac{3}{5}$. Thus $E(X_3)=\frac{5}{3}$.

Similarly, $E(X_4)=\frac{5}{2}$ and $E(X_5)=\frac{5}{1}$.

Add up. To make things look nicer, we bring out a common factor of $5$, and reverse the order of summation. We get $$E(W)=5\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}\right).$$

share|improve this answer

As Dilip Sarwate mentioned this problem is difficult (maybe impossible) to describe as a geometric or negative binomial distribution.

a) Note that in this case you need to draw 9 times balls of only two different colors, after which you don't care anymore. How many color combinations are there? And then what is the probability on 9 draws from exactly those two colors?

b) This is a commonly known result and can be found in most introductory books on probabiliy theory. It is also proven on the wikipedia page for expectation.

c) This is probably clear after solving a) and b)

share|improve this answer
for a do you mean for 3 not two? –  user125627 Mar 10 '14 at 15:18
No, I mean two, since if you draw the third color the monkey stops. So to get $X>9$ we need in the first 9 draws to only get two different colors. –  Marc Mar 10 '14 at 18:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.