User russell may - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:14:53Z http://mathoverflow.net/feeds/user/12261 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108066/sequences-recurrence-relation/108081#108081 Answer by Russell May for sequences - recurrence relation Russell May 2012-09-25T17:09:36Z 2012-09-25T17:09:36Z <p>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. </p> <p>There are lots of examples along these lines in Wilf's book <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow">Generatingfunctionology</a>, chapter 2 sections 1-2.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/108067#108067 Answer by Russell May for Which popular games are the most mathematical? Russell May 2012-09-25T15:32:02Z 2012-09-25T15:32:02Z <p>The game of <a href="http://en.wikipedia.org/wiki/Cootie_%28game%29" rel="nofollow">Cootie</a>, where players roll dice to collect parts of an insect (cootie), is a variant of the coupon collector's problem.</p> <p><img src="http://upload.wikimedia.org/wikipedia/en/thumb/a/a6/Original_Cootie_box_cover_and_components.jpg/250px-Original_Cootie_box_cover_and_components.jpg" alt="alt text"></p> <p>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 <em>finite</em> sum. </p> <p>In particular, if you have $L$ objects to collect and for each object <code>$\ell&lt;L$</code> 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</p> <p><code>$\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_{&lt;q_k}(p_k x))dx.$</code></p> <p>If you're interested, check out my <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1n31" rel="nofollow">paper</a> out for the full computation.</p> http://mathoverflow.net/questions/107443/probability-of-first-collision-with-replacement/108020#108020 Answer by Russell May for Probability of first collision with replacement Russell May 2012-09-25T03:47:32Z 2012-09-25T04:20:38Z <p>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 <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow">book</a> is an excellent reference.</p> <p>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,<br> $\langle p\rangle=\frac{d^2}{dx^2}(xD(x))|_{x=1}$. </p> <p>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}$.</p> <p>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.</p> http://mathoverflow.net/questions/52370/eigenvalues-of-an-oblique-diagonal-matrix Eigenvalues of an "oblique diagonal" matrix Russell May 2011-01-18T02:25:59Z 2012-07-26T07:22:00Z <p>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 <a href="http://www.csee.umbc.edu/~lomonaco/pubs/Final-Version-QIP-Quantum-Knots.pdf" rel="nofollow">here</a> ). 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):</p> <p><code>$\begin{array}{l|lll|lll|} \text{row}\backslash\text{column}&amp;0&amp;4&amp;\ldots&amp;4^n/2&amp;4^n/2+4&amp;\ldots\\ \hline 0&amp;\boxed{a_1\,a_2\,a_1\,a_2}\\ 1&amp;&amp;\boxed{a_1\,a_2\,a_1\,a_2}\\ \vdots&amp;&amp;&amp;\ddots\\ \hline 4^n/8&amp;&amp;&amp;&amp;\boxed{a_3\,a_4\,a_3\,a_4}\\ 4^n/8+1&amp;&amp;&amp;&amp;&amp;\boxed{a_3\,a_4\,a_3\,a_4}\\ \vdots&amp;&amp;&amp;&amp;&amp;&amp;\ddots\\ \hline 2\cdot4^n/8&amp;\boxed{a_5\,a_6\,a_5\,a_6}\\ 2\cdot4^n/8+1&amp;&amp;\boxed{a_5\,a_6\,a_5\,a_6}\\ \vdots&amp;&amp;&amp;\ddots\\ \hline 3\cdot4^n/8&amp;&amp;&amp;&amp;\boxed{a_7\,a_8\,a_7\,a_8}\\ 3\cdot4^n/8+1&amp;&amp;&amp;&amp;&amp;\boxed{a_7\,a_8\,a_7\,a_8}\\ \vdots&amp;&amp;&amp;&amp;&amp;&amp;\ddots\\ \hline 4\cdot4^n/8&amp;\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ 4\cdot4^n/8+1&amp;&amp;\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ \vdots&amp;&amp;&amp;\ddots\\ \hline 5\cdot4^n/8&amp;&amp;&amp;&amp;\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ 5\cdot4^n/8+1&amp;&amp;&amp;&amp;&amp;\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ \vdots&amp;&amp;&amp;&amp;&amp;&amp;\ddots\\ \hline 6\cdot4^n/8&amp;\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ 6\cdot4^n/8+1&amp;&amp;\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ \vdots&amp;&amp;&amp;\ddots\\ \hline 7\cdot4^n/8&amp;&amp;&amp;&amp;\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ 7\cdot4^n/8+1&amp;&amp;&amp;&amp;&amp;\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ \vdots&amp;&amp;&amp;&amp;&amp;&amp;\ddots\\ \hline \end{array}$</code></p> <p>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:</p> <blockquote> <p>Is there an elementary way to compute the eigenvalues of this matrix in terms of $a_1,\ldots,a_{16}$ and $n$? </p> </blockquote> <p>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, <em>not</em> 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.</p> http://mathoverflow.net/questions/98876/a-probability-question-about-removing-stones-from-piles/98943#98943 Answer by Russell May for A probability question about removing stones from piles Russell May 2012-06-06T11:24:27Z 2012-06-06T11:24:27Z <p>As Brendan noted, the literature on the coupon collector's problem is large. I suspect a close fit to your problem would be <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub89brother.pdf" rel="nofollow">The Collector’s Brotherhood Problem Using the Newman-Shepp Symbolic Method</a> by Foata and Zeilberger. For the case of unequal probabilities, you might consider the methods in my paper <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1n31/pdf" rel="nofollow">Coupon Collecting with Quotas</a>. 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.</p> http://mathoverflow.net/questions/93744/estimating-a-partial-sum-of-weighted-binomial-coefficients/93750#93750 Answer by Russell May for Estimating a partial sum of weighted binomial coefficients Russell May 2012-04-11T10:31:51Z 2012-04-11T10:37:12Z <p>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.</p> http://mathoverflow.net/questions/91390/generating-function-for-regular-tournaments generating function for regular tournaments Russell May 2012-03-16T17:01:33Z 2012-03-16T21:10:10Z <p>At the beginning of a <a href="http://cs.anu.edu.au/~bdm/papers/euler.pdf" rel="nofollow">paper</a> 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 <code>$$\prod_{1\le j&lt;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}}\,.$$</code> 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.</p> <p>Could someone provide a reference or a few words to justify this claim?</p> http://mathoverflow.net/questions/79051/theorems-proved-with-ad-whose-proof-is-also-known-in-the-zf-world/79092#79092 Answer by Russell May for Theorems proved with AD whose proof is also known in the ZF world Russell May 2011-10-25T15:55:54Z 2011-10-25T15:55:54Z <p>Perhaps, this is along the lines of what you're looking for. This <a href="http://digital.library.unt.edu/ark%3A/67531/metadc2789/m1/1/high_res_d/dissertation.pdf" rel="nofollow">thesis</a> 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 $&lt;\aleph_{\omega_2}$ in $L[\mathbb{R}]$ must collapse in $V$.</p> http://mathoverflow.net/questions/29137/good-combinatorics-textbooks-for-teaching-undergraduates/73661#73661 Answer by Russell May for Good combinatorics textbooks for teaching undergraduates? Russell May 2011-08-25T13:54:22Z 2011-08-25T13:54:22Z <p>It's obviously slanted towards the generating-function view of enumeration, but I enthusiastically recommend <em>Generatingfunctionology</em> 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 <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow">website</a>.</p> http://mathoverflow.net/questions/59824/use-of-traces-in-physics/59872#59872 Answer by Russell May for Use of traces in physics Russell May 2011-03-28T17:49:31Z 2011-03-28T17:49:31Z <p>There was a similar question recently posed (and often answered) here:</p> <p><a href="http://mathoverflow.net/questions/13526/geometric-interpretation-of-trace" rel="nofollow">http://mathoverflow.net/questions/13526/geometric-interpretation-of-trace</a></p> http://mathoverflow.net/questions/56210/reference-for-a-edge-matching-problem reference for a edge-matching problem Russell May 2011-02-21T19:54:19Z 2011-02-22T04:49:44Z <p>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 <a href="http://www.csee.umbc.edu/~lomonaco/pubs/Final-Version-QIP-Quantum-Knots.pdf" rel="nofollow">quantum knot mosaics</a>, 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 <a href="http://puzzles.guidestobuy.com/scramble-squares-butterflies" rel="nofollow">here</a> if the image is broken): <img src="http://puzzles.guidestobuy.com/scramble-squares-butterflies/71CVKT0J0BL.gif" alt="alt text"></p> <p>For what it's worth, solving a general edge-matching puzzle is NP-complete (see <a href="http://erikdemaine.org/papers/Jigsaw_GC/" rel="nofollow">article</a> 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.</p> <blockquote> <p>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?</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/107443/probability-of-first-collision-with-replacement Comment by Russell May Russell May 2012-09-18T13:46:52Z 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. http://mathoverflow.net/questions/52370/eigenvalues-of-an-oblique-diagonal-matrix/93173#93173 Comment by Russell May Russell May 2012-04-06T18:44:32Z 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. http://mathoverflow.net/questions/52370/eigenvalues-of-an-oblique-diagonal-matrix Comment by Russell May Russell May 2012-04-05T12:32:24Z 2012-04-05T12:32:24Z Well, as Donald Knuth said, TeX is intended for the creation of beautiful mathematics. http://mathoverflow.net/questions/91390/generating-function-for-regular-tournaments/91413#91413 Comment by Russell May Russell May 2012-03-16T21:26:04Z 2012-03-16T21:26:04Z Thank you, Ira. That helps very much. http://mathoverflow.net/questions/61664/number-of-required-trials-to-sample-all-possible-states-of-a-d-sided-loaded-die/61668#61668 Comment by Russell May Russell May 2011-12-08T13:17:10Z 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. http://mathoverflow.net/questions/79051/theorems-proved-with-ad-whose-proof-is-also-known-in-the-zf-world/79092#79092 Comment by Russell May Russell May 2011-10-25T18:07:26Z 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. http://mathoverflow.net/questions/56210/reference-for-a-edge-matching-problem/56244#56244 Comment by Russell May Russell May 2011-02-22T18:03:51Z 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. http://mathoverflow.net/questions/56210/reference-for-a-edge-matching-problem/56216#56216 Comment by Russell May Russell May 2011-02-22T05:03:02Z 2011-02-22T05:03:02Z The &quot;red lines&quot; 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).