visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
315 experts, 1193 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Algorithms :: Maths :: Sequence
By: Squibi U.S.A.  Date: 05/02/2003 00:00:00  English  Points: 500 Status: Answered
Quality : Excellent
Hi, experts!
Wonder if any one could provide formula for me:
Lets say i've got a n lenght row of random 0 and 1 both 50% percent possible. What is a probability, that i'll meet k-lenght sequence of 0?
Thanks for help.
By: VGR Date: 05/02/2003 18:53:00 English  Type : Comment
the probability of k zeroes following each other in a big chain of 50%-probable zeroes and ones answers to this event :

first 0 : 50% chance (probability)
second 0 in a row : 50%² (independent 50% events) = 25%
[...]
thus
k-th zero in a row : (50%)^k = 0,5^k

application :
k=3
P=12,5% (1/8)
You may convince of this by looking exhaustively at the possible combinations of 0s and 1s of a 3-long row, and count the occurence of the string '000' ;-)
Help : they are 000, 001, 010, 011, 100, 101, 110, 111, cardinal of the ensemble is 8, number of '000' is one, thus probability = 1/8
CQFD

application numérique pour k=10 : P = 0,0976 %

easy one. Gimme the 400 points 8-))
By: Squibi Date: 05/02/2003 18:56:00 English  Type : Comment
surely easy.
what do you say if that sequence started not from first number?
By: Squibi Date: 06/02/2003 07:00:00 English  Type : Comment
Let me explain task more strictly:
I need a formula for probability of meeting x sequences of 0 in n lenght string of 0 and 1 (would be glad, if i can change probability of appearing 0 or 1 - not 50%)
Thanks for responce.
By: VGR Date: 06/02/2003 07:06:00 English  Type : Comment
it doesnt change anything
the probability is position-independant
the fact that other 0s or 1s follow or precede the substring is meaningless

all events are independent

your answer is NOT combinatory (IMHO), and doesn't depend on n (except that k<=n, obviously) but on k only.

regards,
By: VGR Date: 06/02/2003 07:07:00 English  Type : Comment
and if you change the individual probability of the "1 showing" event ("0 showing" being it's complement, it's probability is 1-P("1 showing") so useless to explicit)

it doesn't matter, as long as you can write :
P("k 0 in a row") = P("0 showing")^k
By: Squibi Date: 06/02/2003 07:34:00 English  Type : Comment
>all events are independent
So, you want to say, that probability of meeteng 5 zeros in 6 row and it 100 row are she same? Can you prove?
By: VGR Date: 06/02/2003 07:38:00 English  Type : Comment
***if and only if*** the event of meeting 0 or 1 are independent of previous 0s and 1s, yes I can prove it.

let's say you have an existing k-length string of 0s and 1s, potentially all 0s with probability explained before, P(0)^k.
What is then the probability of 0 showing at position (k+1) ? 50% or P(0)

Thus p("k+1 - length of 0s") = P(0)^k * P(0) = P(0)^(k+1)

CQFD it's proved
By: Squibi Date: 06/02/2003 07:59:00 English  Type : Comment
Thats true - all events are independent, and the probability of each 0.5 but the probability of the whole situation depends on lenght - n. The problem seems to me to be in determining the number of "successive" cases in dependence of n and k. Your P(0)^(k+1) is true in case k = n, if n >k it will differ.
By: VGR Date: 06/02/2003 21:38:00 English  Type : Comment
not at all.

the probavility dpeends on K, not on N

proof : it's like playing (betting) at the LOTO : the probability of a draw 1,2,3,4,5,6 is exactly the same as the probability of any other combination, how "more probable" they could look.



Sorry but I don't think you'll get a better answer than mine.

P("k times 0 in a row") = P(0)^k

dot.
By: TheFalklands Date: 06/02/2003 23:54:00 English  Type : Comment
but if you have 1,000 numbers the chances of getting two 1's in a row is very high - since for this to happen you would need to never get two ones in a row, but if you have just 2 numbers then it is 1/4.
By: Squibi Date: 07/02/2003 00:00:00 English  Type : Comment
That's what i'm talking about, TFL. The question is - how much variants we have?
By: VGR Date: 07/02/2003 00:10:00 English  Type : Comment
exactly, but it doesn't change anything

Given we have 1000 numbers (binary digits, bits, 0 or 1) drawn at random

P("all 0s")=P(0)^1000
P("at least a 1")=1-P("not even a 1")=1-P("all 0s")=1-P(0)^1000 which is in fact very near from 1, whatever P(0) is (even P(0)=70% produces P(0)^1000 = 1,25 . 10^-155 which is neglectable)

this is pure events probability, not combinatory

but what I said above stays true. You asked for the probability of a sequence of k zeroes in a n-draw

What I gave you is the proba of ***at least*** k zeroes in a row anywhere in a sample of n draws, not the proba of exactly k zeroes in a row and then (n-k) ones, and no more the exact probability a a complete sample of size n

I'm not sure to be clear enough.

Not also that I may make a mistake, and also that you make me doubt a bit. Anyway, the first "intuition" is always the good one AFAIK.
By: VGR Date: 07/02/2003 00:47:00 English  Type : Comment

You made me doubt enough 8-))

if you want, let's take a numerical example like I did above :
n=3
k=0,1,2,3

Possibilities are written above : 000, 001, 010, 011, 100, 101, 110, 111

Thus

P("3 zeroes in a row amongst 3")=P(0)³ = 1/8 if P(0) is 50%
This is coherent with experience.

P("2 zeroes in a row amongst 3")=3/8
There seems to be a combinatory part, may-be my answer above was incomplete...

**i give up, I obviously made a big mistake and I don't have the time to find it. Arrangements or permutations, I can't decide and I'm fed up with computing factorials by hand and in a hurry***

sorry
By: Squibi Date: 07/02/2003 01:09:00 English  Type : Comment
it's interesting and may be a way to find a solution.
Seems to me that to compute the probability we need to find all the combinations count and "successive" combinations count - right? So good idea in your last post, that "succesives" count is the sum of P(0)^k + all the combinations os sequences from k+1 to n. May be this will lead to formula?
To make it more clear: "successives" for last example 001, 100 ( P(0)^k-1 ) and 000 which is solution for k = 3.
By: sumotimor Date: 07/02/2003 01:36:00 English  Type : Comment
The binomial formula will give you the probability that any x out of n are selected given an independent probability of p that stays constant throughout and only 2 catagories of outcomes (0 and 1) are possible.

The formula is
P(x)=[(n!)/(n-x)!(x!)] * p^x * (p-1)^(n-x)

***[In your example, your k would equal the formula's n and your n would equal your the formula's x]***

so
if n=10 x=4 p=.50
then P(x)=.20507

Now, .20507 is the probability that any combination of 5 0's will be picked out of 10.
But we want the number of 4 sequences.
Well, there are (n-x)+1 possible sequences of 4.
n1 n2 n3 n4 n5 n6 n7 n8 n9 n10
1. n1 n2 n3 n4
2. n2 n3 n4 n5
3. n3 n4 n5 n6 . . .
10. n7 n8 n9 n10

So only 7 of 210 combinations are acceptable.
So I propose that dividing P(x) by (n-x)+1 will give the answer (.20507/7)=0.2929
By: sumotimor Date: 07/02/2003 01:37:00 English  Type : Comment
Uh oh. .20507/7 =.0292957
By: sumotimor Date: 07/02/2003 01:47:00 English  Type : Comment
Meant .20507 is the probability that **4** 0's will be picked out of 10 (not 5).
There are 7 different sequences of 4 in 10.
(Sorry for the typos. It is hard to type with freezing fingers -- cold office building!)
By: Squibi Date: 07/02/2003 01:47:00 English  Type : Comment
>P(x)=[(n!)/(n-x)!(x!)] * p^x * (p-1)^(n-x)
Seemes like Puassons formula. As far as i know this will give me the probability of having x zeros of n independent of their sequence. Or am i mistaken?
By: Squibi Date: 07/02/2003 01:55:00 English  Type : Comment
So you think result will be:
P(x)=[(n!)/(n-x)!(x!)] * p^x * (p-1)^(n-x) / (n-x)+1 ?
By: sumotimor Date: 07/02/2003 01:56:00 English  Type : Comment
It is the binonmial formula, not the Poisson (sp?) formula (something different)
Yes, it is independent of sequences, but if you read on you will see that I propose dividing P(x) by the number of sequences.

By: Squibi Date: 07/02/2003 02:02:00 English  Type : Comment
As follows from VGR's last post correct answer for n = 3 and x = 2 equals to 3/8.
That P(x)=[(n!)/(n-x)!(x!)] * p^x * (p-1)^(n-x) / (n-x)+1
gives me 1.875
by the way, (p-1) should be changed to (1-p)
By: sumotimor Date: 07/02/2003 02:03:00 English  Type : Comment
Technically, P(x)=[(n!)/(n-x)!(x!)] * p^x * (p-1)^(n-x) / ((n-x)+1)
-- watch out for the order of operation rules at the end!

Either that or the number of sequences divided by the number of combinations (n-x-1)/(n!/((n-x)!x!)), since 1 and 0 have equal probability of being selected.
By: Squibi Date: 07/02/2003 02:13:00 English  Type : Comment
Imagine that situation:
0001000
3 zeros out of 7 which are not counted by (n-x)+1. Seemes like we need another formula to "filter" succeeds...
By: Squibi Date: 07/02/2003 02:15:00 English  Type : Comment
>Well, there are (n-x)+1 possible sequences of 4.
>n1 n2 n3 n4 n5 n6 n7 n8 n9 n10
>1. n1 n2 n3 n4
>2. n2 n3 n4 n5
>3. n3 n4 n5 n6 . . .
>10. n7 n8 n9 n10

>So only 7 of 210 combinations are acceptable

Seemes we had to add to each of seven all the combinations of remaining digits - you don't think so?
By: sumotimor Date: 07/02/2003 02:24:00 English  Type : Comment
Wouldn't a "sequence" of 0's
be 4 0's together: i.e. 0000100?
if you want any four 0's then the binomial formula by itself will give you want.
If you want any four or more, then the binomial formula
for P(x)+P(x+1)+P(x+2) . . . P(n)
is what you need.
But 0001000 is not defined as a sequence of 4 0's.
By: Squibi Date: 07/02/2003 02:24:00 English  Type : Comment
i think your formula should be multiplied by p ^ (x-n)...
By: sumotimor Date: 07/02/2003 02:28:00 English  Type : Comment
combinations
1. n1 n2 n3 n4
2. n2 n3 n4 n5
3. n3 n4 n5 n6
4. n4 n5 n6 n7
5. n5 n6 n7 n8
6. n6 n7 n8 n9
7. n7 n8 n9 n10

All 7 possible sequences 4 of 10 numbers.
By: Squibi Date: 07/02/2003 02:31:00 English  Type : Comment
Ok, in 4 out of 7 there are:
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
all will be the correct, since you count them only once - see what i mean? for each "successful" combination there will be p^(x-n) variants....
By: Squibi Date: 07/02/2003 02:36:00 English  Type : Comment
and even this is not correct, cause
0000000
should be counted as one single successive variant, and then formula will be multiplyed, i'll get it counted 7 times...
By: VGR Date: 07/02/2003 02:38:00 English  Type : Answer
just two penny's :
1) Poisson ("fish" in French ;-)
2) this problem could be related to "runs" problematic

1100001111100 is composed of four runs

there are specific algorithms and rules for this kind of stuff
By: sumotimor Date: 07/02/2003 02:41:00 English  Type : Comment
Questions
1. <<i think your formula should be multiplied by p ^ (x-n)...>>
Which formula? The binomial formula is correct. You can find it in any statistical text book.

2. What type of pattern of 0's are you looking for? Are you looking for any x 0's or a sequence of exactly x 0's or a sequence of (x, x+1, x+2 . . . ) to x=n?

I want to help you out and I want to run some simulations to see get an estimate, but I need to know the answer to #2 before I can do so.
By: sumotimor Date: 07/02/2003 02:51:00 English  Type : Comment
<<Ok, in 4 out of 7 there are:
0000000
0000001
0000010 . . .>>

Ah! I was assuming only a sequence of exactly 4.
0000111111
1000011111
1100001111

I still believe that finding the possible combinations with the binomial formula for all probabilitys of x to x=n and then adjusting that number for the number of possible sequences is the key. The tricky part now is county the sequences. In the example of x=4 and n=10, the probability that at least 4 0's will occur is .828. Now just need to figure out how to get the number of possible sequences given that other runs of 0's may occur.
By: Squibi Date: 07/02/2003 02:55:00 English  Type : Comment
>1) Poisson ("fish" in French ;-)
I'm tempted to give you a point's for that answer right now :)
>2) this problem could be related to "runs" problematic
Well, i'm seeking formula, not algo....

>Which formula? The binomial formula is correct. You can find it in any statistical text book.
binomial divided by (n-x+1)

>2. What type of pattern of 0's are you looking for? Are you looking for any x 0's or a sequence of exactly x 0's or a sequence of (x, x+1, x+2 . . . ) to x=n?
i need to find a probability of meeting x zeros. So i think any x+1 will include my variant...
By: sumotimor Date: 07/02/2003 03:11:00 English  Type : Comment
For n=10 and x=4 (need to meet 4 0's in 10 numbers)
then
0000111111
0001011111
0101010101
0000111000
all meet your criteria?

If so, then your work is cut out for you.

In the n=10, n=4 example use the binomial formula to find
P(4)+P(5)+P(6)+P(7)+P(8)+P(9)+P(10)=.828.
By: sumotimor Date: 07/02/2003 03:17:00 English  Type : Comment
For n=10 and x=4 (need to meet 4 0's in 10 numbers)
then
0000111111
0001011111
0101010101
0000111000
all meet your criteria?

If so, then your work is cut out for you.

In the n=10, n=4 example use the binomial formula to find
P(4)+P(5)+P(6)+P(7)+P(8)+P(9)+P(10)=.828.
By: sumotimor Date: 07/02/2003 03:20:00 English  Type : Comment
(Continued). In that case, your example is a classic binomial probability problem, and you don't have to do any adjustments. The other stuff was because I thought you needed exactly 4 0's in a row.
By: GW Date: 07/02/2003 03:46:00 English  Type : Comment
Squibi,
This is not just a classic binomial problem, it is complicated.

GW
By: sumotimor Date: 07/02/2003 03:56:00 English  Type : Comment
GW,
It IS a binomial problem if he wants the probability of having x or x+ 0's out of n. But if he wants actual "sequences" (i.e. 0's in a row) then it is not.

It meets the criteria for a binomial experiement.
1. Fixed number of trials (yes, he has "an n length row")
2. Trials must be independent (yes, the probability (.5 in this case) of selecting 0 or 1 is not dependent on the prior selection.
3. Each trial must have 2 catagories (yes, 0 and 1).
4. The probabilites must remain constant for each trial. (yes, from information, probability is always .50).


But you are correct that it is complicated if he is actually looking for sequences of 0's.
That is why I said, but if the examples that I gave 2 comments before yours meet his criteria, then it is a binomial problem.
But I am confused because he complained that
0001000 would not be selected as a sequence earlier (or that is how I interpreted it).

Then he also gave
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
as examples. So if 10000111 does not satisfiy his criteria (i.e. the criteria is is what is the probability of x 0's before hitting a 1), then the probability no longer depends on n but then becomes .50^x. Probability of selecting 3 zeros would be .50^3=.125. Probability of 4,5, or 100 zeros after that would be irrelevant because they would be subsets of the .125.

And if he means 1000010010 as acceptable for a sequence of 4, then yes, it is extremely complicated.
By: Squibi Date: 07/02/2003 04:47:00 English  Type : Comment
No,
from these:
For n=10 and x=4 (need to meet 4 0's in 10 numbers)
then
*0000111111
0001011111
0101010101
*0000111000
all meet your criteria?
my criteria meet to marked *
By: Squibi Date: 07/02/2003 04:48:00 English  Type : Comment
> This is not just a classic binomial problem, it is complicated.

Hi, GW ! That's why i ask experts. Question is - can it be counted with formula depending on p, x and n ?
By: GW Date: 07/02/2003 05:09:00 English  Type : Comment
sumotimor,
If the criteria is " what is the probability of x 0's before hitting a 1" then this problem is trivial and 400 points strikes me as a very large number of points for such a simple problem.
I think we should ask Zmey2 to define his problem more precisely

Zmey2,
(1) Are these the types of strings that you are looking at 0000011, 0000100, 00000101 (i.e.what is the probability of k 0's before hitting a 1).

(2) You question could also be interpreted as what is the probability of a binary string of length n having a sequence of 0's of length k in it.

Could you clarify please?

GwynforWeb









GwynforWeb
By: TheFalklands Date: 07/02/2003 05:51:00 English  Type : Comment
From 'Probability' by James R Gray

in this book a complicated recurrence relation is calculated

v(x) = probability of no run of r success in x tosses, where p = prob success and q = prob failure

v(n) = v(n-1) - qp^rv(n-r-1) + qp^(r+1)v(n-r-2)

and

v(0)=v(1)=v(2)=....=v(r-1)

v(r)=1-p^r

v(r+1)= 1 - 2qp^r


EXAMPLE

what is the probability that ten tosses of a coin will give at least one run of four heads

vn = prob that n trials contain no such run

vr = 1 - (.5)^r


v0=v1=v2=v3=1

v4 = 1 - (.5)^5 = 15/16

v5 = 1 - 2(.5)^4 * .5 = 15/16

n(n)=v(n-1) - 1/32 v(n-5) + 1/64 v(n-6)

v6 = v5 - 1/32 v1 + 1/64v0 = 15/16 - 1/32 + 1/64 = 59/64

v7 = v6 - 1/32v2 + 1/64v1 = 59/64 - 1/32+1/64 = 58/64


etc.. until

v10 = 883/1024

giving required prob = 1-v10 = 141/1024

very messy where r is less than half of n - but can be simplified otherwise
By: TheFalklands Date: 07/02/2003 05:58:00 English  Type : Comment
so yes, but you'll be best writing a program, which I could do for you.

Note that this predicts 'exactly' r in a row (r+1 would not count) so you would need some further summing.
By: GW Date: 07/02/2003 06:04:00 English  Type : Comment
Squibi
For sequence of length n of r 0's and s 1's (ie n=r+s) the probabilty P of the first k being zeroes and the k+1th being a 1 is



P= r(r-1)(r-2)........(r-k+1) s
-------------------------- *-----
n(n-1)(n-2)..... (n-k+1) (n-k)


= r!(n-k)!(n-r)
---------------
n! ( r-k)!(n-k)

If r & s are very much larger than k, so that the probabilty of a zero is approximately P=r/n at the first k choices then the equation reduces to

Probabilty of zero = (1-P)*P^k


This may or may not be what you want.


GwynforWeb
By: GW Date: 07/02/2003 06:21:00 English  Type : Comment
Squibi
To summarise the above a little better.
For sequence of length n of r 0's and s 1's (ie n=r+s) the probabilty P of the first k being zeroes and the k+1th being a 1 is

P = r!(n-k)!(n-r)
-----------------
n! ( r-k)!(n-k)

If r & s are very much larger than k, so that the probabilty of a zero at each of the 1st k choices is approximately Q=r/n then the equation reduces to

Probabilty of 1st k being zero = P = (1-Q)*Q^k

where Q=r/n
By: Squibi Date: 07/02/2003 06:26:00 English  Type : Comment
Ok, i'll answer in order of appearance from my last post:

>(1) Are these the types of strings that you are looking at 0000011, 0000100, 00000101 (i.e.what is the probability of k 0's before hitting a 1).

>(2) You question could also be interpreted as what is the probability of a binary string of length n having a sequence of 0's of length k in it.

>Could you clarify please?

exactly second option.
I seek a formula of probability of appearing k strings-a-row in n row lenght of 0 and 1.
By: Squibi Date: 07/02/2003 06:41:00 English  Type : Comment
TFL!
I don't understand if you offer a formula or algorithm - i need formula. If you offer formula, please post it in form of:
P = f(n,x,p)

Thanks.
By: Squibi Date: 07/02/2003 06:52:00 English  Type : Comment
GW!
Let me describe the way of solution i see.
To find probability of meeting at least one sequence of k zeros in n row we need to find
1) number of all the possible combinations (easy - 2^n)
2) number of all the combinations, that will satisfy the conditions (hard)
When we'll got these, the overall probability will be second divided on first - thats what i think (maybe i'm wrong here?)
So, when we have first k zeros and k+1 = 1 that will do. And when we have first k zeros and k+1 = 0 that will also do. And when we'll have zeros from 2 to k+1 and first element equal to 1 that will do. But we need to avoid counting twice variants when we have k+1 zeros.
I searched internet and know the formulas for having k zeros form n row without any order. I also know the formula for probability of k zeros from the start. But now i need to find formula for probability of meeting sequence at least once everywhere in the row.
Thanks for all your help, hope now the task is clear.
By: sumotimor Date: 07/02/2003 07:29:00 English  Type : Comment
I was thinking about this earlier. One thing is sure: you have to have a lot of money to play roulette just for black or red :)))

ps: Don't forget the zeros!
By: Squibi Date: 07/02/2003 07:39:00 English  Type : Comment
Just to increase fun i'll double points.... :)
By: Squibi Date: 07/02/2003 07:42:00 English  Type : Comment
Whoops... can't have more than 500... but i promise to give 300 more to answer giver - but please, spent some time understanding task and give the solution in required form (formula).
By: TheFalklands Date: 07/02/2003 08:30:00 English  Type : Comment
ok, found the correct recurrence relations -

i've done it in the form of some vb code. There is NO single one line formula due to dependence problems. Anyway here is some code that you can save with a .vbs extension, then run as vb script hopefully.

note that in your case p =.5 (head or tails)

e.g. wscript c:\calc.vbs


--------------------------------------


Option Explicit



MsgBox RunProb(2, 0.5, 2) 'prob of rolling 2 heads in a row out of 2



MsgBox RunProb(10, 0.5, 4) '4 or more heads in a row out of 10 rolls






Private Function RunProb(n, p, r)

'Calculates the probability of at least one run of r or more
'consecutive events in n indepentent bernoulli events
'bernoulli parameter = p

Dim v()
Dim c
Dim q

q = 1 - p

ReDim v(n)

For c = 0 To r - 1
v(c) = 1
Next

v(r) = 1 - p ^ r

For c = r + 1 To n
v(c) = v(c - 1) - q * p ^ r * v(c - r - 1)
Next

RunProb = 1 - v(n)

End Function
By: Squibi Date: 07/02/2003 08:44:00 English  Type : Comment
hi, TFL!
As far as i see, your function gives correct answers. I need to think little more if it is possible to convert it to formula.
By: TheFalklands Date: 07/02/2003 09:10:00 English  Type : Comment
To explain further.

For a process with chance of success or failure, there is a probability p success or q failure where q = 1-p

lets say you are looking for the probability of at least r in a row occurring

v(c) = prob that the r in a row have not occurred after 'c' rolls

then you must have rolled r times for there to be any chance, so

v(0)=1
v(1)=1
v(2)=1
.
.
.
v(r-1)=1

v(r)= 1 - p ^ r '1-the chance of getting r all in a row straight off.

Now if there have not been r in a row after n-1 rolls, then after n rolls either that will still be the case.

OR the nth roll will result in a sequence of r rolls occurring

Now imagine this second case, on the c-1 roll, the r-1 success in row occurred, so suppose we are lloking for 5 heads in a row

we could have THHHH at this point, and we have

v(c-r-1)qp^(r-1)=qp^r v(c-r-1) as the probability that the run will be completed on roll c

this leads to

v(c-1)=v(c) + qp^r v(c-r-1)

or

v(c)= v(c-1) - qp^r v(c-r-1)

so with the starting values given earlier, you can calculte v(c) up to any value step by step


e.g. looking for the chances of a run of 2 heads or more, we have

v(0)=1
v(1)=1
v(2)=1-.5^2 = .75
v(3)=v(2)- .5 * .5 ^2 * v(0)=.75 - .125=.615

and so on
By: TheFalklands Date: 07/02/2003 09:14:00 English  Type : Comment
there is no one off formula given in my book., only to step through calculating prob of no run after 1 roll, 2 rolls, 3 rolls, 4 rolls, 5 rolls..... each subsequent probability involves previous probabiliites.

I don't know if a single formula is possible.
By: GW Date: 07/02/2003 09:46:00 English  Type : Comment
Squibi,
Thanks now I understand what the problem is. I did not think it was easy as others were suggesting. This may be possible. Give as some time now we now what it is.

GW
By: Squibi Date: 07/02/2003 09:57:00 English  Type : Comment
Sure, GW.

By: sumotimor Date: 07/02/2003 19:44:00 English  Type : Comment
Here is a method that agrees with the simulations of the problem.
q(n)=
{[(1-px)]/[(r+1-rx)q]}*{1/[x^(n+1)]}

...or (1-px) over (r+1-rx)q multiplied by 1 over (x^n+1)...
(Trying to preserve order of operations).

where x=1 + q*(p^r) + (r+1)*(q*(p^r))^2 + ....+(r+1)*(q*p^r))^r

where r=number of runs p=probibility q=p-1 n=number trials
This is the probability of NO runs, so you have to take 1-w(n) to get the answer.

In the 4 runs in 10 numbers example.

r=4 p=.50 q=.5 n=10

then
1 + .5*(.5^4) + (4+1)*(.5*(.5^4))^2 + . . .

= 1 + 0.03125 + 0.004882813 + 0.000152588 + 4.76837E-06 + 1.49012E-07
= 0.761668812

So 1-0.761668812 =0.238330372
The probability of at least 4 runs in 10 trials is 0.2383

I simulated 10,000 scenarios and counted where at least 4 runs occured (using random number). The number with at least four runs was 2469. So I feel that this is the correct solution to the problem. I can explain how to set up a simulation in Excel, if you like.
By: sumotimor Date: 07/02/2003 20:25:00 English  Type : Comment
Actually, the source with formula only showed the first 2 terms of the formula for x. I duplicated the numbers from the example exactly (at least 6 runs in 100 trials using (r+1) for each of the terms.
But really it should be (r+2) for the third term of the equation, (r+3) to the next, etc.

x=1 + q*(p^r) + (r+1)*(q*(p^r))^2 + (r+2)*(q*(p^r))^3 . . .

So 1 + 0.03125 + 0.005859375 + 0.000213623 + 7.62939E-06=0.756176203
The probability of at least 4 runs in 10 trials is 0.2438.

Since n was larger in their example, it did not affect it as much as the example we've been using.

Interesting that I still get an average of 2460 runs over many simulations. I think it should be closer to 2438. Maybe a flaw in the generation of so many random numbers in Excel. Have *heard* that there is a small flaw in Excel that is significant if generation thousands of numbers. Never use it enough to find out for sure.
By: TheFalklands Date: 07/02/2003 20:32:00 English  Type : Comment
Bah! Brain is not working well at 4:30PM on Friday.
>This is the probability of NO runs, so you have to take 1-w(n) to get the answer.<
Meant to say probability of NOT having at least r number of runs, i.e., having <r runs.
Have a good weekend everyone!
By: GW Date: 08/02/2003 19:12:00 English  Type : Comment
TFL,
I do not want to act as a spoiler here but I looked at this morning and I was clearly getting that the probability of a run of length at least r in a sequence of length n is dependant on n mod r and n div r. Which is some thing I do not see in your equation. Have you tested yor work against deighton's program? Your simultaion results could be accurate since you have r very much smaller than n
I am obtaining terms very similar to your's though. I will look at this later today or tomorrow when I have more time. It may be an idea to restrict the analysis for now to p=q=0.5 as the algebra is messy and it is what the original question is.


GW
By: GW Date: 09/02/2003 19:26:00 English  Type : Comment
sumotimor
TFL's program for a run of length 4 in 10 trials gives 0.2451171875 and not 0.2438. It is close and probably because the run length is small. Try calculating your formula for p=0.5, here are results some from the program

n=10 r=3 0.507812
n=10 r=5 0.109375
n=15 r=4 0.372283
n=20 r=7 0.0581817
n=20 r=4 0.478018

Frankly I hope you formula is right and that there is a mistake in arithmetic some where, but my analysis is giving terms that do not reduce to what one could call a formula.
This is a significant result and yet there is nothing on the web or any books I have. A lot has been written on binary sequences and yet nothing. I wonder if there is a formula

GW
By: Squibi Date: 14/02/2003 21:10:00 English  Type : Comment
Hi all!
Unfortunately, the question lost it actuality for me, and i did not get the answer in the form i needed.
I want to reward efforts of people, who spend time understanding and trying to help - i'll post points for them.
This topic will stay open if someone will find a solution... some day.
Thanks to all of you.
Squibi.
By: sumotimor Date: 20/02/2003 05:50:00 English  Type : Comment

I don't think there is anyway to make it less than 2 formulas. Do the formulas work for you? And deighton has a vb code that comes up with a similar result. What else are you looking for so we can help?

Since I had typos across 3 posts, I will repost the formulas:
Probability of NOT having at least r runs =
q(n)=
{[(1-px)]/[(r+1-rx)q]}*{1/[x^(n+1)]}

where x=1 + q*(p^r) + (r+1)*(q*(p^r))^2 + (r+2)*(q*(p^r))^3 . . .

where r=number of runs p=probibility q=p-1 n=number trials
q(n) is the probability of not having at least r runs, so you have to take 1-q(n) to get the answer you are looking for.

Cheers,
higginspi
By: relf Date: 24/02/2003 22:29:00 English  Type : Comment

The probability is equal to

(p(n+1,1,k) + p(n+1,2,k) + ... + p(n+1,n+1,k))/2^n,

where p(n,m,k) is a number of positive integer solutions of x_1 + ... + x_m = n, where each x_i is at most k (so-called "compositions with bounded parts" ).

Values of p(n,m,k) can be computed using recurrence formula
p(n+1,m,k) = p(n,m-1,k-1) + p(n-1,m-1,k-1) + ... + p(n-(k-1),m-1,k)
with trivial terminal conditions.
By: relf Date: 24/02/2003 22:32:00 English  Type : Comment

Ops. Correct recurrence formula is
p(n+1,m,k) = p(n,m-1,k) + p(n-1,m-1,k) + ... + p(n-(k-1),m-1,k)
By: Squibi Date: 11/03/2003 05:05:00 English  Type : Comment

Hi all!
I close that question by reasons i mentioned above.
Thanks again to all.

If someone thinks that he didn't get the points he deserved, let him post it here, i may add some.

Points for this specific question goes to VGR
For 1 part of 02/06/2003 07:38AM PST post.

Bye.
By: VGR Date: 11/03/2003 05:28:00 English  Type : Comment
I wonder why but thanks 8-))

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 461.169960 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page