expected number of populated blocks

Question

Let $p$ be a positive integer. For each positive integer $N$, let: $$F: \{1, \ldots , pN\} \rightarrow \{1, \ldots, N\} $$ $$ F(n) = \lceil n/p \rceil$$ Let $r \in [0,1]$. I'm curious about the limit of the expected value $\mathbb E(\#F(A)/N)$ for $A \subseteq \{1, \ldots, pN\}$ a subset of cardinality $\lfloor rpN\rfloor$ selected randomly. I have no background in combinatorics; this question may be below the level of mathoverflow.

Answer 1

The chance each block is hit is (for large $N$) very close to $1-(1-r)^p$: the distribution of $A$ gets extremely close to a subset where each element of $A$ is included with probability $r$.

In the model where each element is included with probability $r$, one way to obtain a random $A$ is to first decide how many elements it will have - it will be a random variable, $Z$ with a binomial distribution with parameters $Np$ and $r$; secondly, given the value of $Z$, one may obtain $A$ by uniformly choosing one of the subsets of $\{1,\ldots,pN\}$ with $Z$ elements.

The relevance of this is that the distribution of $Z$ is centred at $rpN$ with width roughly $\sqrt{r(1-r)pN}$. That is $Z=rpN+O(\sqrt N)$. Hence the $A$ obtained from the process "include each element with probability $r$" is with very high probability "close" to the process you describe in the question (the $A$'s obtained by the two procedures tend to differ by $O(\sqrt N)$ elements). For the new process I have introduced, you have complete independence: $i$ and $j$ are included independently, so that in the new process, by very elementary probability arguments, each block is hit with probability exactly $1-(1-r)^p$ and the expected number of blocks hit is exactly $(1-(1-r)^p)N$.

In the original process, the number of blocks hit is $(1-(1-r)^p)N+O(\sqrt N)$, so the limit you are asking for is $1-(1-r)^p$.

The same issue occurs in random graph theory. Erdös and Renyí introduced the "Erdös-Renyí model", the random graph on $N$ vertices where exactly $r\binom N2$ edges are included. In practice, it is far easier to study the independent version where each edge is included independently with probability $r$ (because independence makes probability much easier). As $N$ gets large, the properties of the two models are essentially identical.