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

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 $$\Pr(\mathbf{U}: \mathbf{U}\mathbf{x}=\mathbf{1} \text{ for some } \mathbf{x} \in \mathbb{R}_{+}^{n}) = \dfrac{1}{2^{n-1}},$$

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.

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.

• I have not reported in the post numerical findings yet. Basically, there are $2^n$ cases for the combination of signs of each entry of $\mathbf{x}$ as solution to $\mathbf{U x}=\mathbf{1}$. However, these cases are NOT equally likely, meaning that the random partitions of the cube without sign constrains do not give splits of equal volume. However, within each class of solutions for which the number of negative components of $\mathbf{x}$ are fixed, the subcases are equally-likely. This is such a tricky problem. – Chee Apr 14 '15 at 20:15
• Regarding signs, it seems clear that if we consider the case of $\mathcal U(-1,1)$ random variables instead of $\mathcal U(0,1)$, then the associated probability is $2^{-n}$, by symmetry. ($\mathbf U$ will be invertible almost surely and the sign pattern of the solution to $\mathbf U \mathbf x = \mathbf 1$ should then be uniform on $\{-1,+1\}^n$.) Maybe there is a further reduction by symmetry to your case. One approach might be considering the $\mathcal U(0,1)$ matrix as a "rejection-sampled" version of the $\mathcal U(-1,1)$ one I described above. Not sure that helps, though. – cardinal Apr 15 '15 at 15:04
• Hi Cardinal, Thank you. Could you please explain a bit more on your claim that the sign pattern of the solution to $\mathbf{Ux}=\mathbf{1}$ should be uniform on $\{-1,+1\}^n$? Here the entries $u_{ij}$ of $\mathbf{U}$ are uniform on the interval $[0,1]$, not uniform on the binary set $\{0,1\}$ or $\{-1,1\}$. – Chee Apr 15 '15 at 15:59
• Chee: If the variables are uniform on $(-1,1)$ instead of $(0,1)$, then there's an underlying symmetry: Multiplying a given column by $-1$ multiplies the corresponding coordinate in the solution to $Ux=1$ by $-1$. – Kevin P. Costello Apr 15 '15 at 23:12
• Hi Kevin, thank you. But what you described is a general property as long as the $n^2$ entries $u_{ij}$ are jointly dependent and their identical distribution is absolutely continuous with respect to the Lebesgue measure. Since in this case, $\mathbf{U}$ is Lebesgue almost surely invertible, and by Carmer's rule and linearity of determinant, multiplying the $i$th column of $\mathbf{U}$ by $-1$ changes the sign of the $i$th coordinate of the solution $\mathbf{x}$ to $\mathbf{Ux}=\mathbf{1}$, while the signs of other coordinates of such $\mathbf{x}$ remain the same. – Chee Apr 16 '15 at 12:23

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.

• Hi, Greg, thank you very much for the excellent explanation! It definitely invited me into a new branch I did not know before. – Chee May 11 '15 at 16:27
• Hi Greg, may I know your full name, so I can ackownledge you on a related project I am working on? Thanks a lot! – Chee May 16 '15 at 16:56
• Hi Chee - sure, I'm Gregory Minton. I'm glad the answer helped! – Greg M May 17 '15 at 17:27
• Hi Greg, thank you! I am working on a conjecture related to a variant of this problem (which requires also estimation of the probablity of dependent random vectors being linearly dependent and singularity probablity of symmetric random matrices). I am new to this area but will post back with a link once I resolve it. Regards, Chee – Chee May 17 '15 at 23:25