Tài liệu Ma trận ngẫu nhiên và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN —————————————– NGUYỄN THỊ THU THẢO MA TRẬN NGẪU NHIÊN VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC Hà Nội - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN —————————————– NGUYỄN THỊ THU THẢO MA TRẬN NGẪU NHIÊN VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: Lý thuyết xác suất và thống kê toán học Mã số: 60 46 0106 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.TẠ NGỌC ÁNH Hà Nội - 2014 LỜI NÓI ĐẦU Các mức năng lượng của một hệ hạt nhân được mô tả bởi các giá trị riêng của một toán tử Hermit trong không gian Hilbert mà số chiều có thể vô hạn. Do vậy, khi tính toán ta phải đối mặt với không ít khó khăn. Vào những năm 1950, khi nghiên cứu về vấn đề đó, Eugene Wigner chỉ ra rằng thay vì phải đối mặt với toán tử trên không gian vô hạn chiều như trên, chúng ta có thể mô tả một hệ phức tạp các hạt nhân nguyên tử bởi một ma trận có các phần tử là các biến ngẫu nhiên (ma trận ngẫu nhiên). Với những ràng buộc nào đó về phân bố của các phần tử, ta có thể tìm ra phân bố của các giá trị riêng của ma trận ngẫu nhiên, từ đó có thể mô tả được các mức năng lượng của hệ hạt nhân. Với ý tưởng như vậy, Wigner và các đồng nghiệp của ông cũng như các nhà vật lý, toán học sau này đã nghiên cứu và phát triển lý thuyết ma trận ngẫu nhiên (RMT) thành một công cụ mạnh có ứng dụng rộng rãi trong vật lý, toán học và nhiều lĩnh vực kinh tế, kỹ thuật khác. RMT là một vấn đề khá mới mẻ với học viên cao học, đang được nhiều người quan tâm và có nhiều tài liệu tham khảo nên đây là một chủ đề khá hấp dẫn với chúng tôi. Vì vậy chúng tôi đã lựa chọn Ma trận ngẫu nhiên và ứng dụng làm đề tài nghiên cứu của luận văn. Cấu trúc của Luận văn gồm 3 chương. Chương 1: Kiến thức chuẩn bị Chương này đưa ra một số khái niệm, kiến thức cơ bản của lý thuyết ma trận và xác suất như: không gian xác suất, biến ngẫu nhiên, các bất đẳng thức xác suất, các định lí hội tụ, phương pháp moment,... mà sẽ được sử dụng ở các chương tiếp theo. Chương 2: Ma trận ngẫu nhiên Đây là chương chính của Luận văn, trong chương này chúng tôi trình bày các vấn đề sau đây: - Giới thiệu ba lớp ma trận ngẫu nhiên đặc biệt, đưa ra phân bố xác suất của ma trận ngẫu nhiên trong từng lớp. - Nghiên cứu về phân bố giá trị riêng của ma trận ngẫu nhiên: phân bố chính xác của giá trị riêng khi kích thước ma trận nhỏ và phân bố giới hạn các giá trị riêng của ma trận khi kích thước tiến tới vô cùng (luật bán nguyệt). Đưa ra phân bố của giá trị riêng lớn nhất (luật Tracy - Widom). - Nghiên cứu về ma trận hiệp phương sai, đưa ra định lí hội tụ của phân bố 1 thực nghiệm các giá trị riêng của ma trận hiệp phương sai (luật Marchenko Pastur). - Đưa ra định lý về tích hai ma trận ngẫu nhiên: phân bố thực nghiệm của tích giữa ma trận hiệp phương sai và một dãy ma trận Hermitian tiến đến giới hạn không ngẫu nhiên. - Đánh giá giới hạn xác suất đuôi của toán tử chuẩn của ma trận ngẫu nhiên sử dụng các phương pháp: ε lưới, tập trung độ đo và phương pháp moment. Chương 3: Ứng dụng Đưa ra ứng dụng trong vật lí, truyền thông không dây. Trong quá trình tìm hiểu tôi đã nắm bắt được một số vấn đề về lý thuyết ma trận ngẫu nhiên nhưng do thời gian có hạn cũng như kiến thức còn hạn chế nên luận văn khó tránh khỏi những sai sót. Vì vậy tôi mong nhận được sự giúp đỡ chỉ bảo của thầy cô và các bạn. Hà Nội, 2014. 2 LỜI CẢM ƠN Luận văn này được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình của TS. Tạ Ngọc Ánh - trường Học viện kĩ thuật quân sự. Thầy đã dành nhiều thời gian giúp đỡ, giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi xin bày tỏ lòng biết ơn sâu sắc đến người thầy của mình. Qua đây, tôi xin gửi lời cảm ơn sâu sắc tới các thầy giáo, cô giáo trong Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã trực tiếp giảng dạy và tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập Tôi xin cảm ơn gia đình, bạn bè và tất cả mọi người đã quan tâm, tạo điều kiện, giúp đỡ tôi hoàn thành luận văn này. 3 Mục lục Lời nói đầu 1 1 Kiến thức chuẩn bị 6 1.1 1.2 2 Kiến thức cơ bản của xác suất . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Biến ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Các bất đẳng thức cơ bản . . . . . . . . . . . . . . . . . . . 8 1.1.3 Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.4 Tính độc lập . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.5 Tập trung độ đo . . . . . . . . . . . . . . . . . . . . . . . . . 10 Các khái niệm cơ bản về ma trận . . . . . . . . . . . . . . . . . . . 14 1.2.1 Các dạng ma trận . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.2 Vết của ma trận . . . . . . . . . . . . . . . . . . . . . . . . . 15 Ma trận ngẫu nhiên 2.1 2.2 2.3 16 Mô hình ma trận ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Tập hợp các ma trận trực giao có phân bố Gauss (GOE) . 16 2.1.2 Tập hợp các ma trận Unita có phân bố Gauss (GUE) . . . 18 2.1.3 Tập hợp các ma trận đối ngẫu có phân bố Gauss (GSE) . 20 Phân bố giá trị riêng của ma trận ngẫu nhiên . . . . . . . . . . . . 22 2.2.1 Phân bố chính xác (với n hữu hạn) . . . . . . . . . . . . . . 22 2.2.2 Định lí Wigner và luật bán nguyệt (với n lớn) . . . . . . . 24 2.2.3 Luật Tracy Widom . . . . . . . . . . . . . . . . . . . . . . . 32 Ma trận hiệp phương sai . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.1 Luật Marchenko-Pastur . . . . . . . . . . . . . . . . . . . . 35 2.3.2 Luật Marchenko-Pastur đối với trường hợp độc lập cùng phân bố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 2.3.3 Luật Marchenko-Pastur đối với trường hợp không phải độc lập cùng phân bố . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4 Tích của hai ma trận ngẫu nhiên . . . . . . . . . . . . . . . . . . . 43 2.5 Toán tử chuẩn ma trận ngẫu nhiên . . . . . . . . . . . . . . . . . . 50 2.5.1 Phương pháp ε lưới . . . . . . . . . . . . . . . . . . . . . . . 50 2.5.2 Phương pháp đối số đối xứng (tùy chọn) . . . . . . . . . . 53 2.5.3 Phương pháp tập trung độ đo. . . . . . . . . . . . . . . . . 56 2.5.4 Phương pháp moment. . . . . . . . . . . . . . . . . . . . . . 57 3 Ứng dụng 3.1 3.2 62 Trong vật lí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.1.1 Định nghĩa và kết quả liên quan . . . . . . . . . . . . . . . 62 3.1.2 Vật lý hạt nhân . . . . . . . . . . . . . . . . . . . . . . . . . 65 Truyền thông không dây . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.1 Mô hình kênh . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.2 Kênh ma trận ngẫu nhiên . . . . . . . . . . . . . . . . . . . 70 3.2.3 Hệ thống tiền mã hóa tuyến tính 3.2.4 Mô hình chung DS-CDMA . . . . . . . . . . . . . . . . . . . 74 Kết luận . . . . . . . . . . . . . . 71 77 Phụ lục 78 Tài liệu tham khảo 79 5 Chương 1 Kiến thức chuẩn bị Lý thuyết ma trận ngẫu nhiên nghiên cứu về những ma trận có các phần tử là các biến ngẫu nhiên (hay nghiên cứu về các biến ngẫu nhiên lấy giá trị trong không gian các ma trận). Vì vậy, trong chương này chúng tôi trình bày một số kiến thức cơ bản của lý thuyết xác suất và ma trận mà sẽ được dùng ở các chương sau của luận văn. 1.1 Kiến thức cơ bản của xác suất Xét không gian xác suất cơ sở (Ω, F, P), trong đó: Ω là không gian mẫu gồm tất cả các kết quả có thể xảy ra của phép thử ngẫu nhiên. Mỗi kết quả w ∈ Ω gọi là một điểm mẫu hay là một biến cố sơ cấp. Ta còn có thể gọi Ω là không gian các biến cố sơ cấp. F là σ - đại số (σ - trường) các biến cố. Tức F là một họ các tập con của Ω thỏa mãn 3 điều kiện: • Ω∈F • Nếu E ∈ F thì Ω \ E = E c = E ∈ F • Nếu E1 , E2 , . . . ∈ F và Ei ∩ Ej = ∅(i 6= j) thì S∞ n=1 En ∈F Mỗi tập E ∈ F gọi là biến cố. P là độ đo xác suất xác định trên F . Tức là ánh xạ P : F → R thỏa mãn 3 điều kiện sau: • P(E) ≥ 0 với mọi E ∈ F • P(Ω) = 1 6 S∞ • Nếu E1 , E2 , . . . ∈ F và Ei ∩ Ej = ∅(i 6= j) thì P( 1.1.1 n=1 En ) = P∞ n=1 P(En ) Biến ngẫu nhiên Định nghĩa 1.1. (Biến ngẫu nhiên) Cho (R, R) là không gian đo được (tập R được trang bị σ - đại số các tập con của R). Biến ngẫu nhiên lấy giá trị trong R (biến ngẫu nhiên R - giá trị) là một ánh xạ X đo được từ không gian mẫu đến R, tức là một hàm X : Ω → R sao cho X −1 (S) là một biến cố với mọi S ∈ R. Chúng ta xét một vài ví dụ về biến ngẫu nhiên: • Biến ngẫu nhiên rời rạc, trong đó R là tập đếm được và R = 2R là σ -đại số rời rạc gồm tất cả các tập con của R. Ví dụ điển hình của R là tập con đếm được các số thực hoặc phức. Nếu R = {0, 1}, chúng ta nói các biến ngẫu nhiên là Boolean, nếu R = {c} chúng ta nói các biến ngẫu nhiên là tất định. • Các biến ngẫu nhiên có giá trị thực, trong đó R là đường thẳng thực và R là σ -đại số Borel, được tạo ra bởi các tập mở của R. • Các biến ngẫu nhiên có giá trị phức, nhận giá trị trong mặt phẳng phức với σ - đại số Borel. Khi xét các biến ngẫu nhiên có giá trị phức, các biến cố {|X − z| < r} với số phức z và r > 0 (nhỏ) có vai trò quan trọng. • Biến ngẫu nhiên giá trị vector trong không gian vector hữu hạn chiều, có giá trị trong Rn hoặc Cn với σ -đại số Borel. Ta có thể xem biến ngẫu nhiên giá trị vector X = (X1 , . . . , Xn ) là biến ngẫu nhiên đồng thời của các biến ngẫu nhiên vô hướng thành phần X1 , . . . , Xn . • Biến ngẫu nhiên có giá trị ma trận hoặc ma trận ngẫu nhiên, nhận giá trị trong không gian Mn×p (R) hoặc Mn×p (C) các ma trận có giá trị thực hoặc phức cấp n × p, với σ -đại số Borel, trong đó n, p ≥ 1 là các số nguyên (thường tập trung vào trường hợp n = p). Ta có thể xem biến ngẫu nhiên có giá trị ma trận X = (Xij )1≤i≤n;1≤j≤p là biến ngẫu nhiên đồng thời của các biến vô hướng thành phần Xij . Có thể áp dụng tất cả các phép toán ma trận thông thường (ví dụ như tổng, tích, định thức, vết, nghịch đảo, vv) trên ma trận ngẫu nhiên để có được biến ngẫu nhiên mới. 7 Định nghĩa 1.2. (Ký hiệu tiệm cận) Kí hiệu X = O(Y ), Y = Ω(X), X  Y , hoặc Y  X để biểu thị |X| ≤ CY với C không phụ thuộc n và n ≥ C . Kí hiệu X = o(Y ) nếu |X| ≤ c(n)Y với c → 0 khi n → ∞. Nếu X  Y  X thì kí hiệu X ∼ Y hay X = Θ(Y ) . Cho biến cố E = En phụ thuộc vào tham số n, Ta có: • Biến cố E là chắc chắn (hay đúng) nếu nó bằng biến cố Ω, ∅. • Biến cố E là hầu chắc chắn (hoặc với xác suất đầy đủ) nếu nó xảy ra với xác suất 1, P(E) = 1. • Biến cố E có xác suất áp đảo (Overwhelming probabitily) nếu với mọi A > 0 cố định, nó xảy ra với xác suất 1 − OA (n−A ) (tức là P(E) ≥ 1 − CA n−A với CA độc lập với n). • Biến cố E có xác suất cao (Hight probabitily) nếu có xác suất 1 − O(n−c ) với c > 0 độc lập với n (tức là P(E) ≥ 1 − Cn−c với C độc lập với n). • Biến cố E là tiệm cận hầu chắc chắn nếu nó có xác suất 1 − o(1), do đó xác suất tiến đến 1 khi n → ∞. 1.1.2 Các bất đẳng thức cơ bản Với X là biến ngẫu nhiên, chúng ta có một số khái niệm: • X bị chặn chắc chắn nếu tồn tại M > 0 sao cho |X| ≤ M chắc chắn. • X bị chặn hầu chắc chắn nếu tồn tại M > 0 sao cho |X| ≤ M hầu chắc chắn. • X dưới Gauss (Subgaussian) nếu tồn tại C, c > 0 sao cho P(|X| ≥ λ) ≤ C exp(−cλ2 ) với mọi λ > 0. • X có đuôi dưới mũ (Sub-exponential tail) nếu tồn tại C, c, a > 0 sao cho P(|X| ≥ λ) ≤ C exp(−cλa ) với mọi λ > 0. • X có moment cấp k hữu hạn với k ≥ 0 nếu tồn tại C sao cho E|X|k ≤ C . • X khả tích tuyệt đối nếu E|X| < ∞. • X hữu hạn hầu chắc chắn nếu |X| < ∞ hầu chắc chắn. 8 Định lý 1.1. (Bất đẳng thức Markov [8]) Với X là biến ngẫu nhiên không âm, ta có: 1 λ (1.1) 1 λ (1.2) P(X ≥ λ) ≤ EX Với X là biến ngẫu nhiên bất kỳ, ta có P(|X| ≥ λ) ≤ E|X| Hệ quả 1.1. (Bất đẳng thức Chebyshev [8]) P(|X − E(X)| ≥ λ) ≤ Var(X) λ2 (1.3) Định lý 1.2. (Bất đẳng thức Jensen [8]) Cho F : R → R là hàm lồi (tức là F ((1 − t)x + ty) ≥ (1 − t)F (x) + tF (y) với mọi x, y ∈ R, 0 ≤ t ≤ 1 ) và X là biến ngẫu nhiên bị chặn giá trị thực. Thì EF (X) ≥ F (EX). Định lý 1.3. (Bất đẳng thức Bernstein trong trường hợp đơn giản nhất [8]) Nếu X1 , . . . , Xn là các biến ngẫu nhiên Bernoulli độc lập nhận giá trị +1 và −1 với xác suất 1/2, thì với mọi số thực dương ε ta có  ) (   n   X nε2 1   Xi  > ε ≤ 2 exp − . P  2(1 + ε/3)  n i=1 1.1.3 Sự hội tụ Giả sử X1 , X2 , . . . là dãy các biến ngẫu nhiên cùng xác định trên không gian xác suất. Để cho gọn ta dùng kí hiệu (Xn ) để chỉ dãy biến ngẫu nhiên. Hội tụ hầu chắc chắn: Dãy biến ngẫu nhiên (Xn ) được gọi là hội tụ hầu chắc chắn đến biến ngẫu nhiên X nếu tồn tại tập A có xác suất không sao cho Xn (w) → X(w), w ∈ /A hoặc tương đương: P(lim sup |Xn − X| > ε) = 0 a.s Sự hội tụ hầu chắc chắn được kí hiệu là: Xn → X . Hội tụ theo xác suất: Dãy biến ngẫu nhiên (Xn ) được gọi là hội tụ theo xác suất tới biến ngẫu nhiên X nếu với ε > 0 bất kì lim P(|Xn − X| > ε) → 0 n→∞ 9 P Sự hội tụ theo xác suất được kí hiệu là: Xn → X . Trong lí thuyết hàm biến thực, thuật ngữ hội tụ theo xác suất chính là hội tụ theo độ đo. Hội tụ theo phân bố: Dãy biến ngẫu nhiên (Xn ) được gọi là hội tụ phân bố đến X nếu, với mỗi hàm liên tục bị chặn F : R → R, có lim EF (Xn ) = EF (X) n→∞ 1.1.4 Tính độc lập Định nghĩa 1.3. Một họ (Xα )α∈A các biến ngẫu nhiên (có thể là hữu hạn, vô hạn đếm được, hoặc vô hạn không đếm được) được gọi là cùng độc lập nếu phân bố của (Xα )α∈A là độ đo tích của các phân bố thành phần Xα . Một họ (Xα )α∈A là độc lập từng cặp nếu (Xα , Xβ ) là cùng độc lập với mọi α.β ∈ A phân biệt. Tổng quát, (Xα )α∈A là độc lập k-cặp nếu (Xα1 , . . . , Xαk0 ) là cùng độc lập với mọi 1 ≤ k 0 ≤ k và mọi α1 , . . . , αk0 phân biệt. 1.1.5 Tập trung độ đo Giả sử ta có số lượng lớn biến ngẫu nhiên độc lập vô hướng X1 , ..., Xn . Nếu mỗi Xi thay đổi trong khoảng O(1), thì dĩ nhiên tổng của chúng Sn = X1 +. . .+Xn thay đổi trong khoảng O(n). Tuy nhiên hiện tượng tập trung độ đo, khẳng định rằng nếu có đủ số lượng các biến độc lập thành phần X1 , ..., Xn , thì tổng này tập √ trung mạnh trong một phạm vi hẹp hơn nhiều, thường là trong khoảng O( n). A. Tổ hợp tuyến tính và phương pháp moment Đối với trường hợp biến ngẫu nhiên bị chặn: Phương pháp moment cấp 0 đưa ra giới hạn trên thô khi S khác không, P(Sn 6= 0) ≤ n X P(Xi 6= 0). (1.4) i=1 Phương pháp moment cấp một đưa ra giới hạn E|Sn | ≤ n P E|Xi |. Kết hợp i=1 bất đẳng thức Markov (1.2) ta có bất đẳng thức độ lệch lớn n 1X P(|Sn | ≥ λ) ≤ E|Xi | λ i=1 10 (1.5) Bây giờ xét phương pháp moment cấp hai. Ta có: E|Sn |2 = n P n P EXi Xj . Do i=1 j=1 đó: VarSn = n P Var(Xi ). i=1 Kết hợp với bất đẳng thức Chebyshev (1.3) đưa ra bất đẳng thức độ lệch lớn n 1 X Var(Xi ). P(|Sn − ESn | ≥ λ) ≤ 2 λ (1.6) i=1 Bây giờ chúng ta chuyển sang những moment cấp cao hơn. Giả sử chuẩn hóa Xi có trung bình 0, phương sai không quá 1 và độ lớn bị chặn hầu chắc chắn bởi K, |Xi | ≤ K (a.s). Để đơn giản, ta giả sử Xi có giá trị thực, trường hợp giá trị phức là tương tự. Giả sử rằng X1 , ..., Xn là độc lập k -cặp với k là số nguyên dương chẵn. Chúng ta tính moment cấp k : X E|Sn |k = EXi1 . . . Xik 1≤i1 ≤ik ≤n Nếu các Xij chỉ xuất hiện một lần, thì kỳ vọng là 0 (do Xij có trung bình 0). Vì vậy có thể giả sử mỗi Xij xuất hiện ít nhất hai lần. Do đó sẽ có nhiều nhất k/2 Xij xuất hiện riêng biệt. • Nếu có chính xác k/2 xuất hiện, thì từ giả thiết phương sai đơn vị chúng ta thấy rằng kỳ vọng có độ lớn tối đa là 1. • Nếu có k/2 − r xuất hiện, thì từ giả thiết phương sai đơn vị và giới hạn trên bởi K chúng ta thấy kỳ vọng có độ lớn tối đa là K 2r . Điều này dẫn đến giới hạn trên E|Sn |k ≤ k/2 P K 2r Nr . Với Nr là số cách gán số 0 nguyên i1 , . . . , ik trong {1, . . . , n}, sao cho mỗi ij xuất hiện ít nhất hai lần và có chính xác k/2 − r số nguyên xuất  hiện. n Sử dụng giới hạn thô: Có ≤ k nk/2−r cách lựa chọn (k/2 − r) số (k/2 − r)! 2 −r nguyên từ {1, . . . , n}. Mỗi số nguyên ij lấy từ một trong (k/2 − r) số nguyên, dẫn đến giới hạn thô: Nr ≤ nk/2−r (k/2 − r)k (k/2 − r)! Theo công thức Stirling n! ≥ nn e−n (xem [5]) đưa ra k Nr ≤ n 2 −r ( k2 − r) k −r 2 e −( k2 −r) k k k k k k k ( − r)k = (en) 2 −r ( − r) 2 +r ≤ (en) 2 −r ( ) 2 +r 2 2 2 11 r k/2 P K 2k k Do đó: E|Sn | ≤ (en )k/2 ( ) . 2 en 0 k Nếu chúng ta giả sử: K2 ≤ n/k . Thì: E|Sn |k ≤ (enk/2)k/2 k/2 P 0 Do k/2 P 0 1 . er 1 ≤ 2 nên: E|Sn |k ≤ 2(enk/2)k/2 . r e Điều này dẫn đến bất đẳng thức độ lệch lớn: √ E|S |k P(|Sn | ≥ λ n) ≤ √ n k = 2( (λ n) p ek/2 k ) . λ (1.7) Khá phức tạp khi chúng ta kiểm soát những moment lớn E|Sn |k . Tuy nhiên có phương pháp Chernof thực hiện dễ dàng hơn thông qua moment lũy thừa: EetX Lấy φ(x) = etx . Thì: P(X ≥ a) = P(etX ≥ eta ) ≤ ta e Bổ đề 1.1. (Bổ đề Hoefding [8]) Cho X là biến vô hướng lấy giá trị trong [a, b], với t > 0 bất kỳ EetX ≤ etEX (1 + O(t2 Var (X) exp(O(t(b − a))))). (1.8) EetX ≤ etEX exp(O(t2 (b − a)2 )). (1.9) Đặc biệt Định lý 1.4. (Bất đẳng thức Chernof [8]) Cho X1 , . . . , Xn là các biến ngẫu nhiên vô hướng độc lập, |Xi | ≤ K hầu chắc chắn với trung bình µi và phương sai σi2 . Thì với mọi λ ≤ 0, có: P(|Sn − µ| ≥ λσ) ≤ C max(exp(−cλ2 ), exp(−cλσ/K)). trong đó C, c > 0, µ := n P µi và σ 2 := i=1 n P i=1 (1.10) σi2 . Với các biến ngẫu nhiên X1 , . . . , Xn , ... độc lập cùng phân bố với kỳ vọng µ phương sai σ 2 , bất đẳng thức Chernof khẳng định rằng Sn tập trung mạnh trong √ phạm vi nµ + O(σ n). 3 B. Phương pháp chặt cụt Đối với trường hợp biến ngẫu nhiên không bị chặn ta sử dụng phương pháp chặt cụt. Kí hiệu: Xi,≤N := Xi I(|Xi | ≤ N ) 12 Xi,>N := Xi I(|Xi | > N ) khi đó ta chia biến ngẫu nhiên Xi thành Xi = Xi,≤N + Xi,>N với N là tham số chặt cụt được tối ưu hóa sau (phụ thuộc n). Tương tự chia Sn = Sn,≤N + Sn,>N , với Sn,≤N = X1,≤N + . . . + Xn,≤N Sn,>N = X1,>N + . . . + Xn,>N Chúng ta ước tính phần đuôi của Sn,≤N và Sn,>N bằng hai phương pháp khác nhau. Với Sn,≤N , biến Xi,≤N bị chặn, do đó sử dụng bất đẳng thức độ lệch lớn. Với Sn,>N , biến Xi>N không bị chặn, nhưng chúng tiến đến moment cấp 0 và cấp một nhỏ, do đó sử dụng phương pháp moment. Chúng ta sẽ bắt đầu với một ứng dụng của phương pháp này. Định lý 1.5. (Luật yếu số lớn [8]). Cho X1 , X2 , . . . là các biến ngẫu nhiên vô hướng độc lập cùng phân bố với X , trong đó X khả tích tuyệt đối. Thì Sn /n hội tụ theo xác suất đến EX . Chứng minh. Bằng cách trừ EX từ X , không mất tính tổng quát ta có thể giả sử rằng X có trung bình 0. Chúng ta cần chứng minh: P (|Sn | ≥ nε) = o(1) với mọi ε > 0 cố định. Nếu X có phương sai hữu hạn, thì từ (1.6) có điều cần khẳng định. Nếu X có phương sai vô hạn, chúng ta thực hiện phương pháp chặt cụt như sau. Chia Xi = Xi,≤N + Xi,>N , Sn = Sn,≤N + Sn,>N (và X = X≤N + X>N ) như ở trên và N lựa chọn sau. Biến X≤N là bị chặn và do đó phương sai bị chặn, từ các định lý hội tụ trội chúng ta thấy rằng |EX≤N | ≤ ε/4 nếu N là đủ lớn. Từ (1.6), chúng ta kết luận P(|Sn≤N | ≥ εn/2) = o(1) Trong khi đó, để giải quyết X>N chúng ta dùng (1.5): 2 ε P(|Sn>N | ≥ εn/2) ≤ E|X>N | Theo định lý hội tụ đơn điệu, chúng ta có thể làm cho E|X>N | nhỏ tùy ý (có thể nhỏ hơn so với δ > 0) bằng cách lấy N đủ lớn. Vậy chúng ta có: P(|Sn | ≥ 2 nε) = δ + o(1), với mọi δ . ε 13 3 Định lý 1.6. (Luật mạnh số lớn [8]) Cho X1 , X2 , . . . là các biến ngẫu nhiên vô hướng độc lập cùng phân bố với X , trong đó X khả tích tuyệt đối. Thì Sn /n hội tụ hầu chắc chắn đến EX . C. Tổ hợp Lipschitz Trong phần trước, chúng ta xét tổ hợp tuyến tính của các biến ngẫu nhiên độc lập X1 , . . . , Xn . Để đơn giản ta kí hiệu X := (X1 , . . . , Xn ). Bây giờ chúng ta xét tổ hợp F (X) tổng quát hơn. Định lý 1.7. (Bất đẳng thức tập trung Talagrand [7]) Cho X1 , . . . , Xn là các biến phức độc lập với |Xi | ≤ K , K > 0, 1 ≤ i ≤ n. Cho F : Cn → R là hàm lồi 1 - Lipschitz. Thì với mọi λ ta có: P(|F (X) − MF (X)| ≥ λK) ≤ C exp(−cλ2 ). (1.11) P(|F (X) − EF (X)| ≥ λK) ≤ C exp(−cλ2 ). (1.12) và với hằng số C, c > 0, MF (X) là trung vị của F (X). 1.2 1.2.1 Các khái niệm cơ bản về ma trận Các dạng ma trận Cho ma trận:  a11 a12  a21 a22 A=  ... ... am1 am2  . . . a1n . . . a2n   = (aij )m×n ... ...  . . . amn ta xét một số loại ma trận sau đây: Ma trận vuông: là ma trận có số hàng bằng số cột (m = n). Ma trận tam giác trên: là ma trận vuông mà các phần tử dưới đường chéo chính của ma trận bằng 0. Ma trận tam giác dưới: là ma trận vuông mà các phần tử phía trên đường chéo chính của ma trận bằng 0. 14 Ma trận đường chéo: là ma trận vuông có tất cả các phần tử ngoài đường chéo chính bằng 0. Ma trận đối xứng: là ma trận vuông có các cặp phần tử đối xứng qua đường chéo chính bằng nhau aij = aji , với mọi i, j . Ma trận chuyển vị: là ma trận nhận được bằng cách đổi hàng thành cột và ngược lại. Thường kí hiệu ma trận chuyển vị của A là AT Ma trận trực giao: là ma trận vuông có các phần tử là số thực sao cho ma trận chuyển vị chính là nghịch đảo của nó, AT A = AAT = I . Ma trận phức liên hợp: là ma trận nhận được từ ma trận ban đầu bằng cách thay phần tử a + ib bởi a − ib. Ký hiệu A∗ là ma trận phức liên hợp của A. Ma trận Hermit (ma trận phức đối xứng): là ma trận vuông với các phần tử trên đường chéo chính là số thực còn các cặp phần tử đối xứng qua đường chéo chính là những số phức liên hợp. 1.2.2 Vết của ma trận Vết của ma trận vuông A cấp n × n được xác định bằng tổng các phần tử trên đường chéo chính. tr(A) = a11 + a12 + . . . + ann = n X aii . i=1 Tương đương với vết của ma trận là tổng các giá trị riêng của nó: tr(A) = n P λi i=1 với λi là giá trị riêng của A. Và vết bất biến khi thay đổi cơ sở. Vết của ma trận liên hợp: Cho A là ma trận vuông cấp n × n bất kì, P là ma trận vuông cấp n × n và khả nghịch. Liên hợp của A theo P là P AP −1 , khi đó ta có: tr(A) = tr(P AP −1 ). Một số tính chất khác: tr(A) = tr(AT ) tr(AB) = tr(BA) tr(A + B) = tr(A) + tr(B) tr(cA) = c.tr(A) 15 Chương 2 Ma trận ngẫu nhiên 2.1 Mô hình ma trận ngẫu nhiên Cho không gian xác suất (Ω, F, P). Xét ma trận vuông M = (Mij )1≤i,j≤n , với n là số nguyên dương và Mij là các biến ngẫu nhiên xác định trên Ω, nhận giá thực hoặc phức. Khi đó M được gọi là ma trận ngẫu nhiên. Có khá nhiều cách phân loại ma trận ngẫu nhiên tuy nhiên cách phân loại dựa theo phân bố của các ma trận được nhiều người quan tâm. Chính vì vậy chúng tôi lựa chọn cách phân loại đó trong luận văn này. Sau đây chúng tôi sẽ đưa ra ba lớp ma trận cơ bản được đề xuất bởi Wigner: tập hợp các ma trận trực giao có phân bố Gauss (Gaussian orthogonal ensemble) (GOE), tập hợp các ma trận unita có phân bố Gauss (Gaussian unitary ensemble) (GUE) và tập hợp các ma trận đối ngẫu có phân bố Gauss (Gaussian symplectic ensemble) (GSE). 2.1.1 Tập hợp các ma trận trực giao có phân bố Gauss (GOE) Phân bố Gauss với trung bình µ và phương sai σ 2 có hàm mật độ xác suất được cho bởi: ρ(x) = √ 1 (x − µ)2 2σ 2 . e − 2πσ 2 Có nhiều cách khác nhau để nói về GOE. Cách thông thường là xét hàm mật độ xác suất đồng thời của các phần tử trong ma trận. Xét ma trận đối xứng M = (Mij )n×n với Mij là các biến ngẫu nhiên độc lập có phân bố như sau: các phần tử nằm trên đường chéo chính có phân bố Gauss 16 với trung bình 0 và phương sai 1: 2 1 ρ(Mii ) = √ e−Mii /2 , 2π các phần tử nằm phía trên đường chéo chính có phân bố Gauss với trung bình 1 2 0 và phương sai , có hàm mật độ 2 1 ρ(Mij ) = √ e−Mij . π Do tính đối xứng nên ma trận là hoàn toàn xác định khi ta biết phân bố của các phần tử ở nửa trên của ma trận kể từ đường chéo chính:  2 1   √ e−Mij /2 i = j ρ(Mij ) = 2π 2 1   √ e−Mij (2.1) i - Xem thêm -