Probability question... We have a certain system evolving at work, and I've noticed some patterns occurring. I'm wondering if anyone can tell me the probabilities associated here.
Tim
Uhhh... were you awake during 7th grade math?
Bob
You've "noticed some patterns" in a "system evolving at work"?
The tail of the "g" in "fog creek software"
"We have a certain system evolving at work, and I've noticed some patterns occurring."
www.MarkTAW.com
>Now, what if I tell you that out of those 10 trials it comes up heads >exactly 5 times, and tails the other 5 times?
a2800276
> I could just count the total number of solutions
a2800276
> what if I tell you that out of those 10
Obviously my work doesn't involve flipping coins, but it seemed an easier way of explaining the situation than going into the details of the wireless network handshaking protocols.
Tim
For the first question, it's just a matter of counting, although there's tricks you can use to make that easier. I can't immediately think of a nice formula (although I expect if you look in a combinatorics textbook you may find some suitable generalisation), so you'll have to do it by cases and think hard to make sure you're never counting the same combination twice.
Matt
Ah yes, a2800276's approach is good, conditioning on outcome the first toss. This could give you a recurrence relation to solve for some sort of formula (although if you just want the answer to this particular case may aswell just count)
Matt
"Actually, given this is a programmer's forum not a mathematician's one"
Tom H
>> "Actually, given this is a programmer's forum not a mathematician's one"
anon
Actually I just saw the bit where he was asking for enlightenment about the calculations. Fair enough.
Matt
I have a fricking BS in Maths! and will have a masters in another year. I was just saying that if you want an immediate answer to that particular problem, and given the tools/skills available to you, brute force would be the way to go. Looks like I didn't read to OP carefully enough though
Matt
4 heads in a row out of 10 flips
This is why I am not a mathematician
Aha! as I suspected after playing around with it for a bit, finding a closed form for this isn't easy.
Matt
Thanks a bunch Matt.
Tim
http://www.amazon.com/exec/obidos/tg/detail/-/0471257087/qid=1086006247/sr=8-1/ref=pd_ka_1/102-8744697-3422511?v=glance&s=books&n=507846
Danil
Sidebar - is anybody else amused by the notion that "staying awake in 7th grade math" would enlighten one about processes involving Fibonacci k-step numbers and the Euler-Mascheroni constant?
Danil
Yeah wolfram is great for reference - trying to actually learn new material from it would be pretty damn hard though. It's just a good summary of mathematical results and definitions
Matt
Danil, what part of "what are the odds of getting 4 in a row?" involves "Fibonacci k-step numbers" [sic]?
Bob
The OP's question comes very close to the gambler's fallacy. If you are flipping a coin, that has a 50% chance of heads or tails, then each trial (each flip) is completely independent of the others.
AllanL5
Agreed Allan, but I don't think that applies here.
Tim
The first marble has 5/10 chance of being white. The next 4/10, then 3/10, then 2/10. Multiply these together, you get .012. So you have a 1.2% chance of 4 marbles in a row for the condition of it being the first 4 marbles.
AllanL5
Probability to get heads is 1/2. Probability to get heads 4 times in a row = 1/2^4. Probability to get 4 in a row in a sequence of 10 is 7 x 1/2^4 = 7/16 (if you didn't hit 4 in a row to the 7th try then you missed - ie you have 7 trys to get 4 in a row)
Dino
So the probability of getting 6 in a row is 7 * 1/2^6 = 7/64?
Edward
What we're saying is - the general case is a fairly hard problem in combinatorics / number theory. Solving a particular case will just involve doing some fairly ugly/boring calculations, and for what it's worth you may aswell just brute-force it, but the general case is certainly non-trivial
Matt
The probability to get 6 in a row out of 10 is
Dino
Oh, and out of 10 flips you'll get any combination of heads and tails which is physically possible. It is random after all.
Dino
May I switch to meta issues? This is an interesting thread. The problem is certainly nontrivial and to anyone who has dealt with serial transmission of binary data, is instantly recognizable.
Dennis Atkins
Hasty, hasty, hast ....
Dino
Dennis, it's only interesting if you're not interested in getting an answer ;-)
Tim
n in a row out of m tries:
Dino
But I think you are ignoring the bag-like nature of the thing. Once you've pulled an item of a particular type out, the probability of getting another of that type is reduced, because there are fewer left.
Tom
(As in, I can't work out how many N-bit values have exactly M bits set, contiguous or otherwise.)
Tom
Actually, I think I am wrong. Certain positions of the "left over" bits will put a contiguous set somewhere other than where you first thought of (as it were). So it isn't quite that simple.
Tom
Continuing the meta thread
Danil
Tom, the key phrase in looking up solutions for bags of marbles is "without replacement".
Danil
I don't know which feeling is stronger.
Tim
Quickly ... I hope I don't make too many mistakes .... :-)
Dino
The real world is seldom really random. Are you sure there isn't some bias in your results or is it really just coin flipping?
MilesArcher
OK, "Let's say you're flipping a coin 10 times. What is the probability of getting heads exactly 4 times in a row?"
Dennis Atkins
My math is screwy - I didn't consider that the sequence can be in different positions as well, or that if it is on the edge of the sequence, there is an implied 0 on one side and we are dealing with 5 variable bits.
Dennis Atkins
Danil, I agree with your comments on the meta thread.
Dennis Atkins
But the thing on the superficially similar problem is that coin toss probability is what most people are familiar with from high school. Probability is really really difficult - harder than calculus. The reason is precisely this - it is very easy to follow the wrong line of reasoning and have it look correct. It is extremely hard to get the right odds unless you do brute force or empirical measurements to know in advance what the right answer is.
Dennis Atkins
Damn, what about:
Dennis Atkins
Dennis, for this problem I'm limited to an equal number of 1's and 0's (or black and white marbles).
Tim
OK, well here are your cases:
Dennis Atkins
For 20 bits with 10 1 and 10 0, so you can have 2 chains of 4 and they can straddle the middle, it's not then a case of extrapolating from these results.
Dennis Atkins
Yep, I'm just in the middle of it now. I'm stuck on some time-optimization stuff, but hoping to get it done soon.
Tim
Some might find this interesting...it's been dumbed down a little, but kind of neat
Tim
Let me know if you get 48025.
Dennis Atkins
Which would be 4.58% of the cases.
Dennis Atkins
BTW, use C - it runs here in just a few milliseconds.
Dennis Atkins
Heh, I left out a few, it's actually 52,580 cases or 5.01442% of all possibilities. Do you get the same?
Dennis Atkins
Work exploded here. I'll post results ASAP.
Tim
This looks like a case where using resampling would be the way to figure out your answer. It eliminates the problem of picking the correct statistical formula, along with that formula's hidden assumptions. I know Julian Simon wrote a couple of books on the subject.
J. Lee
The OP was talking about Bernoulli's Binomail Probabiliites
Bella
Okay, I decided to try writing a little algorithm to calculate these numbers of runs recursively. Make of it what you will:
Matt
If you're interested in my mathematical justification for that algorithm by the way, just ask :-)
Matt
The probability to NOT get k heads sequence in a n toss is:
Dino
I guess Tim was a student scamming for homework answers. And one who can't even program. I was such a fool! When will I learn?
Dennis "Dumbass Patsy Fool" Atkins
Fog Creek Home |