posted February 05, 2005 02:40 PM            

I'm enjoying reading your posts, catching just a glint of your
mind at work as it darts about. Some of your comments made me
decide to reiterate some of the things discussed thus far.

First, there is reason to believe that many onsite games of
chance may NOT be using anything other than the built-in PRNG
process.

Second, one game I frequented for awhile seemed to be showing
strong evidence of either bias or tampering, because certain
hands or pairings of cards were dealt far more often than seemed
probable.

Third, there was more discussion as to the nature of random
number generators and alternate methods for generating random
sequences.

And fourth, I questioned whether an observer could really detect
the sequence being followed for PRNG-guided play if you could
only see a few consecutive cards, because the cards are only
partially representive of the random numbers that generated them.
After all, it is very easy to break a sequence of RND numbers if
you use RANDOMIZE again or elect to use the results of RND in
unexpected ways.

One of the most common unexpected ways would be to reshuffle the
same cards again between hands without first restoring the deck
to its original state - just one shuffle on top of another.
Another way would be to bury the top card before the flop, river,
and turn cards, just as they do in real Texas Hold'em tournament
play. Yet another way is to take cards from the bottom instead
of the top of the deck, which changes the order in which they are
dealt. Another way would be if you adopted a unique shuffling
method that was substantially different from what others might
expect to be employed.

Here's a unique idea for an shuffling method:

DIM a AS INTEGER, Deck AS STRING
DO WHILE LEN(Deck)<52
  a=RND(0,51)
  IF INSTR(DEck,CHR$(a))=0 THEN Deck=Deck+CHR$(a)
LOOP

DIM a AS INTEGER, Deck AS STRING
DO WHILE LEN(Deck)<52
  a=RND(0,51)
  IF INSTR(DEck,CHR$(a))=0 THEN Deck=STRREVERSE$(Deck)+CHR$(a)
LOOP

One writer made some comment that five dealt cards represented
52*51*50*49*48 possible combinations, or 311,875,200 possible
hands involving 5 cards. To know the outcome of the entire deck,
you would have to carry out that process to the last card, which
creates 52!, a really large number. His argument was that 2^32
possible RND choices could in no way approach that number, and
that you were doomed to only be able to represent a small
handful of the possible outcomes of a game of chance using an
PRNG process. According to his way of reasoning, only certain
hands COULD come up in a computer-dealt game. I beg to differ,
but I will leave it to others to explain the error in his thinking.

posted February 05, 2005 11:14 PM            

This morning I ran across a quote that you might like, in an
old book on the history of math:

"Bernoulli took it as commonly known that uncertainty decreased
as the number of observations increased: 'For even the most
stupid of men, by some instinct of nature, by himself and
without instruction (which is a remarkable thing) is convinced
that the more observations have been made, the less danger there
is in wandering from one's goal" (1713). Bernoulli sought both to
provide a proof of this principle and to show that there was no
natural bound to the residual uncertainty. By multiplying the
observations, 'moral uncertainty' about the unknown proportion
could be approached arbitrarily closely."

He is usually credited with having founded "probability" as a
science. I think that he was right on the "instinct of nature",
especially since many nonhumans seem to be very sensitive too
to probabilities and time schedules. One relatively easy
demonstration would be to have 2 people tossing out handfuls of
bread periodically, in a good seagull haunt -- on a rigged
schedule. Who will attract the biggest number of gulls, and how
long does it take the birdies to sense a change in payoff
schedules? They seem as sharp and as quick to spot "jackpots"
as people in a slot machine parlor. The more gulls squawking
collectively, the more the available goodies, I'd predict.

There have been loads of studies on various animals (as well
as people of course) as "intuitive statisticians" and, generally
speaking, some investigators are highly impressed at how sharp
we (people & animals) are, while others say that we are over-
rated and easily led into what amounts to superstitious
behavior. Certainly training helps, & memory. Anyone can greatly
improve their ability to memorize cards, number sequences, etc.

But this is only "pop psychology"; Bernoulli's big contribution
was his formalization... I did have more to say but my wild life
has caught up with me and I'd better get some sleep now.
I'll get back to this tomorrow. Thanks for the review.

posted February 06, 2005 09:50 AM            

Actually the ancients did have some very interesting ideas about
almost everything on which they left records that we can decipher.
Some believed that literally everything was determined, but that
the goddess of Chance was given the last word (e.g., in the last
fraction of a second as the ball is about to be dropped into a
slot of the roulette wheel). You prayed to her for obvious reasons:
"Call it for me, Lady Luck, and I'll say 10 Hail Marys!" or
whatever. I'm a Presbyterian myself, or one of the "frozen
chosen" as we sometimes call ourselves, so I don't use that
language. Nor do I know to the ten-billionth decimal point where
my ball is going to go after I pass my last instant. Let's just
say I have got what I'd call a very good hunch, and it is not
based on anything I did or promised to do. Amazing grace...

My academic specialty used to be animal behavior, and the
majority of my peers were skeptics on just about anything,
including in some cases whether or not a chimpanzee was any
smarter than a door knob, whether any Real Scientist should
ever trust any hunch, etc. I think that funny rather than
sinful, but anyway, by the time I passed adolescence myself
(at about 40, mebbe) I was far more inclined to play my hunches
or rather test them, ideally experimentally and statistically.
I.e., it is not where your ideas or hunches come from, but
where you go from there. Check out Frans de Waal's web site
at Emory University. He's a young (by my standards) primate
ethologist who will tell you the same thing, and back it up
with some amazing evidence.

What I would add to your review is this: Chad was right and
Bernoulli was right: With more and more data you can get
closer & closer to apparent zero error in your estimate of
Pi or probability -- but dead-zero certainty is not possible.
Get as good an estimate as you really need, and in accordance
with how much it is going to cost you if you lose, and reckon
that not just in dollars or rupees either.

Issues to think about in designing your own random number,
stated mostly in the words of Steve Skiena:

*Should my program use the same "random" numbers each time it
runs?
*How good is my computer's random number generator?
*What if I have to implement my own generator?
*What if I don't want large, uniformly distributed random
integers? (tip: be cautious in inventing your own techniques,
and by all means test their output too.)
*How long should I run my Monte Carlo simulation to get the
best results? (tip: it is a good first guess that the longer
you let it run, the better. But watch out on that. Your
program's length of cycle gives what philosophers might
call "eternal recurrence", and that's the end of Lady Luck,
if someone else can detect the pattern.)

Sayonara.

posted February 07, 2005 09:54 PM            

So did Plato anticipate some of the main problems we have been
talking about here? Maybe so, I suppose.

Anyway, I had better close with a small confession, lest someone
think that I think that the programs above somehow disprove
natural selection. They do not. They do, admittedly, make me
far more skeptical than I used to be about the claims of many
proponents of natural selection, especially insofar as these
claims imply that there is literally no limit to how far science can
go in explaining anything that any rational being might care to
know. But I have up to now deliberately omitted any mention of
what Dawkins calls two-step or Darwinian selection as opposed
to one-step selection ala Pythagoras and Plato. In brief, I have
not said a word about DNA or genetic relationships between
individuals. There are good seeds and bad seeds, Adams and Eves,
if you wish, but that is poetry, not biology.

Isn't that cheating? It would be if we were all talking
biology. I was not, except very casually. My immediate concern
was whether there might be bugs in my program. It will be
interesting to add some analogs to genetic relationsips into
the game, and see how much closer we can get to Pi, and zero
error. Place your bets, ladies and gentlemen.

posted February 15, 2005 01:35 PM            

Since my first post on this topic I have also make more posts
on other threads than I would care to count (or than anyone
else would care to read, no doubt). One of my last ones is on
Erik's Christensen's thread on Fundamentalism: http://www.powerbasic.com/support/forums/Forum12/HTML/001544-6.html

Now I've gotta lay off of PB forums for a while. Should anyone
care to rouse me from my dogmatic slumbers, drop me an
email: emenzel491@aol.com. I have another "new, improved"
program on hand by now.

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

posted February 15, 2006 02:07 PM            

'Pi-Ala.BAS (where "Ala" is either ala mode or Alabama, according to your preference)
'FREEWARE
'by E.W. Menzel, Jr
'Feb 2006
'This demo is in honor of Chad D. Wood.
'He was one of the first to comment on the original post,
'& he hit the biggest single nail squarely on its head.

'Language: PBCC but easily convertible to PBDOS
'Reference: Google the term "Pi Monte Carlo" and you should be able to find dozens
'of relevant web sites. A very good one is:
' http://math.fullerton.edu/mathews/n2003/MonteCarloPiMod.html
'(Few if any of them will, however, tell you why Monte Carlo
'estimates are no better than they are. On that, discussions of the Central Limit Theorem
'and the Law of Large Numbers might be more helpful.)

'note 1: this demo does not use any Monte Carlo procedures (or random numbers).
'But it does show why the accuracy of Monte Carlo estimates of Pi is doomed
'to be very poor by "pure math" standards. Briefly: Both on the X axis & on Y,
'random numbers (e.g., PB's RND) range from zero up to, but not including, 1.000...
'The demo program divides that range up into progressively finer fractions, and
'at each step it computes all possible values that X or Y could have, and
'the proportion of these values that would lead to a D^2 >= 1 (where D^2 is X^2+Y^2
'or Pythagorean distance, squared). The theoretical "expected" proportion is
'exactly Pi/4. As you will see, the finer you chop the range, the closer the
'estimate of Pi or Pi/4 will come to meeting expectations. But the question is,
'what would it take to get an estimate that is accurate to N decimal places?

'The bottom line is that for N=infinity you would need infinitely accurate X,Y
'values. Moreover, no Monte Carlo application is going to do any better than the
'present program (at any given level of precision); to do even as well it would
'have to draw precisely representative samples from any given set of all possible
'X,Y values.

'note 2: this demo's "for/next loop method" of generating the X's & Y's
'guarantees that the mean of all X's & all Y's will be exactly .5.
'If that is not the case, Pi est. will be even more inaccurate than it is here.

'I discovered this by examining data from Monte Carlo simulations. There, the
'error in estimates of Pi correlate about .50 with mean X & mean Y -- or using both
'mean X & mean Y as predictors, the multiple correlation cefficient is about .70.
'There should be a straightforward statistical explanation for these correlations,
'but I do not know, offhand, what it is.

'At some point I wondered whether Monte Carlo estimates of Pi would be improved if one
'abandoned the use of pseudo-random numbers and switched to the random numbers obtained
'from (e.g.) www.random.org , which are supposedly "pure" random numbers. The short answer
'is, No. The same correlation between Pi est. and mean X & Y occurs, and (much more important)
'the same correlation between the precision of one's X & Y and the precision of Pi.

FUNCTION PBMAIN
    DIM A AS STRING*15, B AS STRING*15, C AS STRING*15, D AS STRING*15, E AS STRING*15
    DIM m AS STRING, m2 AS STRING
    DIM num AS EXT, fr AS EXT, pi4 AS EXT, start AS EXT, finish AS EXT
    DIM N AS EXT, i AS EXT, j AS EXT, x AS EXT, x2 AS EXT, y AS EXT, piErr AS EXT
    CLS
    OPEN "PI-ALA.2" FOR OUTPUT AS # 1
    PRINT "press Ctrl+Break to quit"
    PRINT "Note that doubling 'num' reduces 'error' by about one-half"
    m$="' Pi ="+STR$(ATN(1)*4)+"  according to PB function ATN(1)*4"
    PRINT m$
    PRINT #1, m$
    m$="' num          (num-1)^2     Pi-estimate          error        sec. comp time"
    PRINT m$
    PRINT #1, m$
    m$="  #.##########  "
    m2$="   ######.##"
    num=2
    DO
        num=num*2
        fr=1##/num
        pi4=0
        N=0
        Start=TIMER
        FOR i=1 TO num-1
            x2=(i*fr)^2
            y=0
            FOR j=1 TO num-1
                y=y+fr
                IF x2+y^2 <= 1 THEN pi4=pi4+1
            NEXT
        NEXT
        Finish=TIMER-Start
        N=(num-1)^2
        PiErr=ABS((ATN(1)*4##) -(pi4/N) * 4##)
        A$= STR$(num)
        B$= STR$(N)
        C$= USING$(m$,(pi4/N) * 4##)
        D$= USING$(m$,PiErr)
        E$= USING$(m2$,Finish)
        PRINT A$;B$;C$;D$;E$
        PRINT #1, A$;B$;C$;D$;E$
    LOOP UNTIL INSTAT
    CLOSE
END FUNCTION
'====== PROGRAM #2  =============================================
'Pi_in_yer_face.BAS
'Language: PBDOS or PBCC
'BUT NOTE: PBCC's answers for McLaurin go haywire after
'about 67,000 iiterations. If you know why, please post a fix.
'     " Purpose: compare Monte Carlo estimates of Atn(1) i.e., Pi /4"
'     " with the 'pure math' iterative Maclaurin series computation"
'
'     " NOTES:"
'     " 1. The Maclaurin series will always give the same answer(s)"
'     "    Its accuracy will vary with the no. of iterations (k) & the precision of your numbers"
'     "    It converges on ATN(1) -- being alternately a bit high & a bit low, on odd vs even iterations"
'     "    (But see the above NOTE re PBCC)
'     " 2. For numerous accounts of estimating Pi from random numbers,"
'     "    Search Google using the term 'Pi Monte Carlo' "
'     " 3. The Monte Carlo estimate will probably never give the same answer"
'     "    unless you use the same seed no. in the pseudo-random number generator"
'     "    Its accuracy will improve with no. of iterations & with precision of your numbers"
'     "    (theoretically speaking, the statistical confidence interval varies inversely with the square root of k;"
'     "    hence to increase accuracy by a factor of 10 -- 1 decimal place -- k must be increased by a factor of 100)"
'     "    BUT it is unlikely that accuracy will ever meet this theoretical expectation"
'     "    on a given computer, or match the accuracy of the Maclaurin formula on that computer --"
'     "    except, of course, possibly, by a very rare fluke."
'     " 4. There is no point in running the program indefinitely unless you"
'     "    use a different random number generator

'''#DIM ALL               'unREM for PBCC
dim x as long: x=pbmain   'REM-out for PBCC
FUNCTION PBMAIN
   DIM atn1 AS EXT,  sum AS EXT, sum2 AS EXT, x AS EXT, y AS EXT
   DIM precision AS EXT,  maxK AS EXT, i AS EXT, k AS EXT
   DIM a AS STRING
   precision = 9      'desired precision of Maclaurin series (1-17)
   maxK = 10^precision
   RANDOMIZE TIMER
   CLS
   LOCATE 10,1
   PRINT"    Comparing Monte Carlo estimates of Atn(1) i.e., Pi /4"
   PRINT"    with the 'pure math' iterative Maclaurin series computation"
   PRINT""
   PRINT"    press Esc to quit, any other key to continue"
   LOCATE 23,20
   atn1=ATN(1)
   PRINT  atn1;"  atn(1) PB built-in function"
   atn1=ATN(1)
   FOR i = 1 TO maxK                          'iteration number
      k=i
      x=((-1)^(k-1)) / (2*k -1)
      sum= sum + x      'Maclaurin series for atn(1)
      x=RND
      y=RND
      IF x^2+y^2 <= 1 THEN INCR sum2  'Monte carlo method
      IF k MOD 100 = 0 THEN
         x=ABS(sum-atn1)
         a$= USING$ ("N ########### ", k)_
            + USING$ ("atn ##.############# ",sum)_
            + USING$ ("err ##.#############    Maclaurin  series ",x )
          LOCATE 24,1: PRINT a$;
          x=sum2/k
          y=ABS((sum2/k)-atn1)
          a$= USING$ ("N ########### ", k)_
             + USING$("atn ##.############# ",x)_
             + USING$("err ##.#############    Monte Carlo ",y )
          LOCATE 25,1: PRINT a$;
          '''WAITSTAT: a$=INKEY$   'unREM for PBCC
          A$=input$(1)             'REM-out for PBCC
          IF a$=CHR$(27) THEN EXIT FOR
       END IF
   NEXT
END FUNCTION

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

posted February 16, 2006 01:56 AM            

Your approach, of finding that certain outcomes of mathematical
process will approximate PI if carried on long enough and based on
random elements, is interesting. It has also been found in nature
that certain relationships can be found based on natural e. I'm
not sure how many "natural" determinants exist, based on different
observations.

Glad you are happy with your findings and desire to share. Now
here is a question: If you wanted to create a purely random
process for use within a program, it is a given that you cannot
accomplish this using any software generator. You can only
approximate the apparent randomness by carefully seeding a
pseudo-random generator. So that leads to the need for finding
a random element that can be injected from a physical source.

Now the problem is, the source would have to not only be random
in nature, but would have to vary over a sufficient range and
rapidly enough to meet interplay requirements for a computer
game, as one example. In other words, though the outcome of the
random element would have to be unpredictable, the outcome can
not remain unchanged from the state it held when previously
sampled.

Take the wind, for instance: There are at least four uncertain
elements related to wind: When a gust starts, the direction it
comes from, the speed of the gust, and its duration. But between
gusts, the wind gauge may have nothing to measure. So during
non-gust intervals, you would get a constant reading. That would
not be good, because repeated samples during this period would
consistently be the same.

You've heard radiation meter clatter, right? Certainly random,
but the randomness of the clicks only become evident over time.
It's sort of a sequential randomness, not an instantaneous and
simultaneous determination, at least not to our ears.

The nearest example I can come up with is some sort of white
noise generator. You measure the current level (volume) of
noise very precisely and quickly in taking your sample. The
same idea could be applied to an instrument that detects back
ground radiation and gives a way to measure it.

But I wonder what other methods might be possiblem or if anyone
has experience in incorporating true randomness into their own
PCs and programming efforts. Having a true random number source
could validate or challenge mathematical theory, or it could be
used to power projects, such as simulations and games, that would
benefit from this.

One question is whether a true random source can be extended by
using it to seed a pseudo-random number generator. Informal
tests have shown that frequent reseeding of a PRNG sppears to
lessen its apparant random output markedly, even though you may
attempt to find some random element that can be reintroduced
with different expected values. For instance, trying to measure
keystroke duration, time between keystrokes, mouse coordinates,
mouse down duration, and take this as sufficiently random to
generate a suitable seed. Sound in theory, but it seems to be
less than satisfactory in practice. Continuing this process
and reseeding at intervals, even random ones, gives disappointing
results. Is this approach fundamentally flawed, or do we need
a pure random element to make it effective?

posted February 16, 2006 09:46 AM            

quote:

---

Sort of wasteful, since it throws away a lot of RND returns due to prior matches..

---

 FOR Z = 1 TO 52
    Key (z) = RND
 NEXT
 ARRAY SORT KEY(1), TAGARRAY Deck()

posted February 16, 2006 10:15 AM            

sorry I haven't the time to read all of this topic - I'm taking a little pause to relax between a long-long work day. If I understood your question is: what precision can I expect from the algorythm?

The program you first posted works as if you had a square and a circular arc that centers on a vertex of the square and has a radius the same length of the side of the square. With random numbers you get coulpes of X and Y coordinates, and see if the resulting point fails above or below the arc.

The precision you can expect depends on the precision of the random numbers you use. Admit you can have only 100 values for both X and Y: the square is divided only in 10000 boxes: 7854 of them are below the arc, the others are above. With this situation, you can do how many tries you want but you will never get more than 3 exact decimal digits.

With extended precision numbers, after you calculated the sum of the two squares, you will get a result that has no more than 18 decimal digits. And this is the max precision you can expect. If you want more precision, you must write algorythms that rely on strings. Starting from X and Y with 18 digits, you can get strings with 36 exact digits - the result will have more exact digits. If you want an even better precision, you must convert also the random number generator.

Aldo

[added later]

By the way, I see (in the first post) you check the square root of the sum of the squares of X and Y against 1: you can completely avoid the square root!

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

posted February 16, 2006 01:25 PM            

Re "pure random numbers", a preferred way to get them might be from
some process of interest to quantum mechanics -- e.g., radioactive
decay. These two sites provide such numbers free, & explain the logic
of using them rather than pseudo-random numbers. http://www.random.org http://www.fourmilab.ch/hotbits/

A die-hard determinist might argue that nothing is purely random;
using hotbits numbers rather than RND simply boils down to taking
someone else's word that it would a waste of time looking for the
"hidden pattern" or "seed number". But still, random.org does provide
extensive tests on their real-time data, updated every 10 minutes (!).
Very interesting -- at least for nerds like me.

Aldo:
You got the main point of the first program; basically it is comparing
the area of a circle to the area of an enclosing square -- from which
comparison the concept of "Pi" emerged in the first place, almost 2500
years ago. No random numbers are used.

If you want 18 decimal places of Pi from the program you
would need a "num" of 1E18 in the program and you can estimate the
amount of computational time that that would require on your
computer. My 2-yr-old Dell would take more than a quarter-million years,
by my reckoning.

Worse yet, as the second program demonstrates, the precision of
additional exact iterative algorithms for computing Pi (e.g., the
McLaurin series) will also be exactly as expected, unless one
exceeds the numerical capacities of one's machine -- but Monte
Carlo estimates poop out long before this. I am still not certain
why this is so. But trying out different random number generators
(cf. my "Swiss Army Random Number Generator" program, which is posted
elsewhere in PB's forums)did not improve performance for me. And of
course there is no need for using very-high precision numbers
unless some totally different Monte Carlo algorithm is used, and the
18-digit threshold is approached. I have yet to see a Pi Monte Carlo
estimate that is accurate, on average, to any more than 4 decimal
places. Of course, it is entirely possible to find particular
seed numbers for the RANDOMIZE statement that will yield considerably
more accurate etimates of Pi (at least in the short run), just as one
can hit a jackpot on a slot machine.

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

posted February 16, 2006 03:03 PM            

FOR card& = 52 TO 2 STEP -1
   SWAP Deck(card&), Deck(RND(1, card& - 1))
NEXT card&