Application Center - Maplesoft

# Stopping Patterns in random Sequences

You can switch back to the summary page by clicking here.

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) = pq

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

 > restart:

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;

 (2.2.2)

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)

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

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;

 (2.3.2)

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

 > restart:

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)

 (3.2.2)

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)

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

 (3.3.1)

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]

 > restart:with(plots):

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)

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.10)

 > eq:=od001=od110;

 (4.2.11)

 > p:=fsolve(eq,p=0.5);

 (4.2.12)

 > od110;

 (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

 > restart:

 > with(RandomTools[MersenneTwister]): M:=NewGenerator(range=10^10):

PLAYER  A

Choose your pattern of length 3
End with
;

 > S[1]:= "101";

 (4.4.1)

Choose probaabilty for 1

within following limits

0.25 < p < 0.75
End with ;

 > p:=0.475; q:=1-p:

 (4.4.2)

Choose number of trials

 > trial:=100000;

 (4.4.3)

PLAYER B

Choose pattern S[2] and  oddb:=

 > S[2]:="110";

 (4.4.4)

 > oddb:=p->1/q;

 (4.4.5)

bi delivers a string "1"  with probability p else "0"

 > bi:=proc()global b;    if Float(M(),-10)

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]));

 (4.4.6)

 > 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

 > restart:

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;

 (5.2.1)

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;

 (5.2.2)

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.4)

 > g(t);

 (5.2.5)

Compressed form above at programming
expanded form below

 > g(t):=sort(expand(g(t)));

 (5.2.6)

 (5.2.7)

 (5.2.8)

 > 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.9)

 > f(t);

 (5.2.10)

 > f(t):=sort(expand(f(t)));

 (5.2.11)

 (5.2.12)

 > gprim:=diff(g(t),t);

 (5.2.13)

 (5.2.14)

Time to choose the value for p=probability("1")

 > p:=0.5;

 (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.

 > r:=r[1];

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;

 (5.2.18)

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:

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

 > restart:Digits:=15:

 > 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.1)

 > g(t);

 (5.4.2)

Compressed form above at programming
expanded form below

 > g(t):=sort(expand(g(t)));

 (5.4.3)

 > 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.4)

 > f(t);

 (5.4.5)

 > f(t):=sort(expand(f(t)));

 (5.4.6)

 > gprim:=diff(g(t),t);

 (5.4.7)

Time to choose the value for p=probability("1")

 > p:=0.5;

 (5.4.8)

 > eq:=g(t)=0; r:=fsolve(eq);

 (5.4.9)

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.

 > r:=r[2];

 (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)

 (5.4.13)

My own experiment

 > u:=ex*ln(r);

 (5.4.14)

 > evalf(s/r^(ex+1));

 (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

 > s/r^(median+1);

 (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)

 > evalf(median/ex);

 (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.