Saturday, July 23, 2016

Random Numbers in Scratch

   Every programming language has a method for generating random numbers and Scratch is no exception. 
   Load Scratch, look in the green Operators menu, and you will find a pick random block. Drag a (pick random) block into the scripting section. 

   Continually click on the block and it will report a string of numbers, 1 though 10. 
   Change the 10 to 6, click on the block several times and note that the numerical results are similar to what you would obtain by rolling a single die. 
   The pick random block actually generates pseudo-random numbers. Since every operation in every programming language has to be based on algorithms, Scratch, like every other language, must contain an algorithm (the antithesis of a random process) that generates numbers that 'look like' random numbers. Hence, the term pseudo-random numbers. A popular class of algorithms that generate pseudo-random numbers are called linear congruential generators and constitute a major topic in contemporary mathematics.
   If you are interested, request the Linear Congruential Generator.pdf, a four-page document that works through the mathematics and provides a Scratch script that implements the Park-Miller parameter set. 
   Psuedo-random numbers, hereafter called random numbers, are fun to play with and Scratch (or any other programming or scripting language) provide students the opportunity to develop dynamic solutions to many types of mathematical problems. Here's a problem in geometrical probability.
   Consider a square is divided into four smaller, congruent squares. The square in the upper right has been shaded.
  The following Scratch block, used in a Repeat block, can be used to generate 100 random points in the above square.
    How many of the 100 points would you expect to fall in the shaded square?
One could argue that since the four smaller squares are congruent, the area of the shaded square is one-fourth the area of the large square. Since the probability of picking any point is equal to the probability of picking any other point, the expectation is that 25 of the100 points, or one-fourth, would fall in the shaded area.
  As you readily see in the graphic shown below, this problem is easily modeled in Scratch. The red circular sprite, sprite 1, is used to plot each random (x, y) point.
  A yellow sprite, sprite 2, is a square with one-quarter the area of the large square (see left screenshot below). Since the yellow square is a sprite, you can click on it and move the yellow square around (see screenshot on right) within (or even outside of) the larger square. This makes the problem dynamic, as compared to the static example given at the beginning of this lecture.  
    When the program is executed (click on the green flag) 100 trials of 100 random points are computed and averaged. As you can see in the left screenshot, the average for the 100 trials is 25.27. The average for the screenshot on the right is 24.62. Both averages are close to the theoretical value of 25.
   This project can be viewed and downloaded by clicking on this link:

Sunday, July 10, 2016

Where Do Random Numbers Come From?


   The random numbers generated in a computer or calculator are not truly random. They are not produced by sampling a physical process that contains a random process, such as flipping a coin or monitoring radioactive decay.

   Computer and calculator-generated random numbers are produced by computing an algorithm. An algorithm, by its very nature, contains no random processes. Still, these computer-generated random numbers pass most statistical tests and are, for most (but not all) practical purposes, random. Random numbers produced by an algorithm are more accurately called pseudo-random numbers.           

   The most commonly used algorithm for generating psuedo-random numbers is the linear congruential generator (LCG). The defining equation for a LCG is

xn+1 = (axn + c )mod m

where xn is called the seed, a is an integer constant called the multiplier, c (also an integer constant) is called the increment, and m is the modulus.
   The project can be viewed and downloaded by clicking on this link:
    A four-page pdf document takes you through a paper and pencil exercise that explains the mathematics of a linear congruential generator and is available, free, on request. Send a request to grandadscience@gmail.com.

Wednesday, July 6, 2016

Ask Fibonacci


  During the Fall of 1998 I was researching the algorithms computer scientists use to generate random numbers (called pseudorandom numbers). One of the references I came across was this brief statement in Ivars Peterson's book, The Jungles of Randomness: A Mathematical Safari.

“At the heart of the Marsaglia-Zaman method of generating random numbers is the so-called Fibonacci sequence…"


   While waiting to see my bone doctor one morning, I remembered this statement and began to explore the patterns exhibited by the one's digit of the Fibonacci sequence. The question in my mind was, What is there about the one’s digit of the Fibonacci sequence that would interest two research mathematicians?


   Using only pencil and paper I soon made two startling discoveries (known to others but unknown to me, and probably you) about the 1's digit of any Fibonacci number. My first discovery made it possible for me to write an algorithm that computes the 1’s digit of the nth Fibonacci number.
   The project can be viewed and downloaded by clicking on this link:


Tuesday, July 5, 2016

What is iteration?


   Many of my Scratch projects are about fractals and mathematical chaos. Examples are given below. 
   Both topics are products of the computer age and are powered by a mathematical method known as iteration. Iteration is sometimes confused with looping but it is a much deeper and more mathematically powerful tool than looping.
   I have written a document that carefully, step-by-step, compares the process of graphing y = f(x) with the iteration of y = f(x). This information is basic for developing an understanding of the mathematics that underlie fractals and chaos.
   In the graphic shown below, the image on the left is the graph of the function given in the center of the graphic with the parameter c varying from 0 to 8 in increments of one.


      The image to the right is the iteration of the same function with c starting at -0.5 and varying to -2.0 in 0.005 increments

   For your free copy of this document send an email to www.grandadscience@gmail.com.

A Sample of My Fractal and Chaos Projects

Langton's Ant – Random Squares Experiment 

Koch Snowflake

x^2+ c Plots

Chaos Game - Midpoint Formula

Mandelbrot Set [Featured Project – 4656 views]





Wednesday, May 18, 2016

More About Random Walks

   I've written two additional random walk projects. The first of the two is essentially a Monte Carlo experiment that shows that the average square displacement of a random walker from zero, its starting point on the integer number line, is n, the number of steps in the walk. In equation form, let D equal the average square displacement. Then D^2 = n (or D = √(n)). 
   The Nobel physicist Richard Feynman provides a simple algebraic proof that D^2 = n.
   A copy of Feynman's proof is available upon request. Email grandadscience@gmail.com.
   This Scratch project can be viewed by clicking on the following link.
Average Square Displacement

   The second project is another Monte Carlo simulation.
   Consider a random walker starting at position 100 on a number line that has no barriers. Instead of flipping a coin to randomize left or right movement the walker has a pack of ten playing cards, 5 black and 5 red. 
 

The cards are shuffled and held face down in the walker’s hand. The walker selects, without peeking, the top card from the pack. The walker then looks at the card. If red, the walker moves to the right half the distance the walker is from 0. If black, the walker moves to the left half the distance the walker is from 0. The card is then discarded.

   The walker continues selecting a card and moving to the left or to the right as determined by the color of the card and the distance-halving rule until the tenth card has been looked at and the walker’s position changed according to the color of the last card. 

   You can explore the problem with paper/pencil or a calculator but a simple Scratch program is the easiest way to reach a surprising conjecture about the problem. The problem originated with Enn Norak, a Canadian mathematician and appeared in May 1969 issue of Scientific American magazine.
   This Scratch project can be viewed by clicking on the following link.
A Random Walk Paradox

Monday, April 11, 2016

The Galton Board (Quincunx)

   The Galton Board (quincunx) was invented by Sir Francis Galton (1822–1911) as a mechanical device to demonstrate the 'normal distribution' in statistics.
   "He had noticed that a normal curve is reproduced by lead shot falling vertically through a harrow of pins…" For more information visit the following link.
   The Galton Board is nothing more than a gravity-powered random walk on the integer number line where the walker, starting at zero, flips a coin to move one unit to the right if a head or one unit to the left if a tail. The probability of flipping a head is 1/2 and the probability of flipping a tail is also 1/2 
   In a Galton Board, the coin flipping is replaced with a marble striking a peg and then going left or right with equal probabilities.
   There is a neat programming shortcut used to determine the bin number (1 – 10) that each ball falls into  after striking the ninth peg. One just has to count the total number of 'lefts' (or 'rights') at the end of the ninth bounce. The order of lefts or (rights) is not important. At the bottom of each numbered bin. Click on 'Show List' to view the totals for each bin.
                                     Bin Number
                1     2     3     4     5     6     7     8     9     10
                Random Walker Position on Number Line
               -9   -7    -5     -3  -1   +1   +3   +5   +7   +9

                Theoretical Values for Each Bin (9 flips)
                                       Bin Number
               1      2      3      4      5      6      7      8      9     10
               1      9     36   84   126  126    84    36     9      1

                 One Run of the Project set to 512 Marbles 
                                        Bin Number
               1     2      3     4     5       6      7     8     9     10
                0    4    34    97  127   129   73    35    9      4

      This project can be viewed and downloaded at this link:
    This project complements my other Random Walk projects:
   The Huckster's Game
   Feynman’s Random Walk
   Random Walk with Barriers
   Jean Perrin's Random Walk Experiment
   Random Walk on the Integer Number Line Probabilities


Friday, December 4, 2015

Random Walk Probabilities

   A mathematician is performing a probability experiment.  Starting from 0 (zero) on the integer number line, the mathematician flips a coin and takes one step to the right if it comes up a head or one step to the left if a tail. This process of flipping and moving either right or left is repeated for a given number of flips of the coin.
   This project computes the probability of ending the walk at position p after f flips of the coin.
   Here is a screenshot reporting the probability of ending a random walk at +3 after 5 flips as 5/32 instead of its decimal equivalent 0.15625.

   Note that the screen shows the positions that can be reached for a given number of flips as red-rimmed black circles. Those that cannot be reached as a function of the number of flips are represented as white circles.
   The number of possible paths to each possible position for a given number of flips is shown as a number above each possible position. It’s an interesting fact that these numbers are given by Pascal’s triangle and the nCr notation for combinations computes these numbers. The screen also shows that the totals number of possible paths for a given number of flips is a power of 2.
   The probability for ending a walk at position p after f flips is the number of paths to position p divided by the total number of paths for the given number of flips.
   This is the link to this project, Random Walk on the Integer Number Line Probabilities.
   A detailed explanation of the mathematics and the programming used in the project, including a couple of additional programming simplifications, are detailed in document that is available at no cost by sending an email request to grandadscience.com.
   This Scratch project needed a power of 2 script, a factorial script, and a nCr script that are available as separate Scratch projects by clicking on the links as shown below.
Combinations
Factorial
Powers of 2 Calculator
These are the links to my other Random Walk on the Integer Number Line projects.
Feynman’s Random Walk
Random Walk with Barriers