2
$\begingroup$

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.

  • 0
    I have a feeling that a formula for general $x$ is kind of hard to find and possibly maybe doesn't have a closed form solution2012-10-02

4 Answers 4

2

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

  • 0
    @numandina: Looking at the related OEIS sequences [A052963](http://oeis.org/A052963) and [A076264](http://oeis.org/A076264), there is probably a complicated and ugly closed form involving the roots of a cubic equation.2012-10-03
2

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.

  • 0
    Thanks for the answer. You're smart.2012-10-03
0

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$

  • 0
    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.2012-10-02
0

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.