User russell may - MathOverflow

Answer by Russell May for sequences - recurrence relation

2012-09-25T17:09:36Z

One standard way to solve recurrence relations is with generating functions. In this case, let $f$ and $g$ be the ordinary generating functions of the sequences $y$ and $z$. Then the generating function equivalent of your recurrence relations would be $$\frac{g(x)-g(0)}x=d\cdot g(x)+\frac e{1-x}$$ and $$\frac{f(x)-f(0)}x=a\cdot f(x)+b\cdot g(x)+\frac c{1-x}.$$ You can then solve these relations for the generating functions $$g(x)=\left(\frac{e\cdot x}{1-x}+g(0)\right)\cdot \frac 1{1-xd}$$and $$f(x)=\left(x\cdot b\cdot g(x)+\frac{x\cdot c}{1-x}+f(0)\right)\frac 1{1-ax}.$$ Lastly, you need to find the partial fraction decomposition of $f$. Using geometric series and its derivatives, you can then read off the coefficients of the partial fraction decomposition to get an explicit solution for the terms in your sequences.

There are lots of examples along these lines in Wilf's book Generatingfunctionology, chapter 2 sections 1-2.

Answer by Russell May for Which popular games are the most mathematical?

2012-09-25T15:32:02Z

The game of Cootie, where players roll dice to collect parts of an insect (cootie), is a variant of the coupon collector's problem.

Instead of collecting a single instance of each coupon, players must collect multiple copies (6 legs, 2 eyes, 1 head, etc.) to win. It turns out you can compute the expected number of rolls to win at Cootie (even with a weighted die) with a finite sum.

In particular, if you have $L$ objects to collect and for each object $\ell<L$ you need $q_\ell$ copies and the probability of getting the object is $p_\ell$, then the expected number of rolls to get all of the needed objects is

$\displaystyle\sum_{\ell\in L} \frac{{p_\ell}^{q_\ell}}{(q_\ell -1)!}\int_0^\infty x^{q_\ell}\exp(-x) \prod_{k\in L-\{\ell\}}(\exp(p_k x)-\exp_{<q_k}(p_k x))dx.$

If you're interested, check out my paper out for the full computation.

Answer by Russell May for Probability of first collision with replacement

2012-09-25T03:47:32Z

There's no closed form for this expectation. However, you can get good approximations. One common way to do this is with generating functions. Herb Wilf's book is an excellent reference.

As noted, the probability that the first collision occurs on the $n$th draw with $m$ balls is $p_n=d_{n-1}\frac{n-1}m$, where $d_n=\frac{m!}{m^n (m-n)!}$. Consider the ordinary generating function $D(x)=\sum_{n=0}^{m}d_nx^n$. Then the expected number of draws to get a collision would be $\langle p\rangle=\sum_{n=1}^{m+1} n\cdot p_n$ or, in terms of the generating function,
$\langle p\rangle=\frac{d^2}{dx^2}(xD(x))|_{x=1}$.

The generating function $D(x)$ is not summable. However, its exponential counterpart is: $E(x)=\sum_{n=0}^{m}\frac{d_n}{ n!}x^n=(1+x/m)^m$. The ordinary and exponential generating functions are related by the Laplace transform, $D(x)=\frac 1x\int_0^\infty e^{-t/x}E(t)dt$. Differentiating under the integral twice and then evaluating at $x=1$, we get $\langle p\rangle=\frac 1m\int_0^\infty e^{-t}(t^2-2t)(1+t/m)^mdt$. The dominant part in this integral comes from the $t^2$ term. So, $\langle p\rangle\approx\frac 1m\int_0^\infty e^{-t}t^2(1+t/m)^m dt$, and substituting $u=t/m$, we get $\langle p\rangle\approx m^2\int_0^\infty e^{m(-u+\log(1+u))}u^2 du$. This integral can be nicely approximated with Laplace's method, where the exponent $-u+\log(1+u)$ is replaced with its second order Taylor series about its maximum (at $u=0$), which turns out to be just $-u^2/2$. So, $\langle p\rangle\approx m^2\int_0^\infty e^{-u^2 m/2}u^2du=\sqrt{{\pi m}/2}$.

If you need greater accuracy or if you want to consider higher moments of the distribution, you can always consider the other terms in the first integral representation of $\langle p\rangle$ and higher order terms in the Laplace's method. Another avenue to analyze this expectation, as suggested in the wikipedia article on the birthday problem, is to learn about the Ramanujan $Q$-function.

Eigenvalues of an "oblique diagonal" matrix

2011-01-18T02:25:59Z

I am looking for guidance about the behavior of powers of a particular matrix (call it $A_n$ for $n\ge2$), which has come up in a counting problem about quantum knot mosaics (a good reference for quantum knot mosaics is here ). Here's a description of the matrix. It has $4^n$ rows and columns. Instead of a traditional diagonal matrix with its non-zero entries on the main diagonal, the non-zero entries of $A_n$ are on an ``oblique diagonal" of slope $4$, modulo the size of the matrix. More precisely, the non-zero entries occur where $\left\lfloor\frac{\text{column}}4\right\rfloor=\text{row}\text{, mod}\;4^{n-1}$. The matrix has sixteen possibly non-zero values $a_1,\ldots,a_{16}$, arranged as follows (with boxes for visual clarity):

$\begin{array}{l|lll|lll|} \text{row}\backslash\text{column}&0&4&\ldots&4^n/2&4^n/2+4&\ldots\\ \hline 0&\boxed{a_1\,a_2\,a_1\,a_2}\\ 1&&\boxed{a_1\,a_2\,a_1\,a_2}\\ \vdots&&&\ddots\\ \hline 4^n/8&&&&\boxed{a_3\,a_4\,a_3\,a_4}\\ 4^n/8+1&&&&&\boxed{a_3\,a_4\,a_3\,a_4}\\ \vdots&&&&&&\ddots\\ \hline 2\cdot4^n/8&\boxed{a_5\,a_6\,a_5\,a_6}\\ 2\cdot4^n/8+1&&\boxed{a_5\,a_6\,a_5\,a_6}\\ \vdots&&&\ddots\\ \hline 3\cdot4^n/8&&&&\boxed{a_7\,a_8\,a_7\,a_8}\\ 3\cdot4^n/8+1&&&&&\boxed{a_7\,a_8\,a_7\,a_8}\\ \vdots&&&&&&\ddots\\ \hline 4\cdot4^n/8&\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ 4\cdot4^n/8+1&&\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ \vdots&&&\ddots\\ \hline 5\cdot4^n/8&&&&\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ 5\cdot4^n/8+1&&&&&\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ \vdots&&&&&&\ddots\\ \hline 6\cdot4^n/8&\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ 6\cdot4^n/8+1&&\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ \vdots&&&\ddots\\ \hline 7\cdot4^n/8&&&&\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ 7\cdot4^n/8+1&&&&&\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ \vdots&&&&&&\ddots\\ \hline \end{array}$

Since $A_n$ has a straightforward geometrical description with non-zero entries only on a diagonal (albeit an oblique one), the following question seems reasonable:

Is there an elementary way to compute the eigenvalues of this matrix in terms of $a_1,\ldots,a_{16}$ and $n$?

I'm no expert in tensor algebra, but it seems that $A_n$ might be expressed as the tensor product of $A_2$ with $n-1$ copies of another transformation. Even an approximation of the largest eigenvalue would be useful, but it would be best to avoid the power method with the Rayleigh quotient since I'm trying to analyze the powers of the matrix in terms of the eigenvalues, not vice versa. Any insight into the computation of the eigenvalues of $A_n$ would be greatly appreciated and would go a long way in answering a question in the paper referenced above.

Answer by Russell May for A probability question about removing stones from piles

2012-06-06T11:24:27Z

As Brendan noted, the literature on the coupon collector's problem is large. I suspect a close fit to your problem would be The Collector’s Brotherhood Problem Using the Newman-Shepp Symbolic Method by Foata and Zeilberger. For the case of unequal probabilities, you might consider the methods in my paper Coupon Collecting with Quotas. It turns out that the case of unequal probabilities is not too much "hairier" than the uniform case, so it seems feasible to mesh these two papers to obtain the result you're looking for.

Answer by Russell May for Estimating a partial sum of weighted binomial coefficients

2012-04-11T10:31:51Z

Your sum can also be thought of as the first $\alpha n$ terms in a binomial distribution with probability of success $p=1-\frac1{\lambda+1}$. So, it is closely approximated by a normal distribution with mean $np$ and standard deviation $\sqrt{np(1-p)}$, i.e., $$\sum_{k=0}^{\alpha n} \binom nk \lambda^k\approx (1-p)^{-n}\Phi\left((\alpha-p)\sqrt{\frac n{p(1-p)}}\right),$$ where $\Phi$ is the cumulative standard normal distribution.

generating function for regular tournaments

2012-03-16T17:01:33Z

At the beginning of a paper by McKay and Robinson on enumerating eulerian circuits, the authors state that the number of regular tournaments containing a directed rooted tree $T$ on vertices $v_1,\dots,v_n$ with root $v_n$ coincides with the constant term in the generating function $$\prod_{1\le j<k\le n}(x_j^{-1}x_k+x_jx_k^{-1})\,\prod_{jk\in\textrm{ edges of }T}\frac{x_jx_k^{-1}}{x_j^{-1}x_k+x_jx_k^{-1}}\,.$$ Unlike most everything else in the paper, this statement is made without justification, which makes me think that it's either a well-known result or obvious, i.e., except to me.

Could someone provide a reference or a few words to justify this claim?

Answer by Russell May for Theorems proved with AD whose proof is also known in the ZF world

2011-10-25T15:55:54Z

Perhaps, this is along the lines of what you're looking for. This thesis gives a proof of the stong partition relation on $\omega_1$ from AD, and then "relativizes" the proof to $V$ to show, assuming the existence of Woodin cardinals, a collapsing result, namely, that some regular cardinal $<\aleph_{\omega_2}$ in $L[\mathbb{R}]$ must collapse in $V$.

Answer by Russell May for Good combinatorics textbooks for teaching undergraduates?

2011-08-25T13:54:22Z

It's obviously slanted towards the generating-function view of enumeration, but I enthusiastically recommend Generatingfunctionology by Herb Wilf. It covers all the topics you mentioned, written mainly in the style of examples, rather than theory---something that usually appeals to undergraduates. To me what makes the book a great introduction for a newcomer to combinatorics is Wilf's obvious enthusiasm and easy-going (yet firmly exacting) writing style. The mileage he gets out of changing a recurrence relation into a generating function is truly amazing. I think most undergraduates would be amazed that their skills in calculus can help them enumerate discrete objects, and this book does exactly that over and over again. If price matters, this one is tough to beat---the second edition is free at Wilf's website.

Answer by Russell May for Use of traces in physics

2011-03-28T17:49:31Z

There was a similar question recently posed (and often answered) here:

http://mathoverflow.net/questions/13526/geometric-interpretation-of-trace

reference for a edge-matching problem

2011-02-21T19:54:19Z

Perhaps not surprisingly, a variation of a recreational math puzzle (a so-called edge-matching puzzle or scramble square) is equivalent to a combinatorics question of interest (in this case, about quantum knot mosaics, question #9). In a traditional edge-matching puzzle, you are given $n^2$ tiles, each tile square in shape and bearing a design, with the goal of arranging the tiles in an $n\times n$ grid so that the designs on the side of adjacent tiles "match". For instance, here's a puzzle with 24 possible tiles (4 sides, 3 colors, 2 halves) of which at most 9 actually appear (link here if the image is broken):

For what it's worth, solving a general edge-matching puzzle is NP-complete (see article of Demaine). The combinatorics problem is phrased in a slightly different fashion. You begin with a finite collection of designs (such as quadruples of colored halves of butterflies) and for each design an ample supply of square tiles bearing that design. The problem is to calculate the number of arrangements of these tiles in an $n\times n$ grid so that, as in the game described above, the designs on sides of adjacent tiles match. The number of arrangements should be in terms of the size of the grid and the collection of designs on the tiles.

Is anyone aware of results along these lines or, even better, able to provide a quick calculation of the number of arrangements of tiles into an edge-matched grid?

My suspicion is that the number of arrangements goes like $\lambda^{n^2}$ where $\lambda$ is determined from the collection of designs on the tiles.

Comment by Russell May

2012-09-18T13:46:52Z

This is a variant of the birthday problem. It looks like even the wikipedia article on this has the information you're asking for.

Comment by Russell May

2012-04-06T18:44:32Z

I agree that there's a permutation matrix P and a block diagonal matrix A' so that the oblique diagonal matrix A is PA'. However, it's not clear how to get the eigenvalues of a product, given the eigenvalues of the factors.

Comment by Russell May

2012-04-05T12:32:24Z

Well, as Donald Knuth said, TeX is intended for the creation of beautiful mathematics.

Comment by Russell May

2012-03-16T21:26:04Z

Thank you, Ira. That helps very much.

Comment by Russell May

2011-12-08T13:17:10Z

For what it's worth, this result goes back to: von Schelling, H., (1934). Auf der Spur des Zufalls. Deutsches Statistisches Zentralblatt, 26, 137-146. An English translation appeared later (in a much more accessible location): von Schelling, H., (1954). Coupon Collecting for Unequal Probabilities, Amer. Math. Monthly, 61, no. 5, 306-311.

Comment by Russell May

2011-10-25T18:07:26Z

@Asaf Kargila: I thought about doing that, but I think it's fairer to say that all the major ideas there were from my advisor, Steve Jackson.

Comment by Russell May

2011-02-22T18:03:51Z

These references look very useful---many thanks. Now that you mention it, this puzzle does look like a slight generalization of an alternating sign matrix. I'll definitely try to see if Zeilberger's or Kuperberg's proofs of the alternating sign matrix conjecture generalize.

Comment by Russell May

2011-02-22T05:03:02Z

The "red lines" come from the referenced paper on quantum knot mosaics by Lomonaco and Kauffman, in which the tiles bear designs of zero, one or two strands of rope (which are drawn in red).