Expected amount of overlap of binary vectors Suppose one has $n$ binary vectors $X_1,\ldots,X_n$ of length $G$, each containing a contiguous series of ones of length $R\ll G$ which have been positioned uniformly at random within the vector, and zeros everywhere else.
Suppose we sum these vectors, $Y=\sum_{i=1}^nX_i$, what is the expected number of entries of $Y$ that are strictly greater than $1$?
After thinking about this problem for a while without making much headway, I considered the following approximation,
$${\bf exercise}(G,n,R)\approx{\bf exercise}(G\;/\;R^2,n,1)$$
Initially, I thought the correct reduction in vector length would be $\frac{G}{R}$, however after testing it empirically, division by $R^2$ appears to be the correct scaling factor.
The solution to ${\bf exercise}(G\;/\;R^2,n,1)$ can be formulated in terms of binomial random variables $B_i$ with probability of success given by $\frac{1}{H}=\frac{R^2}{G}$,
\begin{align}
E\big[\sum_{i=1}^H[B_i>1]\big]=\sum_{i=1}^HE[B_i>1]&=\sum_{i=1}^H\sum_{b_i=0}^n[b_i>1]\binom{n}{b_i}\big(\frac{1}{H}\big)^{b_i}\big(1-\frac{1}{H}\big)^{n-b_i}\\
&=H\Big(1-\sum_{b=0}^1\binom{n}{b}\big(\frac{1}{H}\big)^b\big(1-\frac{1}{H}\big)^{n-b}\Big)\\
&=H\Big(1-\big(1-\frac{1}{H}\big)^n-n\big(\frac{1}{H}\big)\big(1-\frac{1}{H}\big)^{n-1}\Big)
\end{align}
Can anyone provide some rigorous justification for this approximation? Or provide a solution to the original problem?
 A: For each entry, the probability a particular vector contributes to that entry is $R/G$. Therefore, the probability distribution for that entry is $\text{Bin}(n, R/G)$. Using the Poisson approximation to the binomial distribution (which is valid* when $R/G\ll 1$), we find, letting $$\lambda:=nR/G,$$ that
$$
P(\text{entry}>1)\approx P(\text{Poi}(\lambda)>1)=1-e^{-\lambda}(1+\lambda).
$$
Therefore, using linearity of expectation, the expected number of entries greater than $1$ is
$$
E[\text{# entries greater than 1}]=G\cdot P(\text{entry}>1)\approx G[1-e^{-\lambda}(1+\lambda)]
$$
Now, we can justify your approximation. Let us assume that $\lambda$ is small. Since $R\ll G$, we know $R/G$ is small, so further assuming $n\cdot (R/G)$ is small is sometimes reasonable.
When $\lambda$ is small, we have, $e^{-\lambda}\approx 1-\lambda$, so
$$
\begin{align}
E[\text{# entries greater than 1}]
&\approx G[1-e^{-\lambda}(1+\lambda)]\\
&\approx G[1-(1-\lambda)(1+\lambda)]\\
&=G\cdot \lambda^2\\
&= \boxed{n^2G/R^2}
\end{align}
$$
This last formula clearly justifies how the expected number for $(G,n,R)$ is approximately the same for $(G/R^2,n,1)$.

* Here, I am using the following fact. Let $X\sim\text{Bin}(n,p)$ have the binomial distribution, and let $Z\sim \text{Poi}(\lambda)$ be the Poisson variable approximating $X$, where $\lambda =np$. Then for any subset $A$ of nonnegative integers,
$$
|P(X\in A)-P(Z\in A)|\le \min\{p,np^2\}
$$
Therefore, if $p$ is small, then the error in using $Z$ to find probabilities for $X$ is small. I think this fact is not too well known; usually people say that Poisson approximation works as long as "$n$ is large and $p$ is small", but this shows that it is only necessary to have $p$ small. It is easy to prove the above error is at most $np^2$, but improving this to $\min\{p,np^2\}$ requires a sophisticated method known as the Chen-Stein method.
My sources for this claim (that you only need $p$ small) are these lecture notes on Chen-Stein approximation (see example 5.5 for my claim), and [this Wikipedia article on Le Cam's theorem]( Probability Theory: the Coupling Method). The wiki article states a bound that works well when $\lambda$ is large, and cites Probability Theory: The Coupling Method by Frank den Hollander.
