0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Sep 17 '17 at 8:43
  • $\begingroup$ Interesting comment. I didn't know that there were interesting properties that are sensitive enough to care about adding or deleting $\sqrt n$ edges. $\endgroup$ – Anthony Quas Sep 17 '17 at 15:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Sep 18 '17 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.