User mfolz - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:14:51Z http://mathoverflow.net/feeds/user/5153 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105038/continuous-notions-with-compelling-discrete-analogues/105369#105369 Answer by mfolz for Continuous notions with compelling discrete analogues mfolz 2012-08-24T05:21:56Z 2012-08-24T08:08:45Z <p>Continuous-time random walks on graphs are in some sense a discrete analogue of diffusions on a Riemannian manifold (of course, the reverse can be argued, but I think that diffusions play a more central role in modern probability theory). Of course, the most important diffusion is Brownian motion, i.e., the Markov process associated with the Laplace-Beltrami operator. From my perspective, the natural analogue of Brownian motion is the operator $\mathcal{L}_V$ given by (we use unweighted graphs for simplicity)</p> <p>\begin{equation*} (\mathcal{L}_Vf)(x) := \sum_{y\sim x}(f(y)-f(x)). \end{equation*}</p> <p>A more 'common' choice might be the rate-1 continuous time random walk with generator $\mathcal{L}_C$ given by</p> <p>\begin{equation*} (\mathcal{L}_Cf)(x) := \frac{1}{\deg(x)}\sum_{y\sim x}(f(y)-f(x)). \end{equation*}</p> <p>However, this choice of generator has several 'bad' properties if you want to view it as an analogue of Brownian motion -- for example, the generator is always bounded on $L^2(\deg)$, it cannot have discrete spectrum, and the associated random walk cannot explode; in contrast, the operator $\mathcal{L}_V$ may be unbounded, and discrete spectrum and explosiveness are possible.</p> <p>Once you have this discrete (space) analogue of Brownian motion on a Riemannian manifold, a natural question is to ask what the discrete analogue of the Riemannian metric should be for this process. It is not too hard to find examples that show that the graph metric is a bad analogue, since the Riemannian metric governs heat flow (in some sense) on a Riemannian manifold (see e.g. <a href="http://www.math.uni-bielefeld.de/~grigor/super.pdf" rel="nofollow">here</a>), but Gaussian heat kernel estimates do not hold for the random walk associated with $\mathcal{L}_V$ if you take the manifold heat kernel estimates and replace the distance function with the graph metric. A reasonable analogue has been formulated recently, see e.g. <a href="http://arxiv.org/abs/1012.5050" rel="nofollow">here</a> and <a href="http://arxiv.org/abs/1201.5908" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/104900/large-deviations-for-sums-of-exponentially-distributed-random-variables Large deviations for sums of exponentially distributed random variables. mfolz 2012-08-17T08:52:48Z 2012-08-17T18:23:58Z <p>Take a large integer $R$, and let $(X_j)_{j\geq R}$ be a sequence of exponentially distributed random variables with parameters $\pi_j := j^{1+\alpha}$ ($\alpha>0$), so that $\sum_{j\geq R} \frac{1}{\pi_j} &lt; +\infty$. Set $X_R := \sum_{j\geq R} X_j$. Assume that $t>0$ is small enough that $\mathbb{E}X_R \ll t$.</p> <p>I am interested in good upper bounds for $\mathbb{P}(X_R>t)$. By using $\mathbb{P}(X_R>t) = \mathbb{P}(e^{\lambda X_r}> e^{\lambda t})$, applying Markov's inequality, and optimizing over $\lambda$, I think that I can get bounds like</p> <p>\begin{equation*}\mathbb{P}(X_R>t)\leq C\exp(-ctR^{1+\varepsilon}) \end{equation*}</p> <p>for $0&lt;\varepsilon&lt;\alpha$, but I am not sure if these are close to being optimal.</p> http://mathoverflow.net/questions/88433/reference-for-estimation-gaussian-of-the-heat-kernel/88551#88551 Answer by mfolz for Reference for estimation gaussian of the heat kernel mfolz 2012-02-15T20:01:58Z 2012-02-15T20:01:58Z <p>You may also be interested in the following paper of Grigoryan, <a href="http://www.math.uni-bielefeld.de/~grigor/super.pdf" rel="nofollow">Gaussian upper bounds for the heat kernel on arbitrary manifolds</a>, which establishes the desired Gaussian bounds whenever one can show that there exists $C>0$ such that for all $x\in M$ and $t>0$, $p_t(x,x) \leq Ct^{-n/2}$. The latter estimate may be obtained via a Sobolev inequality or a Nash inequality or through other means (and I'm sure it's discussed in the Davies and Saloff-Coste books already mentioned). This paper also establishes Gaussian upper bounds even when the function appearing in the 'on-diagonal bound' is not of the form $t^{-n/2}$, or if one only has control of $p_t(x,x)$ at two points $x_1$ and $x_2$. </p> http://mathoverflow.net/questions/85046/interesting-applications-of-martingale-brown-motion-diffusion-percolation-theo/85109#85109 Answer by mfolz for Interesting applications of [Martingale/Brown motion/diffusion/percolation ] theory? mfolz 2012-01-07T04:10:47Z 2012-01-07T04:10:47Z <p>The <a href="http://en.wikipedia.org/wiki/Gambler%27s_ruin" rel="nofollow">Gambler's Ruin Problem</a> is a nice motivator for martingale techniques (the wikipedia solution is really a martingale solution in disguise, but not totally rigorous -- it can be made so by using the Optional Stopping Theorem for martingales).</p> http://mathoverflow.net/questions/68774/probability-of-returning-to-starting-point-before-hitting-adjacent-point-for-rw-o Probability of returning to starting point before hitting adjacent point for RW on Z^2 mfolz 2011-06-25T02:56:53Z 2011-10-23T07:51:29Z <p>Consider (simple) random walk on $\mathbb{Z}^2$ started at the origin. The probability that the walk returns to the origin before hitting $(0,1)$ is $1/2$.</p> <p>To see this, let $a(x)$ be the potential kernel for random walk on $\mathbb{Z}^2$. Then $2a(x)$ counts the expected number of visits to the origin by a random walk started at the origin before the first time it hits $x$. Let $p$ denote the probability that the walk returns to the origin before hitting $x$.</p> <p>Hence,</p> <p>\begin{equation*} 2a(x) = (1-p)+p(1-p)+p^2(1-p)+\cdots = \frac{1}{1-p}, \end{equation*}</p> <p>and consequently, </p> <p>\begin{equation*} p = 1-\frac{1}{2a(x)}. \end{equation*}</p> <p>On the other hand, one can also obtain that </p> <p>\begin{equation*} a(x) = \frac{1}{(2\pi)^2}\int_{[-\pi,\pi]^2}\frac{1-\exp(-ix\cdot\theta)}{1-\phi(\theta)}d\theta, \end{equation*}</p> <p>where $\phi(\theta)$ is the characteristic function of the random walk. In particular, one can work out that $a(0,1) = 1$, and hence that the probability we are looking for is $1/2$. With some more work, one can also work out what the answer would be for, say, $(3,2)$ in place of $(0,1)$ (it turns out to be $(16\pi+3)/(16\pi+6)$).</p> <p>But the expression for $(0,1)$ suggests that there is some sort of underlying symmetry. Is there a simple argument for why this is the case? </p> <p>I'm aware that this problem can be rephrased in terms of electrical networks, and that there <a href="http://stevensholland.com/challenge-problem-solution-from-jan-19th-2007/" rel="nofollow">appears to be a simple solution involving symmetry in that setting</a>, but I'd prefer a simple solution involving symmetry without these techniques, if possible.</p> http://mathoverflow.net/questions/59117/assigning-positive-edge-weights-to-a-graph-so-that-the-weight-incident-to-each-ve Assigning positive edge weights to a graph so that the weight incident to each vertex is 1. mfolz 2011-03-21T23:42:45Z 2011-03-22T20:57:43Z <p>Let $\Gamma=(G,E)$ be a connected undirected graph, with no loops or multiple edges. $G$ is finite or countably infinite. For each edge $e=\{x,y\}\in E$, we assign a positive, symmetric edge weight $c_e := c_{\{x,y\}} = c_{xy} = c_{yx}$. I would like to know for which graphs $\Gamma$ it is possible to choose $(c_e)_{e\in E}$ so that for each $x\in G$,</p> <p>\begin{equation*} \sum_{y\sim x} c_{xy} = 1. \end{equation*}</p> <p>For example, this is possible on any $d-$regular graph if one sets $c_e \equiv 1/d$. The graph with vertex set $\{x,y,z\}$ and edges $\{x,y\}$ and $\{y,z\}$ shows that it is not always possible.</p> http://mathoverflow.net/questions/52282/does-generator-of-continuous-time-random-walk-map-heat-kernel-from-l2-to-l2 Does generator of continuous time random walk map heat kernel from L^2 to L^2? mfolz 2011-01-17T01:45:12Z 2011-01-26T00:58:33Z <p>Let $\Gamma = (G,E)$ be an undirected, infinite, connected graph with no multiple edges or loops. We equip $\Gamma$ with a set of edge weights $\pi_{xy}$, where, given $e=\{x,y\}\in E$, we write $\pi_{\{x,y\}} = \pi_{xy}=\pi_{yx}>0$. If $\{x,y\}\not\in E$, we set $\pi_{xy}=0$. We write $\pi_x$ for $\sum_{y\sim x} \pi_{xy}$. We also assign a set of positive vertex weights $(\theta_x)_{x\in G}$.</p> <p>We consider the continuous time random walk on $\Gamma$ with generator $\mathcal{L}_\theta$ given by</p> <p>\begin{equation*} (\mathcal{L}_\theta f)(x) = \frac{1}{\theta_x}\sum_{y\sim x}\pi_{xy}(f(y)-f(x)), \end{equation*}</p> <p>and denote the resulting Markov process by $(X^\theta_t)_{t\geq 0}$. Roughly speaking, at a vertex $x$, this process waits an exponential time with mean $\theta_x/\pi_x$, and then jumps to one of its neighbors $y$ with probability $\pi_{xy}/\pi_x$. It's not hard to see that if one chooses the $\theta$ s and $\pi$ s in certain ways, the process can behave quite pathologically and run away from its starting point very quickly (e.g., the process may have a finite lifetime). </p> <p>The function $p_t(x,y) := \frac{\mathbb{P}^x(X^\theta_t=y)}{\theta_y}$ is the called the heat kernel of the random walk. </p> <p>I'm interested in some analytic aspects of the generator $\mathcal{L}_\theta$. For example, $\mathcal{L}_\theta$ is a bounded operator from $L^2(\theta)$ to $L^2(\theta)$ if and only if</p> <p>\begin{equation*} \sup_{x\in G} \frac{\pi_x}{\theta_x}&lt; \infty. \end{equation*}</p> <p>Set $u(x) := p_t(x_0,x)$. Note that $u$ is always in $L^2(\theta)$, as</p> <p>\begin{equation*} \sum_{x\in G} u^2(x)\theta_x = \sum_{x\in G} p_t(x_0,x)p_t(x,x_0)\theta_x = p_{2t}(x_0,x_0) \leq \frac{1}{\theta_{x_0}} \end{equation*}</p> <p>Is it the case that $\mathcal{L}_\theta u$ is always in $L^2(\theta)$ also?</p> http://mathoverflow.net/questions/52282/does-generator-of-continuous-time-random-walk-map-heat-kernel-from-l2-to-l2/53304#53304 Answer by mfolz for Does generator of continuous time random walk map heat kernel from L^2 to L^2? mfolz 2011-01-26T00:58:33Z 2011-01-26T00:58:33Z <p>I was able to answer this question, although it didn't turn out to be useful in the way I thought it would be.</p> <p>Let $P^\theta_t$ be the transition operator, $(P^\theta_tf)(x) = \sum_{y\in G} p_t(x,y)f(y)\theta_y$. Then a fairly easy computation shows that $P_t$ maps $L^2(\theta)$ to $L^2(\theta)$, and one can also show that if $v\in C_c(G)$, then $P_t(\mathcal{L}_\theta v) = \mathcal{L}_\theta (P_tv)$, basically from a self-adjointness calculation. If one applies this to the function $u=\theta^{-1}_{x_0}\delta_{x_0}$, then we get $\mathcal{L}_\theta u = \mathcal{L}_\theta (P_tv) = P_t(\mathcal{L}_\theta v)$, and the right-hand side of this is in $L^2(\theta)$. </p> http://mathoverflow.net/questions/51949/liouville-property-in-zd/52279#52279 Answer by mfolz for Liouville property in Z^d mfolz 2011-01-17T01:19:20Z 2011-01-17T01:19:20Z <p>Yuval Peres gave a fairly short proof of this result in his lectures at the 2009 Cornell Probability Summer School (http://www.math.cornell.edu/~durrett/CPSS2009/peres6.pdf).</p> <p>If one wants to use more machinery from probability theory, the Hewitt-Savage 0-1 law implies that the tail $\sigma$-field $\mathcal{T}$ associated with the SRW on $\mathbb{Z}^d$ is trivial. But the tail $\sigma$-field is a superset of the 'invariant' sigma field $\mathcal{I} := \{F\in\mathcal{F}:F\circ \theta_n = F \text{ for all }n\}$, and the invariant sigma field being $\mathbb{P}^x$-trivial for all $x$ is equivalent to the graph having the Liouville property. </p> http://mathoverflow.net/questions/20355/book-for-probability/20426#20426 Answer by mfolz for book for probability mfolz 2010-04-05T22:04:22Z 2010-04-05T22:04:22Z <p>Rick Durrett's book "Probability: Theory and Examples" is a very readable introduction to measure-theoretic probability, and has plenty of examples and exercises. This is the second text that I learned probability theory out of, and I thought it was quite good (I used Breiman first, and didn't enjoy it very much). As a bonus, there is a free .pdf version of the 4th edition (which will be published in a few months) available on his website for the time being. </p> <p>A recent text covering similar material (which I admit I haven't read that fully) which looked good on a quick reading was "Probability Theory: A Comprehensive Course" by Klenke. It has a very nice selection of modern topics.</p> http://mathoverflow.net/questions/110650/expectation-distribution-of-stopping-time-for-a-2-d-brownian-motion-hits-a-unit-c Comment by mfolz mfolz 2012-10-25T21:44:57Z 2012-10-25T21:44:57Z Try doing some reading on the Bessel process (<a href="http://en.wikipedia.org/wiki/Bessel_process" rel="nofollow">en.wikipedia.org/wiki/Bessel_process</a>); this gives you the solution for dimensions 2 and higher. http://mathoverflow.net/questions/106133/random-walk-police-catching-the-thief Comment by mfolz mfolz 2012-09-03T07:26:12Z 2012-09-03T07:26:12Z @David: the Catalan number argument does work, though: the ratio of the binomial coefficients is $Cj^{-1/2}$ and the additional $1/(j+1)$ factor in the Catalan numbers gives $Cj^{-3/2}$. Summing over $j$ from $1$ to $n$ gives $Cn^{-1/2}$. http://mathoverflow.net/questions/104900/large-deviations-for-sums-of-exponentially-distributed-random-variables/104929#104929 Comment by mfolz mfolz 2012-08-17T23:13:22Z 2012-08-17T23:13:22Z I am not sure if these results are applicable, since (in the notation of that paper) $\gamma_n$ is required to be infinite, but is necessarily finite in the context I am interested in. http://mathoverflow.net/questions/85046/interesting-applications-of-martingale-brown-motion-diffusion-percolation-theo Comment by mfolz mfolz 2012-01-08T08:32:03Z 2012-01-08T08:32:03Z The thing that makes the question puzzling is that while there are fairly natural connections between martingales, Brownian motion, and diffusions, percolation is really apparently unrelated to the others (which is not to say that, for example, one cannot find martingale techniques used in percolation theory...) http://mathoverflow.net/questions/68774/probability-of-returning-to-starting-point-before-hitting-adjacent-point-for-rw-o/68948#68948 Comment by mfolz mfolz 2011-06-28T05:31:47Z 2011-06-28T05:31:47Z Thanks for the link. I have nothing 'against' electrical networks (anyone working in random walks needs to be familiar with them!); I was just hoping for an especially simple solution involving some sort of symmetry argument. But it seems unlikely that there is one. http://mathoverflow.net/questions/59117/assigning-positive-edge-weights-to-a-graph-so-that-the-weight-incident-to-each-ve/59122#59122 Comment by mfolz mfolz 2011-03-22T01:32:18Z 2011-03-22T01:32:18Z Maybe I am missing something, but suppose that each edge is contained in a perfect matching. Let $(a_e)_{e\in E}$ satisfy $a_e&gt;0$ and $\sum_E a_e = 1$, and for each edge $e_j$, let $(c^{(e_j)}_e)_{e\in E}$ be an assignment of nonnegative edge weights with $c^{e_j}_{e_j}=1$ (i.e., using the perfect matching). Then $d_e = \sum_j a_{e_j}c^{(e_j)}_e$ is what we want, and satisfies $d_e&gt;0$ for all $e\in E$. http://mathoverflow.net/questions/59117/assigning-positive-edge-weights-to-a-graph-so-that-the-weight-incident-to-each-ve/59122#59122 Comment by mfolz mfolz 2011-03-22T00:54:21Z 2011-03-22T00:54:21Z Well, it is certainly a sufficient condition, in both the finite and countably infinite settings. http://mathoverflow.net/questions/59117/assigning-positive-edge-weights-to-a-graph-so-that-the-weight-incident-to-each-ve/59122#59122 Comment by mfolz mfolz 2011-03-22T00:36:19Z 2011-03-22T00:36:19Z Thanks for the answer, JBL. The distinction between positive and nonnegative is actually significant in this instance. For the infinite case, it seems that one can just as easily take an infinite, strictly positive, convex combination of matchings.