Một đồng xu gồm hai mặt: head và tail. Khi gieo một đồng xu, chúng ta chỉ thấy được một trong hai mặt ngửa lên, hoặc là head, hoặc là tail (giả sử đồng xu rơi xuống sẽ nằm chứ không đứng :Đ). Vì có hai khả năng trên xảy ra nên không gian mẫu của chúng ta là $\Omega$ = {head, tail}.

Đồng xu cân đối, theo định nghĩa cổ điển của xác suất, là đồng xu khi gieo có xác suất (ngửa) mặt head và tail bằng nhau:

$\Pr[head] = \Pr[tail] = \frac{1}{|\Omega|} = \frac{1}{2}.$

Nếu đồng xu không cân đối thì sao? Liệu có cách nào để gieo với xác suất một nửa mỗi mặt như đồng xu cân đối không?

Thuật toán đơn giản

Dĩ nhiên, ta giả sử rằng cả hai mặt đều có khả năng xuất hiện, tức $\Pr[head] > 0$ và $\Pr[tail] > 0$. Vì xác suất một trong hai bằng zero thì chỉ việc ngồi phán chứ tính toán chi cho hói trán.

John von Neumann có nghĩ ra một cách thế này: gieo đồng xu không cân đối hai lần; nếu kết quả hai lần gieo khác nhau thì lấy kết quả lần một, nếu khác nhau thì bỏ qua hai kết quả này và gieo lại từ đầu. Thuật toán viết bằng Python như sau:

def neumann_flip():
	x = weird_flip()
    y = weird_flip()
    if x != y:
        return x
    else:
        return neumann_flip()

Ta có hai quan sát nhỏ:

• Cụ Neumann cóc quan tâm đồng xu lệch cỡ nào.
• Thuật toán về căn bản có thể chạy mãi mãi, vì không tồn tại big-Oh cho trường hợp xấu nhất.

Đơn giản! Nhưng đơn giản không có nghĩa là dễ.

Practice

Để “thí nghiệm” thuật toán trên, ta cần định nghĩa hàm weird_flip():

from random import randint

def weird_flip():
    x = randint(1, 3)
    if x % 2 == 0:
        return 0
    else:
        return 1

• Giá trị 0 được trả về nếu random ra số chẵn, kí hiệu cho mặt head
• Giá trị 1 được trả về nếu random ra số lẻ, kí hiệu cho mặt tail.
• Chúng ta random trong đoạn $[1, 3]$ nên xác suất random số lẻ là $2/3$, điều này tạo ra đồng xu không cân đối.

Ta thí nghiệm weird_flip() với 1000 lần gieo:

trials = 1000
flipping = [weird_flip() for i in range(trials)]
# Tổng của flipping chính là số lần gieo được số lẻ
print(sum(flipping) / trials)

0.674

Kết quả xấp xỉ $2/3$ như dự định. Thay weird_flip() bằng neumann_flip():

0.507

Xấp xỉ $1/2$, cũng như dự định, nhưng là dự định xác suất của đồng xu cân đối :Đ. Magic!

Cần một lời giải thích

Tôi không rõ cụ Neuman đã chứng minh thuật toán ra sao. Nhưng có ra sao đi nữa thì chúng ta vẫn cần đọc lại lý thuyết về xác suất :Đ.

Một ít lý thuyết xác suất

• Tổng: $\sum_{i = 1}^{|\Omega|} \Pr[A_i] = 1 \quad \forall A_i \in \Omega$.

• Độc lập: Hai biến cố $A$ và $B$ độc lập khi và chỉ khi $\Pr[A \wedge B] = \Pr[A] \cdot \Pr[B]$.

• Xác suất điều kiện: Xác suất xảy ra $ A $ khi $ B $ đã xảy ra là

$\Pr[A \ | \ B] = \frac{\Pr[A \wedge B]}{\Pr[B]}.$

Chứng minh

Gọi xác suất gieo mặt head là $p$, xác suất gieo mặt tail là $q = 1 - p$. (Lưu ý rằng ta đã giả sử rằng cả hai mặt đều có khả năng xuất hiện ở phần trước, do đó $pq \neq 0 $.)

Xét hàm neumann_flip(), hai lần gieo độc lập với nhau, ta có:

$\Pr[x=0 \wedge y=1] = \Pr[x=1 \wedge y=0] = pq.$

Từ phương trình trên dễ nhận thấy

$\Pr[x \neq y] = \Pr[x=0 \wedge y=1] + \Pr[x=1 \wedge y=0] = 2pq.$

Rõ ràng khi gieo được $x = 0$ và $y = 1$ hay ngược lại, thì kéo theo $x$ hiển nhiên khác $y$. Do đó:

$\Pr[x=0 \wedge y=1 \wedge x \neq y] = \Pr[x=1 \wedge y=0 \wedge x \neq y] = pq.$

Sử dụng công thức xác suất điều kiện với $x = 0$ và $y = 1$:

$\Pr[x=0 \wedge y=1 \ | \ x \neq y] = \frac{\Pr[x=0 \wedge y=1 \wedge x \neq y]}{\Pr[x \neq y]} = \frac{pq}{2pq} = \frac{1}{2}.$

$\Pr[x=1 \wedge y=0 \ | \ x \neq y]$ cũng nhận được kết quả $1/2$.

Giá trị hàm trả về, $x$ (hoặc $y$ nếu ta muốn), được phân phối đồng bộ. Vì các lần gieo độc lập với nhau nên đệ quy cũng tương tự.