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
    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 something2012-10-02
  • 0
    I don't know where that quation came from, but you can certainly simplify it to (1/3)^x*x*2 :)2012-10-02
  • 0
    Oh, I think it's more [binomial](http://en.wikipedia.org/wiki/Binomial_distribution) than poisson distribution :/2012-10-02
  • 0
    I think I solved it!2012-10-02
  • 0
    is it the same as my answer?2012-10-02
  • 0
    This is it: The answer is in the form A/((1/3)^x), which is obvious since the denominator is the total number of possibilities, but what is the value of A? We want RGB. If we only pick three balls (x = 3) then there is only one correct pick. For x = 4, we have RGB. 4-3 = 1, so we can either add one ball to the right (RGB[r/g/b]) or to the left ([r/g/b]RGB). This gives 6 correct picks so A = 6. For x = 5, we have RGB. 5-3 = 2, so can either: a. put two balls to the right (RGB[r/g/b][r/g/b]), two to the left or one right and one left ([r/g/b]RGB[r/g/b]). Same thing going up. So the prob.2012-10-02
  • 0
    The problem becomes how many ways can we add a certain number which is x - 3. For x = 4, x - 3 = 1, which can be obtained through either 1+0 or 0+1. This means A = 1*3+1*3 = 6. For x = 5, x - 3 = 2, which can be obtained through either 2+0 or 0+2 or 1+1. This means A = 2*3+2*3+1*3+1*3 = 18. For x = 6, x-3 = 3, the possibilites are 0+3, 3+0, 1+2, 2+1 so A = 36. The sequence is 1,6,18,36,60. This looks familiar.2012-10-02
  • 0
    huh for x = 5 you get A = 27 not 18. Also the answer is in the form A*(1/3)^x.2012-10-02
  • 0
    My bad. The main point I'm going for is that for x = 5, x - 3 = 2. To make 2 as a sum there are three possibilities: 0+2, 2+0 or 1+1. For the first (0+2), you can arrange [rgb] in the two slots on the right in 9 ways. For (2+0) you can arrange them in 9 ways. For (1+1) you can arrange them in 9 ways. So you get 9+9+9=27.2012-10-02
  • 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
    Could you please explain how to use the generative function?2012-10-02
  • 0
    BTW I think you meant b(0) = c(0) = d(0) = 0.2012-10-02
  • 0
    @numandina: On your second point you are correct. On the first, if you want to understand you could try [Wikipedia](http://en.wikipedia.org/wiki/Generating_function) or [generatingfunctionology](http://www.math.upenn.edu/~wilf/DownldGF.html); if you want to calculate the coefficients of the series expansion at $0$ then you can use a Computer Algebra System such as [this](http://www.wolframalpha.com/input/?i=series%20expansion%20x%5E3/%281-x%29/%2827-27*x%2bx%5E3%29)2012-10-02
  • 0
    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?2012-10-03
  • 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
    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.2012-10-02
  • 0
    @numandina Sorry, I think I misunderstood the question. I thought you take three balls, and do that four times.2012-10-02
  • 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.