More about Chernoff

Chặn Chernoff (Chernoff bound) quả thật là rất hữu dụng trong phương pháp xác suất và các giải thuật ngẫu nhiên hóa. Tôi có một lecture note   tóm tắt vài chặn đơn giản dùng trong phương pháp xác suất, các bạn có thể tìm hiểu thêm.

Tình cờ cách đây vài hôm, đang viết một bài báo về routing trong ad hoc networks thì lòi ra bài toán sau: cho trước một đồ thị G  với degree lớn nhất là d, mỗi cạnh của G tồn tại với xác suất p, tính xác suất xem G liên thông (connected) là bao nhiêu. Tôi hỏi anh Văn thì hóa ra hàm xác suất này có tính concentration rất cao (xem bài báo này của anh Văn và vài đồng nghiệp).