Question? Leave a message!




Stochastic algorithms

Stochastic algorithms
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Stochastic algorithms Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Stochastic algorithms 2 Outline In this topic, we will cover: – Concepts about random numbers – Random number generators – Monte Carlo methods • Monte Carlo integration – Randomized quicksort – Skip listsStochastic algorithms 3 Stochastic The word stochastic comes from Greek: στόχος, – The relative translation is a word describing a target stick for archery practices – The pattern of arrow hits represents a stochastic process http://marshfieldrodandgunclub.com/ArcheryStochastic algorithms 4 Random Numbers I flipped a coin 30 times: HTHTHHHTTTHHHTHTTTTTTHHHHHHTTH One may almost suggest such a sequence is not random: what is the probability of getting 6 tails and then 6 heads? – Unfortunately, this is exactly what I got with the first attempt to generate such a sequence, and is as random a sequence as I can generate – Humans see patterns where none are…Stochastic algorithms 5 Random Numbers Generating random numbers is difficult… A small radioactive source is believed to have been used to generate the Rand Corporation's book A Million Random Digits with 100,000 Normal Deviates – Called an electronic “roulette wheel” • uses a ―random frequency pulse source‖ – 20,000 lines with 50 decimal digits per line divided into five columns of ten digits each – Available at the low price of USD 90 http://www.wps.com/projects/million/index.htmlStochastic algorithms 6 Random Numbers Problem: humans will not open the book to a random page... 73735 45963 78134 63873 02965 58303 90708 20025 The instructions include: 98859 23851 27965 62394 ―...open the book to an unselected page... 33666 62570 64775 78428 blindly choose a 5-digit number; this 81666 26440 20422 05720 number reduced modulo 2 determines the 15838 47174 76866 14330 starting line; the two digits to the right... 89793 34378 08730 56522 determine the starting column...‖ 78155 22466 81978 57323 16381 66207 11698 99314 75002 80827 53867 37797 Column: 81978 / 20000 = 4 99982 27601 62686 44711 84543 87442 50033 14021 Line: 81978 % 20000 = 01978 77757 54043 46176 42391 80871 32792 87989 72248 30500 28220 12444 71840Stochastic algorithms 7 Random Numbers Strategy 0: – Roll a die Not very useful, especially for computers http://xkcd.com/221/Stochastic algorithms 8 Random Numbers Strategy 1: – Use the system clock This is very useful for picking one 5-decimal-digit number about once a day It is also very poor for picking many random numbers, as any program doing so will most likely do so periodicallyStochastic algorithms 9 Random Numbers Strategy 2: – Use the keyboard Certain encryption programs use intervals between keystrokes to generate random numbers The user is asked to generate some text which is then analyzed – Random, but slow and tediousStochastic algorithms 10 Random Numbers Our best hope is to generate (using mathematics) a sequence of numbers which appears to be random A sequence of numbers which appears to be random but is not is said to be pseudo-random – We will look at one random number generatorStochastic algorithms 11 Linear Congruential Generators The first pseudo-random number generator which we will look as described by Lehmer in 1951 It is called a linear congruential generator because: – it uses a linear multiplier – it produces objects of the same shapeStochastic algorithms 12 Linear Congruential Generators Select an initial value x (called the seed) 0 Choose two fixed values A 0 and M 1 Given x , calculate i x = Ax mod M i + 1 i There are some restrictions on these values: – M should be prime – A and x should both be relatively prime to M 0Stochastic algorithms 13 Linear Congruential Generators For example, if M = 17, A = 6, and x = 3, the first 17 numbers are: 0 3, 1, 6, 2, 12, 4, 7, 8, 14, 16, 11, 15, 5, 13, 10, 9, 3 th The 17 number equals the first, so after this, the sequence will repeat itself A different seed generates a different sequence, e.g., with x = 4 we 0 get 4, 7, 8, 14, 16, 11, 15, 5, 13, 10, 9, 3, 1, 6, 2, 12, 4 however, it is only a shift...Stochastic algorithms 14 Linear Congruential Generators The choice of A will affect quality of the sequence Given the previous seed and modulus, but if we choose A = 2, we get the sequence 3, 6, 12, 7, 14, 11, 5, 10, 3, 6, 12, 7, 14, 11, 5, 10, 3 which you may note repeats itself earlier than when we used A = 2Stochastic algorithms 15 Linear Congruential Generators 31 If we choose the prime M = 2 – 1, then one value of A recommended by Lehmer is A = 48271 31 This generates a sequence of 2 – 2 unique numbers before it repeats We can then use modulus to map this onto a smaller range, or divisionStochastic algorithms 16 Linear Congruential Generators A word on linear congruential generators and the like: ―Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin...‖ John von Neumann The point here is, these methods produce pseudo-random numbers and not actually random numbersStochastic algorithms 17 Linear Congruential Generators The C++ standard library comes equipped with the int rand() function – Don’t use it... Most C++ standard libraries come with: Function Name Range 31 long lrand48() 0, 1, ..., 2 – 1 31 31 long mrand48() –2 , ..., 2 – 1 double drand48() 0, 1)Stochastic algorithms 18 Linear Congruential Generators By default, these use a 48-bit seed with x = 0 and 0 x = (Ax + C) mod M k + 1 k where A = 25214903917 10111011110111011001110011001101101 2 C = 11 1011 2 48 M = 2 and where the most significant bits of x are used k + 1Stochastic algorithms 19 Linear Congruential Generators All three generates use the same value – Suppose that x is the value is the following 48 bits: k + 1Stochastic algorithms 20 Linear Congruential Generators lrand48() uses the most significant 31 bits – Recall the avalanche effect