Random() có thực sự ngẫu nhiên ?

Không, trên đời chẳng có gì là ngẫu nhiên cả!

Tất cả đều là những quy luật được ẩn giấu, chỉ là chúng ta có phát hiện hay hiểu được nó hay không mà thôi; bởi đôi khi nó đơn giản, đôi khi phức tạp, thậm chí siêu phức tạp.

Random() cũng vậy. Bản thân máy tính do con người tạo ra, nên những quy tắc hoạt động của nó đều dựa trên những gì mà con người thiết kế. Tuỳ vào các hệ thống khác nhau mà random sẽ được thiết kế với các thuật toán khác nhau, nhưng ít nhất cần đảm bảo được các tiêu chí sau:

1. Tính ngẫu nhiên của kết quả tạo ra
2. Tính bảo mật của thuật toán

Quá trình sinh ra random trong máy tính được gọi là Pseudo Random Number Generation (PRNG).

1. PRNG Concept

Ta sẽ có 3 khái niệm chung trong PRNG:

• Seed: giá trị khởi tạo của PRNG.
• Internal State: trạng thái của PRNG, lưu trữ các biến số để có thể dự đoán được giá trị và trạng thái tiếp theo của PRNG.
• Period: chu kỳ của random, random sẽ lặp lại mỗi khi chu kỳ kết thúc.

2. Random Distribution Types

Tuỳ vào mục đích sử dụng, Random() trong các ngôn ngữ lập trình sẽ sinh ra các số ngẫu nhiên theo các phân phối khác nhau.

Thông thường nhất là phân phối đều (Uniform Distribution) với xác suất xuất hiện các số là gần như nhau hoặc phân phối chuẩn (Normal Distribution) để sinh ra các giá trị xung quanh một giá trị nào đó. Đó, rõ ràng Random() không phải là dùng tuỳ tiện được mà phải phụ thuộc vào việc vào chúng ta muốn dữ liệu như thế nào nữa.

3. PRNG Algorithms

Có rất nhiều thuật toán trong PRNG, các bạn có thể tham khảo thêm tại đây Trong bài này mình sẽ giới thiệu qua 3 thuật toán được sử dụng trong các ngôn ngữ lập trình.

3.1. Linear Congruential Generator (LCG)

Đây là thuật toán sinh ngẫu nhiên cổ điển nhất và phổ biến nhất được sử dụng trong PRNG. LCG là thuật toán built-in trong Pascal, C/C++, Java và C#.

LCG rất đơn giản, rất trực quan và dễ hiểu, sử dụng chỉ một hàm:

$$X_{n+1}=(a{X}_n+c)modm$$

Trong đó:

• $m,0<m$: Mô đun, thường sẽ là một số đủ lớn, ví dụ $2^{32},2^{31}-1,2^{48},2^{64}$
• $a,0<a<m$: Hằng số nhân mutiplier
• $c,0\le c<m$: Hằng số cộng thêm increment
• $X_0,0\le X_0<m$: seed, giá trị khởi tạo

Chu kỳ của LCG lớn nhất là m, và để LCG sinh ra tất cả các giá trị trong chu kỳ với mọi giá trị khởi tạo (full-period) thì sẽ cần những điều kiện ràng buộc như sau (các bạn hãy thử tự chứng minh bằng toán học xem sao