Actuarial Outpost What is the probability...
 Register Blogs Wiki FAQ Calendar Search Today's Posts Mark Forums Read
 FlashChat Actuarial Discussion Preliminary Exams CAS/SOA Exams Cyberchat Around the World Suggestions

 DW Simpson International Actuarial Jobs Canada  Asia  Australia  Bermuda  Latin America  Europe

#21
12-29-2017, 03:01 PM
 Vorian Atreides Wiki/Note Contributor CAS Join Date: Apr 2005 Location: Hitler's Secret Bunker Studying for ACAS College: Hard Knocks Favorite beer: Sam Adams Cherry Wheat Posts: 60,645

Quote:
 Originally Posted by Academic Actuary Lets say n = 5 and we want strings of 2 0's 001xx 001xx 001xx 001xx 1001y 1001y 11001 01001 11100 01100 10100 there are not 4 with a longest string of 2 zeros
There are four when you're only interested in the first time such a sequence occurs. However, the OP does look at "more than the one occurrence," so I agree that we will need to count more.

My original point still stands; start simpler and see what you can learn. Then extend it out to see if what you found is general enough or if you need to work to refine it. The big key here is to not take the monster problem head on.

As it is, there is a clear recursion pattern that can be seen by looking at this simpler problem.

If P(n, k) = Probability of finding no more than k consecutive zeros in a string of n (binary) digits, then we have the following recursion:

P(n, k) = 0.5*P(n-1, k) + 0.5*P(n-1, k-1)

And the answer to the OP would be

1 - P(2k, 8) - P(2k, 7) - ... - P(2k, 1) - P(2k, 0).
__________________
I find your lack of faith disturbing

Why should I worry about dying? It’s not going to happen in my lifetime!

Freedom of speech is not a license to discourtesy

#BLACKMATTERLIVES
#22
12-29-2017, 03:33 PM
 Academic Actuary Member Join Date: Sep 2009 Posts: 7,373

Quote:
 Originally Posted by Vorian Atreides There are four when you're only interested in the first time such a sequence occurs. However, the OP does look at "more than the one occurrence," so I agree that we will need to count more. My original point still stands; start simpler and see what you can learn. Then extend it out to see if what you found is general enough or if you need to work to refine it. The big key here is to not take the monster problem head on. As it is, there is a clear recursion pattern that can be seen by looking at this simpler problem. If P(n, k) = Probability of finding no more than k consecutive zeros in a string of n (binary) digits, then we have the following recursion: P(n, k) = 0.5*P(n-1, k) + 0.5*P(n-1, k-1) And the answer to the OP would be 1 - P(2k, 8) - P(2k, 7) - ... - P(2k, 1) - P(2k, 0).
I don't think your recursion is correct. Let's look at a simple case.

P(4,3) = 2/16 P(3,3) = 1/8 P(3,2) = 2/8

Your first term is the outcome is a 1, but the second outcome being 0 does not necessarily increase the maximum length of your string.
#23
12-29-2017, 04:33 PM
 Z3ta Member SOA Join Date: Sep 2015 Posts: 361

Having 9 consecutive 0's can be broken into two cases:

(1) Having 9 consecutive 0's within the first 1999 elements of the sequence
$\underbrace{X_{1}X_{2}X_{3}\dots X_{1997}X_{1998}X_{1999}}_{\text{has 9 consecutive 0's sequence}}X_{2000}$
or

(2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end:
$\underbrace{X_{1}X_{2}X_{3}\dots X_{1987}X_{1989}X_{1990}}_{\text{no 9 consecutive 0's sequence}}1000000000$

So let $p_{i}$ be the probability that 9 consecutive 0's are found in the first $i$ elements of the sequence.

Then the two cases give:
$p_{i}=p_{i-1}+(1-p_{i-10})\cdot\frac{1}{2^{10}}$

So if you calculate $p_{9}=\frac{1}{2^{9}}$ and let $p_{0}=\dots=p_{8}=0$ then you can just use the recursion above to find $p_{2000}$ right?

Starting with $p_{9}$ the sequence looks like this:
$0.00195,\text{ }0.00293,\text{ }0.00391,\text{ }\dots,\text{ }0.85937,\text{ } 0.85951,\text{ } 0.85964,\text{ } 0.85978$
#24
12-29-2017, 05:05 PM
 Academic Actuary Member Join Date: Sep 2009 Posts: 7,373

Quote:
 Originally Posted by Z3ta Having 9 consecutive 0's can be broken into two cases: (1) Having 9 consecutive 0's within the first 1999 elements of the sequence $\underbrace{X_{1}X_{2}X_{3}\dots X_{1997}X_{1998}X_{1999}}_{\text{has 9 consecutive 0's sequence}}X_{2000}$ or (2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end: $\underbrace{X_{1}X_{2}X_{3}\dots X_{1987}X_{1989}X_{1990}}_{\text{no 9 consecutive 0's sequence}}1000000000$ So let $p_{i}$ be the probability that 9 consecutive 0's are found in the first $i$ elements of the sequence. Then the two cases give: $p_{i}=p_{i-1}+(1-p_{i-10})\cdot\frac{1}{2^{10}}$ So if you calculate $p_{9}=\frac{1}{2^{9}}$ and let $p_{0}=\dots=p_{8}=0$ then you can just use the recursion above to find $p_{2000}$ right? Starting with $p_{9}$ the sequence looks like this: $0.00195,\text{ }0.00293,\text{ }0.00391,\text{ }\dots,\text{ }0.85937,\text{ } 0.85951,\text{ } 0.85964,\text{ } 0.85978$
That is very nice. But what about cases where a 0 in 1991 might lead to the sequence of 9 0's.

Last edited by Academic Actuary; 12-29-2017 at 05:15 PM..
#25
12-29-2017, 05:16 PM
 Z3ta Member SOA Join Date: Sep 2015 Posts: 361

Quote:
 Originally Posted by Academic Actuary That is very nice. But what about cases where a 0 in 1991 might lead to the sequence of 9 0's.
That's case (1)
#26
12-29-2017, 05:18 PM
 Tsin banned Non-Actuary Join Date: Jul 2017 Posts: 80

I found other solutions and they are waaay more complicated. Seems like this problem is super hard.

http://mathforum.org/library/drmath/view/56637.html
#27
12-29-2017, 05:20 PM
 Marcie Member CAS Join Date: Feb 2015 Posts: 6,621

Quote:
 Originally Posted by Academic Actuary That is very nice. But what about cases where a 0 in 1991 might lead to the sequence of 9 0's.
Then there would be 9 0's in the first 1999, Perfesser.

ETA: ***** ninjas!

Last edited by Marcie; 12-29-2017 at 05:25 PM.. Reason: Ninjas!
#28
12-29-2017, 05:27 PM
 Marcie Member CAS Join Date: Feb 2015 Posts: 6,621

Quote:
 Originally Posted by Z3ta Having 9 consecutive 0's can be broken into two cases: (1) Having 9 consecutive 0's within the first 1999 elements of the sequence $\underbrace{X_{1}X_{2}X_{3}\dots X_{1997}X_{1998}X_{1999}}_{\text{has 9 consecutive 0's sequence}}X_{2000}$ or (2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end: $\underbrace{X_{1}X_{2}X_{3}\dots X_{1987}X_{1989}X_{1990}}_{\text{no 9 consecutive 0's sequence}}1000000000$ So let $p_{i}$ be the probability that 9 consecutive 0's are found in the first $i$ elements of the sequence. Then the two cases give: $p_{i}=p_{i-1}+(1-p_{i-10})\cdot\frac{1}{2^{10}}$ So if you calculate $p_{9}=\frac{1}{2^{9}}$ and let $p_{0}=\dots=p_{8}=0$ then you can just use the recursion above to find $p_{2000}$ right? Starting with $p_{9}$ the sequence looks like this: $0.00195,\text{ }0.00293,\text{ }0.00391,\text{ }\dots,\text{ }0.85937,\text{ } 0.85951,\text{ } 0.85964,\text{ } 0.85978$
Cool. So does it come out to 1/2?
#29
12-29-2017, 05:36 PM
 Z3ta Member SOA Join Date: Sep 2015 Posts: 361

Quote:
 Originally Posted by Marcie Cool. So does it come out to 1/2?
Yes just apply the following:

$\text{\underline{Marcie's Theorem}} \\ \text{If }S=A_{1}\cup A_{2}\text{ and }A_{1}\cap A_{2}=\emptyset\text{ then }P(A_{1})=P(A_{2})=\frac{1}{2}$

#30
12-29-2017, 05:51 PM
 Marcie Member CAS Join Date: Feb 2015 Posts: 6,621

 Tags binary, martingale, sequence, string

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off

All times are GMT -4. The time now is 01:24 PM.

 -- Default Style - Fluid Width ---- Default Style - Fixed Width ---- Old Default Style ---- Easy on the eyes ---- Smooth Darkness ---- Chestnut ---- Apple-ish Style ---- If Apples were blue ---- If Apples were green ---- If Apples were purple ---- Halloween 2007 ---- B&W ---- Halloween ---- AO Christmas Theme ---- Turkey Day Theme ---- AO 2007 beta ---- 4th Of July Contact Us - Actuarial Outpost - Archive - Privacy Statement - Top