Samuel Karlin's problem: Probability of positive solution to system of random linear equations

Question

I came to know this problem from Dr. W. Bryc's slides (at University of Cincinnati), and I have been continually working on this problem for almost 5 days using different techniques. But I am only able to understand the geometry and algebra for the problem when $n=3$.

Background and Physical Meaning of Problem

This research problem was proposed by late Samule Karlin, who knew the answer but has never published it. As I realized yesterday, it can be understood as the probability of $n$ independent random walks, with positively weighted uniform step size, all starting at $0$ but all reaching $1$ at step $n$. The solution itself seems to have strong symmetry but this symmetry seems to be hard to exploit due to dependence.

Satement of Problem

The problem and solution, both due to Samuel Karlin', are stated below:

Let the $n \times n$ matrix $\mathbf{U}=(u_{ij})$ have entries that are independent and identically distributed on the unit interval $[0,1]$, and let $\mathbb{R}_{+}^{n} = \{\mathbf{y}=(y_1,\ldots,y_n) \in \mathbb{R}^n: y_i >0 \text{ for } i=1,\ldots,n\} $, where $\mathbb{R}^n$ is the $n$-dimensional Euclidean space. Then \begin{equation} \Pr(\mathbf{U}: \mathbf{U}\mathbf{x}=\mathbf{1} \text{ for some } \mathbf{x} \in \mathbb{R}_{+}^{n}) = \dfrac{1}{2^{n-1}}, \end{equation}

where $\Pr$ is the probability measure with respect to $\mathbf{U}$, $\mathbf{1}$ is a vector of $n$ $1$'s, and all vectors are column vectors.

Latest update

I spent sometime on this tough problem during the vacation and found out the following when $n \geq 3$: (a) the distribution of $\pi(c_i)$ is NOT symmetric with respect to (wrt) $0$ because its characteristic function is not a real-valued function, where $c_i$ is the $i$th column of $\mathbf{U}$; this means that the distribution of $\eta(\pi(c_i))$ is NOT symmetric wrt to $0$; (b) Wendel's argument (Wendel 1962, a problem in geometric probability) can not be directly applied to $\eta(\pi(c_i))$ due to (a) and because the vectors $\eta(\pi(c_i))$ are restricted to be in the orthogonal complement of $\mathbf{1}$; (c) however, Greg's strategy definitely will help resolve the problem. For meaning of these notations, please see comment by Greg.

Attempts Made

1. Conditioning: splitting $\mathbf{U}$ into a $(n-1) \times (n-1)$ principal submatrix $\mathbf{W}$ and $\mathbf{x}$ into an $(n-1)$-dimensional subvector and the $n$th entry. But such conditioning does not seem to help since the induced joint equations for the solution in $\mathbf{x}$ involves the volume form with respect to the inverse $\mathbf{W}^{-1}$.

2. Geometry: for $n=3$ the problem has a clear geometric meaning, in that two random planes cut the unit cube, and the relative positions of the columns of $\mathbf{U}$ and $\mathbf{1}$ have to remain in a configuration in order for $\mathbf{x}$ to exist. However, when $n>4$, we can not visualize the configuration that induces the solution $\mathbf{x}$.

Any comments/suggestions on how to derive Karlin's solution? Thank you.

Answer 1

Let $c_1,\dots,c_n$ be the columns of $\mathbf{U}$; these are i.i.d. random vectors. Let $\pi(v) = v - \tfrac{1}{n} (v \cdot \mathbf{1}) \cdot \mathbf{1}$ be the projection onto the orthogonal complement of $\mathbf{1}$, and let $\eta(v) = \tfrac{1}{|v|} v$ be the normalization map. For each $i$, $\eta(\pi(c_i))$ is an element of the unit sphere $S^{n-2}$.

Claim: $\mathbf{U}\mathbf{x} = \mathbf{1}$ for some $\mathbf{x} \in \mathbb{R}_{+}^n$ iff the elements $\{\eta(\pi(c_i))\} \subset S^{n-2}$ are not contained in a hemisphere.

Proof: First note that, if $\mathbf{U}\mathbf{x} = \alpha \mathbf{1}$ for some $\mathbf{x} \in \mathbb{R}_{+}^{n}$ and $\alpha \in \mathbb{R}$, then $\alpha > 0$ (unless $\mathbf{U}=0$, but let's disregard that null event). So it is equivalent to ask for $\mathbf{x} \in \mathbb{R}_{+}^n$ such that $\pi(\mathbf{U}\mathbf{x}) = 0$. Restating and rescaling, we want $0$ to be in the convex hull of the vectors $\{\eta(\pi(c_i))\}$; but, by Farkas's lemma, the origin is in the convex hull of a set of points iff they fail to lie on one side of a hyperplane.

Now we are reduced to the following question: given $n$ i.i.d. points on the sphere $S^{n-2}$, what is the probability that they are contained in a hemisphere? Of course the answer depends on the distribution of the points in general, but there is a common answer as long as the distribution is nondegenerate (in the sense of independent points being in general position a.s.) and symmetric. In that case, the answer is $1 - \tfrac{1}{2^{n-1}}$; see, e.g., Dmitri's answer here. To summarize the argument: consider first picking $n$ lines through the origin - somehow - and then picking which of the two points on each line to keep. No matter which lines we choose (as long as they are in general position), there are exactly two sign choices that lead to points not in a hemisphere.

All that remains is to say that the distribution of the vectors $\eta(\pi(c_i))$ is symmetric. But this is true because $\mathbf{1}-c_i$ has the same distribution as $c_i$ (both have uniform $[0,1]$ coefficients) and $\eta(\pi(\mathbf{1}-c_i)) = -\eta(\pi(c_i))$.

Finally, note that this generalizes to a range of other random matrix distributions - we just need positivity, to distinguish between $+\mathbf{1}$ and $-\mathbf{1}$, and antipodal symmetry.