User alex r. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T15:13:25Z http://mathoverflow.net/feeds/user/934 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/133436/random-rsk-and-plancherel-measure Random RSK and Plancherel Measure Alex R. 2013-06-11T22:47:24Z 2013-06-12T00:26:12Z <p>Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this sequence (and looking at the <em>recording tableau</em>) gives the (infinite) Plancheral measure on Young Tableaux. Restricting the above sequence to length $n$ to give the Plancheral measure on partitions of $n$. The proof is straightforward as the sequence of $X_i$ induce uniformly random permutations and RSK follows through. </p> <blockquote> <p>Here's my question: what is known in the case of other distributions for the $X_i$? I suppose one can equivalently say what is known for non uniformly random permutations but I'd like to stick to the former.</p> </blockquote> <p>In particular, is anything known about the resulting limit shape of the tableau like the result of Logan-Shepp-Vershik-Kerov? I did some simulations with other distributions and it seems the limit shape is the same! Here's a picture of the usual Plancheral limit shape:</p> <p><img src="http://algo.inria.fr/seminars/sem00-01/dembo1001.gif" alt="alt text"></p> http://mathoverflow.net/questions/75346/coin-pusher-game Coin Pusher Game Alex R. 2011-09-13T19:48:17Z 2013-05-27T14:22:00Z <p>While doing laundry at my local laundromat, I saw a coin pusher game. Below is a picture, and here is a <a href="http://www.youtube.com/watch?v=7Iz3-3x0lNE&amp;feature=related" rel="nofollow">video</a> depicting how it works (disregard non-coins). </p> <p><img src="http://www.simpalife.com/wp-content/uploads/Coin-Pushers-or-the-Fair-Quarters-Game.jpg" alt="alt text"></p> <p>Essentially, one has a distribution of coins on a table, and you get to drop one coin at a time at one end, which ends up being pushed into the table, thereby potentially pushing coins off the edge. Note that you can choose where you can drop your coin, width wise. For simplicity, assume coins cannot stack on each other.</p> <p>My question is, are there known limit laws for this game? That is, if I specify a distribution of coins on the table, and then start dropping coins in randomly, what can be said about how the expected number of dropped coins fluctuates, per turn. Consequently, are there various phase transitions as a function of coin density? As well, if I feed coins at a specific spot, what will the distribution of coin falls look like as a function of the table width? Do the boundary conditions (the side walls and the pusher) create interesting "modes" in the coin falling distribution? </p> <p>I would think that this has to do with sand stacking cascades and KPZ growth but, do not have much experience in this area. Or perhaps this is just a simple Galton box that produces a normal distribution?</p> http://mathoverflow.net/questions/128540/generating-random-young-tableaux-a-peculiar-probability-identity Generating Random Young Tableaux: A peculiar probability identity Alex R. 2013-04-23T20:58:52Z 2013-04-25T07:46:43Z <p>In <a href="http://www.math.upenn.edu/~wilf/website/Probabilistic%20proof.pdf" rel="nofollow">the paper by Greene, Nijenhuis and Wilf</a>, an algorithm is proposed for generating uniformly random Young tableaux of shape $\lambda$. The algorithm is to uniformly randomly pick a starting cell, and then do a hook walk algorithm until it terminates at one of the edges of the tableau. Another way of looking at this is to fix a starting cell $(a,b)$, and then start a random hook walk, so that one gets a path </p> <p>$$(a,b)=(a_1,b_1)\rightarrow(a_2,b_2)\rightarrow\cdots\rightarrow (a_k,b_k)=(\alpha,\beta)$$</p> <p>where $(\alpha,\beta)$ is the terminal cell. This defines a probability of hitting terminal cell $(\alpha,\beta)$ given starting cell $(a,b)$. </p> <p>A peculiar observation is made on page 108, that:</p> <p>$$P(\ (\alpha,\beta) \ |\ (a, b)\ ) = P(\ (\alpha,\beta) \ | \ (\alpha, b)\ ) \cdot P(\ (\alpha,\beta)\ |\ (a,\beta) \ )$$</p> <p>In other words the probability of reaching the terminal point is the product of probabilities of starting in the row and column of the terminal point, which amounts to perpetually staying within the respective hooks. The authors point out that they have no obvious direct explanation of this fact.</p> <blockquote> <p>Has anyone come up with an explanation more recently? </p> </blockquote> http://mathoverflow.net/questions/127029/memory-of-uniformly-random-dyck-paths Memory of Uniformly Random Dyck Paths Alex R. 2013-04-10T00:31:01Z 2013-04-10T12:25:09Z <p>Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)=0$ and $S(2n)=0$.</p> <p>Consider picking uniformly random Dyck paths from the set $D$. Let $P_t(x)$ denote the probability distribution of $X_t$ subject to the uniform distribution on Dyck paths. Suppose that $n$ is very large and that I pick a uniformly random Dyck path conditioned on having the first $k$ steps being fixed, where $k=o(n)$. I would like to conclude that $\mathbb{P}(X_t=x | \mbox{first$k$steps})\approx P_t(x)$ for $t>>k$. Is there a straightforward way of doing this? In other words, far away steps become asymptotically independent from the first $k$ steps. In general, is there a way of extending this to uniformly random paths of fixed length on regular graphs?</p> <p>I can see that this is probably related to asking a similar question for brownian bridges. Specifically, I am very interested in seeing how one would obtain explicit bounds for the quantity $|\mathbb{P}(X_t=x | \mbox{first$k$steps})-P_t(x)|$ in terms of $n$ and $t$</p> http://mathoverflow.net/questions/121749/number-of-permutations-with-k-inversions-and-with-a-single-clamped-value Number of Permutations with k-inversions and with a single clamped value Alex R. 2013-02-13T22:18:05Z 2013-03-26T19:22:00Z <p>This question is <a href="http://math.stackexchange.com/questions/300026/number-of-permutations-with-k-inversions-and-with-a-single-clamped-value" rel="nofollow">cross-posted</a> from math.stackexchange because it might be too technical.</p> <p>Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i&lt; j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:</p> <p>$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$</p> <p>If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $$G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t),$$ </p> <p>and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$. </p> <p>I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:</p> <p>$$I_{n}^{\sigma(y)=x}(k)=\sum_{i=0}^{n-1-y}I_{n-1}^{\sigma(y)=x}(k-i)+\sum_{i=n-y+1}^nI^{\sigma(y-1)=x}_{n-1}(k-i)$$</p> <p>where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).</p> <blockquote> <p>Assuming the above is right, is it at all tractable to derive an <em>asymptotic formula</em> for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?</p> </blockquote> <p>As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:</p> <p>$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$</p> <p>where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. <a href="http://academic.csuohio.edu/bmargolius/homepage/inversions/invers.htm#s5" rel="nofollow">Here is a reference for such a calculation.</a></p> <p>Naively, the above formula comes from the <a href="http://en.wikipedia.org/wiki/Pentagonal_number_theorem" rel="nofollow">Euler pentagonal number theorem</a>. I would think one needs a specialized form of this theorem for what I am interested in.</p> <blockquote> <p>Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?</p> </blockquote> http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions/122453#122453 Answer by Alex R. for Box removing operators on partitions Alex R. 2013-02-20T20:46:40Z 2013-02-23T01:54:38Z <p>These are the Coxeter relations, and I believe equivalence comes from a general theorem: Tit's Theorem. For example, if you are willing to accept the Edelemann-Greene correspondence between Young Tableau and reduced words of permutations, then it would be equivalent to show that one can move freely between two reduced words using the above relations (now correspondingly, $d_i$ act on permutations via adjacent transpositions: $d_i(i,i+1)=(i+1,i)$. You can find a proof of <a href="http://www.math.ucsd.edu/~garsia/schur/saga.pdf" rel="nofollow">reduced word equivalence here</a>, page 4, Theorem 1.1.2. Essentially, the proof for tableaux should be of the same flavor: show that you can pass from any word to a carefully chosen canonical word.</p> http://mathoverflow.net/questions/108295/system-of-equations-upper-bound System of Equations Upper Bound Alex R. 2012-09-27T22:52:27Z 2012-10-08T17:55:22Z <p>I asked a related question on math.stackexchange <a href="http://math.stackexchange.com/questions/192549/upper-bound-on-a-system-of-sum-equations" rel="nofollow">here</a> but would now like to obtain a better bound. This question comes from a graph theory problem. I'll restate the new question here:</p> <p>For $i=1,2,\ldots,n$, let $d_i$ be a sequence of <strong>positive integers</strong> satisfying $d_1\geq\cdots\geq d_n$ with $2\leq d_i\leq n-1$, and $r_i$ a sequence of <strong>positive real numbers</strong> that satisfy the following system of equations:</p> <p>$$d_i=\sum_{j=1}^n \frac{r_ir_j}{1+r_ir_j}$$</p> <p>for each $i=1,2\ldots,n$.</p> <p>I have additional constraints that $d_1+\cdots+d_n$ is even and for every $1\leq k\leq n$,</p> <p>$$\sum_{i=1}^k d_i &lt; k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$$</p> <p>(this is the strict Erdos Gallai theorem for the degrees of a graph). </p> <p><strong>Question</strong>: Can we find a qualitative bound on $r_i$ in terms of $n$? I would ideally like a bound of the form $n^c$ for some constant $c$ (that doesn't depend on $n$, $r_i$ or $d_i$). If such a bound doesn't exist, is there a counterexample or are there additional "mild" conditions on the $d_i$'s that can yield such a bound (for example, $d^2_{\mbox{max}}:=d^2_n\leq \frac{1}{2}\sum_{i=1}^nd_i$ gives a bound of $n^7$). ?</p> <p>Notice that in the previous question, a bound of $n^{2n}$ was obtained but, sadly the posted argument doesn't seem to yield a better bound, unless I'm missing something obvious.</p> http://mathoverflow.net/questions/107547/percolation-in-z2-problem-in-the-proof-of-the-existence-of-a-critical-probabi/107585#107585 Answer by Alex R. for Percolation in $Z^2$, problem in the proof of the existence of a critical probability Alex R. 2012-09-19T16:12:16Z 2012-09-19T16:17:35Z <p>I think your formula for $P(N_n=k)$ is false because as you said, paths are dependent on one-another. With that said:</p> <p>Expectation is linear, regardless of dependence. Let $S_n$ be the index of set of SAWs of length $n$ and $\gamma_{ni}$ denote a self avoiding path of length $n$, $i\in S_n$. You write </p> <p>$$N_n=\sum_{i\in S_n} 1_{\gamma_{ni}}$$</p> <p>Now you note that each $\gamma_{ni}$ has probability $p^n$ and $S_n$ has $\sigma_n$ elements in it. Using $E[1_{\gamma_{ni}}]=p^n$, it immediately follows that $E[N_n]=p^n\sigma_n$.</p> http://mathoverflow.net/questions/58554/preferably-rare-audio-video-recordings-of-famous-mathematicians/101695#101695 Answer by Alex R. for (Preferably rare) Audio/Video recordings of famous mathematicians? Alex R. 2012-07-08T18:57:05Z 2012-07-08T18:57:05Z <p><a href="http://www.youtube.com/watch?v=D7Kz_Le7BOc" rel="nofollow">Here is a long video about Richard Courant.</a> Apparently he was one of the first people to own a video camera so there is some really old footage of some of the fathers of modern mathematics. If you scroll to 33:00, you will find footage of David Hilbert shoveling snow! </p> http://mathoverflow.net/questions/101014/fundamental-problems-whose-solution-seems-completely-out-of-reach/101132#101132 Answer by Alex R. for Fundamental problems whose solution seems completely out of reach Alex R. 2012-07-02T10:09:27Z 2012-07-02T12:45:39Z <p>Can we exactly calculate <a href="http://en.wikipedia.org/wiki/Ramsey_theory" rel="nofollow">Ramsey numbers</a>? Erdős once famously remarked:</p> <blockquote> <p>"Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack."</p> </blockquote> http://mathoverflow.net/questions/95308/generating-conditional-random-graphs Generating Conditional Random Graphs Alex R. 2012-04-26T21:35:02Z 2012-04-26T21:51:40Z <p>Let $G(n,p)$ be the usual random graph on $n$ vertices with each edge existing independently with probability $p$ (no self loops , or double edges not are allowed). I would like to simulate the distribution of a random graph given the event $T\geq a$ where $T$ is the number of triangles in the random graph. The natural approach is Metropolis Hastings. I've already found some semi-efficient algorithms that approximate the number of triangles in a given random graph, however I am still at a loss of what Markov chain to pick for a good rate of convergence. I would immensely appreciate a push in the right direction. In particular, some references would be fantastic. Thanks!</p> http://mathoverflow.net/questions/87761/implications-of-half-space-percolation Implications of Half-Space Percolation Alex R. 2012-02-07T04:18:11Z 2012-02-07T04:18:11Z <p>Let $\mathbb{Z}^d$ be the usual $d$-dimensional lattice and let $\mathbb{H}:=\mathbb{Z}^{d-1}\times Z_+$, where $Z_+:=[0,1,2,\ldots]$. If we now consider bond percolation on $\mathbb{H}$, it is a well known result that at the critical probability for $\mathbb{H}$, $p_c(\mathbb{H})$, equals the usual critical probability $p_c$ for the $d$ dimensional lattice. </p> <p>Following Grimmett's <em>Percolation</em> textbook, we learn that for $d\geq 2$, $\theta_\mathbb{H}(p_c)=0$, where $\theta_\mathbb{H}$ is the usual probability of 0 connecting to infinity, in this case for the half-space. The conclusion of this is that if $\theta(p_c)>0$ for $\mathbb{Z}^d$ percolation, then there exists a.s. a unique infinite open cluster in $\mathbb{Z}^d$, which is a.s. partitioned into only finite clusters by ANY division of $\mathbb{Z}^d$ into two half-spaces.</p> <p>My question is, how does this fall short of proving say, $\theta(p_c)=0$ for $d=3$ and so on? It's hard for me to imagine configurations of an infinite cluster even in 3-dimensions that satisfy the slicing criteria above. If I understand correctly, the cluster would need to spiral out radially in all directions and at the very least cross the $x-y$, $y-z$ and $x-z$ planes infinitely many times. It's easy to see that such a construction fails in two dimensions (and rightfully so, $\theta(p_c)=0$ for $d=2$). Where does the difficulty lay? Or rather, if we attempt to rigorously approach a proof in this direction where do we get stuck?</p> http://mathoverflow.net/questions/13230/erdos-conjecture-on-arithmetic-progressions Erdos Conjecture on arithmetic progressions Alex R. 2010-01-28T06:09:38Z 2012-01-29T08:16:20Z <p>Introduction:</p> <p>Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The <a href="http://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions" rel="nofollow">Erdos Conjecture</a> states that A must have arithmetic progressions of arbitrary length. </p> <p>Question:</p> <p>I was wondering how one might go about $\it{categorizing}$ or $\it{generating}$ the divergent series of the form in the introduction above. I'm interested in some particular techniques and I list some examples below:</p> <p>If we let $S$ be the set of such divergent series: $S=\left[ A: \sum_{n\in A}\frac{1}{n}=\infty, \ A\in\mathbb{N} \right]$, what kind of operations are there that would make S a group, or at the very least a semigroup? I'm rather vague on what the operatons should be for a reason, because although I presume trivial operations exist, their usefulness in understanding the members of $S$ would be questionable. </p> <p>Alternately, can one look at these divergent sums through the technique of Ramanujan summation (think: $1+2+3+\ldots =^R -\frac{1}{12}$, $R$ emphasizing Ramanujan summation)? The generalizations of Ramanujan summation (a good reference <a href="http://algo.inria.fr/seminars/sem01-02/delabaere2.pdf" rel="nofollow"> here </a>) allow one to assign values to some of these series and give some measure of what kind of divergence is occurring. Moreover, basic series manipulations that hold for convergent series tend to carry over to Ramanujan summation, so can one perhaps look at the set $S$ above as a set of equivalence classes in the sense of two elements being equivalent if they share the same Ramanujan summation constant. </p> <p>Thanks in advance for any input!</p> http://mathoverflow.net/questions/1890/describe-a-topic-in-one-sentence/43883#43883 Answer by Alex R. for Describe a topic in one sentence. Alex R. 2010-10-27T21:44:37Z 2012-01-07T17:53:05Z <p>Analytic Number Theory: log log log log log...</p> <p>Did I see that quote in Havil's book <a href="http://press.princeton.edu/titles/7494.html" rel="nofollow"><em>Gamma</em></a>?</p> http://mathoverflow.net/questions/41771/pdes-as-a-tool-in-other-domains-in-mathematics/83153#83153 Answer by Alex R. for PDEs as a tool in other domains in mathematics Alex R. 2011-12-11T00:39:09Z 2011-12-11T00:39:09Z <p>Some other probability PDE techniques:</p> <p>1) Percolation: The Aizenman Barsky proof of exponential decay in subcritical percolation hinged on establishing a number of differential inequalities.</p> <p>2) Conformal Invariance and SLE: Many conformal invariance proofs reduce to showing that the discrete stochastic process in question satisfies a Riemann Hilbert boundary value problem along with defining a flow on the state space which is divergence and curl free. This makes it clear how Cardy's formula arises as the hypergeometric function which solves the appropriate differential equation. </p> http://mathoverflow.net/questions/80267/guessing-game-with-guess-cost Guessing game with guess cost Alex R. 2011-11-07T03:54:06Z 2011-11-07T03:59:59Z <p>This is a question about <a href="http://projecteuler.net/problem=328BlockquoteBlockquote" rel="nofollow">Problem 328</a> on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. In particular, I am interested in <em>analytic</em> results about the cost function in the problem. Thus far, this question has been highly resistant to any analytic results on my part. Notice that I am NOT asking for an algorithm that solves this question. Let me first establish some terminology.</p> <p>First let's generalize the game to an interval $[a,b]$ instead of just $[1,n]$. Define $C(a,b)$ to be the best-worst-case cost of searching through interval [a,b]. The most obvious recursive approach to the problem would be to notice that if the first guess is $p$, then:</p> <p>$C(a,b) = \min_{p\in [a,b]} ( p + \max${ $C(a,p-1),C(a,p+1)$ } $)$</p> <p>From here on, i'll refer to the first guess $p$ as the "pivot." Notice that any strategy of guesses can be defined as a binary tree $T$ where a leftward branch represents "your guess is higher than the hidden number" and the rightward represents "your guess is lower than the hidden number." In this way we can catalog the best-worst-case strategies, $T_1,\ldots,T_k$.</p> <blockquote> <p>Question 1: can it be shown that the pivots of $T_i$ are all the same? </p> </blockquote> <p>While the answer to question 1 is likely "no" without further assumptions, let me add this: I think that it may be possible to say "yes" if we allow reorganization of the sub-trees of $T_i$, by moving the desired pivot to the top of the tree. That leaves the question of what is the asymptotic number of pivots is for $C(1,n)$ for large $n$?</p> <p>In my current algorithm I have observed the following behavior of pivots for $C(1,n)$:</p> <p><img src="http://i.imgur.com/BL68Z.jpg" alt="alt text"></p> <p>Basically, the pivot for each successive $n$ goes up by 1 most of the time, except when an unbalancing occurs causing a drop. I suspect that the max function above tends to pick the right interval cost except at the drop points. For those interested, the drop points occur at 4,19,51 and so on, with the interval between drops growing exponentially. </p> <blockquote> <p>Question 2: Can one show that compared to a previous pivot either $p$ must increase exactly by 1 most of the time or otherwise drop? Can these drop points be predicted asymptotically as $n$ grows?</p> </blockquote> <p>Finally, it's easy enough to show right-sided monotonicity: $C(a,b) \leq C(a,b+1)$. What interests me is how $C(a,b)$ relates to $C(a+1,b)$. This would be related to question 2 as sudden switches of inequality here would likely signify a drop. </p> http://mathoverflow.net/questions/63749/dimensional-analysis-in-mathematics Dimensional Analysis in Mathematics Alex R. 2011-05-02T23:02:13Z 2011-10-28T04:14:41Z <p>Is there a sensible and useful definition of units in mathematics? In other words, is there a theory of dimensional analysis for mathematics?</p> <p>In physics, an extremely useful tool is the <a href="http://en.wikipedia.org/wiki/Buckingham_Pi" rel="nofollow">Buckingham Pi theorem</a>. This allows for surprisingly accurate estimates that can predict on what parameters a quantity depends on. Examples are numerous and can be found in this short <a href="http://www.math.ntnu.no/~hanche/notes/buckingham/buckingham-a4.pdf" rel="nofollow">reference</a>. One such application (pages 6-7 of the last reference) can derive the dispersion relation exactly for short water ripples in deep water, in terms of surface tension, density and wave number. In this case an exact relation is derived, but in general one expects to be off by a constant. The point is that this gives quick insight into an otherwise complex problem.</p> <p>My question is: can similar techniques be used in mathematics? </p> <p>I envision that one application could be to derive asymptotic results for say, ode's and pde's under certain asymptotic assumptions for the coefficients involved. For any kind of Fourier analysis, dimensions naturally creep up from physics if we think about say, time and frequency. I find myself constantly using basic dimensional analysis just as a sanity check on whether a quantity makes sense in these areas.</p> <p>Otherwise, let's say I'm working on a problem involving some estimate on a number theoretic function. If I have a free parameter, can I quickly figure out the order of the quantity i'm interested in in terms of my other fixed parameters?</p> http://mathoverflow.net/questions/46431/poincare-recurrence-and-dense-sets Poincare Recurrence and Dense Sets Alex R. 2010-11-17T23:50:03Z 2011-10-04T18:37:52Z <p>This is kind of a spin-off of the question asked <a href="http://mathoverflow.net/questions/46414/how-quickly-will-billiard-trajectories-cluster" rel="nofollow">here</a>. Take the interval $X:=[0,1]$ with $\mu$ being standard Lebesgue measure. Let $f$ be a measure preserving map $f:[0,1]\rightarrow [0,1]$. The Poincare Recurrence theorem tells us that if I pick a measurable set $E\subset [0,1]$, then under iterations of $f$ almost every point in $E$ returns to $E$ infinitely often, i.e.</p> <p>$\mu\left({x\in E: \ \exists N, \mbox{ such that } \forall n\geq N, \ f^n(x)\notin E}\right)=0$</p> <p>Call the set of exceptions above $M$. My question is:</p> <blockquote> If I specify an $f$, for what class of sets $E$ in $X$ is $M$ not dense? I am interested in two cases: <p></p> <p>1) "dense" with respect to $X$, if $E$ is dense in $X$</p> <p>2) "dense" with respect to $E$</p> </blockquote> <p>For example, let $E=\mathbb{Q}\cap[0,1]$ and $f(E):=E+\phi$ where $\phi$ is irrational. Then $M=E$, which of course is not a contradiction since $\mu(M)=\mu(E)=0$. On the other hand, throw in the set $H:={n\cdot \phi: n\in \mathbb{N}}$, so that $E':=H\cup E$. In this case we still have $M=E$. As well, it looks like the class of sets I'm interested in is $H\cup {\mbox{not a dense set in X}}$.</p> <p>Note: My original motivation for asking this was to try and conceptualize the Poincare recurrence theorem for a human physicist. If I were looking at the phase plot of balls on a billiard table at a specific time, I would only be able to give imprecise measurements of both position and velocity. In this case, it seems that in order to invoke Poincare recurrence, I would need small intervals around every point to recur perfectly, in the sense that $M=\emptyset$. Perhaps this IS the case if $f$ arises from some nice ODE, but I'm interested in a more general setting. I also don't really want to require that $\mu(M)>0$, which is why I feel asking about denseness is more appropriate. </p> http://mathoverflow.net/questions/76133/dynamical-systems-for-undergraduate-students/76142#76142 Answer by Alex R. for Dynamical Systems for undergraduate students Alex R. 2011-09-22T17:34:13Z 2011-09-22T17:34:13Z <p>I would recommend reading through <a href="http://www.google.com/products/catalog?q=nonlinear+dynamics+and+chaos&amp;oe=utf-8&amp;rls=org.mozilla%3Aen-US%3Aofficial&amp;client=firefox-a&amp;um=1&amp;ie=UTF-8&amp;tbm=shop&amp;cid=3730006166953307001&amp;sa=X&amp;ei=rW57Tpy7DMnt0gH04uzAAg&amp;ved=0CEAQ8wIwAQ" rel="nofollow"><em>Nonlinear dynamics and chaos: with applications to physics, biology, chemistry, and engineering</em></a> by Steven Strogatz. He does a great job of motivating the applications of the field to various branches of science with a plethora of exercises. I wouldn't say it's entirely rigorous at times, but it covers a huge amount of material which should give you plenty to think about if you want to do a research topic. Out of all the books I've seen on the subject, his is probably the only elementary one that tackles renormalization techniques and universality, involving <a href="http://en.wikipedia.org/wiki/Feigenbaum_constants" rel="nofollow">Feigenbaum's constant</a>. </p> http://mathoverflow.net/questions/75345/exponential-equations/75348#75348 Answer by Alex R. for Exponential Equations Alex R. 2011-09-13T19:59:17Z 2011-09-13T19:59:17Z <p>If you want, you can use <a href="http://en.wikipedia.org/wiki/Lambert_W_function" rel="nofollow">Lambert's W function</a>. Let $z:=x+4$, so that the equation becomes $3^{z-4}=z$, so that $-3^{-4}=-z3^{-z}$, which upon inverting with Lambert's $W$ gives:</p> <p>$x=-\frac{W(-\ln(3)3^{-4})}{\ln(3)}-4$</p> <p>In particular, $W(r)$ has a nice taylor expansion:</p> <p>$W(r)=\sum_{n=1}^\infty \frac{(-1)^{n-1}n^{n-2}}{(n-1)!}r^n$</p> http://mathoverflow.net/questions/74552/a-formal-definition-of-scaling-limits/74595#74595 Answer by Alex R. for A formal definition of Scaling Limits? Alex R. 2011-09-05T16:35:33Z 2011-09-05T16:35:33Z <p>I think the main issue you'll encounter with scaling limits and conformal invariance will be that it is a very new subject. Many of the papers will be very high level or still in preprint with details missing. </p> <p>Here's a list of references that helped me learn the subject. I'll try to comment on some of them later on when time permits. I would first start with <a href="http://www.math.uchicago.edu/~lawler/pims2010.pdf" rel="nofollow">"Scaling Limits and SLE"</a> by Greg Lawler. This set of notes is in context of self avoiding walks and how they connect to SLE and you'll find they quickly dive into scale invariance and conformal invariance. </p> <p>If you are further interested in proofs, I would consult Lawler's "Conformally Invariant Processes in the Plane." This book gives very rigorous formulations of SLE and tackles a myriad of technical difficulties. </p> <p>Next I would look at <a href="http://arxiv.org/abs/0708.0032" rel="nofollow">"Toward conformal invariance of 2D lattice models"</a> by Smirnov. Here you'll be introduced to the notion of the duality between holomorphic martingales and scale invariance. In particular, you need to understand how discrete complex analysis connects with conformal invariance. I would hold out for proofs of many of the results for now.</p> <p>Now you'll probably want to look at some simpler examples. I would first start trying to understand the proof of Cardy's Formula. Geoffrey Grimmett has an excellent set of lecture notes, "Probability on Graphs" which should be available off Grimmett's website (I can't seem to access it right now). As well I would consult the original paper by Smirnov, <a href="http://arxiv.org/abs/0909.4499" rel="nofollow">"Critical percolation in the plane"</a>. I'll add here that the proof of Cardy's formula doesn't need the full machinery of holomorphic martingales because of the really nice symmetries Smirnov observed. What IS important though is how the Riemann Hilbert boundary conditions are set up. </p> <p>One of the big issues with discrete complex analysis is how to rigorously define discrete holomorphic functions on graphs. If you want the gory details, <a href="http://arxiv.org/abs/0810.2188" rel="nofollow">"Discrete complex analysis on isoradial graphs"</a> by Chelkak and Smirnov is a good place to look. </p> http://mathoverflow.net/questions/66084/open-problems-with-monetary-rewards/66227#66227 Answer by Alex R. for Open problems with monetary rewards Alex R. 2011-05-27T20:54:28Z 2011-05-27T20:54:28Z <p>I remember reading in Havil's book <em>Gamma</em> that supposidly Hardy was willing to offer his Savilian Chair at Oxford University to anyone who could prove that the Euler Mascheroni constant is irrational. I wonder if this offer still stands?</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/63846#63846 Answer by Alex R. for What is the easiest randomized algorithm to motivate to the layperson? Alex R. 2011-05-03T20:32:20Z 2011-05-03T20:38:14Z <p>How about using Monte Carlo for deciphering encrypted messages? <a href="http://www.scribd.com/doc/36753044/Diaconis-P-the-Markov-Chain-Monte-Carlo-Revolution" rel="nofollow">This</a> paper by Diaconis deciphers a prison message that involves prison lingo, multiple languages, bad spelling and centers around a prison slashing. The younger TV-detective-show obsessed crowd will love it. The algorithm is very simple. Showing precise rate-of-convergence estimates is a bit if a mixing time problem, but perhaps they can take it on faith?</p> <p>I remember reading it a while ago and feeling inspired by random algorithms. I'll be honest I know very little cryptography, but it seems to me that the given problem in the reference can ONLY be solved by a randomized algorithm. The fact that it converges so quickly and even has a moderate window for "data corruption" (such as bad spelling and different languages) really makes you appreciate the power of this stuff.</p> http://mathoverflow.net/questions/62949/positive-definite-functions-and-fourier-transforms Positive-Definite Functions and Fourier Transforms Alex R. 2011-04-25T18:19:36Z 2011-04-26T01:19:00Z <p>Bochner's theorem states that a positive definite function is the Fourier transform of a finite Borel measure. As well, an easy converse of this is that a Fourier transform must be positive definite. </p> <p>My question is: is there a high-brow explanation for why positive definiteness and Fourier transforms go hand-in-hand? </p> <p>As I understand it, positive definiteness imposes wonderfully strong regularity conditions on the function. We immediately deduce that the function is bounded above at its value at 0, that it is non-negative at 0 and that continuity at 0 implies continuity everywhere. </p> <p>A leading example I have in mind comes from probability. One can show (Levy's Theorem) that a sum of iid rv converges weakly to some probability distribution by considering the product of characteristic functions and showing that its tail converges to 1 around an interval containing 0, so by positive definiteness and by the identity $1-\mbox{Re} \phi(2t) \leq 4(1-\mbox{Re} \phi(t))$ this implies convergence to a degenerate distribution. It just seems rather mysterious to me how this kind of local regularity becomes global. </p> <p><strong>Edit:</strong></p> <p>To be a little more specific, I understand that the Radon Nikodym derivative is positive and $e^{ix}$ is positive definite. I am more interested in consequences of positive-definiteness on the regularity of the function. For example, if one takes the 2x2 positive definite matrix associated with the function and considers its determinant, it follows that $|f(x)|\leq |f(0)|$. If I take the 3x3 positive definite matrix, I can conclude that if $f$ is continuous at 0, it is then continuous everywhere. My issue is that these types of arguments give me no intuition at all as to what positive definiteness is. </p> <p>Let me thus add an additional question: what is it about positive definiteness that adds such regularity conditions? </p> http://mathoverflow.net/questions/62782/random-walk-origin-return-monotinicity Random walk origin return monotinicity Alex R. 2011-04-23T22:00:08Z 2011-04-26T00:10:02Z <p>Consider a Markov chain on $\mathbb{Z}^d$ with transition kernel $P$ for adjacent vertices (non-diagonal). Essentially this is a $d$ dimensional random walk with the probability of a transition dependent on it's location in the grid. This comes from a random conductance model. The theorem that concerns me is a general result for Markov chains, but I leave this motivation to assist in its proof (see below).</p> <p>Let $P^{2k}(0,0)$ be the probability of going from the origin and back in $2k$ steps. Moreover, suppose $P$ is reversible. The theorem that concerns me is: </p> <blockquote> <p>$P^{2n}(0,0)$ is decreasing in $n$. </p> </blockquote> <p>I am interested in a probabilistic proof of this. The proof that I know is of a spectral nature:</p> <p>Define $\langle f,g\rangle:= \sum_{X\in\mathbb{Z}^d} \pi(x)f(x)g(x)$,</p> <p>where $\pi(x)$ is the stationary measure. This gives an inner product on $L^2(\mathbb{Z}^d)$. In the case of a random conductance model, $\pi(x)$ would be the sum of random edge weights at $x$. </p> <p>Then</p> <p>$P^{2k}(0,0)=\langle \delta_0,P^{2k}\delta_0\rangle$,</p> <p>and since $P$ is self adjoint with $\|P\|_2\leq 1$, the desired result follows. </p> <p>I have tried various approaches such as conditioning on the hitting times of the origin and as well trying to prove the result by induction. I would like to see a proof that showcases a probabilistic argument. For example, is it possible to show the result from the machinery of evolving sets of Morris and Peres?</p> http://mathoverflow.net/questions/62866/recent-applications-of-mathematics/62872#62872 Answer by Alex R. for Recent Applications of Mathematics Alex R. 2011-04-24T23:06:23Z 2011-04-24T23:06:23Z <p>How about applications of discrete complex analysis to statistical physics? There was a surge of work this past decade on the subject, such as proofs of conformal invariance of 2-D models (Ising, Potts, Spinglass, O(n),etc.). Before, there were mainly unrigorous physics arguments to prove the various facts involved, such as the value of the Honeycomb Constant. The machinery of SLE and discrete complex analysis has been extremely insightful in the proofs involved. Much of the methodology is based on the foundational work done by Onsager and Baxter decades before. </p> http://mathoverflow.net/questions/60457/elementaryshortuseful/60504#60504 Answer by Alex R. for Elementary+Short+Useful Alex R. 2011-04-03T23:16:40Z 2011-04-04T17:27:23Z <p>Singular Value Decomposition, probably one of the most useful and ubiquitous concepts out there. Half the time can be devoted to listing all the synonyms it goes by in various fields such as statistics and finance. </p> http://mathoverflow.net/questions/59840/surprising-and-useful-physical-intuition-for-mathematical-objects/59990#59990 Answer by Alex R. for Surprising and Useful Physical Intuition for Mathematical Objects Alex R. 2011-03-29T17:11:00Z 2011-03-29T17:20:43Z <p>I remember from Folland's PDE book an anecdote about Green convincing himself of the existence of a Green's Function:</p> <p>Let $\Omega$ be a vacuum and $S$ a perfectly conducting shell grounded to zero potential. Place a negative charge at $x\in \Omega$. This induces a positive charge on the shell $S$. Indeed, the Green's Function $G(x,y)$ is the induced charge at a point $y$.</p> <p>I would also add that the physical interpretations of gradients, divergence and curl are indespensible for REMEMBERING the various theorems of Gauss, Stokes and Green. For example, the curl of a velocity field is twice the angular acceleration, a fact that facilitates the order of differences of partials in the curl operator. </p> http://mathoverflow.net/questions/57656/standard-model-of-particle-physics-for-mathematicians/57712#57712 Answer by Alex R. for Standard model of particle physics for mathematicians Alex R. 2011-03-07T18:22:34Z 2011-03-07T20:28:27Z <p>For a straightforward and quick intro to the standard model, try "<a href="http://books.google.com/books?id=8Aa4uS6ZcJEC&amp;printsec=frontcover&amp;dq=from+finite+groups+to+lie+groups&amp;hl=en&amp;ei=GSF1TayKLJG6sQOg9Ly2Cw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">Groups and Symmetries: From Finite Groups to Lie Groups</a>" by Kosmann-Schwarzbach. It's rigorous and does a good job motivating the standard model in its later chapters. You'll learn what a quark is from the mathematical point of view.</p> <p>In addition, Griffith's textbook on elementary particle physics would be a good historical supplement. It took physicists many years and guesses to work out the standard model. The first few chapter of Griffith's book read like a good mystery novel. Plus, you'll be a little more familiar with weird concepts like isospin, strangeness and color. </p> <p>Finally, for more talk related to particle physics the classic text "Quarks and Leptons" by Halzen and Martin is really in-depth, but does assume a good grasp on physics. It does a good job of explaining concepts in the context of group theory. I would say, try to read the discussions in it rather then get bogged down in the physics. </p> http://mathoverflow.net/questions/57299/how-many-projects-do-you-work-on-concurrently How many projects do you work on concurrently? Alex R. 2011-03-03T23:07:28Z 2011-03-04T00:14:02Z <p>I was wondering how many concurrent research projects a typical math researcher works on at a given time. I ask because I currently have the oppertunity to start a second project on something I'm fairly familiar with (background reading-wise). One of the main reasons I'm considering taking in a second project is because the first one is going rather slowly (I've hit a roadblock which is potentially insurmountable). If you do work on multiple projects, do you tend to jump between them the moment you get stuck or do you dedicate your full attention to one of them, for say, a week? What's your secret to staying productive?</p> <p>Just to be specific, let's limit "projects" to writing (contributing to) papers you intend to publish in the near future. As well, "working on" should be interpreted as dedicating a sizable chunk of your time to researching the problem at hand. I do not wish to count projects that you put aside for more than a few weeks until you have an inspiration.</p> <p>I understand the question is somewhat subjective and the obvious answer is that it depends on the person in question. The way I see it is when you work on multiple problems, part of the reason is that you are hedging your bets on which problem will end up solved. However, I'm just interested in the overall average (which im guessing has little variance) and more importantly whether it's bigger than 1.</p> http://mathoverflow.net/questions/133436/random-rsk-and-plancherel-measure Comment by Alex R. Alex R. 2013-06-12T16:54:50Z 2013-06-12T16:54:50Z @Daniel Parry: I've tried up to $n=10,000$. http://mathoverflow.net/questions/129759/modern-mathematical-achievements-accessible-to-undergraduates Comment by Alex R. Alex R. 2013-05-06T00:11:00Z 2013-05-06T00:11:00Z Could you clarify the time frame you have in mind? A single lecture, a week, or a month? http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/128877#128877 Comment by Alex R. Alex R. 2013-04-27T04:03:01Z 2013-04-27T04:03:01Z It's hard to think of a worse way of computing eigenvalues numerically than calculating and then estimating the zeros of the characteristic polynomial http://mathoverflow.net/questions/128540/generating-random-young-tableaux-a-peculiar-probability-identity/128690#128690 Comment by Alex R. Alex R. 2013-04-26T02:39:17Z 2013-04-26T02:39:17Z Thank you for your answer and links. I'm glad I'm not alone in my bewilderment as to why one gets such a nice identity. I was wondering if you happen to know any other algorithms for generating uniformly random Young Tableaux of a fixed shape $\lambda$? I'm aware that you were able to construct an algorithm akin to bubble-sorting. Do you happen to know of others? http://mathoverflow.net/questions/127043/summing-characters-of-the-symmetric-group-over-derangements-enumerative-combinat Comment by Alex R. Alex R. 2013-04-10T05:38:49Z 2013-04-10T05:38:49Z When you write notation such as $\sum_\lambda$ are you implying that you're summing over all possible tableaux shapes? If yes, then the $h_n$ formula is the sum over a fixed shape, whereas your sum just before your $e^{-h_1}h_n$ conclusion is probably over all shapes. http://mathoverflow.net/questions/127043/summing-characters-of-the-symmetric-group-over-derangements-enumerative-combinat Comment by Alex R. Alex R. 2013-04-10T05:32:08Z 2013-04-10T05:32:08Z If it's not too much trouble, please Tex the problem statement into your question to avoid a future dead link. http://mathoverflow.net/questions/108295/system-of-equations-upper-bound Comment by Alex R. Alex R. 2012-10-12T20:24:21Z 2012-10-12T20:24:21Z @Brendon McKay: sorry I said something dumb earlier. Indeed the K-star gives order $n^2$ and I of no better condition. All I know is that the existence of the $r_i$ is guaranteed whenever the strict Erdos Gallai condition is satisfied. http://mathoverflow.net/questions/108295/system-of-equations-upper-bound Comment by Alex R. Alex R. 2012-10-08T17:54:43Z 2012-10-08T17:54:43Z @Dima Pasechnik: No, but I see my word ordering might make it seem like that. I'll change it, thanks. http://mathoverflow.net/questions/108295/system-of-equations-upper-bound Comment by Alex R. Alex R. 2012-10-05T02:22:35Z 2012-10-05T02:22:35Z @Gerhard Paseman: It's true that you can have 1 or 0 in the degree sequence. However, if $d_i=0$, then unless $r_k$ are all zero, it would mean $r_i$ is zero. Effectively I'm trying to look at the worst case scenario when $d_i\neq 0$. I'm discounting $d_i=1$ for more specific reasons related to what I'm trying to apply this too. http://mathoverflow.net/questions/101382/hammerstein-integral-equation-with-inverse-of-the-solution Comment by Alex R. Alex R. 2012-07-05T14:19:02Z 2012-07-05T14:19:02Z If you differentiate the equation twice in t, you can get $u′′(t)+\omega^2 u(t)=0$ so $u(t)=A\cos(\omega t+\beta)$,which can then be solved by plugging it back into the original equation and plugging in something like $t=0$. Something about this feels quite strange though because the units don′t make physical sense. u(t) looks like some sort of signal that depends on time but $\phi$ is a phase shift of radians. Are you sure this equation is correct? http://mathoverflow.net/questions/101014/fundamental-problems-whose-solution-seems-completely-out-of-reach/101132#101132 Comment by Alex R. Alex R. 2012-07-02T12:46:02Z 2012-07-02T12:46:02Z @alvarezpaiva: Thanks! Corrected http://mathoverflow.net/questions/99300/is-pi-well-approximable Comment by Alex R. Alex R. 2012-06-11T14:38:08Z 2012-06-11T14:38:08Z yes: <a href="http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others" rel="nofollow" title="are some numbers more irrational than others">mathoverflow.net/questions/53724/&hellip;</a> http://mathoverflow.net/questions/95308/generating-conditional-random-graphs Comment by Alex R. Alex R. 2012-04-29T20:47:37Z 2012-04-29T20:47:37Z @Alekk: If I do importance sampling, for my importance sampling distribution would I pick $G(n,p')$ where say $p' &gt;&gt; p$? My reasoning is that I will ultimately need to compute ratios of densities and for even something as simple as triangle counts, while I can count the number of triangles in a particular instance of $G(n,p)$, I have no way of knowing what the normalization factor is (for say $P(T=a)$) http://mathoverflow.net/questions/95308/generating-conditional-random-graphs Comment by Alex R. Alex R. 2012-04-27T18:36:08Z 2012-04-27T18:36:08Z @Alekk: my apologies for being vague. Yes in particular I would be looking at such things as the number of cliques. My hope is that for large (but not too large!) $n$ I can do some basic counting to check some estimates that I have. http://mathoverflow.net/questions/95308/generating-conditional-random-graphs Comment by Alex R. Alex R. 2012-04-27T02:13:21Z 2012-04-27T02:13:21Z @Anthony Quas: I would be interested in all (fixed) values of $p$. What I am sure of is the number of triangles is expected to be much less than $a$, which translates to $P(T\geq a)$ being very small by itself.