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.

Say I have three balls - red, green and blue in a bag. I will choose a ball from the bag and then return it, then choose another one, etc. Say I will do this 3 times; then the possibility of me picking a certain sequence (for example RGB) is 1/3 * 1/3 * 1/3. But say I do this 4 times. What is the possibility then of running into the same sequence? The desired pick becomes one of the following: BRGB or RRGB or GRGB or RGBB or RGBG or RGBR. I can do the math for this, but what is the general equation where the number of picks is X? Say I want to pick ten balls, what is the possibility of getting RGB then?

For example if I pick four times there is a (1/3)^4 chance that I would get RGBR, but my question isn't the possibility of getting a FOUR letter sequence, rather of getting a three letter sequence in a four letter possibility. The correct answer when x = 4 is (1/3)^4 *6 = 6/81.

Am I explaining this easily? Thanks.

EDIT: Please note that there is only one trial.

share|improve this question
    
That looks... relevant... I think. I'll look into it but I thought the question I asked is actually a very well known and common one, and a question that already has a solution in the form of an elegant equation somewhere. Something like (1/3)^x * x!/(x-1)! * 2 or something –  numandina Oct 2 '12 at 8:35
    
I don't know where that quation came from, but you can certainly simplify it to (1/3)^x*x*2 :) –  Alex Oct 2 '12 at 8:38
    
Oh, I think it's more binomial than poisson distribution :/ –  Alex Oct 2 '12 at 8:40
    
I think I solved it! –  numandina Oct 2 '12 at 9:20
    
is it the same as my answer? –  Alex Oct 2 '12 at 9:20

4 Answers 4

up vote 2 down vote accepted

Let

  • $a(n)$ be the number of strings of length $n$ not containing RGB and not ending R or RG

  • $b(n)$ be the number of strings of length $n$ not containing RGB and ending R

  • $c(n)$ be the number of strings of length $n$ not containing RGB and ending RG

  • $d(n)$ be the number of strings of length $n$ containing RGB

then starting at $a(0)=1$ and $b(0)=c(0)=d(0)=0$ you have

  • $a(n+1)=2a(n)+b(n)+c(n)$

  • $b(n+1)=a(n)+b(n)+c(n)$

  • $c(n+1)=b(n)$

  • $d(n+1)=c(n)+3d(n)$

and $a(n)+b(n)+c(n)+d(n)=3^n$. You want the probability $d(n)/3^n$.

That is enough to do the calculation, and for ten balls gives $\frac{16293}{59049}\approx 0.2759$ though you could instead use the generating function $\dfrac{x^3}{(1-x)(27-27x+x^3)}.$

share|improve this answer
    
Could you please explain how to use the generative function? –  numandina Oct 2 '12 at 11:38
    
BTW I think you meant b(0) = c(0) = d(0) = 0. –  numandina Oct 2 '12 at 14:29
    
@numandina: On your second point you are correct. On the first, if you want to understand you could try Wikipedia or generatingfunctionology; if you want to calculate the coefficients of the series expansion at $0$ then you can use a Computer Algebra System such as this –  Henry Oct 2 '12 at 15:55
    
Great answer. Best part is using your logic I can create rules for any other sequence of different length. Just a quick question: I'm thinking of finding a closed form soluition, something without iterations, do you thikn it's possible or not? –  numandina Oct 3 '12 at 7:21
    
@numandina: Looking at the related OEIS sequences A052963 and A076264, there is probably a complicated and ugly closed form involving the roots of a cubic equation. –  Henry Oct 3 '12 at 18:01

Let $a_n$ be the number of strings of length $n$ that do not contain the sequence RGB; I’ll call these the bad sequences. Clearly $a_0=1,a_1=3$, and $a_2=9$. Suppose now that $n\ge 2$. To build a bad sequence of length $n+1$, to a first approximation you can add any color to the end of a bad string of length $n$; that gives you $3a_n$ strings. However, if the string of length $n$ ends in RG, you cannot add a B. Each bad string of length $n$ ending in RG is the result of adding RG to a arbitrary bad string of length $n-2$, so there are $a_{n-2}$ such bad strings of length $n$ to which we cannot add B. Thus, $a_{n+1}=3a_n-a_{n-2}$.

Now let $p_n$ be the probability of drawing a bad string of length $n$; $p_n=\dfrac{a_n}{3^n}$, so

$$p_{n+1}=\frac{3a_n-a_{n-2}}{3^{n+1}}=\frac{3^{n+1}p_n-3^{n-2}p_{n-2}}{3^{n+1}}=p_n-\frac{p_{n-2}}{27}\;,$$

and the probability of drawing a string of length $n$ containing RGB is $1-p_n$. The generating function for $a_n$ involves a somewhat intractable cubic, but the recurrences for $a_n$ and $p_n$ aren’t bad.

share|improve this answer
    
Thanks for the answer. You're smart. –  numandina Oct 3 '12 at 7:22

I think you want this:

No. of possibilities with RGB = $(x-2)3^{x-3}$

$$p = \frac{(x-2)3^{x-3}}{3^{x}} = (x-2)3^{-3} = \frac{x-2}{27}$$

for x=5 you get 27 possibilities, not 24.

However, this only works for $x<6$ as you could get two triples otherwise. I don't exactly know how avoid this at the moment.


Wrong: $$X \sim B\left (4,\frac{1}{3} \right )$$

$$Pr(X \leq 4) = \sum_{i=1}^{4}\binom{4}{i}\left (\frac{1}{9} \right )^{i}\left (1-\frac{1}{9} \right )^{i} \approx 0.45753$$

share|improve this answer
    
Thanks for the help but I don't think I follow. For x = 4 the answer is 6/81 = 0.074. For x = 5 the answer is 24/243 = 0.099. This makes sense since for x = infinity the answer should be 1. –  numandina Oct 2 '12 at 8:52
    
@numandina Sorry, I think I misunderstood the question. I thought you take three balls, and do that four times. –  Alex Oct 2 '12 at 8:55
    
If x = 4: You take four balls, and look for a sequence of three balls. If x = 5, you take five balls, and look for a sequence of three balls. If x = 10000, you take 10000 balls and look for the sequence. Think of infinite monkeys on infinite typewriters or arranging finite atoms in an infinite universe, etc. –  numandina Oct 2 '12 at 8:56

Here is an approach that does not count strings:

There are three nonterminal states in this game, namely $s_1$: only the letter $B$ is missing, $s_2$: the two letters GB are missing, and $s_3$: everything else. Denote by $p_{r,k}$ the probability that we fail when $r\geq0$ picks are left over and we are in state $s_k$. Then $p_{0,k}=1$ $\ (1\leq k\leq 3)$.

The $p_{r,k}$ satisfy the following recurrence: $$\eqalign{p_{r,1}&={1\over3}p_{r-1,2}+{1\over3}p_{r-1,3}\cr p_{r,2}&={1\over3}p_{r-1,2}+{1\over3}p_{r-1,1}+{1\over3}p_{r-1,3}\cr p_{r,3}&={1\over3}p_{r-1,2}+{2\over3}p_{r-1,3}\ .\cr}$$

It follows that ${\bf p}_r={1\over3^r}A^r{\bf 1}$, where $A$ is the matrix $$A=\left[\matrix{0&1&1\cr 1&1&1\cr 0&1&2\cr}\right]\ .$$ Unfortunately this matrix has unfriendly eigenvalues, so that no simple formula for $p_{n,3}$ results, albeit this number is, of course, rational.

share|improve this answer

Your Answer

 
discard

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.