User eckhard - MathOverflow

Continuum limit of first-passage percolation paths

2013-03-19T16:20:53Z

A few years ago, when I was working on first-passage percolation problems, I thought about the following problem. Recently it came back to my mind.

Consider, for some $\delta=n^{-1}>0$, the grid $\delta\mathbb{Z} \times \delta\mathbb{Z}$ and associate with each edge $e$ an independent random weight $w(e)$. The edge weights may be assumed to be positive and drawn from a continuous distribution. Then, with probability one, there exists a unique path $p^\delta$ from, say, $(0,0)$ to $(1,0)$ that minimises the sum of edge weights along the path. The distribution of $p^\delta$ defines a measure $\mu^\delta$ on the space of non-intersecting paths in $\delta\mathbb{Z} \times \delta\mathbb{Z}$ from $(0,0)$ to $(0,1)$.

Question: Is anything known about $\lim_{\delta\to 0}\mu^\delta$?

Intuitively, if the limit exists, it could be interpreted as a measure on the space of continuous curves in $\mathbb{Z}^2$ from $(0,0)$ to $(1,0)$. I am interested in any references, partial/conjectural results, or simulations.

Probability of two vertices to be connected in G(n,p)

2013-03-11T21:53:31Z

A question I asked at math.SE without elliciting an answer.

Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (distinct) vertices $u,v$ lie in the same connected component of $G(n,p)$?

I'm familiar with the standard asymptotic results about connected components in Erdős–Rényi graphs but was unable to find explicit results for $P_{n,p}$ for finite $n$. I expect these probabilities to be polynomials in $p$ of degree $n(n-1)/2$ but did not succeed in determining the coefficients for general $n$ and $p$.

I fed the values of $P_{n,1/2}$, for $n=2,3,4,5$, into OEIS, but did not obtain a match.

Singular values of sequence of growing matrices

2012-12-29T14:11:01Z

I asked this question on math.stackexchange and haven't received an answer in two weeks, so I'm repeating it here.

Let

$$ H=\left(\begin{array}{cccc} 0 & 1/2 & 0 & 1/2 \cr 1/2 & 0 & 1/2 & 0 \cr 1/2 & 0 & 0 & 1/2\cr 0 & 1/2 & 1/2 & 0 \end{array}\right), $$

$K_1(\alpha)=\left(\begin{array}{c}1 \\ \alpha\end{array}\right)$ and consider the sequence of matrices defined by $$ K_L(\alpha) = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes K_{L-1}(\alpha)\right], $$ where $\otimes$ denotes the Kronecker product, and $I_n$ is the $n\times n$ identity matrix.

I am interested in the limiting behaviour of the singular values of $K_L(\alpha)$ -- in particular, $K_L(0)$ -- as $L$ tends to infinity. Some calculation indicate that the $2^L\times 2^{L-1}$-matrix $K_L$ has $L$ non-zero singular values and that, for any positive integer $k$, the $k$ largest singular values converges to some limit.

Question: Can this limit be described in terms of the matrix $H$?

I did some experiments and it seems that the limiting behaviour of the singular values of $K_L$ does not only depend on the matrix $H$, but also on the initial value $K_1(\alpha)$. This makes it unlikely for fixed-point arguments to work in this setting.

I also tried to obtain combinatorial expressions for the coefficients in the characteristic polynomial $\chi_L^\alpha(\lambda)$ of $K_L(\alpha)K_L(\alpha)^T$ but was successful only for the three highest non-trivial powers of $\lambda$.

Edit:

The analysis of $\Sigma(\alpha):=\lim_{L\to\infty}\sigma_1(K_L(\alpha))$ as a function of $\alpha$, as suggested by Suvrit, seems to be a good idea. Numerical calculations indicate that, asymptotically, $$ \Sigma(\alpha)\sim \Sigma(0)\left(.3540+\alpha\right),\quad \alpha\to\infty,\quad \Sigma(0)\approx .8254, $$ and that $\Sigma(\alpha)$ has a minimum at $\approx(-.2936,.7696)$.

I do not see yet, however, if this can be used to compute $\Sigma(0)$ more precisely.

Edit:

Using the improved bound $\sigma_1(K_L)\leq \frac{1}{2}\sqrt{3+2\alpha +3 \alpha ^2}$, which is sharp for $\alpha=\pm 1$, we can deduce that $d/d\alpha \Sigma(-1)=-1/2$, and $d/d\alpha \Sigma(1)=1/\sqrt{2}$.

Edit3:

After staring at the problem a little longer I've come up with a conjecture for the characteristic polynomial $\chi_L^{\alpha}(\lambda)$ of $K_L(\alpha)K_L(\alpha)^T$. More precisely, I believe that $$ \lambda^{-2^L+L}\chi_L^{\alpha}(\lambda) =\lambda ^L-\left(1+\alpha ^2\right)\lambda ^{L-1}+\\ +\frac{1}{2^L-1}\sum _{k=2}^L \left(-2\right)^{-k}\left[(1-\alpha)^{2(k-1)}\right]\left[(1-\alpha )^2+k (1+\alpha )^2 \right]\frac{(2^{-L};2)_k}{[k]_2!}\left(2^k-2+2^L\right)\lambda^{L-k}, $$ where $(a;q)_k$ denotes a q-Pochhammer symbol and $[k]_q!$ denotes a q-factorial.

It appears that this formula implies that $\lim_{L\to\infty}\sigma_1(K_L(0))$ can be characterized as $\kappa^{-1/2}$, where $\kappa$ is the smallest positive zero of $x\mapsto f(-x/2)$ and $$ f:x\mapsto\sum_{k=0}^\infty{\frac{(k+1)x^k}{[k]_2!}}. $$ Interestingly, this function is related to the q-exponential.

More generally, $\lim_{L\to\infty}\sigma_1(K_L(\alpha))$ can apparently be characterized as $\kappa_\alpha^{-1/2}$, where $\kappa_\alpha$ is the smallest positive solution of $x\mapsto f_\alpha(-x/2)=0$ and $$ f_\alpha:x\mapsto\sum_{k=0}^\infty{\frac{(1-\alpha )^{2 (k-1)} \left[(1-\alpha )^2+k (1+\alpha )^2\right]x^k}{[k_2]!}}. $$ The other singular values are similarly obtained from the remaining zeros of $x\mapsto f_\alpha(-x/2)$.

The next task will be to say something about the singular vectors.

Comment by Eckhard

2013-03-19T18:29:56Z

@Leonid Petrov: Thank you for your comment. I did have a look at the literature, but the problem I'm interested it doesn't seem to have received a lot of attention in the past.

Comment by Eckhard

2013-01-28T16:27:20Z

What about the density $f$ being a triangle-shaped function centered at $1/2$, of width $2\epsilon$ and height $1/\epsilon$? Then the range of a sample is almost surely less than $2\epsilon$.

Comment by Eckhard

2013-01-07T22:04:49Z

@Suvrit: Is it possible that you meant to write in your analysis that $2^LM_L$ is comprised of the two numbers $\theta=(1+\alpha)^2$ and $2(1+\alpha^2)$, as opposed to $\theta$ and $2\theta$? This would lead to the bound $\sigma_1(K_L)\leq \frac{1}{2}\sqrt{3+2\alpha +3 \alpha ^2}$, which is tighter and indeed sharp for $\alpha=\pm 1$.

Comment by Eckhard

2012-12-29T22:32:59Z

@Suvrit: Thank you for your answer. Indeed, $\sigma_1(K_2(0))=\sqrt{3/4}$, and after that the sequence $(\sigma_1(K_L(0)))_L$ seems to be decreasing. Do you see a way to characterize the limit more precisely, as alluded to in your last sentence?