From: Stuart Anderson[SMTP:strt@u.washington.edu]

Sent: Saturday, December 20, 1997 6:55 PM

To: Granillo, Anthony R

Subject: Re: Help with my homework

Here are some partial results. I ran out of time to work on it, as

there were many interruptions. I'll have more for you after I come back

from my Christmas visit to my parents...

These are the meanings of each line (as I understand them) and their

probabilities:

Value Probability Changing? Strong?

6 1/8 yes no

7 3/8 no yes

8 3/8 no no

9 1/8 yes yes

By adding up the cases, you can see that the following are true for

each line:

p(s) = 1/2, p(w) = 1/2, p(c) = 1/4, p(u) = 3/4,

where p( ) means "probability of" and s = strong, w = weak, c = changing,

u = unchanging.

Since each oracle consists of 6 lines, the probability of an oracle

with NO changing lines is (3/4)^6, that is, 3/4 to the sixth power.

Whenever you have a yes/no question (in this case, "is there at least

one changing line?") and the probability is constant (in this case, p(no

c's) = (3/4)^6 and p(at least one c) = 1-(3/4)^6), you get a BINOMIAL

distribution. The theory of such distributions then states that the

expected number of "yes" answers to the question out of N trials will

be p(yes)*N, and the expected number of "no" answers will be p(no)*N.

Since p(no)=(3/4)^6 and N=431, you should expect [(3/4)^6]*431 oracles

to show up with no changing lines. Call this E(nochange). (The accepted

mathematical abbreviation for "expected # of" is E( ), so E(no) is the

expected number of "no" answers to the question, E(xx) is the expected

number of repetitions of two identical oracles, etc.)

For comparison with your actual castings, you also need to know the

standard deviation sigma. Theory says it is [p(yes)*p(no)*N]^1/2,

that is, the square root of the product of the yes and no probabilities and

the number of trials.

As for the expected numbers of various patterns of repetition, they

are somewhat more complicated, but I can calculate them too, I just didn't

get to it yet. The basic idea is that you an prove from the table I gave

at the top of this letter that the question of whether a line is weak or

strong is statistically independent of the question of whether it is

changing or unchanging. You can see this as follows:

Assume a line is weak. Then it is a 6 or an 8, and there are three

ways to throw an 8 and only one way to throw a 6, so the probability of a 6

is 1/4. Therefore there is a 1/4 probability that the line is changing,

given that we know it is weak. But that's the same probability you

get if you DON'T know whether it's weak or strong, so knowledge of the line's

strength or weakness doesn't give you any new clue as to whether it's

changing or unchanging. Therefore the probabilities are independent.

That means that we can think of the process of generating an oracle as

two separate and independent steps: (A) Toss two coins. If they both

come up heads, the line is changing. (B) Toss one coin. If it comes up

heads, the line is strong. This process gives exactly the same probabilities

as the one you described to me, and is obviously composed of two

independent parts, one determining strength/weakness and the other

determining change/nochange.

To calculate the probability that two specific oracles x1, x2 will

match, you need to know whether they have changing lines. There are 4 cases:

1) If there are no changing lines in either oracle, then they must

match first try, i. e., they have one chance to match, x1=x2.

2) If x1 has a changing line and the x2 doesn't, then x2 could match

either x1 or x1' (where x1' is what x1 changes to), i. e., they have

two chances to match, x1=x2 or x1'=x2. Likewise, if x1 is unchanging and

x2 changes, then there are two chances to match, x1=x2 or x1=x2'.

3) If both oracles are changing, and exactly the same lines are

changing in both oracles, then they have two chances of matching, since either

all the lines match so x1=x2 (and then automatically x1'=x2', since they

change in the same way), or all the unchanging lines match and all the

changing lines mismatch, so x1=x2' (and then automatically x1'=x2).

4) Finally, if both oracles are changing but in different ways, there

are 4 chances for them to match: x1=x2, x1'=x2, x1=x2', or x1'=x2'.

Since the question of changing vs. unchanging is independent of the

question about strong vs. weak, I can break the calculation into two

steps:

First, calculate the probabilities of the 4 cases above. Call them

p(1), p(2), p(3), and p(4).

Second, calculate the probability of the match given only one chance.

Call it p(1match).

Then, since p(1) through p(4) are probabilities having to do with

changing vs. unchanging, they are independent of p(1match) which is about

strong vs. weak. Therefore, to calculate the total probability of a match

between two oracles x1 and x2, you can multiply and add: the total

probability of a match is p(match)= p(1)*p(1match)*1 + p(2)*p(1match)*2 +

p(3)*p(1match)*2 + p(4)*p(1match)*4, where the last number multiplied on in

each term is the number of chances to match for that case.

Now p(1match) is easy to calculate: since p(s)=1/2=p(w), the chance

of a match on each line is 1/2, i. e., there is a 1/2 chance that the first

line of x2 will match the first line of x1, etc. Then since each line

is generated independently, the probability of matching two oracles in

one try is just (1/2)^6. This is p(1match).

All I have left to do is to calculate p(1) through p(4) and plug them

into the formula I gave above. This will give the p(match), the

probability that any two specific oracles will match.

Now since we are assuming for purpose of argument that the oracles are

truly random, and each is generated independently, it does not matter

which two we pick. In other words, p(match) is the probability of

finding two consecutive oracles that match, or also two non-consecutive

oracles.

Therefore, the probability of finding xx is the same as x-x or x--x.

These are all p(match). Now finding xxx means that x1=x2 and x2=x3.

Each of these is p(match) and they are independent, since the fact x1=x2

shouldn't influence x3 in any way. Therefore the probability of xxx

is p(match)*p(match) = [p(match)]^2. All the other probabilities you

want to know can also be derived from p(match) in this way.

Then once you have all these probabilities, since the distribution is

binomial, you can use the formulas I gave above for the expected

number of occurrences of each pattern (E(xx), E(x-x), E(x--x) E(xxx), etc.) and

its standard deviation.

One word of caution though: When counting xx patterns, the xxx

patterns will get mixed up with them, since xxx means x1=x2 and x2=x3, so it

will be counted as two xx patterns. Similarly, xxxx will show up as three

xx patterns and two xxx patterns. If you want to find the expected

number of xx repetitions that are NOT embedded in these longer repetitions, you will need to take E( xx)-2*E(xxx).

Once I complete the calculations of p(1) through p(4) I'll get back to

you with hard numbers instead of formula and theory. In the mean time, I

hope this helps, (or at least gives you something to think about!)

Happy holidays!

Stuart Anderson

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

12/30/97

Hi again, Tony.

Here are the numerical results and the rest of the theory.

We still needed to calculate p(1) through p(4), which is done as follows:

Case p(1): neither oracle has any changing lines. Since the chance of a

given line NOT changing is 3/4 and there are 6 lines in each oracle, the

chance that all 6 lines will not change is (3/4)^6. Since both oracles are

assumed to be random and independent, the probability of case p(1) is

[(3/4)^6]*[(3/4)^6].

Case p(2): one oracle has changing lines and one does not. Since the

probability of no changing lines is (3/4)^6, the opposite case, namely

that there ARE some changing lines, has probability 1-(3/4)^6. Therefore

the probability of the first oracle having no changing lines and the

second having some changing lines is [(3/4^6]*[1-(3/4)^6]. There is also

the possibility that the second oracles is the one without changing lines,

while the first oracle has some; the probability of this is exactly the

same of course, and so the total probability of case p(2) is

2*[(3/4^6]*[1-(3/4)^6].

Case p(3): both oracles have exactly the same pattern of changing lines.

For each corresponding pair of lines in the two oracles, the probabilities

break down as follows: The probability that both lines are unchanging is

(3/4)*(3/4) = 9/16. The probability that both lines are changing is

(1/4)*(1/4) = 1/16. Since these are the two possible ways of matching,

the total probability of a match at each line position in the oracle pair

is 9/16 + 1/16 = 5/8. Therefore, the chance that all 6 pairs of lines

match (so that both oracles have the same pattern of changing lines) is

(5/8)^6. HOWEVER, this includes the case p(1), since if neither oracle

has any changing lines, then the pattern of changing lines is the same for

both oracles, namely, there aren't any. Therefore to get the pure case

p(3) without case p(1) mixed up in it, we must subtract p(1), i. e., we

have the net probability p(3) = (5/8)^6 - [(3/4)^6]*[(3/4)^6].

Case p(4): both oracles have changing lines and the patterns are

different. This is now very easy, since the 4 cases cover all

possibilities, and the total probability must add up to 1. Therefore,

p(4) = 1-p(1)-p(2)-p(3) = 1-(2*[(3/4^6]*[1-(3/4)^6])-(5/8)^6.

From these formulas, you can calculate the following explicit numbers:

p(1)=0.031676352

p(2)=0.146302164

p(3)=0.027928293

p(4)=0.794093192

Notice that nearly 80% of the time, the two oracles will both have

changing lines and in different patterns.

From the formula I gave you last time, p(1match)= (1/2)^6=0.015625000., or

a roughly 1.6% chance. Putting all this into the formula from last time,

p(match)= p(1match)*[1*p(1) + 2*(p(2)+p(3)) + 4*p(4)] = .055570469, about

5.6%.

This is the probability of finding a repetition of oracles, but as I said

before, if you had a longer pattern of repetitions XXX, there would be 2

pairs XX embedded in it, so to count accurately, you have to make sure

that when you are counting pairs and you come to a triple, you count it as

two pairs. Likewise, a quadruple has 3 pairs embedded in it, etc.,

although a quadruple is so unlikely that I bet there aren't any in your

data!

Also, with 431 oracles, there are 430 positions where pairs are possible

(the last oracle can't match the one that follows, since there isn't one),

and 429 positions for patterns xxx and x-x, and 428 places for x--x.

Now I can give you all the numbers you want:

Pattern possible probability expected std dev

XX

XX+1 430 .055570469 23.895 4.7505

XX-1

X-X 429 .055570469 23.834 4.7450

X--X 428 .055570469 23.784 4.7395

XXX 429 .003088077 1.325 1.1492

The first three cases XX, XX+1, XX-1 are identical. As you can see, you

should expect about 24 +/- 5 of each of the patterns except XXX. For it,

you should expect 0, 1, or 2 occurrences. That's if you want to stay within

1 standard deviation of the average.

You could reject the hypothesis that the data are random at the 90%

confidence level if your data are more than 2 standard deviations away

from the average. In this case, for the first 5 lines of the table above,

you would accept the hypothesis that the data are random if the number of

occurrences lies in the range 24 +/- 2*5, that is, between 14 and 34.

Fewer than 14 or more than 34 occurrences of any of these patterns would be

cause to reject the null hypothesis at the 90% level. As for the last

line, 4 or more triples XXX would be cause to reject the null hypothesis.

Finally, here are the expected number and standard deviation of unchanging

oracles. I gave the formula last time; it's only necessary to plug in the

numbers: p(no c's) = (3/4)^6 = 0.177978516, p(at least 1 c) = 1-p(no c's)

= 0.822021484, and the number possible is 431. Therefore, there is the

following additional line in the table:

pattern possible probability expected std dev

UNCHANGING 431 0.177978516 76.709 7.9408

Again, 90% level rejection of the null hypothesis occurs at about 2

standard deviations, which in this case means that a result within

77 +/- 2*8 is random. You should reject the null hypothesis if the number

of unchanging oracles is greater than 93 or less than 61.

Well, these are (I think) all the numbers you asked for. By the way, all

these calculations are based on the my understanding that 6 and 8 are

weak, 7 and 9 are strong, 6 and 9 are changing, and 7 and 8 are

unchanging. Do I have that right? If not, please tell me so; it's no

trouble to recalculate the numbers now that the theory is in place.(ed. note, this is accurate, the numbers 7 and 8 generate unchanging lines.)

Also, in my last email, I mentioned an alternate method of generating the

oracles where you flipped 2 coins to determine changing vs. unchanging and

1 coin to determine weak vs. strong. I didn't mean to say that that was

the way I thought you really did it. I just meant that the method I

described would generate precisely the same probabilities as the real

method, and that it was easier for me to think about mathematically.

Anyway, I hope that's what you wanted. Drop a line if you have any

questions about any of this. I'm home till January 5, but I check my work

email regularly from here.

Good luck with the rest of your project.

Stuart Anderson

Tony, it looks like I made a slight calculation error. I forgot to punch

in the factor or 2 in the formula for p(2). All the formulae I gave you

are correct, but of course this throws all the numbers off (slightly).

The correct numbers are as follows:

p(1)= 0.031676352

p(2)= 0.292604327

p(3)= 0.027928293

p(4)= 0.647791028

p(1match)= 0.015625000

p(match)= 0.050998527

Pattern possible probability expected std dev

XX

XX+1 430 0.050998527 21,929 4.5619

XX-1

X-X 429 0.050998527 21.878 4.5566

X--X 428 0.050998527 21.827 4.5513

XXX 429 0.001476728 0.63352 0.79535

UNCHANGING 431 0.177978516 76.709 7.9408

As you can see, p(1), p(3) and p(1match) were already correct. Correcting

p(2) changes p(4) and p(match), which changes everything else except the

probabilities of UNCHANGING. (Good thing I had this in a spread

sheet...click, click, all fixed!)

In the correct computation, it is 65% of the time that two oracles will

both have changing lines in different patterns, and the chance of a match

between any two oracles works out to almost exactly 5.1%.

Also, I must admit I made a theoretical error in computing p(XXX). I

originally just said, X1=X2 and X2=X3, so it's just two matches, and the

probability is [p(match)]^2. That's wrong, because X1=X2 can happen in

several ways when there are changing lines in X1 or X2 or both. For

example, if X1=X2' (remember, X2' is what X2 changes to), then X3 has to

match X2', and it's no good if X3 matches X2, since that won't be the same

as X1. so you wouldn't have three in a row. That means you have to be

careful about which version, X2 or X2', matches X3. It has to be the same

version that matches X1. Therefore, in cases p(1), p(2) and p(4), X3 has

only one "target" to match, but if you have case p(3), then X1, X1' are

both the same as X2, X2', so X3 has 2 "targets" to match. Therefore, the

true calculation for p(XXX) is like this:

Cases p(1) through p(4) each break down into two subcases: p(u) in which

X3 is unchanging, and p(c) in which X3 is changing. p(u) = 0.177978516

from the table above, and p(c) = 1-p(u) = 0.822021484. These

probabilities are independent of p(1) through p (4), since they refer to a

different oracle, X3. Therefore, the probabilities multiply, so for

example, for case p(1u), the probability is p(1)*p(u). Also, in case p(u),

X3 has only 1 try to hit a target, while in case p(c) it has two tries.

The total n umber of ways to hit a target is (# of targets)*(# of tries).

Then you have the following table of cases (where the column "ways X1=X2"

is from the discussion of cases p(1) through p(4) in my first email):

#ways #ways

Case probability X1=X2 (X1=X2)=X3 product

p(1u) 0.005637710 1 1 0.005637710

p(1c) 0.026038642 1 2 0.052077284

p(2u) 0.052077284 2 1 0.104154568

p(2c) 0.240527043 2 2 0.962108172

p(3u) 0.004970636 2 2 0.019882544

p(3c) 0.022957657 2 4 0.183661256

p(4u) 0.115292886 4 1 0.461171544

p(4c) 0.532498142 4 2 4.259985136

Total 6.048678214

Each case contributes some probability to a XXX match, and the total is

p(XXX)=

p(1u)*[p(1match)*#ways X1=X2]*[p(1match)*#ways (X1=X2)=X3]

+ p(1c)* " "

+ ...

+ p(4c)* " " .

This total is the contribution of all the ways to match times the

probability of each case. Since [p(1match)]^2 factors out of each term in

the sum, we can get the true p(XXX) by multiplying Total*[p(1match)]^2 =

0.001476728. Whew! That's more complicated than I thought it would be!

A few last notes... I was looking at chi-square theory, and my reference

says that if you want to use it, you have to break your patterns down into

mutually exclusive categories, Now the way you have it set up, you can do

a separate chi-square calculation for each pattern; for instance, you

could take the two cases (A) X1 = X2 or (B) X1 not= X2. They are mutually

exclusive, so you can do chi-square on them. But then you get several

separate chi-square calculations, one for each pattern. I think you would

get a stronger, more incisive statistical correlation if you could combine

all of your patterns into a single chi-square calculation.

To do this, you have to be very careful to define your patterns so that

they are mutually exclusive. Also, since patterns can overlap, you have

to be careful to count each pattern only once. If you want to go for this

method, I'll set it up. Most of the work for it is already done, since

it's only a modification of the calculations I've already done. Still, it

will take another couple of hours for me, and you'll have to re-count your

patterns according to certain exact standard methods; so how about if you

email me and tell me whether you want to go ahead? If so, I'll get to

work on it. If not, well, I think the numbers are pretty good as they

are, and I'd like to see a copy of your paper when it's done.

Take care,

Stuart

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

1/28/98

Hi, Tony.

I've computed the new expected values and standard deviations for XX+1 and

XX-1. Since I already had the spreadsheet for the sticks up and running,

I did both sticks and coins, just for comparison. Since your data are 90%

coins, of course, you'll only be interested in the coin numbers.

The revised computation is based on our phone conversation of Tuesday, in

which you clarified for me the way you counted the XX+1 and XX-1

occurrences. My understanding now is that you only counted times

when a single casting gave an oracle changing from X to X+1 or X-1. You

were NOT counting X showing up in one casting and X+1 or X-1 showing up in

the next day's casting. Do I have that all right? If so, then the

following numbers are correct:

method pattern probability expect std dev

Stick X-->X+1 0.00855 3.685 1.911

X-->X-1 0.01124 4.845 2.189

Coin X-->X+1 0.01006 4.336 2.072

X-->X-1 SAME SAME SAME

These expected and standard deviation values are all computed based on 431

oracles, i.e., if all the oracles were with yarrow sticks, you would

expect the X-->X+1 pattern about 3.685 times. Since so much of your data

is from the coin method, you should just use the coin numbers "as is." If

you wanted to be *really* picky, you could separate your data and compute

the expected number from each type, and then add them up -- but the

numbers are so close anyway, that it wouldn't change your answer.

(I just included the stick calculation to show you the interesting fact

that X-->X+1 happens less often than X-->X-1 using yarrow sticks. Some of

the numbers on my spreadsheet came out really wild: for example, oracle

#1 almost never changes to #2. It happens only 4 times in every million

castings of the oracle, whereas in the coin method it would happen

something like 250 times in every million castings. On the other hand,

oracle #22 likes to change to #23. That happens about 61000 times in

every million oracles, whereas in the coin method it happens about only

about 20000 times out of a million.)

Well, I think this is finally all the way you want it. Sorry about the

misunderstanding. Best of luck in finishing up your paper.

Stuart Anderson