STOPPING PATTERNS IN RANDOM SEQUENCES
Author Roland Engdahl
University of Kalmar
Sweden
mr.engdahl@telia.com
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
Leading numbers
Choose binary pattern S and probability for "1"
Recursion to calculate c[i]
Expectation and Variance
Results
Distribution
Program one pattern simulation
Simulation one pattern
Choose same binary pattern S and probability for "1" as in theoretic, number of trials
bi delivers a string "1" if with probability p else "0"
trier gives the number k of bi to give the stopping pattern
Simulation
Start new simulation from here
mean and variance
Two Stopping Patterns
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
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"
Calculation
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
expectation
Program two patterns simulation
Two stopping patterns simulation
Choose same binary pattern S[1] and S[2] probability for "1" as in theoretic, number of trials
Winning Ways for Two Persons Game
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
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
Calculation of odds for S[2] against s[1] Temporary results depending on S[2]
jump to applicable line of S[2] if S[2]=S[1] choose 1 in stead of odds after simplify
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
PLAYER A
Choose your pattern of length 3 End with ;
Choose probaabilty for 1
within following limits
0.25 < p < 0.75 End with ;
Choose number of trials
PLAYER B
Choose pattern S[2] and oddb:=
bi delivers a string "1" with probability p else "0"
procedure trier gives bi (0 or 1) to eventually give one of the stopping patterns
Asymptotic Values for one Stopping Pattern
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
Recursion to calculate c[i] for denominator
Recursion to calculate e[i] for numerator
Compressed form above at programming expanded form below
Time to choose the value for p=probability("1")
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
Distribution Asymptotic : qa[i]
Distribution Theory : q[i]
Compare results in theory and asymptotic
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
ex=mean waiting time (Expectation)
My own experiment
median = The probability that the pattern has not occured is 0.5 (calculate by the formula for asymptotic values)
control: Probability q for the median waiting time
median/mean q[median] = 1/2 median ∼ (ln(2)+ln(s))/ln(r) ∼ ln(2)/ln(r) ∼ln(2)*ex median/ex ∼ ln(2)
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.
