# expected number of populated blocks

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.

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.

• There are notable exceptions to the last paragraph. For example, for constant $r$, Svante Janson proved that the number of hamiltonian cycles is asymptotically normal for the independent-edge model but asymptotically log-normal for the edge-count model. Even the means are different. – Brendan McKay Sep 17 '17 at 8:43
• Interesting comment. I didn't know that there were interesting properties that are sensitive enough to care about adding or deleting $\sqrt n$ edges. – Anthony Quas Sep 17 '17 at 15:49
• I remembered it around the wrong way; it is the edge-count model that gives normality and the independent-edge model that gives log-normality. The paper is at Combinatorics, Probability and Computing (1994), 3, 97-126. – Brendan McKay Sep 18 '17 at 0:06