I repeat rolling a fair die and writing the result down, - after a while I let the software to continue random generation of the integers 1 to 6 till the 1000th digit.

What is the probability for my 7-digit phone number being somewhere within the sequence?

As a first approximation we can realize that there are 6^7=279936 possible 7-digit sequences. The 1000 chosen digits contain 1000-6=994 7-digit sequences, starting at choice 1 through choice 994.

One would expect that 2543663 would occur 994/279936 ~= .00355081161408322 of such times and would therefore have that probability of being in the longer sequence.

However, this expectation includes multiple occurrences occasionally in rerunning this experiment. Its true probability of occurring at least once is slightly less.

One approximation would be to use the poisson distribution with mean .00355081161408322, taking its given probability of zero occurrences and complementing it with regard to 1.  The poisson probability of zero occurrences is approximately .9964554850625006 and its complement is .00354451493749941.

The exact answer can be gotten with a Markov chain. The possible states at any given stage are given by in reverse numerical order:

7: The 7-digit sequence has already occurred
6: 254366 has occurred as the last few up to now, but the 7-digit sequence had not appeared any time before that.
5: 25436 has occurred as the last few up to now, but the 7-digit sequence had not appeared any time before that.
4: 2543 has occurred as the last few up to now, but the 7-digit sequence had not appeared any time before that.
3: 254 has occurred as the last few up to now, but the 7-digit sequence had not appeared any time before that.
2: 25 has occurred as the last few up to now, but the 7-digit sequence had not appeared any time before that.
1: 2 has occurred as the last step up to now, but the 7-digit sequence had not appeared any time before that.
0: None of the above.

At the start, the state is this last state, zero. It's probability is 1.

At any given throw among the 1000 throws, except for state 7 there is a 1/6 probability of advancing to the next state numerically as well as a 1/6 probability of regressing to (or remaining at) state 1 (in the case of from existing state zero there is only that one 1/6 of getting to state 1--not 2/6) and 2/3 probibility of regressing to state zero. Once in state 7 it can't go back; it has achieved the goal no matter what follows.

The first eight generations, from state 0 to state 7:

gen   prob of states 0 through 7
 1  5/6  1/6  0  0  0  0  0  0
 2  29/36  1/6  1/36  0  0  0  0  0
 3  173/216  1/6  1/36  1/216  0  0  0  0
 4  1037/1296  1/6  1/36  1/216  1/1296  0  0  0
 5  6221/7776  1/6  1/36  1/216  1/1296  1/7776  0  0
 6  37325/46656  1/6  1/36  1/216  1/1296  1/7776  1/46656  0
 7  223949/279936  1/6  1/36  1/216  1/1296  1/7776  1/46656  1/279936
 8  1343689/1679616  279935/1679616  1/36  1/216  1/1296  1/7776  1/46656  1/139968

   10   dim P(7),Pn(7)
   20   P(0)=1
   30   for Gen=1 to 1000
   40    Pn(0)=5//6*P(0)+2//3*(P(1)+P(2)+P(3)+P(4)+P(5)+P(6))
   50    Pn(1)=1//6*(P(0)+P(1)+P(2)+P(3)+P(4)+P(5)+P(6))
   60    for I=2 to 6:Pn(I)=P(I-1)*(1//6):next
   70    Pn(7)=P(6)*1//6+P(7)
   90    print Gen
  100    for I=0 to 7:P(I)=Pn(I):next
  110   next
  120    for I=0 to 7:print P(I);:next:print
  130   for I=0 to 7:print P(I)/1:next

At the end, after 1000 runs the approximate values for the various states are:

state       probability

 0  0.7971677398239170601
 1  0.1660764938070764306
 2  0.027679514514641778
 3  0.0046132688991873417
 4  0.000768880896554432
 5  0.0001281472738756865
 6  0.0000213579552767671
 7  0.0035445968294705033
 
 This final number is the sought answer.
 
 So the successively better methods gave:
 .00355081161408322 (reciprocal of expected number of occurrences)
 .00354451493749941 (complement of Poisson expectation of zero occurrences)
 .0035445968294705033 (Markov chain)
 
For the curious, the exact value of the probability is

 4484339496027558931509147206565753779923283536157745791644006436728006354284075
90132572959325984025879254901570697987895767170295311918573418558046237493251771
11041596385081265281382157135533773625742775920894119926944418663945963210540998
01721528673297765082285129582112316915314262752382974946416426176941375058740454
32375521632503419372896704642174675180909982430967375097916679833984654849656173
34575733600793084883404557843946864672307434396725515622599343161627444506825481
63538302521295350478608970716769187594663060734429338009758934351288737543233280
99000748513120910481144013337860335323685709297517967650430635138119288769463434
51979215570640330972659121620678518318493213889402278634629283316888752378295871
418570310899565338600254882297491628736921941135129
                           /
126511976164506009621808668
09659372514289401712275476646736707168907017092832367430723148624926132455337030
56171949078085342935767569339125246310461841661621961876384540839741011475583790
49613375384231731520806697807853604908159152052615260837553651462294165243900327
77201196280786492559996971343560471781564788750907157857620122297498724563594509
19037263280007838644946493259907280315363635619250182929178037746991733654051530
29483490077654400986913305843147882746268182102038217758516498682462747725631370
58567840810749899742927597179889784548054854763216518885252583785175142405494038
88298882737083372617944226554622971425054317924072222602220340903283473999477571
14129788663274612392091432607712327856534138620467669225699821905173058478549121
89832219376262475734319104

And this is the reduced fraction.

Posted by Charlie on 2014-04-15 12:49:18