STOPPING PATTERNS IN RANDOM SEQUENCES
Author Roland Engdahl
University of Kalmar
Sweden
mr.engdahl@telia.com
Introduction
Introduction
We take random characters or digits from a set A : {1,2,3...n}, one at a time. Continue until a choosen
stopping pattern S is obtained.
As example we toss an fair coin and observe head H and tails T. A : {H,T} and the stopping pattern S=(HH).
A real tossing gives : HTTHTHTHH
We are interested in the mean waiting-time E(
)
A classical way is to use Markov chains for a given stopping pattern. In programming it will be rather intricate.
Here other means will be used.
What do you think about E(
) for the patterns (HH) and (HT) (unbiased coin). Are they equal?
In this paper we will use one stopping pattern as well as two stopping patterns at the same time
Sources:
HOW MANY RANDOM DIGITS ARE REQUIRED UNTIL GIVEN SEQUENCES ARE OBTAINED?
This is the title of an article in the periodical
J. Appl.Prob. 19. 518-531
0021-9002/82/030518-14
by Gunnar Blom and Daniel Thorburn.
This article was the main source of inspiration for my contribution of theory for Maple programs.
When quoting to content in their article: GB&DT
Another source is the well-known:
William Feller,
An Introduction to Probability Theory and Its Applications, vol 1.
When qouting to this source: Feller
Martin Gardner,
Mathematical Games in Scientific American 1974
On the paradoxial situations that arise from nontransitive relations
The author has made a development of the theory in GB&DT and adepted it for Maple and programming of theory and simulation.
The evolution of theory has not been published anywhere.
When referring to my own contribution of theory: RE
One Stopping Pattern
Theory
Part 1 Generalities. Overlapping in sequences. Generating functions
GENERALITIES
General concepts about overlapping within and between stopping patterns.
introduced by Convay
Let S(1) and S(2) be two stopping patterns.
Denote 
S(1) the r rightmost (last) digits in S(1)
Denote 
S(2) the r leftmost (first) digits in S(2)
lenS(1) is the length of the pattern S(1)
The leading numbers are defined by (observe the order)
1 if 
S(1) = 
S(2)
(1,2) =
0 if 
S(1) ≠ 
S(2)
RE : weighty leading numbers
(1,2) = 
(1,2) 
where pr
are the probabilities for the digits in S
(1,2)
and the product is taken digit by digit in S
(1,2)
In GB&DT all the digits have the same probability
In the following we use weighty leading numbers
The measure of overlapping 
of S(1) on S(2) (observe the order) is defined by
With one stopping pattern S we write S
Example 1 S(1) = (101) S(2) = (1011)
(1,2) = () 
(1,2) = (101)
(1,2) = p
(1,2) = p
q
f
= p
+ p
Example 2 S= (10101)
S
Generating Functions
Generalities according to Feller p 264- Notation as in GB&DT
Let {a
A(t) = 
{a
The variable t has no significance (compare polynom)
Let X be a stochastic (random) variable assuming the values 0, 1, 2, ...
For the distribution of the probabilities p
P(X = j) = p
and for the tail P(X > j) = q
Then q
+ p
The generating functions for the sequences {p
Ψ(t) = q
Ψ(t) = (1 - Φ(t)) / (1-t) for -1 < t < 1
The expectation E(X) satisfies (Theorem and proof in Feller)
E(X) = 
E(X) = Φ'(1) = Ψ(1)
The variance Var(X)
Var(X) = 2Ψ'(1) + Ψ (1) - Ψ
Part 2 Coefficients in recursion formula
Coeffients in recursion formula. Expectation and Variance
The generating function for the overlaps is (GB&DT)
d
where S is the stopping pattern and k is the length of S
Other notations in GB&DT Here we use weighty leading numbers
Theorem and proof in GB&DT
Φ
(1)
It is not easy (impossible?) to determine p
From here development by RE
With the formula by Feller we rewrite (1) as
Ψ
(t) = 
(2)
We have q
The 
Var(X) = 2Ψ'(1) + Ψ (1) - Ψ
Var
Program one pattern theory
One pattern theoretic values
Leading numbers
Choose binary pattern S and probability for "1"
| > |
S:="101":p:=0.5:
len:=length(S):
for i from 1 to len do
d[i]:=0:
ls:=substring(S,1..i):rs:=substring(S,-i..-1):
if ls=rs then
d[i]:=1:
for j from 1 to i do
if substring(ls,j..j)="1" then
d[i]:=d[i]/p
else d[i]:=d[i]/(1-p):
end if
end do
end if
end do:
|
Recursion to calculate c[i]
| > |
k:=len:d[0]:=1:
for i from 1 to k do
c[i]:=(d[k-i+1]-d[k-i])/d[k]:
end do: |
Expectation and Variance
| > |
ex:=0:ss:=0:
for i from 1 to len do
ex:=ex+d[i]:ss:=ss+i*d[i]:
end do:
var:=ex*ex+ex-2*ss:
|
Results
| > |
Digits:=5:
print('expectation',evalf(ex));
print('standard','deviation',sqrt(var));
|
 |
 |
(2.2.1) |
Distribution
| > |
k:=len:
for i from 0 to k-1 do
qd[i]:=1:
end do:
for i from k to k+10 do
qd[i]:=0:
for j from 1 to k do
qd[i]:=qd[i]+c[j]*qd[i-j]:
end do
end do:
|
Results
| > |
Digits:=5:
print('i','distribution');
for i from k to k+10 do
print(i,1-qd[i]);
end do; |
Program one pattern simulation
Simulation one pattern
| > |
restart:
with(RandomTools[MersenneTwister]):
M:=NewGenerator(range=10^10):
|
Choose same binary pattern S and probability for "1" as in theoretic, number of trials
| > |
S:="101":p:=0.5:trial:=10000:len:=length(S):
|
bi delivers a string "1" if with probability p else "0"
| > |
bi:=proc()global b;
if Float(M(),-10)<p then
b:= "1"
else b:="0"
end if
end proc:
|
trier gives the number k of bi to give the stopping pattern
| > |
trier:=proc() local i,U;global k;
U:="":k:=len:
for i from 1 to k do
U:=cat(U,bi()):
end do:
if S<>U then
while S<>U do
U:=substring(U,2..len):
U:=cat(U,bi());
k:=k+1:
end do:
end if:k;
end proc:
|
Simulation
Start new simulation from here
| > |
lim:=2000:lim2:=50:
for i from len to lim do r[i]:=0 end do:
for i from 1 to trial do
tr:=trier():
if tr<lim then r[tr]:=r[tr]+1:end if:
end do: |
mean and variance
| > |
ss:=0:
for i from len to len+lim2 do
ss:=ss+r[i]:
q[i]:=ss/trial:
end do:
sa:=0:ra:=0:
for i from len to lim do
sa:=sa+i*r[i]:
ra:=ra+i*i*r[i]:
end do:
Digits:=5:
m:=evalf(sa/trial):
print('mean',m);
v:=evalf(ra/trial-m*m):
print('standard','deviation',sqrt(v)); |
 |
 |
(2.3.1) |
Distribution
| > |
Digits:=5:
print('i','distribution');
for i from len to len+10 do
print(i,evalf(q[i]));
end do; |
Two Stopping Patterns
Theory
Two stopping patterns. Theory
We will consider the case with two stopping pattern S(1) and S(2) and with the random sequence common to both patterns.
Further we assume that the patterns are binary and of the same length. (these restrictions are not necessary in the general case)
Let X be the waiting time until one of the two patterns occurs and k = length(S(1))=length(S(2))
As in the genralities define the measure of overlapping of S(i) on S(j) by
Results from GB&DT (other notations here and smaller modifications))
The linear system of equations
has the solutions 
Let x = 
The mean waiting time is
E(X) = 
Let 
be the probability that the pattern S(i) occurs first
(End of GB&DT)
Set for simplification of writing
α = 
β = 
The solution of the system of equtions gives
E(X) = 
We intoduce the notion of odds
Definition
= 
Example S(1) = (0101) S(2) = (1011)
For p=0.5 E(X) = 90/7 
With separate random sequences
Waiting times for one pattern
E(S(1)) = 
Program two patterns theoretic
Two stopping patterns theoretic values
Choose two binary patterns with equal length and probability for "1"
| > |
S[1]:="1110":S[2]:="1001":p:=.618034:
l1:=length(S[1]):l2:=length(S[2]):
if l1<>l2 then print('WARNING'):STOP end if;
st:=l1:
for i from 1 to 2 do
for j from 1 to 2 do
f[i,j]:=0:
for k from 1 to st do
d[k]:=0:
ls:=substring(S[j],1..k):rs:=substring(S[i],-k..-1):
if ls=rs then
d[k]:=1:
for r from 1 to k do
ts:=substring(ls,r..r):
if ts="1" then
d[k]:=d[k]/p else d[k]:=d[k]/(1-p):
end if:
end do:
end if:
f[i,j]:=f[i,j]+d[k]:
end do:
end do:
end do:
|
Calculation
| > |
Digits:=5:
p[1]:=(f[2,2]-f[2,1])/(f[1,1]-f[1,2]+f[2,2]-f[2,1]);
p[2]:=(f[1,1]-f[1,2])/(f[1,1]-f[1,2]+f[2,2]-f[2,1]); |
 |
 |
(3.2.1) |
odds[1] odds for S[1] against S[2] = p[1]/(1-p[1])
odds[2] odds for S[2] against S[1] = p[2]/(1-p[2])
odds[1] * odds[2] = 1
| > |
odds[1]:=(f[2,2]-f[2,1])/(f[1,1]-f[1,2]);
odds[2]:=(f[1,1]-f[1,2])/(f[2,2]-f[2,1]); |
 |
 |
(3.2.3) |
expectation
| > |
ex:=(f[1,1]*f[2,2]-f[2,1]*f[1,2])/(f[1,1]+f[2,2]-f[1,2]-f[2,1]); |
 |
(3.2.4) |
Program two patterns simulation
Two stopping patterns simulation
| > |
restart:
with(RandomTools[MersenneTwister]):
M:=NewGenerator(range=10^10):
|
Choose same binary pattern S[1] and S[2] probability for "1" as in theoretic, number of trials
| > |
S[1]:="1001":S[2]:="0110": p:=0.5:trial:=10000:len:=length(S[1]):
if length(S[1])<> length(S[2]) then print('WARNING'):STOP end if;
|
bi delivers a string "1" if with probability p else "0"
| > |
bi:=proc()global b;
if Float(M(),-10)<p then
b:= "1"
else b:="0"
end if
end proc:
|
trier gives the number k of bi to give the stopping pattern
| > |
trier:=proc() local ok,i,U;global k,v1,v2,len;
U:="":k:=len:v1:=false:v2:=false:ok:=false:
for i from 1 to k do
U:=cat(U,bi()):
end do:
if U=S[1] then
v1:=true:ok:=true:
end if;
if U=S[2] then
v2:=true:ok:=true:
end if:
while ok=false do
U:=substring(U,2..len):
U:=cat(U,bi());
k:=k+1:
if U=S[1] then
v1:=true:ok:=true:
end if;
if U=S[2] then
v2:=true:ok:=true:
end if:
end do:k;
end proc: |
Simulation
Start new simulation from here
| > |
for i from 1 to 2 do
w[i]:=0:
end do:
ssum:=0:lim:=100:
for i from 1 to lim do
g[i]:=0:
end do: |
| > |
for i from 1 to trial do
tr:=trier();
if tr<lim then
g[k]:=g[k]+1:
end if:
if v1 then w[1]:=w[1]+1: end if:
if v2 then w[2]:=w[2]+1: end if:
end do:
Digits:=4:
print('S1first',w[1]);
print('S2first',w[2]);
for i from len to 50 do
ssum:=ssum+i*g[i]:
end do:
print('mean',evalf(ssum/trial));
print('distribution');
for i from len to 20 do
print(i,g[i]):
end do;
|
Winning Ways for Two Persons Game
Introduction
Introduction to winning ways...
Two persons, A and B, decide to play a game. A is unsuspecting.
B has read in Scientific American some 30 years ago an essay by Gardner.
It was about tossing an unbiased coin. No said A, we must do it a little harder, perhaps a biased coin,
B proposed a wheel of fortune with sectors for 1 and 0.
At last B said we do our own wheel of fortune in a Maple program.
This program is found here under Simulation
Before starting they have to come to an agreement concerning the rules of the game.
The rules are:
The probability for 1 is p and p is restricted to 0.25 < p < 0.75
(i e 1 between one quarter to three quarters of an orbit on a wheel of fortune)
We restrict to both pattern of length three
A starts choosing a pattern e g 101
A continues by choosing a value for p e g p=0.618
At last B chooses another pattern e g 111
She who gets her pattern first at the simulation wins that turn
Both agrre that the rules above are fair
After a while they can start the program simulation
But B will make some preparations, and A must not look at them
B starts with the program FOR THE THEORY
WINNING WAYS FOR YOUR GAMES WITH TWO BINARY SEQUENCES
Then B continues with table graphs and strategy under theory
Well prepared B suggets A to start the simulation program
You can of course go at once to strategy (and perhaps look at the graphs).
The program is for understanding the background of the strategy
Program for creating Theory
WINNING WAYS FOR YOUR GAMES WITH TWO BINARY SEQUENCES
Instruction for use
You must follow all the patterns for S[2]
Choose two binary patterns with equal length 3
p is probability for 1. Vary S[2] from 000 to 111
le = left limit ri = right limit
| > |
S[1]:="101":S[2]:="111": le:=0.3:ri:=0.7:
if (length(S[1])<>3 or length(S[2])<>3) then print('WARNING'):STOP end if;
|
| > |
for i from 1 to 2 do
for j from 1 to 2 do
f[i,j]:=0:
for k from 1 to 3 do
d[k]:=0:
ls:=substring(S[j],1..k):rs:=substring(S[i],-k..-1):
if ls=rs then
d[k]:=1:
for r from 1 to k do
ts:=substring(ls,r..r):
if ts="1" then
d[k]:=d[k]/p else d[k]:=d[k]/(1-p):
end if:
end do:
end if:
f[i,j]:=f[i,j]+d[k]:
end do:
end do:
end do: |
Calculation of odds for S[2] against s[1] Temporary results depending on S[2]
| > |
odds:=(f[1,1]-f[1,2])/(f[2,2]-f[2,1]); |
 |
(4.2.1) |
jump to applicable line of S[2]
if S[2]=S[1] choose 1 in stead of odds after simplify
| > |
od000:=simplify(odds);
p0:=plot(od000,p=le..ri,color=cyan):
|
 |
(4.2.2) |
| > |
od001:=simplify(odds);
p1:=plot(od001,p=le..ri,color=black):
|
 |
(4.2.3) |
| > |
od010:=simplify(odds);
p2:=plot(od010,p=le..ri,color=blue):
|
 |
(4.2.4) |
| > |
od011:=simplify(odds);
p3:=plot(od011,p=le..ri,color=red):
|
 |
(4.2.5) |
| > |
od100:=simplify(odds);
p4:=plot(od100,p=le..ri,color=magenta):
|
 |
(4.2.6) |
| > |
od101:=simplify(1);
p5:=plot(1,p=le..ri,color=green):
|
 |
(4.2.7) |
| > |
od110:=simplify(odds);
p6:=plot(od110,p=le..ri,color=orange):
|
 |
(4.2.8) |
| > |
od111:=simplify(odds);
p7:=plot(od111,p=le..ri,color=navy):
|
 |
(4.2.9) |
| > |
display(p0,p1,p2,p3,p4,p5,p6,p7); |
 |
(4.2.11) |
 |
(4.2.12) |
 |
(4.2.13) |
Theory for strategy
tables
Instruction for reading the table of odds
S(1) and S(2) are two patterns of length three
In the table we read the
odds for S(2) against S(1)
Choose the S(1) in left vertical column
Choose the S(2) in upper horizontal row
In the intersection we find the odds for S(2) against S(1)
Example
The odds for S(2) = 
The digit 3 in 
graphs
Graphs for strategy in winning ways for two persons game
In the image beolw you can see eight graphs, one for each pattern
On the vertical axes you see the text odds mot xxx
read odds against xxx
The graphs with highest odds are in red. The digits are in bas ten.
Convert to base two. e g 6(ten)=110(two)
Q is a break point for probability BPP
example
A choice 011
B if p < BPP choose 1 = "001"
if p > BPP choose 5 = "101"
B has always odds >1 against A
strategy
STRATEGY FOR CHOICE OF PATTERN
In the corners of the cube the patterns are given 000,...,111
Over the patterns the break-point-probability BPP in green eg 011 has BPP= 0.592
Person A (unsuspecting) makes a choice of one pattern and the probability p for 1
Restriction for choice of p 0.25 < p < 0.75 NA = not applicable e g p=0.206
After that person B makes her choice of pattern.
State : The odds for B against A. Of course B is interesting odds > 1
To every pattern (execpt 000 and 111) there are two arrows
Example Pattern 011
If p < BPP take the blue arrow from 001
If p > BPP take the red arrow from 101
For details see the table below (q = 1 - p)
Calculating the value of BPP Solve in Maple the equation odds(p<BPP) = odds(p > BPP)
Pattern for A BPP Pattern for B and odds min odds for B
p < BPP odds p > BPP odds
000 0.206 NA 100 1/
1.37
001 0.382 000 q/p 100 1/
- 1 1.618
010 0.525 001 1/p 110 p(1+pq)/
1.905
011 0.592 001 q/
101 (1-pq)/(q(1+p)) 1.167
100 0.408 010 (1-pq)/(p(1+q)) 110 p/
1.167
101 0.475 001 q(1+pq)/(
110 1/q 1.905
110 0.618 011 1/
- 1 111 p/q 1.618
111 0.794 011 1/
- 1 NA 1.37
NONTRANSITIVITY
The strategy shows that B always can win over A
When A (unsuspecting) sees B winning, A choose the last pattern of B and perhaps a new p
B chooses a new pattern according to pattern and p of choice by B
Sooner or later we get a loop with 3 ... 8 patterns
An example with all patterns in the loop is
110 - 111 - 011 - 101 - 001 - 000 - 100 - 010 - 110
Program for simulation of game
| > |
with(RandomTools[MersenneTwister]):
M:=NewGenerator(range=10^10): |
PLAYER A
Choose your pattern of length 3
End with ;
 |
(4.4.1) |
Choose probaabilty for 1
within following limits
0.25 < p < 0.75
End with ;
 |
(4.4.2) |
Choose number of trials
 |
(4.4.3) |
PLAYER B
Choose pattern S[2] and oddb:=
 |
(4.4.4) |
 |
(4.4.5) |
bi delivers a string "1" with probability p else "0"
| > |
bi:=proc()global b;
if Float(M(),-10)<p then
b:= "1"
else b:="0"
end if
end proc:
|
procedure trier gives bi (0 or 1) to eventually give one of the stopping patterns
| > |
trier:=proc() local ok,i,U;global k,v1,v2;
U:="":k:=3:v1:=false:v2:=false:ok:=false:
for i from 1 to k do
U:=cat(U,bi()):
end do:
if U=S[1] then
v1:=true:ok:=true:
end if;
if U=S[2] then
v2:=true:ok:=true:
end if:
while ok=false do
U:=substring(U,2..3):
U:=cat(U,bi());
k:=k+1:
if U=S[1] then
v1:=true:ok:=true:
end if;
if U=S[2] then
v2:=true:ok:=true:
end if:
end do:k;
end proc: |
Simulation
Start new simulation from here
| > |
for i from 1 to 2 do
w[i]:=0:
end do:
|
| > |
for i from 1 to trial do
tr:=trier();
if v1 then w[1]:=w[1]+1: end if:
if v2 then w[2]:=w[2]+1: end if:
end do:
Digits:=4:
print('RESULTOFSIMULATION');
print('Afirst',w[1]);
print('Bfirst',w[2]);
print('oddsforBagainstA');
print(evalf(w[2]/w[1])); |
| > |
print('theoreticvalueforodds');
print(evalf(oddb(p))); |
 |
 |
(4.4.7) |
Asymptotic Values for one Stopping Pattern
Theory
Generating rational functions for asymptotic expansion
Quotation from Feller (Generating functions, Partial Fraction Expansions p 275)
... limit our exposition to the simple case of rational functions
Suppose then that the generation function is of the form
(4.1) P(s) = U(s)/V(s)
where U and V are polynomials ...
(...proof..)
(4.5) 
(...proof...)
Theorem. If P(s) is a rational function with a simple root 
A numerical example on tossing a coin is given in Feller . It treats the event that after n trials no sequence HHH can occur.
The result in Feller can be tested by the program below. SeeApplication
I will use the ideas in Feller and the results from the investigatioons in one stopping pattern.
Put Ψ(t) = 
Put e[i] = 
The values e[i] are calculated for i from 1 to k-1 in the program
In program a method is used to calculate f(t) in collapsed form in f:=proc(t)
and then the expanded form See program
The values c[i] are calculated for i from 1 to k in the program with the method in one stopping pattern
In program the same method of calculating g(t) in collapsed form in g :=proc(t)
and then expanded form See program
We need the derivative
gprim := diff(g(t),t); in the program
Time to choose the value p for the probability P(1) to determine the roots of denominator
p:= ...
Solve the equation
eq:=g(t)=0;
r:=fsolve(eq);
If there is more than one value for r choose the one with least absolute value and
Insert applicable index
Eventually
q
Program compare theoretic and asymptotic values
DISTRIBUTION ASYMPTOTIC
Leading numbers Choose binary pattern S
| > |
S:="111":
len:=length(S):k:=len:
for i from 1 to k do
d[i]:=0:
ls:=substring(S,1..i):rs:=substring(S,-i..-1):
if ls=rs then
d[i]:=1:
for j from 1 to i do
if substring(ls,j..j)="1" then
d[i]:=d[i]/p
else d[i]:=d[i]/(1-p):
end if
end do
end if
end do:
for i from 1 to k do
d[i];
end do;
|
Recursion to calculate c[i] for denominator
| > |
k:=len:d[0]:=1:
for i from 1 to k do
c[i]:=(d[k-i+1]-d[k-i])/d[k]:
end do:
for i from 1 to k do
simplify(c[i]);
end do;
|
Recursion to calculate e[i] for numerator
| > |
for i from 1 to k-1 do
e[i]:=d[k-i]/d[k]:
end do:
for i from 1 to k-1 do
simplify(e[i]):
end do;
|
 |
 |
(5.2.3) |
| > |
g:=proc(t) local i; global k,gv;
gv:=0:
for i from 1 to k do
gv :=gv+c[k-i+1]:
gv:=gv*t:
end do;
1-gv;
end proc; |
 |
(5.2.5) |
Compressed form above at programming
expanded form below
| > |
g(t):=sort(expand(g(t)));
|
 |
(5.2.6) |
| > |
f:=proc(t) local i; global k,fv;
fv:=0:
for i from 1 to k-1 do
fv:=fv+e[k-i]:
fv:=fv*t:
end do;
1+fv;
end proc; |
 |
(5.2.10) |
| > |
f(t):=sort(expand(f(t)));
|
 |
(5.2.11) |
 |
(5.2.13) |
Time to choose the value for p=probability("1")
 |
(5.2.15) |
| > |
eq:=g(t)=0;
r:=fsolve(eq); |
 |
 |
(5.2.16) |
Jump over next line if only one value for r above.
If there are several roots above take that with the
least positive value, choose the applicable index in r[] below.
s=numerator in asymptotic
| > |
t:=r: s:=-evalf(f(r)/gprim); |
 |
(5.2.17) |
Distribution Asymptotic : qa[i]
| > |
k:=len: trial:=20: Digits:=k+10: |
| > |
for i from k to trial do
qa[i]:=s/r^(i+1):
end do: |
Distribution Theory : q[i]
| > |
for i from 0 to k-1 do
q[i]:=1:
end do:
for i from k to trial do
q[i]:=0:
for j from 1 to k do
q[i]:=q[i]+c[j]*q[i-j]:
end do
end do:
|
Compare results in theory and asymptotic
| > |
print('i','theory','asymptotic');
for i from k to trial do
print(i,q[i],qa[i]);
end do; |
Application
Application on asymptotic distribution
Example 1
Compare the results from Feller and from running program shows that they agree
In Feller 
Example 2
Example from school (faked)
The pupils got as exerice to toss a coin 1000 times and write down the result
In the report from a pupil you found the sequence ....1010101010101010 ...
What is the probability that the report was faked?
With the program we find
S:="1010101010101010" p:=0.5;
trial:=1000:
Answer: about 99%
Example 3
Mr Feller and his friend Mr Fellow played backgammon with unbiased dices
Feller had just published his famous book about Probability Theory
Mr Fellow proposed to set the dice outcomes 5 and 6 to P(1), the other to 0
So P(1) =1/3.
Mr Feller rolls the dice with a sequence 10110011100011110000
Mr Feller says to his friend:
How many tosses do you have to be sure to 99 % to get my sequnce.
I think that will take about 2 seconds for a roll
Mr Fellow : I think we have to wait at least 50 years to have a machine and a program,
perhaps it will be named Maple 11. or 11.00
In the year 2008 and with Maple 11 we find
1 - 99% = 0.01
s/r
Program for mean and median waiting times
COMPARE MEAN WAITING TIME TO MEDIAN WAITING TIME
| > |
S:="1101001110010101010111":
len:=length(S):k:=len:
for i from 1 to k do
d[i]:=0:
ls:=substring(S,1..i):rs:=substring(S,-i..-1):
if ls=rs then
d[i]:=1:
for j from 1 to i do
if substring(ls,j..j)="1" then
d[i]:=d[i]/p
else d[i]:=d[i]/(1-p):
end if
end do
end if
end do:
|
Recursion to calculate c[i] for denominator
| > |
k:=len:d[0]:=1:
for i from 1 to k do
c[i]:=(d[k-i+1]-d[k-i])/d[k]:
end do:
for i from 1 to k do
simplify(c[i]);
end do:
|
Recursion to calculate e[i] for numerator
| > |
for i from 1 to k-1 do
e[i]:=d[k-i]/d[k]:
end do:
for i from 1 to k-1 do
simplify(e[i]):
end do:
|
| > |
g:=proc(t) local i; global k,gv;
gv:=0:
for i from 1 to k do
gv :=gv+c[k-i+1]:
gv:=gv*t:
end do;
1-gv;
end proc; |
 |
(5.4.2) |
Compressed form above at programming
expanded form below
| > |
g(t):=sort(expand(g(t)));
|
| > |
f:=proc(t) local i; global k,fv;
fv:=0:
for i from 1 to k-1 do
fv:=fv+e[k-i]:
fv:=fv*t:
end do;
1+fv;
end proc; |
 |
(5.4.5) |
| > |
f(t):=sort(expand(f(t)));
|
Time to choose the value for p=probability("1")
 |
(5.4.8) |
| > |
eq:=g(t)=0;
r:=fsolve(eq); |
Jump over next line if only one value for r above.
If there are several roots above take that with the
least positive value, choose the applicable index in r[] below.
 |
(5.4.10) |
s=numerator in asymptotic
| > |
t:=r: s:=-evalf(f(r)/gprim); |
 |
(5.4.11) |
ex=mean waiting time (Expectation)
| > |
ex:=0:
for i from 1 to len do
ex:=ex+d[i]:
end do:
ex; |
 |
(5.4.12) |
My own experiment
| > |
u:= ex*ln(r); |
 |
(5.4.14) |
 |
(5.4.15) |
median = The probability that the pattern has not occured is 0.5
(calculate by the formula for asymptotic values)
| > |
median:=(evalf((ln(s)-ln(.5))/ln(r)))-1; |
 |
(5.4.16) |
control: Probability q for the median waiting time
 |
(5.4.17) |
median/mean
q[median] = 1/2
median ∼ (ln(2)+ln(s))/ln(r) ∼ ln(2)/ln(r) ∼ln(2)*ex
median/ex ∼ ln(2)
 |
(5.4.18) |
ln(2) ∼ 0.6931471
Summary
q[ex] ∼ 1/e
median/ex ∼ ln(2)
Finis
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author
are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.
This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.
