User alex r. - MathOverflow

Random RSK and Plancherel Measure

2013-06-11T22:47:24Z

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 recording tableau) 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.

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.

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:

Coin Pusher Game

2011-09-13T19:48:17Z

While doing laundry at my local laundromat, I saw a coin pusher game. Below is a picture, and here is a video depicting how it works (disregard non-coins).

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.

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?

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?

Generating Random Young Tableaux: A peculiar probability identity

2013-04-23T20:58:52Z

In the paper by Greene, Nijenhuis and Wilf, 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

$$(a,b)=(a_1,b_1)\rightarrow(a_2,b_2)\rightarrow\cdots\rightarrow (a_k,b_k)=(\alpha,\beta)$$

where $(\alpha,\beta)$ is the terminal cell. This defines a probability of hitting terminal cell $(\alpha,\beta)$ given starting cell $(a,b)$.

A peculiar observation is made on page 108, that:

$$P(\ (\alpha,\beta) \ |\ (a, b)\ ) = P(\ (\alpha,\beta) \ | \ (\alpha, b)\ ) \cdot P(\ (\alpha,\beta)\ |\ (a,\beta) \ )$$

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.

Has anyone come up with an explanation more recently?

Memory of Uniformly Random Dyck Paths

2013-04-10T00:31:01Z

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$.

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?

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$

Number of Permutations with k-inversions and with a single clamped value

2013-02-13T22:18:05Z

This question is cross-posted from math.stackexchange because it might be too technical.

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< 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:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

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),$$

and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

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:

$$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)$$

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).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$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},$$

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. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

Answer by Alex R. for Box removing operators on partitions

2013-02-20T20:46:40Z

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 reduced word equivalence here, 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.

System of Equations Upper Bound

2012-09-27T22:52:27Z

I asked a related question on math.stackexchange here but would now like to obtain a better bound. This question comes from a graph theory problem. I'll restate the new question here:

For $i=1,2,\ldots,n$, let $d_i$ be a sequence of positive integers satisfying $d_1\geq\cdots\geq d_n$ with $2\leq d_i\leq n-1$, and $r_i$ a sequence of positive real numbers that satisfy the following system of equations:

$$d_i=\sum_{j=1}^n \frac{r_ir_j}{1+r_ir_j}$$

for each $i=1,2\ldots,n$.

I have additional constraints that $d_1+\cdots+d_n$ is even and for every $1\leq k\leq n$,

$$\sum_{i=1}^k d_i < k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$$

(this is the strict Erdos Gallai theorem for the degrees of a graph).

Question: 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$). ?

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.

Answer by Alex R. for Percolation in $Z^2$, problem in the proof of the existence of a critical probability

2012-09-19T16:12:16Z

I think your formula for $P(N_n=k)$ is false because as you said, paths are dependent on one-another. With that said:

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

$$N_n=\sum_{i\in S_n} 1_{\gamma_{ni}}$$

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$.

Answer by Alex R. for (Preferably rare) Audio/Video recordings of famous mathematicians?

2012-07-08T18:57:05Z

Here is a long video about Richard Courant. 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!

Answer by Alex R. for Fundamental problems whose solution seems completely out of reach

2012-07-02T10:09:27Z

Can we exactly calculate Ramsey numbers? Erdős once famously remarked:

"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."

Generating Conditional Random Graphs

2012-04-26T21:35:02Z

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!

Implications of Half-Space Percolation

2012-02-07T04:18:11Z

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.

Following Grimmett's Percolation 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.

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?

Erdos Conjecture on arithmetic progressions

2010-01-28T06:09:38Z

Introduction:

Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.

Question:

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:

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.

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 here ) 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.

Thanks in advance for any input!

Answer by Alex R. for Describe a topic in one sentence.

2010-10-27T21:44:37Z

Analytic Number Theory: log log log log log...

Did I see that quote in Havil's book Gamma?

Answer by Alex R. for PDEs as a tool in other domains in mathematics

2011-12-11T00:39:09Z

Some other probability PDE techniques:

1) Percolation: The Aizenman Barsky proof of exponential decay in subcritical percolation hinged on establishing a number of differential inequalities.

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.

Guessing game with guess cost

2011-11-07T03:54:06Z

This is a question about Problem 328 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 analytic 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.

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:

$C(a,b) = \min_{p\in [a,b]} ( p + \max${ $C(a,p-1),C(a,p+1)$ } $)$

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$.

Question 1: can it be shown that the pivots of $T_i$ are all the same?

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$?

In my current algorithm I have observed the following behavior of pivots for $C(1,n)$:

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.

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?

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.

Dimensional Analysis in Mathematics

2011-05-02T23:02:13Z

Is there a sensible and useful definition of units in mathematics? In other words, is there a theory of dimensional analysis for mathematics?

In physics, an extremely useful tool is the Buckingham Pi theorem. 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 reference. 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.

My question is: can similar techniques be used in mathematics?

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.

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?

Poincare Recurrence and Dense Sets

2010-11-17T23:50:03Z

This is kind of a spin-off of the question asked here. 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.

$\mu\left({x\in E: \ \exists N, \mbox{ such that } \forall n\geq N, \ f^n(x)\notin E}\right)=0$

Call the set of exceptions above $M$. My question is:

If I specify an $f$, for what class of sets $E$ in $X$ is $M$ not dense? I am interested in two cases:

1) "dense" with respect to $X$, if $E$ is dense in $X$

2) "dense" with respect to $E$

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}}$.

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.

Answer by Alex R. for Dynamical Systems for undergraduate students

2011-09-22T17:34:13Z

I would recommend reading through Nonlinear dynamics and chaos: with applications to physics, biology, chemistry, and engineering 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 Feigenbaum's constant.

Answer by Alex R. for Exponential Equations

2011-09-13T19:59:17Z

If you want, you can use Lambert's W function. 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:

$x=-\frac{W(-\ln(3)3^{-4})}{\ln(3)}-4$

In particular, $W(r)$ has a nice taylor expansion:

$W(r)=\sum_{n=1}^\infty \frac{(-1)^{n-1}n^{n-2}}{(n-1)!}r^n$

Answer by Alex R. for A formal definition of Scaling Limits?

2011-09-05T16:35:33Z

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.

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 "Scaling Limits and SLE" 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.

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.

Next I would look at "Toward conformal invariance of 2D lattice models" 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.

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, "Critical percolation in the plane". 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.

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, "Discrete complex analysis on isoradial graphs" by Chelkak and Smirnov is a good place to look.

Answer by Alex R. for Open problems with monetary rewards

2011-05-27T20:54:28Z

I remember reading in Havil's book Gamma 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?

Answer by Alex R. for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-03T20:32:20Z

How about using Monte Carlo for deciphering encrypted messages? This 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?

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.

Positive-Definite Functions and Fourier Transforms

2011-04-25T18:19:36Z

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.

My question is: is there a high-brow explanation for why positive definiteness and Fourier transforms go hand-in-hand?

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.

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.

Edit:

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.

Let me thus add an additional question: what is it about positive definiteness that adds such regularity conditions?

Random walk origin return monotinicity

2011-04-23T22:00:08Z

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).

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^{2n}(0,0)$ is decreasing in $n$.

I am interested in a probabilistic proof of this. The proof that I know is of a spectral nature:

Define $\langle f,g\rangle:= \sum_{X\in\mathbb{Z}^d} \pi(x)f(x)g(x)$,

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$.

Then

$P^{2k}(0,0)=\langle \delta_0,P^{2k}\delta_0\rangle$,

and since $P$ is self adjoint with $\|P\|_2\leq 1$, the desired result follows.

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?

Answer by Alex R. for Recent Applications of Mathematics

2011-04-24T23:06:23Z

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.

Answer by Alex R. for Elementary+Short+Useful

2011-04-03T23:16:40Z

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.

Answer by Alex R. for Surprising and Useful Physical Intuition for Mathematical Objects

2011-03-29T17:11:00Z

I remember from Folland's PDE book an anecdote about Green convincing himself of the existence of a Green's Function:

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$.

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.

Answer by Alex R. for Standard model of particle physics for mathematicians

2011-03-07T18:22:34Z

For a straightforward and quick intro to the standard model, try "Groups and Symmetries: From Finite Groups to Lie Groups" 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.

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.

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.

How many projects do you work on concurrently?

2011-03-03T23:07:28Z

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?

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.

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.

Comment by Alex R.

2013-06-12T16:54:50Z

@Daniel Parry: I've tried up to $n=10,000$.

Comment by Alex R.

2013-05-06T00:11:00Z

Could you clarify the time frame you have in mind? A single lecture, a week, or a month?

Comment by Alex R.

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

Comment by Alex R.

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?

Comment by Alex R.

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.

Comment by Alex R.

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.

Comment by Alex R.

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.

Comment by Alex R.

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.

Comment by Alex R.

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.

Comment by Alex R.

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?

Comment by Alex R.

2012-07-02T12:46:02Z

@alvarezpaiva: Thanks! Corrected

Comment by Alex R.

2012-06-11T14:38:08Z

yes: mathoverflow.net/questions/53724/…

Comment by Alex R.

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' >> 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)$)

Comment by Alex R.

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.

Comment by Alex R.

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.