Showing posts with label random walk. Show all posts
Showing posts with label random walk. Show all posts

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/

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/

Tuesday, July 9, 2013

Feynman's Linear Random Walk


   The famous physicist Richard Feynman is performing a random walk on the integer number line. Starting at position 0, he flips a coin. If it's heads, he takes one step to the right or, if tails, one step to the left, and flips again and again until a preset number of flips have been completed. He then marks his position.
   

   This type of random walk is called a Symmetric Random Walk on the 1-D Lattice. It's symmetric because the transition probability from left-to-right is 0.5.
   Most people think the most probable position to end a walk is 0, where the walk began. They reason that if the probability is 50-50, the walk should end on or near the origin.
   In The Feynman Lectures on Physics, Volume 1, Chapter 6, Probability, physicist Richard Feynman proves the amazing fact that for the random walk described above, the random walk is 'most likely' to end at the position marked by the 'square root of the number of steps in the walk'! If n is the number of steps in the walk, then the most probable end point of the walk is √(n).
   This Scratch project allows you to explore a simulation that should convince you of the truth of his finding. Click on the following link to view and use the Scratch project.

http://scratch.mit.edu/projects/11282377/ - player

   Set the Number of coin flips slider to a value from 500 to 1000 flips.
   Click on the green flag, run in Turbo if you want to speed up the random walk.
   Compare the position of the walker to the RMS distance prediction.
   A derivation of the Root Mean Square law (PDF format) can be obtained (free) by sending an email to grandadscience@gmail.com.