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/

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.

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/

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 2^x operator.

   By definition, 2^x 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 = 2^x. 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 [10^x 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 2^x.

   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/

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:

http://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/Martin2011.pdf

   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.

Order of Operations in Scratch

   Order of Operations is one concept in the traditional mathematics curriculum that programmers quickly forget. You will never see code written to evaluate expressions like this, 4² - 6 x 2 ÷ 4 x 3 + 5.

   So, how are operations handled in Scratch?

   Look at the green Operators menu in Scratch. Note that the four arithmetic operators, the random number picker, string operators (join, letter, length), mod, round, and square root operators are rounded at each end. The relational (<. =, >) and Boolean operators (and, or, not) are pointed at each end.

   The rounded ends represents parenthesis.

   Will this block evaluate as 9 or 7?

   If you look carefully you will see that the parenthesis tell us that the block will evaluate as 7.

   To build the expression, drop the multiplication block into the addition block. The white circle can be thought of as a set of  parenthesis ( ).

   If you build the expression and then click on it, it will report 7.

   Order of operations are very simple in Scratch.

Think parenthesis!

The Grecian Urn Problem

   The following problem is one of three problems A. K. Dewdney discussed in his Mathematical Recreations column appearing in the March 1991 issue of Scientific American. The three problems originated with mathematics professor Ross Honsberger, University of Waterloo, Canada.

   A Grecian urn contains 75 white beans and 150 black beans. Next to the urn is pile of 200 black beans.  

   Pick two beans at random from the urn.

   If both beans are black (A), place one on the pile and return the other to the urn.

   If one of the beans is black and the other bean white (B), place the black bean on the pile and drop the white bean, back into the urn.

   If both beans are white (C), discard both white beans, pick a black bean from the pile and drop it into the urn.

   No matter the color of the two beans, every time two beans are picked at random, the number of black and white beans in the urn will decrease by one.

   Question: Will there ever be just one bean in the urn and if, so, what will be its color?

   Not having a Grecian urn and a supply of black and white beans handy, I decided to write a Scratch simulation of the problem. You can view and download the Scratch program by clicking on this link.

https://scratch.mit.edu/projects/67083730/

   You can click on the green flag to run the program to find the answer to the problem. If you don't believe the result, run it again. If you still don't believe it, check my code and determine if there is a mistake in my logic.