Update: problem reformulation
Following the advice in comments, I now restate my problem using Voronoi
tessellation.
Given a unit hypercube $H_n=\{(x_1,\ldots,x_n)\in \mathbb{R}^n: 0\leq x_i\leq
1\}$, generate $K$ random points in $H_n$ using
uniform Poisson point process with intensity 1.
Let $V_k$ be the $k$-th Voronoi cell. Define
$\mathcal{V}=\{k\in\{1,\ldots,K\}|L\cap V_{k}\neq \emptyset\}$,
where $L$ is a line that intersects $H_n$
My question
Assume that $L$ is a random line (i.e. $L$ is uniformly distributed over all lines that intersect $[0,1]^n$), what is the expected value of $|\mathcal{V}|$? i.e. what is the average number of Voronoi cell that a random line intersects?
Clarification of edits
-
In the last formulation, $K$ points were uniformly distributed on $[0,1]^n$. Anthony Quas suggests that using a Poisson point process is preferable.
-
My original definition of a random $L$ is: the end points of $L$ are
uniformly distributed on $H_n$'s edges. However, in Remark's comment:I suggest that $L$ should be uniformly distributed over all lines that intersect $[0,1]^n$ . It is not equivalent to the current distribution because with uniform distribution if you know the first intersection point is close to a corner, then the second intersection point is also more likely to be close to that corner.
I guess this formulation is clearer than the old one. So if you can understand my question by reading above, please ignore everything I wrote below.
Old formulation: a messy one
I'll first describe how I divide $\mathbb{R}^{n}$ into $K$ convex sets, then describe my problem.
First of all, I define a function
$\mathcal{C}(\mathbf{x}): \mathbb{R}^{n}\mapsto \{1,\ldots,K\}$ as follows:
$\mathcal{C}(\mathbf{x})=\underset{k=1,\ldots,K}{\mathrm{sargmax}} \mathbf{w}_{k}^{T}\mathbf{x}$,
where sargmax denotes the maximizer with the smallest $k$ value. Moreover,
define
$S_{k}=\{\mathbf{x}\in \mathbb{R}^{n}|\mathcal{C}(\mathbf{x})=k\}$,
where $ k\in\{1,\ldots,K\}$.
The following statements can be easily proved.
-The collection $S_{1},S_{2},\ldots,S_{K}$ forms a partition of $\mathbb{R}^{n}$.
-$\forall k\in\{1,\ldots,K\}$, $S_{k}$ is a convex set.
For a line $L$ in $\mathbb{R}^{n}$, let
$V=\{k\in\{1,\ldots,K\}|L\cap S_{k}\neq \emptyset\}$.
A random line in $\mathbb{R}^n$ is a line connecting two points sampled from a $n$-dimensional normal distribution.
Here comes my question:
Assume that $\mathbf{w}_1,\ldots, \mathbf{w}_K$ are iid random variables in $\mathbb{R}^n$, each $\mathbf{w}_i \sim \mathcal{N}_n(\mu, \Sigma)$.
For a random line $L$ in $\mathbb{R}^{n}$, what is the expected value of $|V|$?
It would be also nice if someone could re-formulate this problem into a less cumbersome one, or perhaps point me to some literature about this problem.
Best Answer
I'm not saying the distribution of $L$ is inappropriate, but I think it will be more easy to work with another one.
Let me give an answer that works with a general class of distributions. I also only assume that the tessellation is only made from convex polytopes.
First remark that if I denote by $T$ the union of all faces of cells of the tessellation (edges of $[0,1]^n$ included), you are interested in the variable $$F=card (T\cap L)-1$$ (because a.s. each time the line touches a cell, it only touches its border twice, and the exit point is actually the entrance point for a new cell, except at the end-points).
Let $\mathcal{L}$ be the class of all lines of $\mathbb{R}^n$, and $\mu$ some measure on $\mathcal{L}$ (endowed with a topology coming from a parametrization of $\mathcal{L}$), and for a set $C$ of $\mathbb{R}^n$, denote by $[C]$ the class of all lines intersecting $C$. Instead of working with a single line $L$, consider an independant Poisson point process of lines $\Pi$ on $\mathcal{L}$ with intensity measure $\mu$. I emphasize that a.s. only a finite number of lines of $\Pi$ will hit $[0,1]^n$, so I can label them independantly $N_1, N_2, ...$ so that the $L_i$ are iid. Call $N$ then number of lines touching $[0,1]^n$. Given any fixed tessellation $T$, we have $$\mathbb{E}\sum_i card(T\cap L_i)=\mathbb{E}\sum_n \mathbb{P}(N=n) \sum_{i=1}^n card(T\cap L_i)=\sum_n \mathbb{P}(N=n) n\mathbb{E} card(T\cap L_1)$$
$$=(\mathbb{E}(F)+1)\mathbb{E}(N).$$
So we will compute $\mathbb{E}(N)$ and $\mathbb{E}\sum_i card(T\cap L_i)$. We have $\mathbb{E}(N)=\mu([[0,1]^n])$ because $\Pi$ is a Poisson point process.
Let $T$ be a deterministic tessellation, written as $T=\cup f$, where the $f$ are the facets of the tessellations. Remarking that any given line can hit a facet no more than one time, we have $$\mathbb{E}\sum_i card(T\cap L_i)=\mathbb{E}\sum_i\sum_f card(f\cap L_i)=\sum_f \mathbb{E} card(i:f\cap L_i\neq \emptyset)=\sum_f \mu([f])$$ because $(L_1,L_2,...)$ is a Poisson point process with intensity $\mu$.
At this point you need to make assumptions on the distribution of the lines, so I make the assumption that $\mu$ is translation invariant. In this case it is a standard fact from integral geometry that $\mu([f])=c |f|$ where $c$ is a constant depending solely on $\mu$ and $|f|$ is the $(n-1)$-dimensional measure of $f$. Thus you have $$\mathbb{E}F=\mathbb{E}\frac{\sum_f c|f| }{\mu([[0,1]^n])}-1=c\frac{\mathbb{E}|T|}{\mu([[0,1]^n])}-1.$$
With normalisation conditions you can probably compute $c/\mu([[0,1]^n])$. Thus the above results holds for any random tessellation with facets as convex polytopes and a random line segment that is the restriction of a stationary measure $\mu$ on $\mathcal{L}$ to $[[0,1]^n$. For example the uniform distribution works, but you can also choose a different directional distribution, for instance "only horizontal lines and vertical lines", etc...I don't know if the iid intersection points enters this framework.