Có bao nhiêu từ $k$-bit của một chuỗi bit ngẫu nhiên mà chúng tôi dự kiến ​​sẽ trích xuất trước khi tất cả $2^k$ từ có thể xảy ra?

Để cho $C(X)$ biểu thị lực lượng của tập hợp $X$. Ví dụ, $C(\{0\}) = 1, C(\{0, 2\}) = 2$ vân vân.

Để cho $S$ biểu thị một chuỗi (có khả năng vô hạn) các bit ngẫu nhiên. Tách ra $S$ vào trong $k$-bit từ $w_1, w_2, w_3, \ldots$ Ví dụ, nếu $k = 4$ và $S = 0001111010100100\ldots$, sau đó $w_1 = 0001, w_2 = 1110, w_3 = 1010, \ldots$

Ở mỗi bước $i$ (đây $i \geq 1$), hãy thực hiện các bước phụ sau:

1. Trích xuất $w_i$ và chuyển sang bước phụ 2;
2. Nếu $C(X) < 2^k$ và $X$ chứa $w_i$, không làm bất cứ điều gì và đi đến bước $(i+1)$; nếu $C(X) < 2^k$ và $X$ không chứa $w_i$, đặt $w_i$ Trong $X$ và chuyển sang bước phụ 3;
3. Nếu $C(X) < 2^k$, đi đến bước $(i+1)$; nếu $C(X) = 2^k$, dừng lại.

Câu hỏi: giá trị kỳ vọng của $i$ khi thuật toán trên tạm dừng? Nói cách khác, nếu $S$ là nguồn của các bit giả ngẫu nhiên thực sự hoặc không thiên vị, chúng ta nên trích xuất bao nhiêu từ để lấp đầy $X$ với tất cả những gì có thể $k$phần tử -bit?