MHB Is There a Unique Solution to This Random Matrix Problem?

[Ackbach]

Here is this week's POTW:

-----

Suppose that each of $n$ people writes down the numbers $1,2,3$ in random order in one column of a $3\times n$ matrix, with all orders equally likely and with the orders for different columns independent of each other. Let the row sums $a,b,c$ of the resulting matrix be rearranged (if necessary) so that $a\le b\le c$. Show that for some $n\ge 1995$, it is at least four times as likely that both $b=a+1$ and $c=a+2$ as that $a=b=c$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 217 - May 24, 2016

This was Problem A-6 in the 1995 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

View this as a random walk/Markov process with states $(i,j,k)$ the triples of integers with sum 0, corresponding to the difference between the first, second and third rows with their average (twice the number of columns). Adding a new column adds on a random permutation of the vector $(1,0,-1)$. I prefer to identify the triple $(i,j,k)$ with the point $(i-j) + (j-k)\omega + (k-i)\omega^{2}$ in the plane, where $\omega$ is a cube root of unity. Then adding a new column corresponds to moving to one of the six neighbors of the current position in a triangular lattice.

What we'd like to argue is that for large enough $n$, the ratio of the probabilities of being in any two particular states goes to 1. Then in fact, we'll see that eventually, about six times as many matrices have $a=b-1,b=c-1$ than $a=b=c$. This is a pain to prove, though, and in fact is way more than we actually need.

Let $C_{n}$ and $A_{n}$ be the probability that we are at the origin, or at a particular point adjacent to the origin, respectively. Then $C_{n+1} = A_{n}$. (In fact, $C_{n+1}$ is $1/6$ times the sum of the probabilities of being at each neighbor of the origin at time $n$, but these are all $A_{n}$.) So the desired result, which is that $C_{n}/A_{n} \geq 2/3$ for some large $n$, is equivalent to $A_{n+1}/A_{n} \geq 2/3$.

Suppose on the contrary that this is not the case; then $A_{n} < c (2/3)^{n}$ for some constant $n$. However, if $n=6m$, the probability that we chose each of the six types of moves $m$ times is already $(6m)!/[m!^{6} 6^{6m}]$, which by Stirling's approximation is asymptotic to a constant times $m^{-5/2}$. This term alone is bigger than $c (2/3)^{n}$, so we must have $A_{n+1}/A_{n} \geq 2/3$ for some $n$. (In fact, we must have $A_{n+1}/A_{n} \geq 1-\epsilon$ for any $\epsilon>0$.)