What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements?

Question

Let $F$ denote a function that returns the first $800$ bits of the input.

Let $G(N)$ denote a function that returns the last $800$ bits of the binary encoding of the given number $N$. For example,

$$\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}$$

etc (we are only interested in the interval $0 \le N \lt {2^{800}}$ ).

Let $P$ denote Keccak permutation function that operates on $1600$-bit blocks.

Choose (arbitrarily or randomly) any 800-bit sequence. Denote it by $S$.

Consider the following collection (set) of bitsequences:

$$\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}$$

(it contains $2^{800}$ elements, and each element is a $800$-bit sequence).

Let $Y$ denote the number of different (unique) elements in $C$.

Question: what is the expected value of $Y$? And why?

Edit: I have read Expected number of different birthdays, and found the following formula:

$$\begin{array}{l}\\& D = 2^{1600},\\& n = 2^{800},\\& \varphi = (D-1)/D,\\& Y = D\times (1-\varphi^n) \end{array}$$

Is this the correct formula for $Y$?

Answer 1

Every input $G(i) \mathbin\| S$ to $P$ is distinct. If $P$ were a uniform random permutation, the random function $x \mapsto F(P(x))$ would have almost uniform distribution. So the answer can't be much different from the number of distinct 800-bit strings in an independent uniform random sampling of $2^{800}$ of them, which is a fraction of $$1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1}$$ of them by the usual reason. The fact that $S$ is chosen independently at random is not relevant to this analysis; the same analysis would apply if $S = 0$.