User eckhard - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:38:32Z http://mathoverflow.net/feeds/user/30264 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/124981/continuum-limit-of-first-passage-percolation-paths Continuum limit of first-passage percolation paths Eckhard 2013-03-19T16:20:53Z 2013-04-30T14:52:58Z <p>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.</p> <p>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)$.</p> <p><strong>Question:</strong> Is anything known about $\lim_{\delta\to 0}\mu^\delta$?</p> <p>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.</p> http://mathoverflow.net/questions/124268/probability-of-two-vertices-to-be-connected-in-gn-p Probability of two vertices to be connected in G(n,p) Eckhard 2013-03-11T21:53:31Z 2013-03-11T21:53:31Z <p>A <a href="http://math.stackexchange.com/questions/326804/probability-of-two-vertices-to-be-connected-in-gn-p" rel="nofollow">question</a> I asked at math.SE without elliciting an answer.</p> <p>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)$?</p> <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$. </p> <p>I fed the values of $P_{n,1/2}$, for $n=2,3,4,5$, into OEIS, but did not obtain a match.</p> http://mathoverflow.net/questions/117513/singular-values-of-sequence-of-growing-matrices Singular values of sequence of growing matrices Eckhard 2012-12-29T14:11:01Z 2013-01-12T14:38:33Z <p>I asked this <a href="http://math.stackexchange.com/questions/258736/limit-of-sequence-of-growing-matrices" rel="nofollow">question</a> on math.stackexchange and haven't received an answer in two weeks, so I'm repeating it here.</p> <p>Let </p> <p>$$H=\left(\begin{array}{cccc} 0 &amp; 1/2 &amp; 0 &amp; 1/2 \cr 1/2 &amp; 0 &amp; 1/2 &amp; 0 \cr 1/2 &amp; 0 &amp; 0 &amp; 1/2\cr 0 &amp; 1/2 &amp; 1/2 &amp; 0 \end{array}\right),$$</p> <p>$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.</p> <p>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. </p> <p><strong>Question:</strong> Can this limit be described in terms of the matrix $H$?</p> <p>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.</p> <p>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$.</p> <p><strong>Edit:</strong></p> <p>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)$.</p> <p>I do not see yet, however, if this can be used to compute $\Sigma(0)$ more precisely.</p> <p><strong>Edit:</strong></p> <p>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}$.</p> <p><strong>Edit3:</strong></p> <p>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.</p> <p>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.</p> <p>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)$.</p> <p>The next task will be to say something about the singular vectors.</p> http://mathoverflow.net/questions/124981/continuum-limit-of-first-passage-percolation-paths Comment by Eckhard Eckhard 2013-03-19T18:29:56Z 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. http://mathoverflow.net/questions/120083/probability-density-that-minimizes-the-sample-range Comment by Eckhard Eckhard 2013-01-28T16:27:20Z 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$. http://mathoverflow.net/questions/117513/singular-values-of-sequence-of-growing-matrices/117543#117543 Comment by Eckhard Eckhard 2013-01-07T22:04:49Z 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$. http://mathoverflow.net/questions/117513/singular-values-of-sequence-of-growing-matrices/117543#117543 Comment by Eckhard Eckhard 2012-12-29T22:32:59Z 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?