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
https://scratch.mit.edu/projects/109926519/

   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
https://scratch.mit.edu/projects/108902059/

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.
http://www.encyclopedia.com/topic/Sir_Francis_Galton.aspx

   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:
https://scratch.mit.edu/projects/92200985/
    This project complements my other Random Walk projects:
   The Huckster's Game
https://scratch.mit.edu/projects/68836046/
   Feynman’s Random Walk
https://scratch.mit.edu/projects/11282377/
   Random Walk with Barriers
https://scratch.mit.edu/projects/11300964/
   Jean Perrin's Random Walk Experiment
https://scratch.mit.edu/projects/87807676/
   Random Walk on the Integer Number Line Probabilities
https://scratch.mit.edu/projects/86951083/


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.
https://scratch.mit.edu/projects/86951083/
   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
https://scratch.mit.edu/projects/88028765/
Factorial
https://scratch.mit.edu/projects/87399897/
Powers of 2 Calculator
https://scratch.mit.edu/projects/86877882/
These are the links to my other Random Walk on the Integer Number Line projects.
Feynman’s Random Walk
https://scratch.mit.edu/projects/11282377/
Random Walk with Barriers
https://scratch.mit.edu/projects/11300964/

Wednesday, November 18, 2015

Combinations - nCr


   In the previous post on Factorials I mentioned that I needed a factorial algorithm for a Combinations project and the Combinations project for a Random Walker project.
   As you can see in the formula for the number of combinations of n things taken r at a time with no duplications there are three factorials to compute to get to the nCr.
   This is a screenshot of the Combinations project. The graphic of the fruit is to illustrate that if n = 4 (the pear, orange, banana, and strawberry) then there are four combinations (shown in the four rows) when taken 3 at a time. The project first asks for n, then r and then computes nCr.
   The project can be viewed and downloaded by clicking on this link.
https://scratch.mit.edu/projects/88028765/
   A free document in PDF format describing the coding in more detail can be obtained on request. Send an email to grandadscience@gmail.com.


Friday, November 13, 2015

Factorial


   This project computes Factorial N written as N!
   Here is the definition of Factorial N.
    Writing code is not a one-step process. Over the years I've found that breaking the coding process into three parts helps students understand that first of all, coding is an exercise in problem-solving and breaking the coding problem into a series of smaller problems is the most efficient method for coding.
   Here are the three Parts and seven Steps I encourage students to use when coding.
   I Do the Math with Paper & Pencil Part
     • (1) Analyze the problem
   II Do the Algebraic Thinking Part
     • (2) Identify the variables
     • (3) Determine the relationships between the variables
   III Do the Algorithmic Thinking Part
     • (4) Create a Logic Flow diagram
     • (5) Translate the relationships (math syntax) into (computer
             syntax)
     • (6) Combine the pieces of code (into the algorithm that solves
        the problem)
     • (7) Test the algorithm (debug)
   I describe in detail how to apply this method to the problem of coding a Factorial algorithm in a six-page document. Any interested reader can obtain a copy of this copyright-free document in pdf format by sending an email to grandadscience@gmail.com
   Here is the opening screen of the project. The user is asked to input N! The number 11 was typed into the blue-lined box at the bottom of the screen.
   In this picture the computation of 11! is reported as 39,916,800.
   This project can be viewed and downloaded by clicking on the following link to the Scratch web site.
https://scratch.mit.edu/projects/87399897/

Saturday, November 7, 2015

Powers of 2 Calculator

   In the Random Walker project that computes the probability of landing on position p after f flips of the coin there is the need to compute powers of 2.
   If you click on the green operators tab you will find the [sqrt  ( 0 )] block. Next to the sqrt in the block is a small downward-pointing triangle that opens a pull-down menu to reveal the list of operators built into Scratch. Note that there is not a 2x operator.
   By definition, 2x means ‘use 2 as a factor x times’. This short script does exactly that and is probably the way most Scratch programmers build a powers of 2 script.
   I enjoy coding work-arounds but my first thoughts didn’t coalesce around the definition method coded above. Instead, it focused on another method using logarithms.
   Let y = 2x. Then taking the logarithm of both sides, log(y) = 2log(x). Since x is the exponent, I created a variable in Scratch named exponent.
   Next, I created a green log of 2 block.
   I picked a green multiplication block from the green operator menu and set the exponent variable as one factor and the [log of 2] block as the other variable to build the block shown below.
   There is an inverse (anti-log) block in the green pull down operators menu labeled [10x of (  )] that computes log(y). 
   The [exponent * log of (2)] block is then set into the [10^ of (  )] block.
   But this computation will be a decimal close to the integer value of 2x.
   There is a [round (   )] block in the green operators menu.
   The [(10^ of (exponent)* (log of (2))] is placed in the [round (   )] block.
   This block is set into a [say (                ) block to report the needed powers of 2.
   This project can be viewed and downloaded by clicking on the following link.
https://scratch.mit.edu/projects/86877882/









Thursday, November 5, 2015

Cycloid - The Helen of Geometry

   The cycloid is the curve traced by a point on the circumference of a circle which rolls along a straight line without slipping.
   The cycloid has been called "The Helen of Geometry" in reference to the beauty of Helen of Troy (her face launched a thousand ships) and the infighting between mathematicians as they fought over the properties of the curve and who did what and when.
   In this Scratch project I code the cycloid using two different methods.
   The first method (see graphic below) uses the parametric equations for the cycloid,
           x = r(theta -sin(theta))
           y = r(1 - cos (theta))
where r is the radius of the generating circle.
   In the coding of the equation for x, there is a problem. If theta is given in degrees (º) then the value of (theta - sin(theta)) will not vary much since the sine varies from 0 to 1. Therefore it's necessary to change the first theta in the parenthesis from degrees to radians. The formula for converting degrees to radians is  
                         radians = degrees * (pi/180)
and this formula can be seen in the script for x in the parametric form.
   The second method (seen in the bottom half of the graphic) shows how a point on the rim of the circles traces a path (locus) identical to the shape generated by the parametric equations. Click on the video to see the Scratch program in action.
   For readers interested in the history and mathematics of the cycloid a free PDF about the Cycloid can be downloaded at this link:
   Apparently Galileo worked on the problem of the area under the curve for 50 years!
   The cycloid, when inverted, is called a brachistochrone. This curve has many surprising properties and will be the topic of a future Scratch project.