1、Games, Random NumbersandIntroduction to simple statisticsPRNGPseudo Random Number Generator蔡文能tsaiwn.tw蔡文能 C/C+ 程式設計1AgendaWhat is random number(亂數) ?How the random numbers generated ?rand( ) in C languages: Linear Congruential Why call “Pseudo random” ? (P不發音)How to do “true random” ?Application of

2、 Rrandom number ?Other topics related to Random numbersIntroduction to simple statistics (統計簡介)蔡文能 C/C+ 程式設計2BATNUM game/basicgames/showpage.php?page=14An ancient game of two playersOne pile of match sticks (or stones)Takes turn to remove 1, maxTake(至少拿 1, 至多拿 maxTake)可規定拿到最後一個贏或輸 !Winning strategy

3、? Games 須用到 Random Number! Why?蔡文能 C/C+ 程式設計3Bulls and Cows Game http:/5ko.free.fr/en/bk.html /wiki/Bulls_and_cows/zh-hant/%E7%8C%9C%E6%95%B0%E5%AD%97/od/paperpencil/a/bulls_and_cows.htm/eng/play/bk.html/index.php/online-games/bulls-and-cows/index.phpGames 須用到 Random Number! Why?蔡文能 C/C+ 程式設計4What i

4、s random number ?Sequence of independent random numbers with a specified distribution such as uniform distribution (equally probable)Actually, the sequence generated is not random, but it appears to be. Sequences generated in a deterministic way are usually called Pseudo-Random sequences.參考 /softwar

5、e/gsl/manual/gsl-ref_19.htmlNormal distribution? exponential, gamma, Poisson, 蔡文能 C/C+ 程式設計6Turbo C+ 的 rand( )與srand( ) #define RAND_MAX 0 x7fffu static unsigned long seed=0; int rand( ) seed = seed * 1103515245 + 12345; return seed % (RAND_MAX+1); void srand(int newseed) seed = newseed; static glob

6、al 變數請參考K&R課本4.6節Pseudo random number就是15個 1的binary注意 C 語言的 rand( ) 生出的不是 Normal Distribution!static 使其它file裡的function 看不見這 seed蔡文能 C/C+ 程式設計7Random Number Generating AlgorithmsLinear Congruential GeneratorsSimple way to generate pseudo-random numbersEasily crackedProduce finite sequences of numbers

7、Each number is tied to the othersSome sequences of numbers will not ever be generatedCryptographic random number generatorsEntropy sensors (i.e., extracted randomness)蔡文能 C/C+ 程式設計9Linear Congruential Generator (LCG) for Uniform Random DigitsPreferred method: begin with a seed, x0, and successively

8、generate the next pseudo-random number by xi+1 = (axi + c) mod m, for i = 0,1,2, wherem is the largest prime less than largest integer computer can storea is relatively prime to mc is arbitraryLet A be largest integer less than A (就是只取整數部份), then N mod m = N N/T*TAccept LCG with m, a, and c which pa

9、sses tests which are also passed by know uniform digitsmod 在C/C+/Java 用 %蔡文能 C/C+ 程式設計10The use of random numbers1. Simulation2. Recreation (game programming)3. Sampling4. Numerical analysis5. Decision making randomness an essential part of optimal strategies( in the game theory)6. Game program, . .

10、 .蔡文能 C/C+ 程式設計11Uniform Distribution(齊一分配 )在 發生的機率皆相同蔡文能 C/C+ 程式設計12Normal Distribution (常態分配 )蔡文能 C/C+ 程式設計13Standard Normal Distribution(標準常態分配)N(0, 1)平均是 0標準差 1蔡文能 C/C+ 程式設計14Central Limit Theorem (CLT)(中央極限定理 )如果觀察值數目 n 增加，則 n 個獨立且具有相同分配(independent and identically distributed, I.I.D.)的隨機變數(Ran

11、dom variable)之平均數向常態分配收斂。 樣本大小n30時， 趨近於常態分配。 蔡文能 C/C+ 程式設計16如何用 C 生出常態分配的亂數?#include double randNormal( ) / 標準常態分配產生器 int i; double ans =0.0; for(i=1; i =30 observations are drawn from the same population where X ?(,), then 蔡文能 C/C+ 程式設計38 Central Limit Theorem （中央極限定理）For a population with a mean a

12、nd a variance , the sampling distribution of the means of all possible samples of size n generated from the population will be approximately normally distributed - with the mean of the sampling distribution equal to and the variance equal to assuming that the sample size is sufficiently large.蔡文能 C/

13、C+ 程式設計39The Normal DistributionDescribed by (mean) (standard deviation; 標準差)Variance 變異數 = 標準差的平方Write as N( , ) 或 N( , 2) Area under the curve is equal to 1Standard Normal Distribution 蔡文能 C/C+ 程式設計40Why is the Normal Distribution important?It can be a good mathematical model for some distribution

14、s of real dataACT ScoresRepeated careful measurements of the same quantityIt is a good approximation for different types of chance outcomes (like tossing a coin)It is very useful distribution to use to model roughly symmetric distributionsMany statistical inference procedures are based on the normal

15、 distributionSampling Distributions are roughly normal (TBC)蔡文能 C/C+ 程式設計41Normal Distributions and the Standard DeviationNormal DistributionBlack line - MeanRed lines - 1 Std. Dev. from the mean (68.26% Interval)Green lines 2 Std. Dev. from the mean (95.44% Interval)What about 3 Std. Dev. from the

16、mean?95% Confidence interval 1.96 Std. Dev.蔡文能 C/C+ 程式設計4268-95-99.7 Rule for Normal Curves68.26%+-+3-399.74%+2-295.44%68.26% of the observations fall within of the mean 99.74% of the observations fall within 3 of the mean 95.44% of the observations fall within 2 of the mean 蔡文能 C/C+ 程式設計43Notations

17、It is important to distinguish between empirical and theoretical distributionsDifferent notation for each distribution蔡文能 C/C+ 程式設計44Density function of Normal DistributionThe exact density curve for a particular normal distribution is described by giving its mean () and its standard deviation ()den

18、sity at x = f(x) =蔡文能 C/C+ 程式設計45Confidence Intervals (CI) for ,from a single sample mean 蔡文能 C/C+ 程式設計46Confidence Interval? (1/2)當我們使用軟體去模擬真實環境時，通常會用亂數(random number)模擬很多次，假設第一次模擬的結果數據是X1，第二次是X2，重覆了n次後，就有X1、X2Xn共n個數據，這n個數據不盡相同，到底那個才是正確的? 直覺上，把得到的n個結果加總求平均，所得到的值應該比較能相信。但是我們可以有多少程度的去相信這個平均值(sample m

19、ean)呢? 這個問題討論的就是所謂的Confidence Interval (信賴區間)與顯著水準(significance level)。蔡文能 C/C+ 程式設計47Confidence Interval? (2/2)在實務上，想要在有限個模擬數據結果中得到一個較完美接近真實結果的數據，其實是不可能的。因此我們能做的就是去求得一個機率範圍(probability bound)。若我們可以得到一個機率範圍的上限c1和一個範圍的下限c2，則就有一個很高的機率1 ，會使得每次所得到的模擬結果平均值(sample mean)都落在c1到c2的範圍之間。Probability c1 = = c2

20、= 1 我們把(c1, c2)這個範圍稱為信賴區間(confidence interval)；稱為顯著水準(significance level)；100(1-)%稱為信心水準(confidence level)，用百分比表示；1-稱為信心係數(confidence coefficient)。蔡文能 C/C+ 程式設計48為何簡單隨機抽樣是個合理的抽樣方法？ 試想抽取16所醫院來預測393所醫院的平均出院病人數的例子，共有約1033種的不同樣本。依據中央極限定理，所得到的平均出院病人數分佈像個鐘形曲線，其中心位於所有醫院的平均出院病人數，且大多數的16所醫院平均出院病人數都離中心(大數法則)不

21、遠。 較有保障的抽樣辦法，被選取的樣本應使用隨機的原理取得。蔡文能 C/C+ 程式設計49Hypothesis Testing假設之檢定The null hypothesis for the test is that all population means (level means) are the same. (H0)The alternative hypothesis is that one or more population means differ from the others. (H1)蔡文能 C/C+ 程式設計50PRNG 相關補充請用 打 “PRNG” 查看ANSI X9.

22、17 PRNG (PRNG = Pseudo Random Number Generator)Von Neumann 想出的 middle square methodVon Neumann architecture ?PRNG in RC4 (RC4用於 802.11 無線網路加解密)http:/www.wisdom.weizmann.ac.il/itsik/RC4/rc4.htmlWEP : RC4 Stream cipher蔡文能 C/C+ 程式設計51ANSI X9.17 PRNGUse 3DES and a key KTi = Ek(current timestamp)outputi

23、= Ek(Ti seedi)seedi+1 = Ek(Ti outputi)WeaknessesOnly 64 bits are used for Tiseedi+1 can be easily predicted if state compromise蔡文能 C/C+ 程式設計52Jon von Neumann 1946 suggested the production of random number using arithmetic operations of a computer, middle square, square a previousrandom number and ex

24、tract the middle digits, Example generate 10-digit numbers, was 5772156649, square 33317792380594909201the next number is 7923805949Middle squaremiddle square has proved to be a comparatively poor source of random numbers. If zero appear as a number of the sequence, it will continually perpetuate itself.蔡文能 C/C+ 程式設計53Von Neumann architecture (/)The term von Neumann architecture refers to a computer design model that uses a single storage structure to hold both programs and data. The term von Neumann machine can be used to descr