With trepidation, I am attempting to start another series of mathematical blog posts. The goal of this one will be to present random partitions as a toy model for thinking about random dimer configurations. Ideally, these posts will help prepare the reader to take on the ground breaking papers of Kenyon and Okounkov.
I say ideally because I have an infant daughter at home — her name is Josephine, she is adorable and demanding — so the installments of this series may be spaced very far apart. I make no plans to apologize for this. But I’ve been feeling the lack of mathematical blogging the last few months, so I’m giving it a shot.
The motivating question for today’s post will be: For , approximately how many paths are there from to , made up of steps in direction and ?
This may seem like a silly question. The exact number of such paths is . There are steps, of which are north and of which are east. So the count is the binomial coefficient.
If we need an approximation, we can haul out Stirling’s approximation. In a weak form, this says So, after a little work we get
We’ll define , so this says that the number of paths of (taxicab) length is . Conceptually, one can think that, for every unit of length of the diagonal, there are ways to configure that section of the partition.
Even with this crude bound, we can deduce a nonobvious statement: Almost all paths from to are within of a straight line path.
“Proof“: Suppose, to the contrary, that there were a positive proportion of paths that passed through a point which was significantly off a straight line. These paths can be divided into two shorter paths, one of size and one of size , with and .
The number of paths of these two types is the product of the number of paths of each type. In other words,
But is easily seen to be concave, so . Moreover, the only way that can even be close to is if , meaning that the point is on the main diagonal. In other words, if the point is off the straight line route, the number of paths passing through that point is exponentially less then the number of total paths from to . So almost all paths in the box stay near the straight line. “QED”
By the way, that is the level of rigor you should expect throughout this series. I want to focus on concepts, not on precise bounds.
Another approach to deriving
Now, let’s forget binomial coefficients and Stirlings formula. Suppose that we suspected there was a function such that the number of paths was , but we didn’t know what was. One can see that is concave by thinking about concatenating paths, as above. I now explain how, using generating functions, we can understand the properties of .
Let be the generating function for all north-easterly paths of length , where we weight a northern step by and an eastern step by . Of course, is simply . Suppose that we didn’t know this exact formula, but we did know that there was a function such that . So , but we are pretending not to know this. We now have two functions and , which we are pretending not to know, and we would like to figure out how they are related.
We can break the generating function up according to how many northern and how many eastern steps we take. So
When gets large, only the largest term will contribute to the sum. So we should have
Since is concave, this maximum will be achieved at a unique . Assuming that is sufficiently differentiable, this will obey . In short we have shown:
|If , then .|
The reader may enjoy verifying that our and do in fact verify this relation. The standard term is that and are Legendre dual.
Let’s do a slightly harder problem. We’ll count paths from to again only, this time, when we take a step from to , and is even, we can color the step either black or white. Approximately how many such colored paths are there?
This time, there is no simple formula for . But the same method works to obtain a differential equation. The generating function which used to be would now be and would be . So is Legendre dual to — whatever that may be.
My goal for next time is to derive the shape of a randomly chosen partition of size . See you then!