Tài liệu Dãy ngẫu nhiên, giả ngẫu nhiên và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG --------------------------------------- Lưu Thị Vân Xa DÃY NGẪU NHIÊN, GIẢ NGẪU NHIÊN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH: TOÁN ỨNG DỤNG MÃ SỐ: 60.46.01.12 NGƯỜI HƯỚNG DẪN KHOA HỌC: Người hướng dẫn chính: T.S Nguyễn Công Sứ Hà Nội – Năm 2015 LỜI CAM ĐOAN Tôi xin cam đoan: - Luận văn này là sản phẩm nghiên cứ của tôi. - Các số liệu, những kết luận nghiên cứu được trình bày trong luận văn này trung thực. - Tôi xin chịu tránh nhiệm về nghiên cứu của mình. Thang Long University Libraty MỤC LỤC Trang Trang phụ bìa ...................................................................................................... Lời cam đoan ...................................................................................................... Mục lục................................................................................................................ Chương I CÁC KHÁI NIỆM CƠ BẢN VÀ CÁC TÍNH CHẤT CỦA CÁC DÃY NGẪU NHIÊN Khái niệm về dãy ngẫu nhiên .................................................................. 1 Các tính chất của dãy ngẫu nhiên ........................................................... 2 I.2.1. Block – L (xâu) ......................................................................................... 3 I.2.2. Cỡ của xâu ............................................................................................... 3 I.2.3. GAP (Mảng) ............................................................................................. 5 I.2.4. Xâu đủ ...................................................................................................... 6 I.2.5. Xâu đơn điệu (loạt) .................................................................................. 7 Chương II MỘT VÀI TIÊU CHUẨN THỐNG KÊ ĐỂ KIỂM ĐỊNH VỀ TÍNH NGẪU NHIÊN CỦA MỘT DÃY SỐ Các tiêu chuẩn phù hợp ........................................................................ 11 II.1.1. Tiêu chuẩn χ2 (Khi bình phương) ......................................................... 11 II.1.2. Tiêu chuẩn Kômôgôrôp – Smirnôp (Tiêu chuẩn K – C) ...................... 13 II.1.3. So sánh hai tiêu chuẩn 2 và tiêu chuẩn K – C .................................... 14 Các tiêu chuẩn phi tham số và các tính chất khác ............................. 16 II.2.1. Kiểm tra tính đều (kiểm tra tần số) ...................................................... 17 II.2.2. Kiểm tra Xêri (Cặp) .............................................................................. 18 II.2.3. Kiểm tra (GAP – Mảng ) ...................................................................... 20 II.2.4. Tiêu chuẩn cỡ (Poken).......................................................................... 22 II.2.5. Tiêu chuẩn đủ ....................................................................................... 23 II.2.6. Kiểm tra hoán vị ................................................................................... 23 II.2.7. Tiêu chuẩn về nhóm (Runtest) .............................................................. 24 II.2.8. Tiêu chuẩn nghịch thế .......................................................................... 26 Chương III CÁC DÃY GIẢ NGẪU NHIÊN Khái niệm về dãy giả ngẫu nhiên ....................................................... 29 Dãy giả ngẫu nhiên thặng dư bậc hai ................................................ 31 III.2.1. Định nghĩa ........................................................................................... 31 III.2.2. Giả thuyết thặng dư bậc hai ................................................................ 32 III.2.3. Tính chất của bộ tạo x2 mod N ............................................................ 33 Phương pháp toàn đẳng tuyến tính ................................................... 34 III.3.1. Công thức ............................................................................................ 34 III.3.2. Tiêu chuẩn tần số ................................................................................ 40 III.3.3. Tiêu chuẩn tương quan ....................................................................... 42 III.3.4. Công suất............................................................................................. 44 III.3.5. Ví dụ .................................................................................................... 45 Dãy ghi dịch – Dãy ghi dịch tuyến tính ............................................. 47 III.4.1. Thanh ghi dịch phản hồi tuyến tính bậc n........................................... 47 III.4.2. Dãy ghi dịch, dãy ghi dịch tuyến tính ................................................. 48 Thang Long University Libraty III.4.3. Tính chất của dãy ghi dịch. ................................................................. 49 III.4.4. Tính chất của các M-dãy ..................................................................... 51 III.4.5. Chu kỳ của dãy ghi dịch tuyến tính và điều kiện M – dãy .................. 53 III.4.5.1. Hàm đặc trưng, đa thức đặc trưng của dãy ghi dịch ........................ 53 III.4.5.2. Chu kỳ của dãy ghi dịch tuyến tính. ................................................ 54 III.4.6. Hàm tự tương quan ............................................................................. 59 III.4.7. Một vài ví dụ về dãy ghi dịch chu kỳ cực đại ...................................... 60 LỜI NÓI ĐẦU Với sự phát triển và mở rộng việc ứng dụng máy tính trong các lĩnh vực khoa học. Các thủ pháp lựa chọn ngẫu nhiên các số ngày càng tỏ ra có lợi cho các mục đích khác nhau. Ví dụ: Để thiết lập các mô hình tự nhiên nhờ máy tính điện tử, các số ngẫu nhiên cho phép tiệm cận được các mô hình lí thuyết với thực tế và từ đó đưa ra được các phương pháp điều khiển thích dụng. Các bài toán kiểm tra thường dẫn đến việc kiểm tra ngẫu nhiên trên một số dạng của tổng thể, thành thử việc lựa chọn một cách ngẫu nhiên một số đối tượng của tổng thể sẽ bảo đảm đánh giá khách quan về tổng thể và giải pháp của việc lựa chọn ngẫu nhiên đó là phải thiết lập được các dãy số ngẫu nhiên. Các giá trị ngẫu nhiên sẽ là các dữ liệu đầu vào tốt nhất cho việc thử nghiệm tính hiệu quả của các thuật toán khác nhau để giải một bài toán trên một máy tính, hoặc các máy tính khác nhau. Các khóa ngẫu nhiên – tức là các khóa được lựa chọn một cách ngẫu nhiên là khóa tốt nhất về phương diện bảo mật tuyệt đối cho một hệ mật. Đặc trưng ngẫu nhiên tuyệt đối luôn được xem là tiêu chuẩn về độ tin cậy của khóa nói riêng và của hệ mật nói chung. Nguồn lí tưởng để tạo các dãy số ngẫu nhiên là kết quả đo các đại lượng vật lí ngẫu nhiên, chẳng hạn như nhiễu nhiệt, nhiễu điện (nhiễu trắng). Nếu như trước đây để làm điều đó cần phải tạo ra các thiết bị chuyên dụng thì ngày nay việc tạo ra các số ngẫu nhiên được thực hiện một cách tự động bằng các thuật toán và chương trình mẫu, và được tiến hành chỉ bằng một lệnh máy. Tuy nhiên trong nhiều trường hợp, vì những lí do khác nhau người lập trình vẫn phải tự tạo cho mình những dãy số ngẫu nhiên (mà thực chất chỉ là giả ngẫu nhiên) bằng các phương pháp thích dụng, hoặc các bộ tạo số ngẫu nhiên, ví như các bộ truy toán, các bộ cảm biến toàn đẳng tuyến tính, hoặc các bộ cảm biến M – dãy, các bộ cảm biến phi tuyến… Thang Long University Libraty Trong luận văn này tôi trình bày các khái niệm và tính chất cơ bản của các dãy ngẫu nhiên, giả ngẫu nhiên. Từ đó đưa ra một vài tiêu chuẩn thống kê để kiểm định các tính chất trên. Xây dựng một số phương pháp để sinh dãy giả ngẫu nhiên và khả năng ứng dụng các dãy đó trong thực tế. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của T.S Nguyễn Công Sứ. Tôi xin bày tỏ lòng biết ơn chân thành đến sự hướng dẫn nhiệt tình của thầy. Tôi cũng xin bày tỏ lòng biết ơn đến các thầy phản biện đã dành thời gian đọc bản thảo của luận văn và đóng góp nhiều ý kiến quý báu. Vì thời gian và trình độ có hạn, luận văn chắc chắn không thể tránh khỏi những thiếu sót. Tôi hi vọng sẽ nhận được sự đóng góp ý kiến của các thầy cô và các bạn. Hà Nội, ngày 15 tháng 05 năm 2015 Tác giả luận văn Lưu Thị Vân Xa CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN VÀ CÁC TÍNH CHẤT CỦA CÁC DÃY NGẪU NHIÊN Khái niệm về dãy ngẫu nhiên Ngày nay các dãy ngẫu nhiên được sử dụng rất rộng rãi cho các mục đích và các lĩnh vực khác nhau . Do vậy tùy thuộc vào mục đích sử dụng các định nghĩa về dãy ngẫu nhiên cũng không hoàn toàn giống nhau dù bản chất là như nhau. Sau đây là một số định nghĩa sẽ sử dụng trong luận văn này. Định nghĩa 1: Dãy ngẫu nhiên: Dãy ngẫu nhiên là quá trình ngẫu nhiên {Xt, tT},với thời gian rời rạc, tức là T = {0,1,2,…,n,…}. Từ nay về sau để cho đơn giản ta kí hiệu dãy ngẫu nhiên là {Xn, nN} với Xn là các đại lượng ngẫu nhiên rời rạc. Dãy số ngẫu nhiên: Dãy số ngẫu nhiên {x1, x2, … xn, …} là một dãy các giá trị quan sát được (còn gọi là một mẫu hay một thể hiện) của một dãy ngẫu nhiên {Xn, nN} trong đó các đại lượng ngẫu nhiên thành phần Xn (nN ) là rời rạc. Khi đó dãy {Xn, nN} được gọi là dãy sinh của dãy {x1, x2, …, xn, …}. Dãy ngẫu nhiên được gọi là ngẫu nhiên thực sự (hay lí tưởng) nếu các đại lượng ngẫu nhiên rời rạc thành phần Xn sinh ra nó, có cùng phân phối đều và độc lập với nhau. Định nghĩa 2: Dãy ngẫu nhiên là một thể hiện bất kì của một dãy các đại lượng ngẫu nhiên rời rạc có cùng phân phối đều trên tập M = {1,2,..., M} và độc lập lẫn 1 Thang Long University Libraty nhau, hay là một dãy giá trị bất kì được sinh một cách độc lập bởi cùng một đại 1 lượng ngẫu nhiên X rời rạc lấy giá trị trên tập M với xác suất như nhau bằng . 𝑀 Đại lượng ngẫu nhiên X được gọi là nguồn sinh (nguồn) của dãy và phân phối của X được gọi là phân phối nguồn, M: cỡ (cơ số) của nguồn, M: là tập nguồn. Các tính chất của dãy ngẫu nhiên Nếu gọi {X(t), t = 1, 2, …} là một dãy ngẫu nhiên sinh từ một nguồn sinh X có phân phối đều trên tập M có cơ số M thì về mặt thống kê chúng ta cũng có thể coi mỗi giá trị X(t) của dãy như một đại lượng ngẫu nhiên có cùng phân phối với X và độc lập với các đại lượng ngẫu nhiên khác trong dãy. X(t) được gọi là giá trị sinh của nguồn tại thời điểm t. I.2.1. Block – L (xâu) Định nghĩa 3: (Block – L) (xâu) Đoạn dãy {X(t), X(t+1),…,X(t+L-1)} của {X(t), t = 1,2,…} được gọi là xâu độ dài L (Block – L)(LN) sinh tại thời điểm thứ t của nguồn và được kí hiệu là XL(t). Khi đó XL(t) là một véc tơ ngẫu nhiên L chiều có các thành phần độc lập, cùng phân phối. Tính chất 1: Với mọi (t, L), XL(t) là một véc tơ ngẫu nhiên có phân phối xác suất P(XL(t) = xL) = 1 𝑀𝐿 , trong đó xL = (x0,x1,…,xL-1); xi M. Chứng minh: P(XL(t) = xL) = P(X(t) = x0, X(t+1) = x1, … , X(t+L-1) = xL-1). Do tính độc lập và cùng phân phối với phân phối của nguồn X nên xác suất đồng thời trên 2 L−1 1 L 1 = ∏ P(X(t + i) = xi ) = ( ) = L M M (LN) i=0 I.2.2. Cỡ của xâu Định nghĩa 4: Với một xâu XL(t) có độ dài L sinh tại thời điểm t bất kì của dãy ngẫu nhiên, ta gọi cỡ của xâu và kí hiệu là ∏(X L (t)) là đại lượng được tính bằng số giá trị khác nhau của M có mặt trong xâu XL(t). Đương nhiên ∏(X L (t)) cũng là một đại lượng ngẫu nhiên, nhận các giá trị nguyên m{1, 2, …, min (M, L)} Tính chất 2: Với dãy ngẫu nhiên thì với mỗi xâu độ dài L và với m bất kì ta có: m m P(∏ (X L (t)) = m) = CM SL 1 ML ; Với 1 ≤ m ≤ min (M, L) trong đó: 𝑚 - 𝐶𝑀 : là tổ hợp chập m của M; - 𝑆𝐿𝑚 : là số các xâu có độ dài L có thể lập được từ m phần tử khác nhau của M sao cho mỗi phần tử xuất hiện ít nhất 1 lần trong xâu. Chứng minh: Một xâu có cỡ m được lập nên bằng cách, trước hết chọn m kí tự trong 𝑚 M kí tự của nguồn: có 𝐶𝑀 cách Từ m kí tự chọn được có thể lập được 𝑆𝐿𝑚 xâu có độ dài L sao cho mỗi kí tự có mặt ít nhất một lần. Do tính đồng xác suất của các xâu (tính chất 1) nên: m m P(∏(L) = m) = CM SL 1 ML 3 Thang Long University Libraty 𝑋 𝐿 = {𝑥(𝑡), 𝑥(𝑡 + 1), … , 𝑥(𝑡 + 𝐿 − 1)} Nếu kí hiệu { 𝐿−1 là các xâu có độ 𝑋 = {𝑥(𝑡), 𝑥(𝑡 + 1), … , 𝑥(𝑡 + 𝐿 − 2)} dài L và L-1 tương ứng, sinh tại thời điểm t và kí hiệu ∏(𝑋 𝐿 (𝑡)) = ∏(𝐿) là cỡ tương ứng của xâu { ∏(𝑋 𝐿−1 (𝑡)) = ∏(𝐿 − 1) Khi đó ta có: {∏(𝐿) = 𝑚} = ({∏(𝐿 − 1) = 𝑚}. {𝑋(𝑡 + 𝐿 − 1) = 𝑥 ∈ 𝑋1 }) ∪ ({𝑋(𝑡 + 𝐿 − 1) ∈ 𝑀\𝑋2 }. {∏(𝐿 − 1) = 𝑚 − 1}) (*) Trong đó: - X1 là tập con của M gồm m phần tử có mặt trong XL-1(t); - X2 là tập gồm m-1 phần tử của X1 Bây giờ ta lập công thức cho 𝑆𝐿𝑚 : Do (*) và tính độc lập của các đại lượng ngẫu nhiên trong mỗi xâu nên: m m P{∏(L) = m} = CM SL 1 ML = P{∏(L − 1) = m}. P(X(t + L − 1) = xX1 ) + P(∏(L − 1) = m − 1). P(X(t + L − 1) ∈ M − X2 ) m m = CM SL−1 1 . m ML−1 M 𝑚 𝑚 𝑚−1 ) = 𝐶𝑀 [𝑚(𝑆𝐿−1 + 𝑆𝐿−1 m−1 m−1 + CM SL−1 1 𝑀𝐿 1 ML−1 . M−(m−1) M ] Từ đó ta có: Tính chất 3: Số các xâu có độ dài L có thể lập được từ m phần tử khác nhau (0 ≤ m ≤ min (L, M)) của M phần tử được tính bởi công thức: m m−1 ) SLm = m(SL−1 + SL−1 M Đặc biệt: SL1 = 1, SM = M! 4 I.2.3. GAP (Mảng) Định nghĩa 5: Ta gọi một GAP (mảng ) theo phân hoạch M = B + C của một dãy ngẫu nhiên là một đoạn của dãy bắt đầu từ một giá trị tại thời điểm t: X(t) và kết thúc tại thời điểm thứ t+L+1: X(t+L+1) (được gọi là giá trị đầu và giá trị cuối của GAP) sao cho chỉ 2 giá trị X(t), X(t+L+1)  C còn các giá trị trung gian X(t+1), X(t+2),…,X(t+L)  B. Giá trị L được gọi là độ dài của GAP. Tính chất 4 ( tính chất của GAP): Trước hết tương ứng với mỗi xâu (X(t), X(t+1),…,X(t+L+1)) ta xây dựng đại lượng ngẫu nhiên như sau: (𝐵,𝐶)(𝑡) = −1 nếu X(t)  B (𝐵,𝐶)(𝑡) = L nếu X(t) và X(t+L+1)  C còn X(t+i), (1 ≤ I ≤ L )  B, trong đó B và C là một phân hoạch xác định của M. Rõ ràng (B,C)(t) là một đại lượng ngẫu nhiên nhận các giá trị nguyên từ -1 đến + với phân phối xác suất: P{(B,C)(t) = -1} = 1 – p trong đó 𝑝 = # 𝐶 𝑀 ( #𝐶: Số phần tử của C) P{(B,C)(t) = L} = p2(1-p)L Thật vậy: P{(B,C)(t) = -1} = P(X(t)  B) = # 𝐵 𝑀 # = (𝑀\𝐶) 𝑀 # =1− 𝐶 𝑀 =1-p Ngoài ra {(B,C)=L} = {X(t)C}{X(t+1)B}…{X(t+L)B}{X(t+L+1)C} Từ tính độc lập và phân phối đều của dãy ta có P{(B,C)=L} = P{X(t)C}.{X(t+1)B}…{X(t+L)B}.{X(t+L+1)C} = p.(1-p)… ⏟ … … . … .(1-p)p = p2(1-p)L 𝐿 𝑙ầ𝑛 5 Thang Long University Libraty Bây giờ nếu gọi L(t) là số lượng các GAP (độ dài bất kì) có trong một xâu độ dài L bắt đầu từ thời điểm t. Khi đó ta có Tính chất 5 của GAP (mảng): Điều kiện cần và đủ để trong một xâu độ dài L bắt đầu từ thời điểm t số lượng các GAP theo một phân hoạch cho trước M = BC: L(t) = m với 0 18,31 chỉ trong 5% trường hợp. Khi so sánh giá trị tính được của V theo n phép thử của ta với các giá trị tương ứng p = 1% và p = 99% (bởi lẽ sự khác nhau giữa các giá trị thực tế với giá trị lí thuyết hoặc quá nhỏ hoặc quá lớn cũng gây ra nghi ngờ về tính ngẫu nhiên của thực nghiệm). Nếu giá trị V rơi vào khoảng 9995% hoặc 51% thì kết quả thực nghiệm là đáng nghi. Chú ý rằng các giá trị đưa ra trong bảng chỉ đúng với số n đủ lớn. Vậy thì các giá trị nào của n sẽ được coi là đủ lớn, thường thì trong thống kê giá trị n phải thỏa mãn điều kiện min (𝑛𝑝𝑠 ) ≥ 5. Đương 1≤𝑠≤𝑘 nhiên n càng lớn càng tốt và do vậy việc thực hiện bằng máy tính thì n thường là 1000, 10000 hoặc 100000 tùy theo yêu cầu về độ ngẫu nhiên của thực tế. II.1.2. Tiêu chuẩn Kômôgôrôp – Smirnôp (Tiêu chuẩn K – C) Giả sử ( X1, X2,…, Xn) là một mẫu của đại lượng X. Khi đó 𝐹𝑛 = 𝑚𝑥 𝑛 . Trong đó mx là số giá trị của mẫu nhỏ hơn xR. Tiêu chuẩn K – C dựa trên độ lệch giữa F(x) và Fn(x). Dãy số sẽ được coi là có tính ngẫu nhiên nếu mẫu cho hàm phân phối thực nghiệm tiệm cận tốt với hàm phân phối lí thuyết. Để làm điều đó người ta xây dựng các thống kê sau: 𝐾𝑛+ = √𝑛. ( 𝐾𝑛− = √𝑛. ( max (𝐹𝑛 (𝑥) − 𝐹(𝑥)) max (𝐹(𝑥) − 𝐹𝑛 (𝑥)) −∞<𝑥<+∞ −∞<𝑥<+∞ (Chú ý rằng với x cố định thì độ lệch chuẩn √𝐷(𝐹𝑛 (𝑥) − 𝐹(𝑥)) tỷ lệ với 1 √𝑛 ) 13 Thang Long University Libraty