集合中包含的不同位序列的預期數量是多少280028002^{800}元素？
讓 $ F $ 表示返回第一個函式的函式 $ 800 $ 位的輸入。
讓 $ G(N) $ 表示返回最後一個函式 $ 800 $ 給定數字的二進制編碼位 $ N $ . 例如，
$$ \begin{array}{l} G(0) = 00\underbrace \ldots _{{\rm{796;zeroes}}}00,\ G(1) = 00\underbrace \ldots _{{\rm{796;zeroes}}}01,\ G({2^{800}} - 2) = 11\underbrace \ldots _{{\rm{796;ones}}}10,\ G({2^{800}} - 1) = 11\underbrace \ldots _{{\rm{796;ones}}}11 \end{array} $$ 等（我們只對區間感興趣 $ 0 \le N \lt {2^{800}} $ ).
讓 $ P $ 表示 Keccak 置換函式 $ 1600 $ 位塊。
選擇（任意或隨機）任何 800 位序列。表示為 $ S $ .
考慮以下位序列集合（集合）：
$$ \begin{array}{l} {C} = { &F(P(G(0)|| S)),\&F (P(G(1) || S)),\&F(P(G(2) || S)),\&\ldots ,\&F(P(G({2^{800}} - 2) || S)),\&F(P(G({2^{800}} - 1) || S));;} \end{array} $$ （它包含 $ 2^{800} $ 元素，每個元素都是一個 $ 800 $ 位序列）。
讓 $ Y $ 表示**不同（唯一）**元素的數量 $ C $ .
問：期望值是多少 $ Y $ ? 為什麼？
編輯：我已閱讀Expected number of different birthdays，並找到以下公式：
$$ \begin{array}{l}\& D = 2^{1600},\& n = 2^{800},\& \varphi = (D-1)/D,\& Y = D\times (1-\varphi^n) \end{array} $$ 這是正確的公式嗎 $ Y $ ?
每一個輸入 $ G(i) \mathbin| S $ 至 $ P $ 是不同的。如果 $ P $ 是均勻隨機排列，隨機函式 $ x \mapsto F(P(x)) $ 會有幾乎均勻的分佈。因此，答案與 $ 2^{800} $ 其中，這是一小部分$$ 1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1} $$出於通常的原因。事實是 $ S $ 隨機獨立選擇與此分析無關；如果 $ S = 0 $ .