# What is the possibility of choosing three balls in a certain sequence given a certain number of attempts?

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.

-
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

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)}.$

-
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.

-
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$$

-
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.

-