# Bộ sinh số giả ngẫu nhiên LCG (Linear Congruential Generator)
## 1. Giới thiệu
Khi làm việc với các mô phỏng máy tính hoặc học máy, bạn sẽ thấy mình sử dụng các hàm như `numpy.random.rand()` hay `np.random.default_rng()` rất thường xuyên. Nhưng đã bao giờ bạn tự hỏi: làm thế nào một cỗ máy cứng nhắc, luôn thực hiện các lệnh một cách xác định và không có chút "sáng tạo" nào, lại có thể tạo ra được những con số mang tính "ngẫu nhiên"?
Sự thật là, máy tính (về cơ bản) không thể tạo ra những con số hoàn toàn ngẫu nhiên. Thay vào đó, chúng tạo ra các **số giả ngẫu nhiên** (pseudo-random numbers). Từ "giả" ở đây mang nghĩa là các con số này được sinh ra từ một thuật toán hoàn toàn xác định (deterministic), nhưng chuỗi số tạo ra có các tính chất thống kê trông *giống hệt* như ngẫu nhiên.
Tại sao chúng ta lại cần tính xác định này? Tính xác định cho phép chúng ta tái tạo lại (reproduce) chính xác kết quả mô phỏng khi cần thiết, bằng cách sử dụng chung một giá trị khởi tạo.
Thuật toán sinh số giả ngẫu nhiên là trái tim của các phương pháp như [Mô phỏng Monte Carlo](/posts/math/stats/monte-carlo-simulation/). Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán kinh điển và cơ bản nhất: **Linear Congruential Generator (LCG)** (tạm dịch: *Bộ sinh đồng dư tuyến tính*). LCG chính là "Hello World" của thế giới số ngẫu nhiên.
LCG chỉ là một nhánh nhỏ trong [bản đồ tổng quan về sinh số ngẫu nhiên](/posts/math/stats/random-number-generation-overview/), bên cạnh PCG, xoshiro, Mersenne Twister, các bộ sinh dựa trên counter và CSPRNG.
## 2. Công thức LCG
Khởi điểm của LCG là một hệ thức truy hồi (recurrence relation) cực kỳ đơn giản: giá trị ngẫu nhiên tiếp theo được tính toán trực tiếp từ giá trị hiện tại.
Cụ thể, chuỗi số nguyên $X_n$ được sinh ra theo công thức:
$$X_{n+1} = (a \cdot X_n + c) \mod m$$
Trong đó, các tham số có vai trò cố định:
- $m$ (modulus): **Mô-đun** hay số chia, $m > 0$. Đây là giới hạn trên của các số nguyên có thể được tạo ra.
- $a$ (multiplier): **Hệ số nhân**, $0 < a < m$.
- $c$ (increment): **Hệ số cộng** (hay độ dời), $0 \le c < m$.
- $X_0$ (seed): **Hạt giống** khởi tạo, $0 \le X_0 < m$.
Bằng cách lặp lại công thức trên, chúng ta sẽ thu được một chuỗi các số nguyên nằm trong khoảng từ $0$ đến $m - 1$.
Tuy nhiên, trong thực tế, chúng ta thường cần những số ngẫu nhiên phân phối đều đặn trong khoảng từ $0$ đến $1$, ký hiệu là $Uniform(0, 1)$. Để làm điều này, ta chỉ cần chia số $X_n$ vừa sinh cho mô-đun $m$:
$$U_n = \frac{X_n}{m}$$
Giá trị $U_n$ luôn thoả mãn $0 \le U_n < 1$. Nếu chọn các tham số khéo léo, chuỗi $U_n$ sẽ "trông có vẻ" như được rút ra một cách độc lập từ phân phối $Uniform(0, 1)$.
## 3. Ví dụ cụ thể bằng tay
Hãy cùng theo dõi quá trình sinh số qua một ví dụ cụ thể với các con số nhỏ để dễ hình dung. Giả sử ta thiết lập các thông số như sau:
- Mô-đun $m = 16$
- Hệ số nhân $a = 5$
- Hệ số cộng $c = 3$
- Hạt giống khởi tạo $X_0 = 7$
Ta sẽ sinh ra các giá trị tiếp theo:
1. **Bước 1**:
$$X_1 = (5 \cdot 7 + 3) \mod 16 = 38 \mod 16 = 6$$
$\implies U_1 = 6 / 16 = 0.375$
2. **Bước 2**:
$$X_2 = (5 \cdot 6 + 3) \mod 16 = 33 \mod 16 = 1$$
$\implies U_2 = 1 / 16 = 0.0625$
3. **Bước 3**:
$$X_3 = (5 \cdot 1 + 3) \mod 16 = 8 \mod 16 = 8$$
$\implies U_3 = 8 / 16 = 0.5$
4. **Bước 4**:
$$X_4 = (5 \cdot 8 + 3) \mod 16 = 43 \mod 16 = 11$$
$\implies U_4 = 11 / 16 = 0.6875$
5. **Bước 5**:
$$X_5 = (5 \cdot 11 + 3) \mod 16 = 58 \mod 16 = 10$$
$\implies U_5 = 10 / 16 = 0.625$
Tiếp tục tính toán, ta sẽ được chuỗi $X_n$ là:
$7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1, \dots$
Bạn có nhận thấy điều gì ở chuỗi trên không? Ở lần sinh thứ 17, ta lại thu được con số $7$ (chính là $X_0$), sau đó đến $6, 1, 8, \dots$ Nghĩa là chuỗi số đã bắt đầu lặp lại!
Hiện tượng này được gọi là **tính tuần hoàn** (periodicity). Trong ví dụ này, chuỗi sinh ra 16 số khác nhau trước khi lặp lại, hay nói cách khác, chu kỳ của bộ sinh này là 16 (chính bằng $m$).
## 4. Tính chất quan trọng
Từ công thức và ví dụ trên, chúng ta rút ra được các tính chất then chốt của một bộ LCG:
- **Khả năng tái tạo qua hạt giống (Reproducibility via seed)**: Vì công thức mang tính xác định hoàn toàn, nếu ta đưa cho nó cùng một $X_0$ (seed), nó sẽ luôn sinh ra cùng một chuỗi số y hệt nhau. Đây là một "tính năng" cực kỳ hữu ích cho việc debug chương trình.
- **Tính chu kỳ (Period)**: Do mô-đun là $m$, nên $X_n$ chỉ có thể nhận nhiều nhất $m$ giá trị khác nhau. Do đó, chuỗi chắc chắn sẽ lặp lại với một **chu kỳ** không vượt quá $m$. Một bộ sinh tốt cần có chu kỳ tối đa (bằng $m$). Định lý Hull-Dobell đã chỉ ra các điều kiện chính xác về số học giữa $a, c, m$ để LCG đạt được chu kỳ lớn nhất.
- **Cấu trúc mạng lưới (Lattice structure)**: Đây là một điểm yếu chí mạng của LCG. Trong bài báo [*Random Numbers Fall Mainly in the Planes*](https://pmc.ncbi.nlm.nih.gov/articles/PMC285899/) năm 1968, George Marsaglia chỉ ra rằng: nếu ta gộp các số sinh ra từ LCG thành từng bộ $k$ số liên tiếp để tạo thành tọa độ của các điểm trong không gian $k$-chiều, các điểm này sẽ không rải đều một cách ngẫu nhiên mà sẽ nằm trên những siêu mặt phẳng (hyperplanes) song song.
Trong hai chiều, “siêu mặt phẳng” chỉ là các đường thẳng. Biểu đồ sau dùng một LCG cố ý nhỏ, với $m=256$, $a=5$ và $c=1$, để các đường này hiện rõ bằng mắt:
Minh hoạ tương tác
Các cặp liên tiếp của LCG không lấp đầy mặt phẳng
So sánh các cặp $(U_n,U_{n+1})$ của LCG với cùng số cặp giả ngẫu nhiên dùng làm tham chiếu.
LCG: $m=256,\ a=5,\ c=1$
Mẫu giả ngẫu nhiên tham chiếu
Vì $U_n=X_n/m$, hệ thức truy hồi của bộ sinh trên trở thành
$$
U_{n+1}=5U_n+\frac{1}{256}\pmod 1.
$$
Phép “modulo 1” cắt đường thẳng có hệ số góc $5$ thành đúng năm đoạn song song trong hình vuông đơn vị. Tăng số điểm chỉ làm năm đoạn ấy dày đặc hơn; nó không lấp các khoảng trống ở giữa. Biểu đồ cố ý dùng mô-đun nhỏ để phóng đại hiện tượng. Với LCG 32 hoặc 64 bit được chọn tham số tốt, các mặt phẳng có thể nhiều và khó nhận ra bằng mắt hơn; **spectral test** đo khoảng cách giữa chúng.
## 5. Minh hoạ bằng Python
Hãy cùng viết một đoạn mã Python để hiện thực hoá khái niệm này và xem trực quan điểm yếu cấu trúc mạng lưới.
```python
import numpy as np
import matplotlib.pyplot as plt
class LCG:
def __init__(self, m, a, c, seed):
self.m = m
self.a = a
self.c = c
self.state = seed
def next(self):
# Tính giá trị tiếp theo theo hệ thức truy hồi
self.state = (self.a * self.state + self.c) % self.m
# Trả về giá trị nằm trong [0, 1)
return self.state / self.m
# Khởi tạo bộ sinh nhỏ để dễ thấy năm đường song song
m = 256
a = 5
c = 1
seed = 1
rng = LCG(m, a, c, seed)
# Sinh trọn một chu kỳ, cộng thêm điểm đầu chu kỳ kế tiếp
random_numbers = [rng.next() for _ in range(m + 1)]
# Plot 1: Histogram kiểm tra tính phân phối đều
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.hist(random_numbers[:-1], bins=16, edgecolor='black', alpha=0.7)
plt.title("Phân phối của một chu kỳ LCG")
plt.xlabel("Giá trị U_n")
plt.ylabel("Tần suất")
# Plot 2: Cấu trúc mạng lưới khi xét từng cặp số (U_n, U_{n+1})
u_n = random_numbers[:-1]
u_next = random_numbers[1:]
plt.subplot(1, 2, 2)
plt.scatter(u_n, u_next, s=10, alpha=0.5, color='red')
plt.title("Cấu trúc mạng lưới (Lattice Structure)")
plt.xlabel("U_n")
plt.ylabel("U_{n+1}")
plt.tight_layout()
plt.show()
```
Khi chạy đoạn mã trên, Histogram của một chu kỳ trông hoàn hảo: vì bộ sinh đi qua đủ 256 trạng thái, mỗi bin có cùng số quan sát. Nhưng Scatter của các cặp $(U_n,U_{n+1})$ chỉ tạo thành năm đường chéo song song. Đây là điều Histogram một chiều không thể phát hiện: từng tọa độ riêng lẻ có thể phân bố đều, trong khi quan hệ giữa các tọa độ vẫn để lại những khoảng trống có hệ thống. Nếu tích phân cần lấy mẫu đúng vào các khoảng trống ấy, ước lượng Monte Carlo có thể bị sai lệch.
## 6. Từ LCG đến các bộ sinh hiện đại
Vì LCG có chu kỳ hữu hạn (phụ thuộc vào $m$, mà trong máy tính 32-bit thì thường $m \approx 2^{32} \approx 4 \times 10^9$) và để lộ cấu trúc mạng lưới, nó hiếm khi được dùng một mình cho các mô phỏng quan trọng ngày nay. Lịch sử các bộ sinh hiện đại có thể được đọc như một chuỗi câu hỏi thiết kế ngày càng khắt khe:
LCG
↓thêm trạng thái lớn
Mersenne Twister
↓thêm phép trộn đầu ra
PCG / xoshiro
↓thiết kế cho tính toán song song
Philox / Threefry
↓yêu cầu bất khả dự đoán
ChaCha / AES / HMAC-based CSPRNG
Sơ đồ này là **bản đồ của các áp lực thiết kế**, không phải một cây phả hệ tuyến tính: PCG và xoshiro là hai họ độc lập; Philox và Threefry cũng không phải “phiên bản kế tiếp” của chúng. Mỗi tầng nhấn mạnh một vấn đề mà tầng trước chưa giải quyết trọn vẹn:
- **LCG — trạng thái nhỏ, công thức tối giản:** Trạng thái chỉ là $X_n$. Ưu điểm là nhanh và dễ tái lập; nhược điểm là chu kỳ bị giới hạn bởi $m$ và các điểm nhiều chiều lộ cấu trúc mạng.
- **Mersenne Twister — trạng thái và chu kỳ rất lớn:** MT19937 mang trạng thái nội bộ cỡ 20.000 bit và có chu kỳ $2^{19937}-1$. Nó từng là lựa chọn mặc định của NumPy cũ và hiện vẫn là lõi của mô-đun [`random` trong Python](https://docs.python.org/3/library/random.html), nhưng trạng thái lớn không đồng nghĩa với an toàn mật mã hoặc thuận tiện cho hàng nghìn luồng song song.
- **[PCG](/posts/math/stats/pcg-to-pcg64dxsm/) và xoshiro — chú trọng phép biến đổi đầu ra:** PCG ghép một bước chuyển trạng thái kiểu đồng dư với một hàm hoán vị đầu ra; các biến thể xoshiro dùng trạng thái dựa trên XOR/shift/rotate rồi áp dụng một *scrambler* như `+`, `++` hoặc `**` lên đầu ra. Nhờ vậy, chất lượng bit đầu ra không còn phản ánh trực tiếp toàn bộ cấu trúc đơn giản của bước chuyển trạng thái. `np.random.default_rng()` hiện dùng PCG64 theo [tài liệu NumPy](https://numpy.org/doc/stable/reference/random/).
- **Philox và Threefry — truy cập theo bộ đếm:** Thay vì phải đi tuần tự từ trạng thái $n$ tới $n+1$, bộ sinh dựa trên bộ đếm tính trực tiếp đầu ra từ cặp `(counter, key)`. Có thể chia không gian counter hoặc key cho CPU, GPU và các worker mà không cần một trạng thái chung; đây là động cơ của thư viện [Random123](https://random123.com/).
- **CSPRNG — thêm mô hình đối thủ:** Với token đăng nhập, khoá mật mã hoặc nonce, “vượt qua kiểm định thống kê” vẫn chưa đủ. Ta còn cần kẻ quan sát nhiều đầu ra không thể suy ra trạng thái hay dự đoán đầu ra kế tiếp. Các thiết kế dựa trên ChaCha, AES-CTR hoặc HMAC-DRBG phục vụ mục tiêu này; trong Python nên dùng [`secrets`](https://docs.python.org/3/library/secrets.html) thay vì `random` cho dữ liệu nhạy cảm.
Vì vậy, không có một bộ sinh “tốt nhất” cho mọi tình huống. LCG phù hợp để học công thức và tính tuần hoàn; PCG/xoshiro phù hợp cho mô phỏng thông thường; Philox/Threefry đặc biệt tự nhiên trong tính toán song song; còn CSPRNG là lựa chọn bắt buộc khi đầu ra liên quan đến an toàn.
## 7. Tổng kết
Việc tạo ra sự ngẫu nhiên từ một hệ thống xác định luôn là một nghệ thuật tuyệt đẹp trong khoa học máy tính. LCG đóng vai trò như một bài toán vỡ lòng cho bất cứ ai bước chân vào thế giới của mô phỏng ngẫu nhiên. Mặc dù bộ sinh LCG nguyên bản chứa đựng những nhược điểm khiến nó không phù hợp cho các mô phỏng tính toán cường độ cao, nhưng cái hồn của nó — ý tưởng dùng sự lặp lại của các phép toán số học mô-đun kết hợp cùng hạt giống (seed) — vẫn đang tồn tại trong hầu hết mọi thư viện sinh số ngẫu nhiên hiện tại.
Hiểu về LCG giúp bạn hình dung được "bộ máy" đang vận hành dưới nắp ca-pô mỗi khi bạn gọi một hàm ngẫu nhiên trong Python.
---
*Xem thêm: [Mô phỏng Monte Carlo](/posts/math/stats/monte-carlo-simulation/)*