Trong bài này, chúng ta tìm hiểu nguyên lí deferred decision (mình để nguyên tiếng anh vì không biết dịch tiếng Việt thế nào cho hay và chuẩn) trong phân tích thuật toán ngẫu nhiên. Nguyên lí này được áp dụng khá phổ biến và là phương pháp chứng minh đằng sau của các kết quả đẹp như Isolation Lemma. Nguyên lí này có thể được hiểu tốt nhất thông qua ví dụ sau:

 
Một cách đơn giản là ta tính và so sánh với . Phương pháp này mất thời gian nếu ta sử dụng phép nhân ma trận như định nghĩa hoặc sử dụng phương pháp nhân ma trận nhanh nhất hiện tại (xem tại wikipedia). Tất cả đều hoặc rất chậm hoặc rất phức tạp. Sử dụng ngẫu nhiên, ta có thể kiểm tra tích có bằng hay không chỉ trong thời gian với xác suất cao.

Giải thuật: Chọn vector , có phần tử, và mỗi phần tử là một bít chọn ngẫu nhiên. So sánh với . Nếu hai số này bằng nhau, output Yes; ngược lại, output No. Ta có thể tính trong thời gian , do đó, thuật toán có thời gian .

 
Chứng minh: Nếu thì thuật toán luôn output Yes. Do đó, thuật toán chỉ sai khi mà ta lại chọn phải vector với . Đặt là một ma trận . Do , luôn tồn tại một ô khác 0 của ma trận . Không giảm tính tổng quát, ta giả sử . Gọi . Ta có:

Do , ta suy ra . Từ , ta suy ra:

Do các bít của được chọn ngẫu nhiên độc lập, ta coi như được chọn sau cùng. Do đó, về phải của coi như đã xác định trước khi ta chọn . Vậy, xác suất chọn phải bằng vế phải của là không quá .

Remarks: Nếu ta chọn mỗi phần tử của là một số nguyên 32 bít, bằng cách mở rộng chứng minh ở trên, xác suất thuật toán sai sẽ không quá , một con số khá nhỏ.

Nguyên lí deferred decision thể hiện trong ví dụ trên ở chỗ, phép phân tích chỉ nhìn vào phần tử được chọn cuối cùng của vector ngẫu nhiên.