# Expected number of non-empty regions

Consider $d$ dimensional space cut by $n$ hyperplanes in general position, each one of which goes through the origin. The number of distinct regions created is known to be:

$$2\sum_{i=0}^{d-1} {n -1 \choose i}.$$

Let us assume the hyperplanes are created uniformly at random. Now we sample $k$ points uniformly at random on the surface of the unit sphere centred at the origin. How many distinct regions, on average will have at least one point in it?

• You need to multiply your formula by $2,$ unless you want to identify antipodal regions. That might be a good start. Then for $d=2$ the question would be: $n-1$ points are chosen at random in $[0,1]$ dividing it into $n$ pieces. Then k more random points are chosen. How any sub-intervals will have at least one point. (the first point can be considered to split the circle into an interval.) For $n=2$ I get both regions with probability $\frac{k-1}{k+1}$ so on average $\frac{2k}{k+1}.$ – Aaron Meyerowitz Oct 3 '14 at 10:11
• @AaronMeyerowitz Thank you. The missing $2$ was a typo. – Lembik Oct 3 '14 at 10:28
• If we think of the hyperplanes as the normals to uniform random $v_i$, we can associate to each region a sign sequence based on whether the inner product $\langle v_i, x\rangle$ is positive or negative for each $i$. By symmetry, we can then write the expectation as $2^n$ times the probability that at least one of our $k$ points has positive inner product with all $n$ of the $v_i$. So really it seems to come down to the distribution of the volume of the cone $$\{x | \langle x, v_i \rangle \geq 0 \, \forall \, i\}$$ for $n$ randomly chosen $v_i$. – Kevin P. Costello Oct 8 '14 at 20:58

Here are the first two cases (both with $d=2$). I mention them and the (fairly simple) method in the hope that some more subtle analysis will yield more results. I don't know if one must derive the distribution of region sizes but, if so, that is non-trivial in itself even when $d=2.$

For $d=2$ and $n=1,$ the unit circle is split in two equal halves. The probability that all $k$ points are in the same half (as the first one) is $\frac{1}{2^{k-1}}.$ So the expected number is $$2-\frac{1}{2^{k-1}}.$$

For $d=2$ and $n=2,$ I get an expected number of $$4-\frac{8}{k+1}+\frac{4}{2^k(k+1)}=4\left(1-\frac{1}{2^{k+1}}\right)\left(1-\frac{2}{k+1}\right)-\frac{1}{2^{k-1}} .$$

I'm not sure what the near factorization adds, but there it is.

Analysis: Note: I did this first ,but was reassured when a simulation with $100000$ trials and $k=6$ gave close to the predicted values. The circle is split into four pieces of (relative) sizes $\alpha,\frac{1}{2}-\alpha,\alpha,\frac{1}{2}-\alpha$ with $\alpha$ uniformly distributed in $[0,\frac{1}{4}]$ So the probability that $k$ points all land in the same piece is $$p_1=\int_0^{1/4}\alpha^k+ (\frac{1}{2}-\alpha)^k+\alpha^k+(\frac{1}{2}-\alpha)^kd\alpha=\frac{4}{(k+1)2^k}.$$

There are six ways to pick two regions: four of combined size $\frac{1}{2}$ and one each of sizes $2\alpha$ and $1-2\alpha.$ Accordingly, the probability that all $k$ points land in exactly two regions is

$$p_2=\int_0^{1/4}(2\alpha)^k+ 4(\frac{1}{2})^k+(1-2\alpha)^kd\alpha-3p_1=\frac{2}{k+1}+\frac{4}{2^k}-\frac{12}{(k+1)2^k}.$$ The subtraction is to compensate for the fact that an event that all the points actually land in one region gets counted $3$ times by the integral as being in the union of two regions. There are only two possible sizes for the combined length of $3$ regions leading to $$p_3=\int_0^{1/4}2(\frac{1}{2}+\alpha)^k+2(1-\alpha)^k d\alpha-2p_2-3p_1=\frac{4}{k+1}-\frac{8}{2^k}+\frac{8}{(k+1)2^k}$$ and $$p_4=1-p_1-p_2-p_3=1-\frac{6}{k+1}+\frac{4}{2^k}.$$

Then $p_1+2p_2+3p_3+4p_4$ gives the expected number.

For $k=6$ and $100,000$ trials this would predict frequencies of $$[893,32143,46429,20536]$$ (everything rounds up) and a simulation gave $$[924,32079,46445,20552].$$

For arbitrary $d,n$ the regions come in $R=\sum_{i=0}^{d-1} {n -1 \choose i}$ sizes with two of each size. A (highly?) nontrivial question is what the distribution function (over some $R-1$ simplex) is. For $d=2$, $R=n$ and for $d=3,$ $R=\frac{n^2-n+2}{2}.$ Perhaps for $n=3$ or $4$ iterated integrals as above could be pushed through. For $d=2$ and large $n$, one has a Poisson process.

Here is an answer for $d=2$ and general $n.$ Perhaps it simplifies, but I don't immediately see how. The approach might be more effective for $d \gt 2$ than integrating over a high dimensional simplex.

$$\frac{n}{2^k}\sum_0^k\binom{k}{\ell}\left(\frac{\ell}{n+\ell-1}+\frac{k-\ell}{n+k-\ell-1}\right).$$ I don't immediately see how to simplify that. The reasoning seems valid and agrees with the answer for $n=2.$

One peculiarity of the problem is that we have regions whose sizes come from some distribution, but we have two of each size. Filtering out that feature makes the case $d=2$, which seems pretty challenging, at least by the approach I outlined in my first answer, much easier to solve.

So, as before, $n$ hyperplanes in general position through the origin in $\mathbb{R}^d$ cut the surface of the unit sphere, each creating two hemispheres and collectively $2R$ regions. Each hemisphere cut into $R$ regions, one of each size. In this version choose a hemisphere (it matters not which), randomly choose $k$ points in that hemisphere, and ask:

What is the expected number of regions with at least one point?

For $d=2$ this translates to: We have a unit interval and pick $n-1$ points splitting it into $n$ subintervals whose sizes come from a Poisson distribution. Then we pick $k$ sample points in the same interval and wonder how many subintervals are hit. Now forget the initial distribution and simply say that first we pick $n+k-1$ points and then randomly pick $n-1$ of them to be dividers and the remaining $k$ to be test points. Suddenly we have stars and bars (note that that reference switches the use of $n,k$) available to us. If $x_i$ is the number of test points in region $i$ then we have an ordered sum of non-negative integers $\sum_1^nx_i=k.$ The number of such sums is $\binom{k+n-1}{n-1}.$ The number with all the $x_i \gt 0$ is $\binom{k-1}{n-1}$ and the number with exactly $j$ of the $x_i$ positive is $\binom{n}{j}\binom{k-1}{j-1}.$ So the expected number of non-empty regions is $$E(n,k)=\frac{\sum_1^n j\binom{n}{j}\binom{k-1}{j-1}}{\binom{k+n-1}{n-1}}=\frac{nk}{n+k-1}.$$ Comments:

• I'll leave out the ugly details of how I summed that with the assurance that calculations agree.
• The final answer is so simple that I imagine there is an elegant derivation which escaped me.

• Evidently $E(n,k)=E(k,n),$ the answer is unchanged by switching $k$ and $n$. In hindsight, that is clear from the stars and bars.

Here is the reasoning for the formula claimed at the top:

Go back to picking $k$ test points distributed over the entire sphere. Pick any one of the hyperplanes. Then the $k$ points are split into $\ell$ in one half and $k-\ell$ in the other. The chance of any particular split is $2^{-k}\binom{k}{\ell}.$ It follows that the expected number of regions is $$\frac{n}{2^k}\sum_0^k\binom{k}{\ell}\left(\frac{\ell}{n+\ell-1}+\frac{k-\ell}{n+k-\ell-1}\right).$$

• Thank you for this. Given that finding an exact formula seems hard, do you think one can get an approximation for constant $d$ and large $n$? I am particularly interested in $d \approx 5$ and $n \ge 100$. – Lembik Oct 15 '14 at 13:54