Feb 16, 2015

Solution to Student Puzzle Corner 7

The problem, stated here, was the following:
what is an exact expression for the singularity probability $f(p)$ of a $3\times 3$ random matrix with iid Rademacher entries having the distribution $P(1) = p, P(-1) = 1-p$, to find its average over $p$, and to show that it is minimized at $p = \frac{1}{2}$.

Student members Yixin Wang (Columbia University) and Tengyuan Liang (Wharton School, University of Pennsylvania), provided correct solutions to the various parts of the problem.

SPC Yixin Wang Tengyuan Liang
Yixin Wang (left) and Tengyuan Liang both answered correctly

This can actually be done by a brute force complete enumeration. Alternatively, condition on the first two rows and denote the third row by $(x,y,z)$, and calculate the determinant. It is a linear function of $x, y, z$; find the probability that the determinant is zero. Now uncondition and obtain the unconditional probability that the determinant is zero. At first sight, the singularity probability $f(p)$ is a polynomial of degree $9$. But cancellation occurs and it is actually the sixth degree

\[ f(p) = 1-18p^2+84p^3-162p^4+144p^5-48p^6.\]

Immediately, the average singularity probability is

$\int_0^1 f(p)\,dp = \frac{26}{35}$, and $f(\frac{1}{2}) = \frac{5}{8}$.

Pictures can be deceiving, and this is an instance. A coarse scale picture would suggest that $f(p)$ is convex over the unit interval. It is not. It has the concave-convex-concave shape.

$f”(p)$ is a polynomial of degree four and has a double zero at $p = \frac{1}{2}$ and two other distinct zeros in the unit interval. It has no other real or complex roots. The first derivative $f'(p)$ is a polynomial of degree five, has a zero at $p = 0, 1,$ and $\frac{1}{2}$, and the zero at $\frac{1}{2}$ is a triple zero. The first derivative has no other roots. From the symmetry of $f(p)$ and the fact that it is strictly decreasing in a right neighborhood of zero and so, strictly increasing in a left neighborhood of $p = 1$, it now follows that the minimum must be at $p = \frac{1}{2}$.

We have here the function $f(p)$ written explicitly; an interesting question is whether the coefficients in the polynomial have some relations to a well known number theoretic function. The same question could be asked for other values of $n$.


1 Comment

Leave a comment




Welcome to the IMS Bulletin website! We are developing the way we communicate news and information more effectively with members. The print Bulletin is still with us (free with IMS membership), and still available as a PDF to download, but in addition, we are placing some of the news, columns and articles on this blog site, which will allow you the opportunity to interact more. We are always keen to hear from IMS members, and encourage you to write articles and reports that other IMS members would find interesting. Contact the IMS Bulletin at bulletin@imstat.org

What is “Open Forum”?

In the Open Forum, any IMS member can propose a topic for discussion. Email your subject and an opening paragraph (to bulletin@imstat.org) and we'll post it to start off the discussion. Other readers can join in the debate by commenting on the post. Search other Open Forum posts by using the Open Forum category link below. Start a discussion today!

About IMS

The Institute of Mathematical Statistics is an international scholarly society devoted to the development and dissemination of the theory and applications of statistics and probability. We have about 4,500 members around the world. Visit IMS at http://imstat.org
Latest Issue