Probability of 3 successive ball picks?

[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