3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}.$ $\endgroup$ – Aaron Meyerowitz Oct 3 '14 at 10:11
  • $\begingroup$ @AaronMeyerowitz Thank you. The missing $2$ was a typo. $\endgroup$ – Lembik Oct 3 '14 at 10:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Kevin P. Costello Oct 8 '14 at 20:58
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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). $$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Lembik Oct 15 '14 at 13:54

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.