Xác suất một nửa từ đồng xu không cân đối
probability
1
algorithm
37
White

Nhat Bui viết ngày 10/05/2021

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:
$$
\mbox{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? Liệu có hay không việc ông viết bài bị ngáo?

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 $ \mbox{Pr[head]} > 0$ và $\mbox{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 giống 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ự.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Nhat Bui

2 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
3 2
Bài viết lấy cảm hứng từ bài viết (Link) của anh (Link) và mình cũng muốn note lại tí kiến thức đã học. Dùng Python và nhập dòng dưới đây 0.1 3...
Nhat Bui viết hơn 2 năm trước
3 2
Bài viết liên quan
White
51 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết hơn 3 năm trước
51 7
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
2 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!