## [數學]FAMAT fall 2007 interschool (A) ### [數學]FAMAT fall 2007 interschool (A)

2. Suppose you have a 24-sided fair die, with each face labeled with exactly one of the 24
letters from the Greek alphabet. If you were to begin rolling the die, and keep rolling
until you have three successive rolls of alpha, theta, and mu (in that order), what is the expected number of rolls until you reach your goal?

3.Assume the same conditions as in question 2, except now you're rolling blindfolded
and someone else will record the letters that you roll, but they won't stop you when
your goal is reached. How many rolls would you need to make before stopping to have
greater than 90% probability of having three consecutive rolls of alpha, theta, and mu (in that order) somewhere in the sequence of your rolls?
CCC

QC ### Re: [數學]FAMAT fall 2007 interschool (A)

please ignore it for correct solution

QC 寫到:
2. Suppose you have a 24-sided fair die, with each face labeled with exactly one of the 24
letters from the Greek alphabet. If you were to begin rolling the die, and keep rolling
until you have three successive rolls of alpha, theta, and mu (in that order), what is the expected number of rolls until you reach your goal?

The probability distribution is a geometric distribution.
Let every set of 3 rolls be a single event, the probability of a event of (alpha, theta and mu)
is (1/24)3 = 1/13824
then the expected value for the number of events occur for the distribution
is 1 / (probatility of single event) = 13824
The number of rolls needed for 13824 sets of 3 dies = 13824+3-1 = 13826 rolls.

QC 寫到:
3.Assume the same conditions as in question 2, except now you're rolling blindfolded
and someone else will record the letters that you roll, but they won't stop you when
your goal is reached. How many rolls would you need to make before stopping to have
greater than 90% probability of having three consecutive rolls of alpha, theta, and mu (in that order) somewhere in the sequence of your rolls?

cdf of a geometric distribution = 1-(1-p)k
cdf of the distribution of a set of 3 dies = 1-(1-1/13824)k > 90%
=> 0.1 > (1-1/13824)k => log(0.1) = -1 > k log(1-1/13824)
=> -1 / log(13823/13824) < k  || 13823/13824<1 => log(13823/13824)<0
=> k > 31829.7xxx => Number of rolls = 31830+3-1 = 31832 rolls

☆子 是也 G@ry ### [數學]cool!!!

Very very cool!!!

It's almost a geometric distribution, but not a geometric distribution exactly, I think.

I think the answer of Q3 is 31828, which is very close to yours.
CCC

QC My method:

Let F=p(0)+p(1)x+p(2)x^2+...
F is the genereating function of p(n)

let r=1/24^3=1/13824
because p(n+3)=(1-(p(0)+p(1)+p(2)+...+p(n))*r
F/xxx=r*(1-F)/(1-x)
F*(1-x)=rxxx(1-F)
F=rxxx/(1-x+rxxx)

E(n)=p(1)*1+p(2)*2+...
= F'(1)
=(3rr-r*(3r-1))/rr
=1/r=13824

--------------------------
let 1/a,1/b,1/c be the 3 root of 1-x+rxxx=0

a~ 0.9999276515687950
b~ -0.0084693831120445
c~ 0.0085417315432198

S=F/(1-x)
=rxxx/(1-x+rxxx)(1-x)
~1/(1-x)-1.0001447278597800/(1-ax)-0.0041815685963448/(1-bx)+0.0043262968712862/(1-cx)

s(n)~1-1.0001447278597800*a^n-0.0041815685963448*b^n +0.0043262968712862*c^n

when n >100, b^n and c^n ~0
so
s(n)~1-1.0001447278597800*a^n
0.9~1-1.0001447278597800*a^n
n>= log((1-0.9)/1.0001447278597800)/log(0.9999276515687950)=31827.17955
the smallest n=31828

CCC

QC QC 寫到:
My method:

Let F=p(0)+p(1)x+p(2)x^2+...
F is the genereating function of p(n)

let r=1/24^3=1/13824
because p(n+3)=(1-(p(0)+p(1)+p(2)+...+p(n))*r
F/xxx=r*(1-F)/(1-x)
F*(1-x)=rxxx(1-F)
F=rxxx/(1-x+rxxx)

E(n)=p(1)*1+p(2)*2+...
= F'(1)
=(3rr-r*(3r-1))/rr
=1/r=13824

--------------------------

Sorry, I think you get something wrong:

First, you did not define what is p(n);
Even though you said
p(n+3)=(1-(p(0)+p(1)+p(2)+...+p(n))*r
Definition for p(0), p(1) and p(2) are definitely needed, [I assume that they are all 0 yet]
And I guess that p(n) is the probability that you can get one successive roll of a set of (alpha, theta and mu) by n rolls

Second, I assume that F = F(x) when not specified. And this notation is used for a cdf, we use G(x) for a pgf...

Third, p(n+3) is equal to G(n+3)(0)/(n+3)! but definitely not G(x)/x3
And even if you set x=0, the divided by zero situation make the whole thing undefined.

Forth, can you show how come "1-(p(0)+p(1)+p(2)+...+p(n))" = "(1-F(x))/(1-x)"?
G(x) = p(0)+p(1)x+p(2)x2+...+p(n)xn+p(n+1)x(n+1)+p(n+2)x(n+2)+... infinitely~~
It will NOT stop at any finite probability term.

Fifth, E(n)=1/p is a strong characteristic of a geometric distribution... and it is definitely not the answer as you've said that this is not a geometric distribution also, too.

QC 寫到:let 1/a,1/b,1/c be the 3 root of 1-x+rxxx=0

a~ 0.9999276515687950
b~ -0.0084693831120445
c~ 0.0085417315432198

S=F/(1-x)
=rxxx/(1-x+rxxx)(1-x)
~1/(1-x)-1.0001447278597800/(1-ax)-0.0041815685963448/(1-bx)+0.0043262968712862/(1-cx)

s(n)~1-1.0001447278597800*a^n-0.0041815685963448*b^n +0.0043262968712862*c^n

when n >100, b^n and c^n ~0
so
s(n)~1-1.0001447278597800*a^n
0.9~1-1.0001447278597800*a^n
n>= log((1-0.9)/1.0001447278597800)/log(0.9999276515687950)=31827.17955
the smallest n=31828

The first part is wrong, and certainly this part will get wrong too...
☆子 是也 G@ry (1) p(n) is the probability that you get only one successive roll of a set of (alpha, theta and mu) at the end by n rolls.

(2) what do you think "F" if I say F=1+x+2x^2+3x^4? Of caurse I meant F=F(x).
Do you think "F" or "G" really matter the result?
I've defined that F is the generating function ! Even I can eliminate the statement that "F is the generating function", because I've define that F=p(0)+p(1)x+p(2)x^2+...

(3) what is the coefficient of x^n of (F/xxx)? It's p(n+3), right?
p(n+3)=(1-(p(0)+p(1)+p(2)+...+p(n))*r
F/xxx
=sigma{p(n+3)*x^n|n=0 to infinite}
=r* sigma{(1-(p(0)+p(1)+p(2)+...+p(n))*x^n|n=0 to infinite}
=r*(sigma{x^n|n=0 to infinite}-sigma{(p(0)+p(1)+p(2)+...+p(n))*x^n|n=0 to infinite})
=r*(1/(1-x)-F/(1-x))
=r*(1-F)/(1-x)

(5) In geometric distribution, p(n)=p*(1-p)^(n-1).
In this case, you see that p(1)=0, p(2)=0, p(3)=r, p(4)=r, p(5)=r.
You can tell the difference, right?
That's why I said it's close to geometric distribution, but not a geometric distribution exactly.

(6) I've verified the result with Excel. I think my result in this problem is correct.

CCC

QC if you set x=0, the divided by zero situation make the whole thing undefined.

r=1/24^3=1/13824
F=rx^3+rx^4+rx^5+(1-r)rx^6+....
F/xxx=r+rx+rx^2+(1-r)rx^3+...

I can't find anything undefined even when x=0.

For H(x)=1/x, even H(0) is undefined, we can still deal with H(x), right?

Do I use F(0) or (F(0)/0^3) anywhere in my calculation? No.

CCC

QC generating function 我玩過20幾年了, 再加上用excel驗算, 應該是不會錯的. Sorry for eliminating some steps.
^___^
CCC

QC Well, I'm sorry that I misunderstood some of your points.
But I finally find out what's the problem:

p(n+3)=(1- (p(0)+p(1)+p(2)+...+p(n)) )*r

The above formula is not appropriate.
Assume that p(0)=p(1)=p(2)=0 [ It's really obvious...]
Please consider the case that n=0, 1 and 2
Do you really think that p(3)=p(4)=p(5) = r, whereas p(6) = r(1-r) ≠ r ?

☆子 是也 G@ry Do you really think that p(3)=p(4)=p(5) = r, whereas p(6) = r(1-r) ≠ r ?

yes.
p(3)=p(4)=p(5) = r
p(6) = r(1-r)
p(7)=r*(1-2r)
p(8)=r*(1-3r)
p(9)=r*(1-4r+rr)

I don't think there is any reason to consider "p(6)=r" or not.
p(6) = r(1-r) , no problem.
CCC

QC QC 寫到:

G@ry 寫到:

Do you really think that p(3)=p(4)=p(5) = r, whereas p(6) = r(1-r) ≠ r ?

yes.
p(3)=p(4)=p(5) = r
p(6) = r(1-r)
p(7)=r*(1-2r)
p(8)=r*(1-3r)
p(9)=r*(1-4r+rr)

I don't think there is any reason to consider "p(6)=r" or not.
p(6) = r(1-r) , no problem.

Well, if then, do you think that p(n) can be negative for some n?
Let me show you:
p(8) = 1/2*(1-3/2) = -1/4 < 0

The definition of p(n) is inaccurate.
☆子 是也 G@ry What is the range of probablity "r" to have three successive rolls of "1", "2", and "3" with a k-sided die labled with number "1" to k?
(k>=3)

let the probablity to get "1" in one roll be P1
let the probablity to get "2" in one roll be P2
...
let the probablity to get munber k in one roll be Pk

P1+P2+P3+...+Pk=1
1>= Pi >=0 for very i=1 to k

r=P1*P2*P3
<=((P1+P2+P3)/3)^3
<=(1/3)^3
=1/27

we don't have to consider r=1/2 because r<=1/27
CCC

QC QC 寫到:What is the range of probablity "r" to have three successive rolls of "1", "2", and "3" with a k-sided die labled with number "1" to k?
(k>=3)

let the probablity to get "1" in one roll be P1
let the probablity to get "2" in one roll be P2
...
let the probablity to get munber k in one roll be Pk

P1+P2+P3+...+Pk=1
1>= Pi >=0 for very i=1 to k

r=P1*P2*P3
<=((P1+P2+P3)/3)^3
<=(1/3)^3
=1/27

we don't have to consider r=1/2 because r<=1/27

How about if I flip a coin or roll an unfair die?
Or if I just need a set of 3 rolls of any kinds of conbinations only, which obviously r = 1.
p(0)=0, p(1)=p(2)=1, but p(3) = (1-p(0))*r = 0  , is it possible ???
I don't think that there should be any limit on the probability on a single event probability r.

If you still do not see the problem:

p(3)=p(4)=p(5) = r

Should it be possible?

(1) p(n) is the probability that you get only one successive roll of a set of (alpha, theta and mu) at the end by n rolls.

Actually, we are considering at least one successive roll of a set but not ONLY one...

Anyway, p(4) = p(3) means that p(4)-p(3)=0
Should the probability of 3 rolls same with the probability of 4 rolls to get a successive roll set?
Shouldn't we gain a larger chance of having one more roll?

☆子 是也 G@ry p(n) is the probability that you get only one successive roll of a set of (alpha, theta and mu) at the end by n rolls.

For p(n) & F, I was considering "ONLY one successive roll of a set at the end" but not at least one.
When I was considering "at least one", I use s(n), and "S" as the generating function of s(n).
s(n)=p(0)+p(1)+p(2)+...+p(n)
S=F/(1-x)
CCC

QC In my calculation of r<=1/27, I did not limit the die as fair or unfair one.

If you flip an unfair coin in order to get the pattern "(+)(-)(-)", and the chance to get (+) in one roll is p:
r=p*(1-p)*(1-p)
you will find r<=4/27.
we still don't have to consider r=1/2
----------------------------------------

If you flip an unfair coin/die in order to get the pattern "(+)(+)(+)", and the chance to get (+) in one roll is p, the GF is different because the recurrent relationship is different:
let q=1-p
p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp
(F-pppxxx)/xxxx=pppq(1-F)/(1-x)
F=pppxxx/(1-qx-qpxx-qppxxx)

when you want "a set of 3 rolls of any kinds of conbinations only", take p=1, q=0
F=pppxxx/(1-qx-qpxx-qppxxx)
=xxx
that is, p(3)=1, p(0)=p(1)=p(2)=p(4)=p(5)=...=0
CCC

QC Notice the word "ONLY" and "one set at the end".

CCC

QC QC 寫到:p(n) is the probability that you get only one successive
roll of a set of (alpha, theta and mu) at the end by n rolls.

For p(n) & F, I was considering "ONLY one successive roll of a set at the end" but not at least one.

When I was considering "at least one", I use s(n), and "S" as the generating function of s(n).

s(n)=p(0)+p(1)+p(2)+...+p(n)

S=F/(1-x)

Well, I think I mixed up the question 2 and question 3 somewhere, but it's not the main point...

QC 寫到:In my calculation of r<=1/27, I did not limit the die as fair or unfair one.

If you flip an unfair coin in order to get the pattern "(+)(-)(-)", and the chance to get (+) in one roll is p:
r=p*(1-p)*(1-p)
you will find r<=4/27.
we still don't have to consider r=1/2
----------------------------------------

If
you flip an unfair coin/die in order to get the pattern "(+)(+)(+)",
and the chance to get (+) in one roll is p, the GF is different because
the recurrent relationship is different:
let q=1-p
p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp
(F-pppxxx)/xxxx=pppq(1-F)/(1-x)
F=pppxxx/(1-qx-qpxx-qppxxx)

when you want "a set of 3 rolls of any kinds of conbinations only", take p=1, q=0
F=pppxxx/(1-qx-qpxx-qppxxx)
=xxx
that is, p(3)=1, p(0)=p(1)=p(2)=p(4)=p(5)=...=0

then it's so easy to see as you accept that there should be no difference for the solution for a fair or unfair situation...
how about if I flip an unfair coin to get a pattern of (+)(+)(+) with the probability of (+) is 4/5 ?? The final r = (4/5)3 = 64/125 > 1/2
The main point is, r must be able to be any number between 0 and 1...

If you put r=1/3 in your previous equation, you will still get p(10)<0

What is the difference to get a set of "altha,theta, and mu"  and to get a "(+),(+),(+)"?

But the new equation is still incorrect:

p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp

how about if p = 1/2? q=1/2 too...
I assume that p(3)=1/23 =1/8 as there is no definition from your equation...
p(0)=p(1)=p(2)=0, so p(4)=p(5)=p(6)=1/16
do you think p(3)=1/2 and p(4)=p(5)=p(6)=1/16???
and also p(7)= 7/128????
Do you still think the equation is valid?
☆子 是也 G@ry What is the difference to get a set of "altha,theta, and mu" and to get a "(+),(+),(+)"?
They are really different. I've shown you the difference in the recurrent relationship. Then the result changed according to the recurrent relationship.

If you flip an unfair coin/die in order to get the pattern "(+)(+)(+)",
and the chance to get (+) in one roll is p, the GF is different from "(+)(-)(-)" because the recurrent relationship is different:
let q=1-p
p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp
(F-pppxxx)/xxxx=qppp(1-F)/(1-x)
F=pppxxx/(1-qx-qpxx-qppxxx)

when you want to take p=1/2, q=1/2:
F=1/8*xxx/(1-x/2-xx/4-xxx/8)

we get another recurrent relationship:
p(n+3)=p(n+2)/2+p(n+1)/4+p(n)/8

then
p(0)=p(1)=p(2)=0
p(3)=1/8
p(4)=1/16
p(5)=p(4)/2+p(3)/4+p(2)/8=1/16
p(6)=p(5)/2+p(4)/4+p(3)/8=1/16
p(7)=p(6)/2+p(5)/4+p(4)/8=7/128
No problem at all, I think.

Notice that p(3)=1/8, not 1/2.

If you flip an unfair coin to get a pattern of (+)(+)(+) with the probability of (+) is 4/5

p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp

F=pppxxx/(1-qx-qpxx-qppxxx)
=64/125*xxx/(1-x/5-4xx/25-16xx/125)

we get another recurrent relationship:
p(n+3)=p(n+2)/5+p(n+1)*4/25+p(n)*16/125

 p(0)=0 p(1)=0 p(2)=0 p(3)=0.512 p(4)=0.1024 p(5)=0.1024 p(6)=0.1024 p(7)=0.0499712 p(8)=0.03948544 p(9)=0.02899968 p(10)=0.01851392 p(11)=0.01339686912 p(12)=0.009353560064 p(13)=0.006383992832 p(14)=0.004488167424 p(15)=0.003116328026112

CCC

QC To get ONLY ONE successive roll of a set of (+)(+)(+) at the END by n rolls, we have to get only one successive roll of a set of (-)(+)(+)(+)at the END by n rolls when n>3.
So, p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp

That is the reason of different recurrent relationship form (+)(-)(-) or (alpha, theta, mu). OK?
CCC

QC QC 寫到:To get ONLY ONE successive roll of a set of (+)(+)(+) at the END by n rolls, we have to get only one successive roll of a set of (-)(+)(+)(+)at the END by n rolls when n>3.
So, p(n+4)=(1-(p(0)+P(1)+...+p(n)))*qppp

That is the reason of different recurrent relationship form (+)(-)(-) or (alpha, theta, mu). OK?

Well, thank you very very much for correcting my annoying wrong interpretation of the question and your correct answer.
The main point was that my assumption that "All events are independent" is wrong.
Thank you for your correct solution and detail explanation and sorry for my misunderstanding.
☆子 是也 G@ry 