Rare Event...The Full Moon Strikes Again!

[BobPark]

Tonight, in 27 boards, West held 3 Yarboroughs...2 with 12 cards below
a 9.

[John Crinnion]

On Feb 8, 3:10 am, BobPark <bpar...@comcast.net> wrote:
> Tonight, in 27 boards, West held 3 Yarboroughs...2 with 12 cards below
> a 9.

Sounds as if there were some new decks which were not properly
shuffled.

[Herb]

Or a biased auto-dealer.

[Fred.]

Sometimes the improbable happens without intervention,
but not often.

Someone once gave me a thought experiment. You write
a program to simulate random coin flips.

Case 1: You start it up and it goes heads the 1st 6 times.

Case 2: You start it up and it goes 1000 flips
without 6 six heads in a row.

Fred.

[Charles Brenner]

Tricky! I assume your point is that Case 2 is less likely. Indeed,
it's unbelievably less likely -- Case 1 is 1/64, Case 2 didn't happen
even once in 50000 trials (of 1000 flips each); in fact my empirical
chance of not having 7 heads in a row is under 1/10000.

Breakeven is with about 200 flips.

I don't see how to compute the probability.

Charles

[Travis Crump]

(63/64)^995 ~= 1 in 6,385,978? For 7 in a row: (127/128)^994 ~= 1 in
2,431. Breakeven[50%] is about 50 flips for 6 in a row, 95 flips for 7
in a row.

[HoneyMonster]

My first run of 50,000 trials of 1000 flips got hits (6 or more in a row)
49,990 times, and misses 10 (this is using the Mersenne twister).

Out of curiosity I'm going to try it a few more times.

[Charles Brenner]

On Feb 10, 12:25 pm, Travis Crump <pretz...@techhouse.org> wrote:
> On 02/10/2012 02:34 PM, Charles Brenner wrote:
>
>
>
>
>
>
>
>
>
> > On Feb 9, 6:17 pm, "Fred." <ghrno-goo...@yahoo.com> wrote:
> >> Sometimes the improbable happens without intervention,
> >> but not often.
>
> >> Someone once gave me a thought experiment.  You write
> >> a program to simulate random coin flips.
>
> >> Case 1:  You start it up and it goes heads the 1st 6 times.
>
> >> Case 2:  You start it up and it goes 1000 flips
> >>          without 6 six heads in a row.
>
> >> Fred.
>
> > Tricky! I assume your point is that Case 2 is less likely. Indeed,
> > it's unbelievably less likely -- Case 1 is 1/64, Case 2 didn't happen
> > even once in 50000 trials (of 1000 flips each); in fact my empirical
> > chance of not having 7 heads in a row is under 1/10000.
>
> > Breakeven is with about 200 flips.
>
> > I don't see how to compute the probability.
>
> > Charles
>
> (63/64)^995 ~= 1 in 6,385,978?

I dismissed that calculation because it assumes that the chance of 6
heads on flips 1-6 is independent of the chance of 6 heads in flips
2-7, which is not remotely true. The vast majority of the time that
1-6 are not all heads it's because there is a tail among flips 2-6, in
which case 6 heads in flips 2-7 is precluded.

That said, I think that in my previous message I must have
misinterpreted my table of results. Trying again and comparing with
your formula:

Let n=200 flips, checking for 6 heads in a row:
By your formula, approximate chance to not have a run of 6
heads=(63/64)*195=0.046.
By experiment, max run of heads < 6 occurred 20% (among 10000
sequences of n=200)
Formula 5x too low.

Let n=500 flips:
Your formula: 1/2400
Experiment: 1.5% (close to the chance of 6 conseq heads)
formula 37x too low

Let n=1000 flips.
Your formula=1/6 million
Experiment: 6/10000
formula 3800x too low.

As a sort of confirmation of my revised "experiment" figures, they are
psychologically consistent with Fred's trivia (whomever invented his
examples probably knew that the number 1000 couldn't have been
dramatically lowered).

Charles

[Charles Brenner]

Your result agrees with what I'm now claiming. I think my mistake
wasn't so subtle as an inferior random number generator; more like
being cross-eyed.

Charles

[Fred.]

The real point is that your conclusion from the first
event is that something is "fixed", i.e. your algorithm
for the random number generator has a problem. And, you
have a fairly high probability of being right.

However, your conclusion from the second event is the
same with much more likelihood.

When I get dealt a 0-loser hand, I look for the deck
stacker, and you will not convincing me that that
person doesn't exist, but there is some chance, however
small, that I am wrong, just as I could be wrong when
the starting 6 heads sends me looking for the error in
the geneator.

Fred.

[Thomas Dehn]

mmmh, I'll give it a try.

Chance of six heads in a row on the first six flips: 1/64.
I.e., chance of "surviving" the first six flips: 63/64,
where 32/64 have a tail on flip 6, and 31/64 a head.

On any of the flips from 7 to 1000:
Let p(n) be the probability that after n flips the condition
has not occurred. I.e., p(6)=63/64.
Let p_i(n) be the probability that after n flips the
condition has not occurred, and the exactly the previous
i flips were head.
I.e., p_0(6)=32/64, p_1(6)=16/64, p_2(6)=8/64, p_3(6)=4/64,
p_4(6)=2/64, and p_5(6)=1/64. And, for all n,
p(n)=p_0(n) + ... p_5(n).

Recursion rules:

p_0(n+1)=1/2*p(n)
p_1(n+1)=1/2*p_0(n)
p_2(n+1)=1/2*p_1(n)
p_3(n+1)=1/2*p_2(n)
p_4(n+1)=1/2*p_3(n)
p_5(n+1)=1/2*p_4(n)
p(n+1)=p(n)-1/2*p_5(n)

Or, getting rid of the helper functions
p(n+1)=p(n)-1/128*p(n-6).

p_0(7)=63/128
p_1(7)=32/128
p_2(7)=16/128
p_3(7)=8/128
p_4(7)=4/128
p_5(7)=2/128
p(7)=125/128

p_0(8)=125/256
p_1(8)=63/256
p_2(8)=32/256
p_3(8)=16/256
p_4(8)=8/256
p_5(8)=4/256
p(8)=248/256=124/128

...
p(9)=492/512=123/128
p(10)=976/1024=122/128
p(11)=1936/2048=121/128

Getting too late now for me to try to get
this into one concise formula for p(n).


Thomas

[HoneyMonster]

Results for the next few runs:

49983 17
49981 19
49989 11
49990 10

I think the moral of the story is this:

"One of these days in your travels, a guy is going to come up to you and
show you a nice brand-new deck of cards on which the seal is not yet
broken, and this guy is going to offer to bet you that he can make the
Jack of Spades jump out of the deck and squirt cider in your ear. But,
son, do not bet this man, for as sure as you are standing there, you are
going to end up with an earful of cider."

Damon Runyon

[Charles Brenner]

Nice -- that's how to do it. Assuming that
p(n+1)=p(n)-1/128*p(n-6)
is correct, there's a mechanistic way to write an equation for p(n)
from this. The process is tedious -- it requires writing down the
roots of the characteristic polynomial
x^7 - x^6 + 1/128, then p(n) is a linear combination of the n-th
powers of those roots (finding the coefficients more tedium)
notwithstanding that (I guess) six of the seven roots are complex.
Maybe Mathematica. Anyway my point is that conversely the formula that
this procedure produces, with all it's irrational complex numbers, is
as concise an answer as there is.

Charles

[Thomas Dehn]

I found a functional online polynomial root calculator here:
http://xrjunque.nom.es/precis/rootfinder.aspx

That gives:
x^7 -x^6 +(1/128) = 0 =>
=> x^7 -x^6 +0.0078125 = 0
=> (x +0.420154549170266)*(x -0.5)*(x -0.991791421712163)*(x +(
-0.195146016987811 -i*0.408930828152264))*(x +(0.23096445325876
-i*0.359572188979042))*(x +(0.23096445325876 +i*0.359572188979042))*(x
+( -0.195146016987811 +i*0.408930828152264)) = 0

Real solutions:
Root 1: -0.420154549170266
Root 2: 0.5
Root 3: 0.991791421712163
Complex roots:
Root 4: -0.23096445325876+0.359572188979042 * i
Root 5: -0.23096445325876-0.359572188979042 * i
Root 6: 0.195146016987811-0.408930828152264 * i
Root 7: 0.195146016987811+0.408930828152264 * i

Yes, 1/2 is one of the roots.

I confirmed that x=0.991791421712163 is a good approximation
of a root. As its absolute value is much larger than
for any of the other roots, for practical purposes
this is the speed of the decay (assuming I did not make
a mistake somewhere).

Lets see:
p(12)=120/128
p(13)=7617/8192

p(12)*x^988~0.000272442426
p(13)*x^987~0.000272443924

Thus, I'd expect that the probability that you
get 1,000 flips without six heads in a row is
approximately 0.000272443.

On those runs of 50,000 tests, that would
give an expected value of 13.62215 hits.



Thomas

[Charles Brenner]

On Feb 10, 9:24 pm, Thomas Dehn <thomas-use...@arcor.de> wrote:
> On 02/11/2012 02:41 AM, Charles Brenner wrote:

> > On Feb 10, 1:40 pm, Thomas Dehn<thomas-use...@arcor.de>  wrote:
> >> On 02/10/2012 08:34 PM, Charles Brenner wrote:
>
> >>> On Feb 9, 6:17 pm, "Fred."<ghrno-goo...@yahoo.com>    wrote:
> >>>> Sometimes the improbable happens without intervention,
> >>>> but not often.
>
> >>>> Someone once gave me a thought experiment.  You write
> >>>> a program to simulate random coin flips.
>
> >>>> Case 1:  You start it up and it goes heads the 1st 6 times.
>
> >>>> Case 2:  You start it up and it goes 1000 flips
> >>>>            without 6 six heads in a row.

> >> p(n+1)=p(n)-1/128*p(n-6).

> > Nice -- that's how to do it. Assuming that
> > p(n+1)=p(n)-1/128*p(n-6)
> > is correct, there's a mechanistic way to write an equation for p(n)
> > from this. The process is tedious -- it requires writing down the
> > roots of the characteristic polynomial
> > x^7 - x^6 + 1/128, then p(n) is a linear combination of the n-th
> > powers of those roots (finding the coefficients more tedium)
> > notwithstanding that (I guess) six of the seven roots are complex.
> > Maybe Mathematica. Anyway my point is that conversely the formula that
> > this procedure produces, with all it's irrational complex numbers, is
> > as concise an answer as there is.
>
> I found a functional online polynomial root calculator here:http://xrjunque.nom.es/precis/rootfinder.aspx

Wow. That is one cool web tool.

> That gives:
> x^7 -x^6 +(1/128) = 0 =>
> => x^7 -x^6 +0.0078125 = 0
> => (x +0.420154549170266)*(x -0.5)*(x -0.991791421712163)*(x +(
> -0.195146016987811 -i*0.408930828152264))*(x +(0.23096445325876
> -i*0.359572188979042))*(x +(0.23096445325876 +i*0.359572188979042))*(x
> +( -0.195146016987811 +i*0.408930828152264)) = 0
>
> Real solutions:
> Root 1: -0.420154549170266
> Root 2: 0.5
> Root 3: 0.991791421712163
> Complex roots:
> Root 4: -0.23096445325876+0.359572188979042 * i
> Root 5: -0.23096445325876-0.359572188979042 * i
> Root 6: 0.195146016987811-0.408930828152264 * i
> Root 7: 0.195146016987811+0.408930828152264 * i
>
> Yes, 1/2 is one of the roots.

Euler and Ramanujan would have noticed that. I didn't.

> I confirmed that x=0.991791421712163 is a good approximation
> of a root.

It's the one I found also.

> As its absolute value is much larger than
> for any of the other roots, for practical purposes
> this is the speed of the decay (assuming I did not make
> a mistake somewhere).
>
> Lets see:
> p(12)=120/128
> p(13)=7617/8192
>
> p(12)*x^988~0.000272442426
> p(13)*x^987~0.000272443924
>
> Thus, I'd expect that the probability that you
> get 1,000 flips without six heads in a row is
> approximately 0.000272443.
>
> On those runs of 50,000 tests, that would
> give an expected value of 13.62215 hits.

reasonably validating your calculations. Very good.

Charles

[Thomas Dehn]

Warning: off-topic mathematics below.
No bridge content in this posting.

It is pretty easy to find the 1/2 root
because of the simple structure
of the characteristic polynomial.

I'll transform it a bit to make it more obvious:

Let y=1/x:

y^(-7) - y^(-6) + (1/128) = 0 | multiply by 128*y^7

128 - 128y + y^7 = 0.

This is a polynomial where all coefficients are integer,
and furthermore the coefficient at the highest power of
y is 1 (or -1).
It is pretty easy to see that any rational solution is
integer (*), and must furthermore be a divisor of 128.

So all you have to do is try all divisors of 128:
1, -1, 2, -2, 4, -4, 8, -8, 16, -16, ..., 128, -128.


(*) To see that any rational solution is integer, consider
y^n + a_(n-1)*y^(n-1) + ... + a_0 = 0,
where all a_i are integer.

Let y=p/q be any non-integer rational solution, where p and
q are integers, have no common divisors, and q>1.
Insert y=y/q, multiply the equation by q^n:

p^n + a_(n-1)*p^(n-1)*q + ... + a_0*q^n = 0.

If you look at this modulo q, p^n mod q is not 0, as
p and q have no common divisors, and all other parts
are zero modulo q. This is a contradiction, and thus
such a non-integer rational solution y=p/q cannot exist.


Thomas

[HoneyMonster]

On Sat, 11 Feb 2012 06:24:37 +0100, Thomas Dehn wrote:

<snip>

> On those runs of 50,000 tests, that would give an expected value of
> 13.62215 hits.

And my 5 simulations gave results of 10, 17, 19, 11 and 10, of which the
mean is 13.4, providing further validation of your calculations.

[Charles Brenner]

I had in mind the famous conversation between Ramanujan and Hardy, in
which Hardy happened to mention the number 1729 and Ramanujan
instantly noted that it was the sum of cubes in two different ways.
That fact was obvious to Hardy as well, once alerted to it, for when
Hardy ("naturally") asked for a corresponding number for 4th powers
Ramanujan, knowing his friend, replied that there was no similarly
*obvious* answer. (Euler also explored the question.)

With this polynomial, maybe no manipulation is necessary to guess 1/2
as a root once you think to look. I was just admitting that I didn't
look. I only blindly attacked the polynomial with numeric tools.

Charles

[BobPark]

In this club, we are lucky if we have new decks once a year. This was
not the night.
--bp

[Gerben Dirksen]

> I had in mind the famous conversation between Ramanujan and Hardy, in
> which Hardy happened to mention the number 1729 and Ramanujan
> instantly noted that it was the sum of cubes in two different ways.
> That fact was obvious to Hardy as well, once alerted to it, for when
> Hardy ("naturally") asked for a corresponding number for 4th powers
> Ramanujan, knowing his friend, replied that there was no similarly
> *obvious* answer. (Euler also explored the question.)
>
> With this polynomial, maybe no manipulation is necessary to guess 1/2
> as a root once you think to look. I was just admitting that I didn't
> look. I only blindly attacked the polynomial with numeric tools.
>
> Charles

Although correct, apparently Euler discovered that:

158^4 + 59^4 = 134^4 + 133^4 = 635,318,657

Gerben

[Charles Brenner]

Yes, and needless to say he discovered it by brainpower and not by
sheer calculating. In fact he may (my memory is vague) have had an
algebraic identity of the form, hence an infinite family of solutions.
He also (of course) explored the corresponding question for fifth
powers as did I with a 1960's computer (the 7090, "-ty" standing for
Transistorized), and as have others with much more powerful computers
and more ingenious programs. Discuss: Which is the stronger evidence
that there is no solution for fifth powers, that computers haven't
found one, or that Euler didn't?

Charles

[Michael Stemper]

In article <804945be-ec83-47a0...@l14g2000vbe.googlegroups.com>, Gerben Dirksen <gerb...@hotmail.com> writes:

>> With this polynomial, maybe no manipulation is necessary to guess 1/2
>> as a root once you think to look. I was just admitting that I didn't
>> look. I only blindly attacked the polynomial with numeric tools.
>

>Although correct, apparently Euler discovered that:
>
>158^4 + 59^4 = 134^4 + 133^4 = 635,318,657

Presumably, he used this to factor 635,318,657.

When I learned of his method to factor numbers that can be expressed as
the sum of two positive squares in two ways, I coded it up. Unfortunately,
the only way that I knew to find decompositions into the sum of two squares
was brute force, so the program was painfully slow.

Are there any good ways to perform this decomposition? (I wouldn't
consider "factor it and reverse Euler's method" to be very good.)

--
Michael F. Stemper
#include <Standard_Disclaimer>
This message contains at least 95% recycled bytes.

[Thomas Dehn]

On 02/15/2012 02:46 PM, Michael Stemper wrote:
> In article<804945be-ec83-47a0...@l14g2000vbe.googlegroups.com>, Gerben Dirksen<gerb...@hotmail.com> writes:
>
>>> With this polynomial, maybe no manipulation is necessary to guess 1/2
>>> as a root once you think to look. I was just admitting that I didn't
>>> look. I only blindly attacked the polynomial with numeric tools.
>>
>> Although correct, apparently Euler discovered that:
>>
>> 158^4 + 59^4 = 134^4 + 133^4 = 635,318,657
>
> Presumably, he used this to factor 635,318,657.
>
> When I learned of his method to factor numbers that can be expressed as
> the sum of two positive squares in two ways, I coded it up. Unfortunately,
> the only way that I knew to find decompositions into the sum of two squares
> was brute force, so the program was painfully slow.
>
> Are there any good ways to perform this decomposition? (I wouldn't
> consider "factor it and reverse Euler's method" to be very good.)

Depends on the size of numbers you are thinking about.
I'd guess that computing a rainbow table once isn't
that expensive for, say, all numbers up to 10^12.


Thomas

[micro...@hotmail.com]

Is the Moon Mooning you?