Actuarial Outpost
 
Go Back   Actuarial Outpost > Exams - Please Limit Discussion to Exam-Related Topics > SoA/CAS Preliminary Exams > Exam 1/P - Probability
FlashChat Actuarial Discussion Preliminary Exams CAS/SOA Exams Cyberchat Around the World Suggestions

DW Simpson
Actuarial Jobs

Visit our site for the most up to date jobs for actuaries.

Actuarial Salary Surveys
Property & Casualty, Health, Life, Pension and Non-Tradtional Jobs.

Actuarial Meeting Schedule
Browse this year's meetings and which recruiters will attend.

Contact DW Simpson
Have a question?
Let's talk.
You'll be glad you did.


Reply
 
Thread Tools Search this Thread Display Modes
  #21  
Old 12-29-2017, 03:01 PM
Vorian Atreides's Avatar
Vorian Atreides Vorian Atreides is offline
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: 62,443
Default

Quote:
Originally Posted by Academic Actuary View Post
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
Reply With Quote
  #22  
Old 12-29-2017, 03:33 PM
Academic Actuary Academic Actuary is offline
Member
 
Join Date: Sep 2009
Posts: 7,931
Default

Quote:
Originally Posted by Vorian Atreides View Post
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.
Reply With Quote
  #23  
Old 12-29-2017, 04:33 PM
Z3ta Z3ta is offline
Member
SOA
 
Join Date: Sep 2015
Posts: 361
Default

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

or

(2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end:


So let be the probability that 9 consecutive 0's are found in the first elements of the sequence.

Then the two cases give:


So if you calculate and let then you can just use the recursion above to find right?

Starting with the sequence looks like this:
Reply With Quote
  #24  
Old 12-29-2017, 05:05 PM
Academic Actuary Academic Actuary is offline
Member
 
Join Date: Sep 2009
Posts: 7,931
Default

Quote:
Originally Posted by Z3ta View Post
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

or

(2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end:


So let be the probability that 9 consecutive 0's are found in the first elements of the sequence.

Then the two cases give:


So if you calculate and let then you can just use the recursion above to find right?

Starting with the sequence looks like this:
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..
Reply With Quote
  #25  
Old 12-29-2017, 05:16 PM
Z3ta Z3ta is offline
Member
SOA
 
Join Date: Sep 2015
Posts: 361
Default

Quote:
Originally Posted by Academic Actuary View Post
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)
Reply With Quote
  #26  
Old 12-29-2017, 05:18 PM
Tsin Tsin is offline
banned
Non-Actuary
 
Join Date: Jul 2017
Posts: 80
Default

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
Reply With Quote
  #27  
Old 12-29-2017, 05:20 PM
Marcie's Avatar
Marcie Marcie is online now
Member
CAS
 
Join Date: Feb 2015
Posts: 7,886
Default

Quote:
Originally Posted by Academic Actuary View Post
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!
Reply With Quote
  #28  
Old 12-29-2017, 05:27 PM
Marcie's Avatar
Marcie Marcie is online now
Member
CAS
 
Join Date: Feb 2015
Posts: 7,886
Default

Quote:
Originally Posted by Z3ta View Post
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

or

(2) Not having it in the first 1990 elements, a 1 for element 1991 and then 9 consecutive 0's at the end:


So let be the probability that 9 consecutive 0's are found in the first elements of the sequence.

Then the two cases give:


So if you calculate and let then you can just use the recursion above to find right?

Starting with the sequence looks like this:
Cool. So does it come out to 1/2?
Reply With Quote
  #29  
Old 12-29-2017, 05:36 PM
Z3ta Z3ta is offline
Member
SOA
 
Join Date: Sep 2015
Posts: 361
Default

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



Reply With Quote
  #30  
Old 12-29-2017, 05:51 PM
Marcie's Avatar
Marcie Marcie is online now
Member
CAS
 
Join Date: Feb 2015
Posts: 7,886
Default

Reply With Quote
Reply

Tags
binary, martingale, sequence, string

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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 10:55 AM.


Powered by vBulletin®
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
*PLEASE NOTE: Posts are not checked for accuracy, and do not
represent the views of the Actuarial Outpost or its sponsors.
Page generated in 0.24463 seconds with 9 queries