Probability of 3 successive ball picks?

[themaestro]

Hi

This question has been driving me mad, hoping someone will be able to help me
The question is:

A bag contains X Red balls and Y Blue Balls. A ball is picked from the bag (at random) one at a time until all the balls have been picked. What is the Probability that 3 successive red balls will be picked?

Any help will be most appeciated
Thanks

 

[SW VandeCarr]

A bag contains X Red balls and Y Blue Balls. A ball is picked from the bag (at random) one at a time until all the balls have been picked. What is the Probability that 3 successive red balls will be picked?

Any help will be most appeciated
Thanks

If you simply want the prior probability before any draws, it's (X/X+Y)^3 assuming there are at least three X balls in the mix.

Given you draw a Y ball on the n-1 th draw, the sequential conditional probabilities of k X balls in a row are (up to k=3):

nth draw P(X)1=X-n(x)/X-n(x)+Y-n(y)

n+1 th draw P(X)2=X-n(x)-1/X-n(x)-1+Y-n(y)

n+2 th draw P(X)3=X-n(x)-2/X-n(x)-2+Y-n(y)

Where n(x) is the number of X balls drawn before the run and the same for Y balls and n(y) : negative integer results set to 0 .

Probability of drawing three X balls in a row is P(X)1*P(X)2*P(X)3

 

[themaestro]

Thanks for taking the time to have a look at this. I hadnt considered looking at in this way before. One problem is that the 3 reds can occur anywhere in the sequence, so by your method would we need to sum for all combinations of n(x)n(y)? i.e would it be Double sum( P(n(x))P(n(y))P(X)1*P(X)2*P(X)3) for all valid n(x) and n(y). If this is true, This is could be problematic to use as the number of combinations could be very large, unless anyone can think of a way of Simplifying these terms. One other problem with using this double sum is making sure that don't double count some possiblities (i.e. n(x) could contain 3 successive reds itself)

 

[SW VandeCarr]

Thanks for taking the time to have a look at this. I hadnt considered looking at in this way before. One problem is that the 3 reds can occur anywhere in the sequence, so by your method would we need to sum for all combinations of n(x)n(y)? i.e would it be Double sum( P(n(x))P(n(y))P(X)1*P(X)2*P(X)3) for all valid n(x) and n(y). If this is true, This is could be problematic to use as the number of combinations could be very large, unless anyone can think of a way of Simplifying these terms. One other problem with using this double sum is making sure that don't double count some possiblities (i.e. n(x) could contain 3 successive reds itself)

Your question was regarding the probability of drawing k=3 red balls in a row out of X red balls and Y white balls. The way you phrased it, X is the total number of red balls and Y the total number of white. I may have confused you by the way I used the term "X balls" when simply referring to red balls. The math however, I believe is correct When referring to red or white balls I will use lower case.

Before you start, we have a prior probability of drawing 3 red in a row at any point in the sequence without specifying exactly where. That would be (X/X+Y)^3.

Once you start taking balls out you need to recalculate the probabilities following each draw. All I did was show how this would be done given you draw a white ball, Call that the n-1 th draw. Then probability of drawing a red on the nth draw is P(x1). In doing this, you must account for all balls drawn before the nth draw n(x) and n(y). What I've done is show a running account for the sequential conditional probabilities: P(x2|x1) and P(x3|x2). Because you don't know Px2 until the n th draw, you can't directly calculate P(x2|x1) from Bayes' Theorem.

It's easy to see how the algorithm might be modified if you draw a red ball on the first draw n=1. In any case whenever you draw a red ball, it's the start of a potential run. If you draw a white ball, you are back to n-1 with an updated prior probability based on n(x) and n(y), the number of reds and whites already drawn.

P(x1)*P(x2)*P(x3) is the posterior probability of getting three reds in a row given drawing a white ball at any point in the sequence. It's calculated on the assumption you will get three reds in a row beginning with the next draw immediately following drawing the white ball.

EDIT: If you want to know the prior probability of drawing three reds in a row at any point n in the remaining sequence, that would be (X'/X'+Y')^3 where X' and Y' are the updated values of X and Y remaining. This is really a new prior probability for a shortened sequence

 

[themaestro]

would it not be (X')(X'-1)(X'-2)/[(X'+Y')(X'+Y'-1)(X'+Y'-2)] instead of (X/[X+Y])^3 as the number of remaining balls reduces by one after every pick?

Regarding your main algorithm i think it looks fine, my only issues would be with actually using this as wouldn't there be a very large number of calculations if X and Y or Am I missing a trick? for example if X=5 and Y=8 how many calculations would this involve? what would be the probability in this case?

thanks again for your time

 

[SW VandeCarr]

would it not be (X')(X'-1)(X'-2)/[(X'+Y')(X'+Y'-1)(X'+Y'-2)] instead of (X/[X+Y])^3 as the number of remaining balls reduces by one after every pick?

No. The expression P=(X/X+Y)^k is the prior unconditional probability of exactly k red balls in a row before any balls are drawn. You need to look up what I mean by a prior probability (see also the middle paragraph of my response below).

Regarding your main algorithm i think it looks fine, my only issues would be with actually using this as wouldn't there be a very large number of calculations if X and Y or Am I missing a trick? for example if X=5 and Y=8 how many calculations would this involve? what would be the probability in this case?

The algorithm (if extended) gives you the conditional probability of exactly k red balls in a row starting from any draw of a white ball. It's easily modified if the first ball drawn is red. It can be applied at any or every point of the sequence where a white ball is drawn. It will zero out when n(x) is greater than X-k for some white ball draw.

What are asking for with X=5 and Y=8? The prior is (5/13)^k because you are not taking away anything. Each draw in the set is independent. It's as if you mixed all the balls up and dropped them into a glass tube. What's the probability of three consecutive red balls in the tube?

The algorithm does consider what you take way and the maximum number of calculations will be the number of white balls available or 8 although it will actually be less depending on the size of k. This assumes you want calculate the probability of a k red sequence after each white.

EDIT: Let's take your example. Suppose the first ball is white. You want to calculate the probability of the next 3 balls being red

P=5/12*4/11*3/10=60/1320=.04546

Note what happens if you go on to six red in a row drawn: P=0.4546*2/9*1/8*0/7=0

 

[SW VandeCarr]

Sorry. There was an error in the above post. The probability of 3 reds in a row was incorrectly carried over to the calculation of the probability of six reds in a row. It's .04546 and I carried it over as 0.4546. It's corrected below.

Let's take your example X(red)=5, Y=8. Suppose the first ball is white. You want to calculate the probability of the next 3 balls being red

P=5/12*4/11*3/10=60/1320=.04546

Note what happens if you go on to six red in a row drawn: P=.04546*2/9*1/8*0/7=0

 

[themaestro]

Hi

Was hoping you could clear this thing up about the prior probability (X/X+Y)^3 and exactly what you mean by this. One thing I know its not is the initital probability of the first 3 balls being red as this is (X')(X'-1)(X'-2)/[(X'+Y')(X'+Y'-1)(X'+Y'-2)]
also it can not be the initital probability of 3 successive reds at any point as looking at some trivial examples, if X is 10 and Y is 1 we are guaranteed 3 successive reds but (X/X+Y)^3 gives a value less then 1 for all Y>0. Also if X =2 then clearly 3 successive reds is impossible however
(X/X+Y)^3 is non zero for all X>0. So I am puzzled to what exactly (X/X+Y)^3 is the probability of?

Thanks

 

[yossell]

SW,
I, too, am finding it hard to understand what this prior probability is and would appreciate to know what you had in mind. I have only heard the term applied to a kind of uncertainty or ignorance rather than randomness, and am not sure how this concept applied to this ball-picking case. But I don't know much about this area, so this is probably ignorance.

http://en.wikipedia.org/wiki/Prior_probability

 

[SW VandeCarr]

SW,
I, too, am finding it hard to understand what this prior probability is and would appreciate to know what you had in mind. I have only heard the term applied to a kind of uncertainty or ignorance rather than randomness, and am not sure how this concept applied to this ball-picking case. But I don't know much about this area, so this is probably ignorance.

http://en.wikipedia.org/wiki/Prior_probability

What's the probability of getting three heads in a row tossing a fair coin?

 

[yossell]

In three tosses? 1/8.

But I still don't know what you mean by prior probability. You set me a standard probability question, and I worked it out. Presumably, not every answer to a probability question is a prior probability.

What concept are you getting at when you talk about the prior probability of drawing three successive reds from a bag? The formula you write down, (X/X+Y)^3, looks like the probability for getting three successive reds if you were to replace the ball each time, or if you were to do the picking on three different but similar ensembles. But I'm not getting the concept of prior probability. Sorry.

 

[SW VandeCarr]

Hi

So I am puzzled to what exactly (X/X+Y)^3 is the probability of?

Thanks

Suppose instead of removing the balls you put them back into the sack. What would be the probability of getting three red balls in a row if the ratio of red to all balls is 5/13?

Also, I assume you looked at my post above where I showed exactly how to calculate the probability of k reds in a row from any point in a sequence if the balls are not replaced. (post 7)

 

[SW VandeCarr]

In three tosses? 1/8.
Sorry.

The prior probability in this case is simply the probability of getting three red balls in a row at any point in the sequence before any balls are drawn. In addition to replacing the balls, I gave another example. If you randomly inserted the balls into a glass tube so the sequence was visible, what's the probability seeing of three red balls in a row?

If you draw balls out and don't replace them, you're creating a new set of probabilities each time. These are the posterior probabilities conditional on n(x) and n(y) balls already drawn. I did a calculation in post 7 based on starting with 5 reds out of 13 total and drawing a white ball first.

 

[SW VandeCarr]

Another way to address your question would be: Suppose someone else went through this exercise and you are unaware of the result. You're asked what the probability that three reds in a row were drawn is. What's your answer?Est tam facilis sic difficilis est.

 

[SW VandeCarr]

In three tosses? 1/8.

But I still don't know what you mean by prior probability. You set me a standard probability question, and I worked it out. Presumably, not every answer to a probability question is a prior probability.

Sorry I missed this. I don't see a reason why any unconditional probability could not be a prior probability for some relevant question involving a conditional probability. What kind of question are thinking about?

 

[SW VandeCarr]

Hi

One thing I know its not is the initital probability of the first 3 balls being red as this is (X')(X'-1)(X'-2)/[(X'+Y')(X'+Y'-1)(X'+Y'-2)]
Thanks

I didn't specifically address this either. Yes, this is correct given the first ball is red. This is still a conditional probability, not an unconditional prior which makes no assumptions about where the three ball sequence will occur.

Sorry for all the multiple posts, but I'm responding to two people and I was a bit rushed earlier. I do want to clarify any issues.

 

[yossell]

SW
thanks for the answers.
re 15. I wanted to know what you had in mind by a prior probability. You then surprised me by asking me a simple probability question. I honestly had no idea how this constituted an explanation or a hint about what prior probability was. It was just a probability question. From your answer in 15 it seems as though you think any answer to a probability question can be a prior probability - so I see nothing distinctive to the notion of probability. In particular, I don't see why the answer to the maestro's question, whatever it is, isn't also a prior probability.

I'm familiar with a sense of prior probabilities being a priori credences attached to certain hypotheses before evidence is in, expressing a kind of subjective uncertainty. This is what the wikipedia reference above suggested to me. Perhaps it is why I was uncertain how to interpret you.

Perhaps this is just semantics, so not important. However, when I try to follow your argument, you say things I can't understand.

Themaestro asked for the probability of drawing three balls. `If you simply want the prior probability before any draws, it's (X/X+Y)^3 assuming there are at least three X balls in the mix'. The prior probability of what before three draws? Of getting three draws before any draws? I.e. getting 3 red on the first three draws? Elsewhere, it seems in fact you mean a different game: the chance of getting three reds first go given that you put each one back. Fine - but it's just a different game; it's not something that emerges from the first game by using the word 'prior'.

You also write: `The prior probability in this case is simply the probability of getting three red balls in a row at any point in the sequence before any balls are drawn'. So there's another game - all the balls are already arranged in a sequence; our drawing is thought of not the typical random pulling of balls from a bag, but as the discovery of this sequence. `the chance that our sequence contains three red balls in a row' is now the prior probability? But now, this looks just like another way of thinking about the original question, with drawing balls modeled by picking of an arbitrary sequence. I don't see what this has to do with replacing balls (they're not in this game) or how you calculated (X/X+Y)^3 as the probability of this happening.

Sorry for the long post, I'm just trying to explain my confusion over this concept. I don't know if it really matters for the main calculation and I probably wouldn't bother if it didn't seem to me that themaestro was also asking the questions that are troubling me.

 

[SW VandeCarr]

SW
thanks for the answers.
I don't know if it really matters for the main calculation and I probably wouldn't bother if it didn't seem to me that themaestro was also asking the questions that are troubling me.

I think you are not getting the difference between actually drawing the balls in sequence and not replacing them, and the idea of a simple unconditional probability. In the former situation, you have a series of conditional probabilities which change with each draw. This was actually the OP's question. I think both of you understand that part.

A prior can be any relevant simple probability. I think the best example is randomly inserting balls(say by a machine that first mixes the balls up) into a glass tube. You see 13 balls (using the example in this thread) in a column. What's the probability that three red balls (X), out of five, are in sequence? It's (X/X+Y)^3=(5/13)^3=0.0569.

What's the probability of getting three red balls in a row beginning with having drawn a red ball in the first draw? It's 4/12*3/11=12/132=0.0909.

What's the probability of drawing three red balls in a row anywhere in the sequence after having drawn a red ball on the first draw?

 

[themaestro]

A prior can be any relevant simple probability. I think the best example is randomly inserting balls(say by a machine that first mixes the balls up) into a glass tube. You see 13 balls (using the example in this thread) in a column. What's the probability that three red balls (X), out of five, are in sequence? It's (X/X+Y)^3=(5/13)^3=0.0569.

this is what I do not think is right, I don't know what the answer should be in this example but looking at other examples. If X=2 and Y=3 then this equation gives
(X/X+Y)^3=(2/5)^3=0.008.
but infact the answer should be 0 as it is impossible for there to be 3 reds in a row if there are only 2 reds.

Another example if X=7 and Y=1 , the equation gives
(X/X+Y)^3=(7/8)^3=0.67.
This should equal 1 as there is only 1 non red ball so no matter where that ball is we are guarenteed to have 3 reds in a row

 

[SW VandeCarr]

this is what I do not think is right, I don't know what the answer should be in this example but looking at other examples. If X=2 and Y=3 then this equation gives
(X/X+Y)^3=(2/5)^3=0.008.
but infact the answer should be 0 as it is impossible for there to be 3 reds in a row if there are only 2 reds.

Another example if X=7 and Y=1 , the equation gives
(X/X+Y)^3=(7/8)^3=0.67.
This should equal 1 as there is only 1 non red ball so no matter where that ball is we are guarenteed to have 3 reds in a row

You're right. So what is the probability of getting three reds in a row before any balls are drawn and the run could occur anywhere? I was a using the formula for independent probabilities (for the prior) but they are not independent because of the kinds of constraints you point out. The algorithm is conditional on the existing state of the sequence. So is applying the formula for n(x), n(y)=0 valid for a k red sequence anywhere or only the first K balls drawn? Note that a sequence of size k can occur N-k ways within a sequence of size N.

Also note that my example of drawing balls from a sack and replacing them for a prior is valid since it is a simple probability and the balls can be redrawn. Without replacement, it becomes a conditional probability. However regarding the example of randomly placing X+Y balls in a glass tube, I was wrong to use this as an example of a prior probability. This is always a conditional probability. I think I have an answer to this problem, but I'll let you go first.

 

[techmologist]

Hi

This question has been driving me mad, hoping someone will be able to help me
The question is:

A bag contains X Red balls and Y Blue Balls. A ball is picked from the bag (at random) one at a time until all the balls have been picked. What is the Probability that 3 successive red balls will be picked?

Any help will be most appeciated
Thanks

If you are talking about picking balls without replacement, then it is possible to solve this problem by considering the complementary outcome:

How many ways to arrange X red balls and Y blue balls (all balls are distinguishable, by a number for instance) so that no more than two red balls are adjacent to each other.​

Start by considering how to do these arrangements when the X red balls are split up into k blocks of 1 or 2. Then sum over the allowable values of k.

If you are picking the balls with replacement, then there's the possibility that it could take infinitely long to pick all the balls at least once. That is a harder problem.

 

[SW VandeCarr]

If you are picking the balls with replacement, then there's the possibility that it could take infinitely long to pick all the balls at least once. That is a harder problem.

Why is it a harder problem? With replacement after each draw you have a constant probability of X/X+Y. It's no different than flipping coins except for different probabilities. The probability for k red balls in a row with replacement is (X/X+Y)^k where X is the total number of red and X+Y is the total of all balls.

 

[techmologist]

Why is it a harder problem? With replacement after each draw you have a constant probability of X/X+Y. It's no different than flipping coins except for different probabilities. The probability for k red balls in a row with replacement is (X/X+Y)^k where X is the total number of red and X+Y is the total of all balls.

No. With replacement, if you let X and Y grow to infinity in such a way that their ratio stays the same, then k red balls in a row will happen with probability 1. Same thing for a coin. If you keep flipping a coin forever, you will eventually get k heads in a row with probability 1, no matter how large k is. Your calculation is for k red balls in a row, starting with the first pick (or any other particular predetermined pick, such as the 23rd).

 

[SW VandeCarr]

No. With replacement, if you let X and Y grow to infinity in such a way that their ratio stays the same, then k red balls in a row will happen with probability 1. Same thing for a coin. If you keep flipping a coin forever, you will eventually get k heads in a row with probability 1, no matter how large k is. Your calculation is for k red balls in a row, starting with the first pick (or any other particular predetermined pick, such as the 23rd).

The question here is if I reach into a bag and randomly pick three balls with replacement, what is the probability that they will all be red given reds are X/X+Y of the total. I only posed this as an example of a simple probability as opposed to a conditional probability.

The question I last posed to the OP was if 13 balls were randomly inserted into a clear glass tube, what is probability of seeing three red balls in a row anywhere in the sequence given five balls are red. It's analogous to asking the probability of a series of k heads in a row in N tosses of a fair coin, k<N.

Yes, the cumulative probability of drawing three (or any number) of reds in a row with replacement from a finite total number (where at least one ball is red) approaches unity as the number of draws approaches infinity. I'm not sure that this observation is particularly helpful to this discussion.

 

[techmologist]

The question here is if I reach into a bag and randomly pick three balls with replacement, what is the probability that they will all be red given reds are X/X+Y of the total. I only posed this as an example of a simple probability as opposed to a conditional probability.

Okay. I thought you were offering X^k/(X+Y)^k as a solution to the OP's problem, assuming you draw with replacement. It is not the solution, whether it is assumed that balls are drawn with replacement or without. But you were just using a different problem as an illustration for some point you were making. My mistake.

After reading themaestro's post #19, I'm 95% certain themaestro meant the balls are drawn without replacement, but I thought I'd mention the other possibility just in case. Perhaps themaestro could confirm that for us. With replacement, the problem is hard. You don't know when the process will end, all X+Y balls having been drawn at least once. All you know is that it ends eventually, with probability 1.

The question I last posed to the OP was if 13 balls were randomly inserted into a clear glass tube, what is probability of seeing three red balls in a row anywhere in the sequence given five balls are red.

Yes, this is the essence of the OP's problem as I understand it. For X=5 and Y=8, I get a probability of
1959552000/6227020800, or approximately 31.4%.

 

[SW VandeCarr]

Yes, this is the essence of the OP's problem as I understand it. For X=5 and Y=8, I get a probability of
1959552000/6227020800, or approximately 31.4%.

The original problem was the probability of k reds in a row in the next three draws given the number of reds n(x) and blues n(y) already drawn. I think we solved that problem with the algorithm described in previous posts.

The present problem is the probability of k reds in a row at any location in a sequence of N=X+Y. I don't know how you got your result, but it seems way too high for k=3, n(x)=5 and N=13.

I gave a clue to my approach in post 20. The number of ways a k ball sequence can occur in a sequence of length N is N-k+1. For a three ball sequence its: 123,234,345,456,567,678,789,89 10, 9 10 11, 10 11 12, 11 12 13. That's 13-3+1=11 ways. Now, since there are five reds, the 'first' red ball of will start one of these sequences with P=11/13. The next two red balls have the probabilities of immediately following with probabilities 4/12 and 3/11, so P(k|N,n(x))=13*4/12*3/11=132/1716= 0.0769

Note: I erroneously said the number possible ways a k sequence can occur in a sequence of size N was N-k in post 20. In fact it's N-k+1. I briefly posted the incorrect calculation here but corrected it.

 

[yossell]

Now, since there are five reds, the 'first' red ball of will start one of these sequences with P=11/13.

What does this mean?

The question I last posed to the OP was if 13 balls were randomly inserted into a clear glass tube, what is probability of seeing three red balls in a row anywhere in the sequence given five balls are red. It's analogous to asking the probability of a series of k heads in a row in N tosses of a fair coin, k<N.9

If you're taking those balls from somewhere, from some bag, it's not.

 

[techmologist]

I gave a clue to my approach in post 20. The number of ways a k ball sequence can occur in a sequence of length N is N-k+1. For a three ball sequence its: 123,234,345,456,567,678,789,89 10, 9 10 11, 10 11 12, 11 12 13. That's 13-3+1=11 ways. Now, since there are five reds, the 'first' red ball of will start one of these sequences with P=11/13. The next two red balls have the probabilities of immediately following with probabilities 4/12 and 3/11, so P(k|N,n(x))=11/13*4/12*3/11=132/1716= 0.0769

Okay. In post #19, themaestro gave as a special case of his problem, X=7 red balls and Y=1 blue balls, for a total of N=8 balls. He correctly pointed out that if you have all these balls in a tube, no matter where you put that single blue ball, there will always be three red balls in a row somewhere. So that means the probability is 1. For N=8, k=3, and 7 red balls, the method you just used gives 6/8*6/7*5/6, which is not 1. Did I apply your method incorrectly?

 

[SW VandeCarr]

Okay. In post #19, themaestro gave as a special case of his problem, X=7 red balls and Y=1 blue balls, for a total of N=8 balls. He correctly pointed out that if you have all these balls in a tube, no matter where you put that single blue ball, there will always be three red balls in a row somewhere. So that means the probability is 1. For N=8, k=3, and 7 red balls, the method you just used gives 6/8*6/7*5/6, which is not 1. Did I apply your method incorrectly?

I've been reviewing my method. I'm concluding that the only way to avoid nonsensical answers for extreme cases where probabilities can be unity for finite N is to evaluate all combinations of a given number of red and blue balls. In this example the probability that the first draw is red is 7/8. If the next ball is blue then you have 7/7. But if it's not you still have 6/7 and so on. Clearly any combination of seven red and one blue results in sequences larger than 3, so the method breaks down.

 

[CRGreathouse]

After reading themaestro's post #19, I'm 95% certain themaestro meant the balls are drawn without replacement, but I thought I'd mention the other possibility just in case. Perhaps themaestro could confirm that for us. With replacement, the problem is hard. You don't know when the process will end, all X+Y balls having been drawn at least once. All you know is that it ends eventually, with probability 1.

You're right, that problem is hard. (I didn't think so at first glance.) Here's Mathematica code that solves the problem, if I haven't made any mistakes:

P[r_,0,s_] := 0 /; s < 3
P[0,b_,s_] := 0 /; s < 3
P[r_,b_,s_] := 1 /; s >= 3
P[r_,b_,0] := (
	P[r-1,b,1]*r + P[r,b-1,0]*b + (
		P[r-1,b,2]*r/(R+B) + P[r,b-1,0]*b/(R+B) + (
			R/(R+B) + P[r,b-1,0]*b/(R+B)
		)*(R-r)/(R+B)
	)*(R-r)
) * (b B^2-b B r+3 b B R+b r^2-3 b r R+3 b R^2+B^2 r-B r^2+3 B r R+R^3)/(b B-b r+2 b R+B r+R^2)^2

P[r_,b_,1] := P[r-1,b,2]*r/(R+B) + P[r,b,2]*(R-r)/(R+B) + P[r,b-1,0]*b/(R+B) + P[r,b,0]*(B-b)/(R+B)
P[r_,b_,2] := R/(R+B) + P[r,b-1,0]*b/(R+B) + P[r,b,0]*(B-b)/(R+B)

R = 5; B = 8; P[5, 8, 0]

Unfortunately Mathematica doesn't seem to use memoization here, since it hasn't found the answer yet (though it can handle small instances). There are only 3(5 + 1)(8 + 1) = 162 different function calls in this case, so if it was memoizing it would be pretty quick.

Code overview: R is the number of red balls, B is the number of nonred, r is the number of unpicked red, b is the number of unpicked nonred, and s is the number of consecutive red balls that have been previously pulled.

Edit: the code doesn't work properly because it doesn't handle the cases r = 0, b > 0 or r > 0, b = 0 properly. Maybe I'll work on this later.

 

[techmologist]

You're right, that problem is hard. (I didn't think so at first glance.) Here's Mathematica code that solves the problem, if I haven't made any mistakes:

P[r_,0,s_] := 0 /; s < 3
P[0,b_,s_] := 0 /; s < 3
P[r_,b_,s_] := 1 /; s >= 3
P[r_,b_,0] := (
	P[r-1,b,1]*r + P[r,b-1,0]*b + (
		P[r-1,b,2]*r/(R+B) + P[r,b-1,0]*b/(R+B) + (
			R/(R+B) + P[r,b-1,0]*b/(R+B)
		)*(R-r)/(R+B)
	)*(R-r)
) * (b B^2-b B r+3 b B R+b r^2-3 b r R+3 b R^2+B^2 r-B r^2+3 B r R+R^3)/(b B-b r+2 b R+B r+R^2)^2

P[r_,b_,1] := P[r-1,b,2]*r/(R+B) + P[r,b,2]*(R-r)/(R+B) + P[r,b-1,0]*b/(R+B) + P[r,b,0]*(B-b)/(R+B)
P[r_,b_,2] := R/(R+B) + P[r,b-1,0]*b/(R+B) + P[r,b,0]*(B-b)/(R+B)

R = 5; B = 8; P[5, 8, 0]

Unfortunately Mathematica doesn't seem to use memoization here, since it hasn't found the answer yet (though it can handle small instances). There are only 3(5 + 1)(8 + 1) = 162 different function calls in this case, so if it was memoizing it would be pretty quick.

Code overview: R is the number of red balls, B is the number of nonred, r is the number of unpicked red, b is the number of unpicked nonred, and s is the number of consecutive red balls that have been previously pulled.

Edit: the code doesn't work properly because it doesn't handle the cases r = 0, b > 0 or r > 0, b = 0 properly. Maybe I'll work on this later.

Cool. Thanks for taking a look at it, CRGreathouse. I haven't even attempted the problem with replacement. It looks like a doozy.

I'm going to go ahead and post my solution to the easier problem, which I feel sure is what the OP was asking. I was going to give him a chance to ask questions first, but it's been over 24 hrs, so I'll just put a spoiler warning on it.

 

[techmologist]

SPOILER ALERT: themaestro, if you're still trying to work this problem out for yourself, don't read what follows too carefully :)


How many ways can you arrange X red balls and Y blue balls so that no more than two red balls are adjacent to each other? The balls are assumed to be distinguishable (they can have numbers on them, for example). This is equivalent to asking how many ways you can draw all X+Y balls out of a bag without replacement and never get three consecutive reds.

We know that all red balls come in blocks of 1 or 2 balls each. Let's assume the reds are separated into j blocks. This determines how many of the blocks have 2 balls, and how many have 1 ball. If there are t blocks of 2, then

j - t + 2*t = j + t = X ,or t = X-j

So there are j total blocks, X-j of which are blocks of 2. These can be arranged in (j choose (X-j)) ways. And then X red balls themselves can then be numbered in X! ways.

To make sure these j blocks stay separated, we need to fix the positions of j-1 of the blue balls to act as separators in between the blocks. This leaves Y-j+1 blue balls to be freely arranged along with the j blocks. This can be done in ((Y-j+1 + j) choose j), or ((Y+1) choose j) ways. And then the blue balls can be numbered in Y! ways.

Thus, when it is required that the red balls are separated into exactly j blocks, there are

X!*Y!*(j choose X-j)*(Y+1 choose j)

ways of doing this. To get the final answer, we need to sum over the allowable values of j. The least j can be is ceiling(X/2). Clearly, it can't be any greater than X. Also, it can't be any greater than Y+1, because a blue ball is needed to separate blocks of red balls.

Therefore, the number of ways of drawing all X+Y balls without replacement and getting no more than two reds in a row is

$$X!Y!\sum_{j=\lceil X/2 \rceil}^{\min(X,Y+1)}\binom{j}{X-j}\binom{Y+1}{j}$$

To get the probability, just divide by (X+Y)!:

$$\frac{1}{\binom{X+Y}{X}}\sum_{j=\lceil X/2 \rceil}^{\min(X,Y+1)}\binom{j}{X-j}\binom{Y+1}{j}$$

 

[themaestro]

thanks techmologist, will test this to see what results it gives. The logic looks to be sound as far as I can tell

 

[techmologist]

thanks techmologist, will test this to see what results it gives. The logic looks to be sound as far as I can tell

No problem. If that works to your satisfaction, you might try solving this very similar problem:

What is the probability that an Ace is next to a King somewhere in a well-shuffled deck?​

First, just take a guess. I think the answer is surprising. I encountered this problem several months ago on Jeffrey Shallit's blog, Recursivity:

http://recursed.blogspot.com/2010/01/neat-problem-on-card-arrangements.html

The solution posted there is due to Ian Goulden. That's where I got the idea for the solution to your problem.

 

[SW VandeCarr]

I found the following formula online. It breaks down at extreme values, but seems to work if you simply take values above 1 as equal to probability one. Interestingly, I get the same value using a method somewhat like I posted above for k=3 m=5 and n=13. The trick is to calculate the sequential probability and multiply by n-k+1. I thought the resulting probability was too high, but I get the same result using both formulas.

P(k|n,m)= (n-k+1)!(m)!/(m-k)!(n)!=11!*5!/2!*13!=60/156=0.3846

My method, which I wanted to use, but thought the result was too high:

P(k|n,m)=(n-k+1)(5/13)(4/12)(3/11)= 11*(60/1716)=0.3846http://groups.google.co.bw/group/sci.math/msg/1dd6c23b10534642?dmode=source