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 International Actuarial Jobs
Canada  Asia  Australia  Bermuda  Latin America  Europe


Reply
 
Thread Tools Search this Thread Display Modes
  #11  
Old 12-29-2017, 10:59 AM
Vorian Atreides's Avatar
Vorian Atreides Vorian Atreides is offline
Wiki/Note Contributor
CAS
 
Join Date: Apr 2005
Location: As far as 3 cups of sugar will take you
Studying for ACAS
College: Hard Knocks
Favorite beer: Most German dark lagers
Posts: 62,468
Default

Quote:
Originally Posted by Academic Actuary View Post
10 and 15 flips are easy because you can have only one consecutive string of nine or more zeros. With 2000 flips it isn't so easy unless I am missing something.
You're right . . . starting that small helps get a handle on the problem; then building up to a larger n will help to extract a more general form.

Also, my first question is also a hint/key to answering the original problem.

But the main point is don't try to tackle the n=2000 head on. Make a smaller and more tractable problem first; get a solid handle on it and look to extract generalizations to see how to solve the larger (and more generic) case.
__________________
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
  #12  
Old 12-29-2017, 11:21 AM
Academic Actuary Academic Actuary is online now
Member
 
Join Date: Sep 2009
Posts: 7,939
Default

Quote:
Originally Posted by Vorian Atreides View Post
You're right . . . starting that small helps get a handle on the problem; then building up to a larger n will help to extract a more general form.

Also, my first question is also a hint/key to answering the original problem.

But the main point is don't try to tackle the n=2000 head on. Make a smaller and more tractable problem first; get a solid handle on it and look to extract generalizations to see how to solve the larger (and more generic) case.
Sometimes that works, sometimes it doesn't. In this case it doesn't. With 15 positions you have one string of 15 0's, 2 stings of at most 14 0's, 5 strings of at most 13 0's, 10 strings of at most 12 0's etc. You can count the number of outcomes where there are at least 9 0's in sequence. The counting technique quickyly becomes infeasible.
Reply With Quote
  #13  
Old 12-29-2017, 11:46 AM
Vorian Atreides's Avatar
Vorian Atreides Vorian Atreides is offline
Wiki/Note Contributor
CAS
 
Join Date: Apr 2005
Location: As far as 3 cups of sugar will take you
Studying for ACAS
College: Hard Knocks
Favorite beer: Most German dark lagers
Posts: 62,468
Default

Quote:
Originally Posted by Academic Actuary View Post
Sometimes that works, sometimes it doesn't. In this case it doesn't. With 15 positions you have one string of 15 0's, 2 stings of at most 14 0's, 5 strings of at most 13 0's, 10 strings of at most 12 0's etc. You can count the number of outcomes where there are at least 9 0's in sequence. The counting technique quickyly becomes infeasible.
Based on what you just wrote . . .

with n positions:
Code:
you have 1 string  of n   0's
you have 2 strings of n-1 0's
you have 3 strings of n-2 0's
.
.
.
you have k strings of n+1-k 0's
.
.
.
Now, given that the OP is interested in at least 9 consecutive 0's; simply look at the situation of at most 8 consecutive 0's. You can still find the answer from this angle.
__________________
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
  #14  
Old 12-29-2017, 11:53 AM
stefanos stefanos is offline
Member
SOA
 
Join Date: Mar 2015
Posts: 80
Default

Quote:
Originally Posted by Tsin View Post
there is a string of 2000 random binary numbers (0 and 1) each occurring with the same probability of 50%. What is the probability that in this binary string, there happen to be 1 or more sequence of 9 zeros in a row?

edited 10 to 9
As VA suggested, we may start with an easier problem first: Compute the probability of 2 consecutive zeros in 10 flips.

Let F(1), F(2), ... denote the Fibonacci numbers. As you know, F(1)=F(2)=1 and F(i)=F(i-1)+F(i-2). Then the desired probability turns out to be 1-[F(12)/2^10] ~= 86%.

Now assume you want 3 consecutive zeros in 10 flips. The right sequence to use is the so-called Tribonacci numbers T(i) satisfying T(1)=0, T(2)=T(3)=1, T(i)=T(i-1)+T(i-2)+T(i-3), and the correct answer is 1-[T(13)/2^10] ~= 51%.

For 9 consecutive zeros in 2000 flips, you will use the Enneanacci numbers E(i) (https://oeis.org/A104144) and compute 1-[E(2009)/2^2000].

Edit: I computed E(2009) as 1.60988E+601 in Excel. Answer is 86%.

Last edited by stefanos; 12-29-2017 at 12:23 PM.. Reason: add final answer
Reply With Quote
  #15  
Old 12-29-2017, 12:32 PM
Marcie's Avatar
Marcie Marcie is online now
Member
CAS
 
Join Date: Feb 2015
Posts: 7,934
Default

https://www.youtube.com/watch?v=C_TfdNAXOwE
Reply With Quote
  #16  
Old 12-29-2017, 12:49 PM
Academic Actuary Academic Actuary is online now
Member
 
Join Date: Sep 2009
Posts: 7,939
Default

Quote:
Originally Posted by Vorian Atreides View Post
Based on what you just wrote . . .

with n positions:
Code:
you have 1 string  of n   0's
you have 2 strings of n-1 0's
you have 3 strings of n-2 0's
.
.
.
you have k strings of n+1-k 0's
.
.
.
Now, given that the OP is interested in at least 9 consecutive 0's; simply look at the situation of at most 8 consecutive 0's. You can still find the answer from this angle.
Lets say n = 5 and we want strings of 2 0's

00100 00101 00111 00101 10010 10011 11001 01001 11100

there are not 4 with a longest string of 2 zeros
Reply With Quote
  #17  
Old 12-29-2017, 12:53 PM
Academic Actuary Academic Actuary is online now
Member
 
Join Date: Sep 2009
Posts: 7,939
Default

Quote:
Originally Posted by stefanos View Post
As VA suggested, we may start with an easier problem first: Compute the probability of 2 consecutive zeros in 10 flips.

Let F(1), F(2), ... denote the Fibonacci numbers. As you know, F(1)=F(2)=1 and F(i)=F(i-1)+F(i-2). Then the desired probability turns out to be 1-[F(12)/2^10] ~= 86%.

Now assume you want 3 consecutive zeros in 10 flips. The right sequence to use is the so-called Tribonacci numbers T(i) satisfying T(1)=0, T(2)=T(3)=1, T(i)=T(i-1)+T(i-2)+T(i-3), and the correct answer is 1-[T(13)/2^10] ~= 51%.

For 9 consecutive zeros in 2000 flips, you will use the Enneanacci numbers E(i) (https://oeis.org/A104144) and compute 1-[E(2009)/2^2000].

Edit: I computed E(2009) as 1.60988E+601 in Excel. Answer is 86%.

I ran the simulation and that does look right. The fact that this works is not something that is in any way obvious to me.

Last edited by Academic Actuary; 12-29-2017 at 01:18 PM..
Reply With Quote
  #18  
Old 12-29-2017, 02:04 PM
tommie frazier tommie frazier is online now
Member
 
Join Date: Aug 2003
Favorite beer: The kind with 2 e's
Posts: 22,769
Default

my friend who bets red/black roulette tells me 0 chance. the wheel learns and doesn't have sequences that long.
__________________
Removed a dated athletic reference under pressure from a friend. You can still give money to help fund research on neurofibromatosis (nf).

General info at www.ctf.org

Team donation page here.
Reply With Quote
  #19  
Old 12-29-2017, 02:08 PM
stefanos stefanos is offline
Member
SOA
 
Join Date: Mar 2015
Posts: 80
Default

Quote:
Originally Posted by Academic Actuary View Post
I ran the simulation and that does look right. The fact that this works is not something that is in any way obvious to me.
What I did was count the final nodes in the subset of the binomial tree that doesn't contain the strings of zeros. For example, for the case of 2 zeros in n flips, the sub-tree looks like:

0--1--0--1
----`--1--0
--------`--1
1--0--1--0
|------`--1
`--1--0--1
----`--1--0
--------`--1

For n=1, we have F(3)=2 outcomes, for n=2 we have F(4)=3 outcomes, for n=3 we have F(5)=5 outcomes, for n=4 we have F(6)=8 outcomes, etc.

Last edited by stefanos; 12-29-2017 at 06:40 PM..
Reply With Quote
  #20  
Old 12-29-2017, 02:38 PM
rgreenlee's Avatar
rgreenlee rgreenlee is offline
Member
Non-Actuary
 
Join Date: Jun 2014
Location: in a van down by the river
College: you have never heard of it
Favorite beer: chocolate milk
Posts: 1,040
Default

My intuition is telling me that there is some trick where you look at this problem in the context of group theory and that there could be some subgroup where the elements are easy to count and line up nicely with the target or its complement.
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 12:27 PM.


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.23088 seconds with 9 queries