Random là gì? Bản chất của sự ngẫu nhiên trong khoa học máy tính

Random (ngẫu nhiên) là kết quả từng lần không do ai chọn tay và người dùng không biết trước, dù có thể biết những khả năng xảy ra. Trong máy tính, số random thường là số giả ngẫu nhiên: thuật toán tính từ một giá trị khởi đầu, ai biết cả hai vẫn tính lại được.

Random nghĩa là gì trong đời thường, toán học và máy tính?

Trong đời thường, random là tình cờ, không theo kế hoạch; trong toán học, đó là kết quả được mô tả bằng một phân phối xác suất; trong máy tính, đó là đầu ra của một bộ sinh số. Mỗi ngữ cảnh đòi hỏi một mức chặt khác nhau.

Nghĩa đời thường khớp với định nghĩa của từ điển Cambridge. Khi bạn nói "random một bài hát" hay "gặp random một người quen ngoài đường", ý là không ai sắp đặt trước.

Toán học mô tả ngẫu nhiên cụ thể hơn. Nó không đoán được một lần cụ thể sẽ ra gì, nhưng nói được tỉ lệ mỗi kết quả khi lặp lại rất nhiều lần.

Ví dụ giả định: chọn một trong bốn tên An, Bình, Chi, Dũng. Nếu chọn đều, mỗi tên có 1/4, tức 25%.

• An 25%
• Bình 25%
• Chi 25%
• Dũng 25%

Nếu cho An tỉ lệ gấp đôi (trọng số 2, ba người còn lại 1), tổng trọng số là 5: An có 2/5 = 40%, mỗi người kia 1/5 = 20%.

• An 40%
• Bình 20%
• Chi 20%
• Dũng 20%

Cả hai cách đều là chọn ngẫu nhiên. "Mọi kết quả bằng nhau" chỉ là một phân phối cụ thể (phân phối đều), không phải định nghĩa của random.

Trong khoa học máy tính, số ngẫu nhiên là đầu ra của một bộ sinh số (RNG, random number generator). Bộ sinh được thiết kế để chuỗi giá trị không có quy luật dễ nhận ra và tuân theo một phân phối định trước.

Bộ sinh có thể là một thuật toán tất định hoặc lấy dữ liệu từ một nguồn vật lý khó đoán. Chương trình sau đó đổi con số này thành lựa chọn: ô nào trúng, lá bài nào được rút, ai lên bảng.

Mô hình lý tưởng mà NIST (Viện Tiêu chuẩn và Công nghệ Hoa Kỳ) mô tả là một chuỗi bit trong đó mỗi bit là 0 hoặc 1 với xác suất 1/2, các bit độc lập với nhau và không ai đoán trước được.

Máy tính làm theo lệnh thì tạo số ngẫu nhiên bằng cách nào?

Máy tính tạo số ngẫu nhiên bằng hai cách: dùng thuật toán giả ngẫu nhiên, hoặc lấy "độ khó đoán" từ thế giới vật lý. Trong thực tế hai cách thường đi cùng nhau.

Cách thứ nhất là bộ sinh số giả ngẫu nhiên (PRNG). Đây là thuật toán tất định: nó nhận một giá trị khởi đầu gọi là seed (hạt giống), rồi tính ra từng số kế tiếp từ trạng thái trước đó.

Chuỗi tạo ra không có quy luật dễ thấy và có các tính chất thống kê giống chuỗi ngẫu nhiên, nhưng bản chất vẫn là phép tính. Cùng thuật toán, cùng seed và cùng trạng thái thì ra cùng một chuỗi. Tính chất này hữu ích khi cần chạy lại một mô phỏng hoặc dò lại một lỗi.

Module random của Python dùng thuật toán Mersenne Twister. Tài liệu của nó cho biết dùng lại seed thì chuỗi số tái tạo được giữa các lần chạy nếu không có nhiều luồng cùng gọi bộ sinh; còn thuật toán và cách gieo seed có thể đổi giữa các phiên bản Python.

Cách thứ hai là nguồn entropy: phần cứng hoặc hệ điều hành thu những biến động khó đoán (nhiễu) rồi đưa vào bộ sinh.

Theo NIST, một nguồn entropy gồm nguồn nhiễu, các bước kiểm tra để phát hiện khi nguồn hỏng, và có thể thêm bước xử lý dữ liệu thô. Nó không đơn giản là "đo một tiếng ồn là xong".

Hai cách thường kết hợp như sau: entropy dùng để gieo seed, một thuật toán được thiết kế cho mật mã dùng seed đó để sinh nhanh nhiều số khó đoán.

1. Nguồn entropybiến động khó đoán từ phần cứng, hệ điều hành
2. Seedgiá trị khởi đầu, gieo từ entropy
3. Thuật toántính từng số kế tiếp từ trạng thái trước
4. Dãy sốnhiều số khó đoán, sinh nhanh
5. Lựa chọnô trúng, lá bài, người lên bảng

Bài so sánh True Random, Pseudo-Random và CSPRNG đi sâu vào từng loại. Trình duyệt web có hai hàm cho hai mức yêu cầu; theo MDN, cả hai thường đều do thuật toán sinh ra, khác nhau ở độ khó đoán:

Trên Vongquay.com, vòng quay thường chạy trên máy bạn và dùng Math.random() để chọn ô theo tỉ lệ, đủ cho lớp học hay buổi tiệc. Công cụ tạo mật khẩu ngẫu nhiên thì dùng crypto.getRandomValues(), vì mật khẩu cần khó đoán. Mục Vongquay.com dùng loại ngẫu nhiên nào nói rõ từng công cụ của site dùng hàm nào.

Random được dùng vào những việc gì?

Random được dùng trong trò chơi, mô phỏng, chia nhóm, kiểm thử phần mềm, bảo mật và bốc thăm, tức là bất cứ đâu cần một lựa chọn mà người làm không tự quyết, hoặc cần thử rất nhiều khả năng. Mỗi việc đòi hỏi một mức chặt khác nhau:

• Trò chơi: tạo sự khác biệt giữa các ván, như xúc xắc ảo, lá bài được chia, vật phẩm rơi theo tỉ lệ. Cách game dùng tỉ lệ và vì sao người chơi hay thấy mình "đen" có trong bài RNG trong game là gì.
• Mô phỏng Monte Carlo: lặp lại một phép tính rất nhiều lần, mỗi lần với một bộ số ngẫu nhiên khác, để ước lượng dải kết quả có thể xảy ra.
• Chia nhóm, chọn mẫu: để người tổ chức không tự quyết ai vào nhóm nào, ai được hỏi trước.
• Kiểm thử phần mềm: sinh dữ liệu thử ngẫu nhiên với seed cố định, để khi gặp lỗi có thể chạy lại đúng chuỗi đó.
• Bảo mật: mật khẩu, khoá mã hoá, mã đăng nhập cần giá trị mà kẻ tấn công không đoán được, nên phải dùng nguồn an toàn mật mã.
• Bốc thăm, quay số: từ việc quay số ngẫu nhiên trong một khoảng cho lớp học tới bốc thăm online có mã niêm phong khi cần người khác kiểm lại được kết quả.

Chuỗi kết quả lặp lại có chứng tỏ không ngẫu nhiên không?

Không. Chuỗi lặp lại hay dồn cụm là chuyện bình thường trong một dãy ngẫu nhiên: mỗi chuỗi cụ thể đều hiếm, nhưng khi tung rất nhiều lần thì gặp vài đoạn lặp là điều dễ xảy ra.

Ví dụ với đồng xu lý tưởng: mỗi lần tung, mặt ngửa có xác suất 1/2 và các lần tung độc lập với nhau. Theo quy tắc nhân cho các biến cố độc lập, xác suất tám lần liền đều ngửa là:

Con số này hiếm, nhưng không phải không thể: nếu rất nhiều người cùng tung tám lần, trung bình cứ khoảng 256 người sẽ có một người ra tám mặt ngửa.

Điều ít người để ý: chuỗi xen kẽ "ngửa, sấp, ngửa, sấp…" tám lần cũng có đúng xác suất 1/256, như mọi chuỗi tám mặt cụ thể khác. Chuỗi trông "đều đặn" không ngẫu nhiên hơn chuỗi toàn ngửa.

Toàn ngửaNNNNNNNN

Xen kẽNSNSNSNS

Và sau tám lần ngửa, lần thứ chín vẫn là 1/2 ngửa, 1/2 sấp: đồng xu không nhớ những lần trước.

Vì vậy chỉ nhìn một chuỗi ngắn thì không kết luận được nguồn ngẫu nhiên tốt hay xấu. Muốn đánh giá phải nhìn rất nhiều kết quả và dùng kiểm định thống kê.

Ngay cả khi đó, NIST lưu ý các bộ kiểm định thống kê giúp phát hiện độ lệch hay quy luật, nhưng không bộ nào tự chứng nhận một bộ sinh là đủ an toàn cho mật mã.

Random có đồng nghĩa với công bằng và an toàn không?

Không. Random không tự động đồng nghĩa với công bằng hay an toàn. Với bốc thăm hay chọn người trước nhiều người, kết quả chỉ được xem là công bằng khi danh sách đầu vào đúng, tỉ lệ rõ ràng với người tham gia và không ai can thiệp được giữa chừng. Còn an toàn hay không tuỳ nguồn ngẫu nhiên có đủ khó đoán cho việc đang làm.

Nên chọn bộ sinh theo mục đích và rủi ro:

Với bốc thăm có giải giá trị, thêm một bước nữa là để người ngoài kiểm lại được, ví dụ khoá kết quả bằng mã niêm phong trước khi bốc.

Nguồn tham khảo

• Cambridge Dictionary — random
• NIST CSRC — Ideal randomness source
• NIST DADS — Pseudorandom number generator
• NIST CSRC — Entropy source
• NIST SP 800-22 Rev. 1a — Statistical test suite for random number generators
• Python — random: Generate pseudo-random numbers
• MDN — Math.random()
• MDN — Crypto.getRandomValues()
• OpenStax Statistics — Two basic rules of probability
• IBM — What is Monte Carlo simulation?