User alekk - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:25:03Z http://mathoverflow.net/feeds/user/1590 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/123665/the-limiting-behavior-of-geometric-random-walk/123726#123726 Answer by Alekk for The limiting behavior of geometric random walk Alekk 2013-03-06T09:32:08Z 2013-03-06T09:32:08Z <p>For $n$ large, each direction is chosen $n/d + O(n^{-1/2})$ so that each coordinate evolves approximately (after usual $\epsilon^{1/2}$-in-space-$\epsilon$-in-time scaling) as a Brownian motion and the coordinate are approximately independent. In other words $W_t^{(\epsilon)} = \sqrt{\epsilon} \ Q_{\epsilon^{-1}t}$ behaves as a standard Brownian motion with infinitesimal variance $\sigma^2(p) \ dt$, with $\sigma^2(p)=(1-p)p^{-2}$ the variance of a $p$-geometric random variable, looked at time $t/d$. This is the same as saying that $W_t^{(\epsilon)}$ behaves as a standard Brownian motion with infinitesimal variance $d^{-1} \ \sigma^2(p) \ dt$.</p> http://mathoverflow.net/questions/110559/contraction-property-for-conditioned-sdes contraction property for conditioned SDEs Alekk 2012-10-24T16:31:05Z 2012-10-25T08:51:58Z <p>Consider a strictly convex potential $U: \mathbb{R}^d \to \mathbb{R}$ and the Langevin diffusion $$dX = -\nabla U(X) dt + dW \qquad (*)$$ where $W$ is a standard Brownian motion. If $(X_t)_{t \geq 0}$ and $(Y_t)_{t \geq 0}$ are two solutions driven by the same Brownian motion, one can check that $t \mapsto \mathbb{E} \| X_t-Y_t \|^2$ is decreasing since $d \| X_t-Y_t \|^2 = -2 \langle X_t-Y_t, \nabla U(X_t) - \nabla U(Y_t)\rangle \leq -2 \lambda \|X_t - Y_t\|^2$ where $\textrm{Hessian}(x) \geq \lambda I_d$ on $\mathbb{R}^d$. In other words, given two starting positions $x_0, y_0 \in \mathbb{R}^d$, one can construct a coupling $(X_t,Y_t)$ of the diffusion $(*)$, one starting from $x_0$ and the other one from $y_0$, such that $\mathbb{E} \|X_t-Y_t\| \leq e^{- \lambda t} \|x_0-y_0\|$. Indeed, if the function $U$ is not strictly convex, one can only say that $\mathbb{E} \|X_t-Y_t\|$ can be made non-increasing. This can also be expressed in terms of Wasserstein distance between $P_t(x,dx)$ and $P_t(y,dy)$ where $P$ is the transition operator of the diffusion $(*)$.</p> <p><strong>Question</strong>: given $x_-,x^+,y_-,y^+ \in \mathbb{R}^d$, can we find a coupling $(X_t,Y_t)$ of the conditioned diffusion $(*)$ with $$X_0=x_-, \quad X_T=x^+, \quad Y_0=y_-, \quad Y_T=y^+,$$ and such that there is still a contraction property of the type $$\mathbb{E} \|X_{T/2}-Y_{T/2}\| \leq \beta \big( \|x_- - y_-\| + \|x_+ - y_+\|\big)$$ where $0&lt;\beta&lt;\frac12$ is some constant that does not depend on $(x_-,x^+,y_-,y^+)$. Is this known or have already been studied? Any reference welcome.</p> <p><strong>PS</strong>: one can check that this is true for a quadratic potential $U(x) = \frac12 \|x\|^2$ since the Ornstein-Uhlenbeck process is easy to study. The case of a brownian bridge (i.e. vanishing potential) is also straightforward and corresponds to the case $\beta = \frac12$.</p> <p><strong>PPS</strong>: it is important to exploit the structure of the SDE. Indeed, one can find counter examples of Markov processes $(X_t)_{t \geq 0}$ that have the contraction property $\mathbb{E} \|X_t-Y_t\| \leq e^{-\lambda t} \|x_0 - y_0\|$ but that do not verify the 'conditioned' contraction property.</p> http://mathoverflow.net/questions/110092/ising-model-on-a-cycle Ising model on a cycle Alekk 2012-10-19T13:05:51Z 2012-10-21T07:21:44Z <p>The Ising model on $\mathbb{Z} / 2d\mathbb{Z}$ gives to the configuration $x=(x_0, \ldots, x_{2d-1}) \in \{-1,+1\}^{2d}$ a probability proportional to $\exp\big(\beta \sum_i x_ix_{i+1} \big)$. The Gibbs sampler with block updates is a Markov chain $X_k$ that evolves on the set of such configurations and updates the odd (resp. even) indices conditionally on the even (resp. odd) indices with probability a half.</p> <p>It seems like a relatively straightforward application of the path coupling [1] approach (two configurations are neighbours if they agree on all odd or all even coordinates; distance between two neighbours is $1+H(x,y)/d$ where $H$ is the Hamming distance) shows that the mixing time of the Gibbs sampler stays bounded as the size $d$ of the system goes to infinity, which looks rather surprising. Any intuition behind that? If this is already written somewhere, any reference concerning this (or similar) result?</p> <ul> <li>[1] Chapter 14 of <em>Markov Chains and Mixing Times</em> by D. Levin, Y. Peres and E. Wilmer</li> </ul> http://mathoverflow.net/questions/108472/brownian-motion-inside-a-domain Brownian motion inside a domain Alekk 2012-09-30T14:19:03Z 2012-09-30T14:19:03Z <p>Consider a regular domain $D \subset \mathbb{R}^d$ and a Brownian motion $B_t$ conditioned to stay inside $D$ for time $t \in [0,T]$. In the limit $T \to \infty$ the conditioned Brownian motion behaves like an homogenous diffusion in $D$ whose invariant distribution is the first eigenfunction of the Laplacian in $D$ (which gives another proof that the first eigenfunction is positive).This should also work for more general diffusion processes. Where can I find a reference for this (and similar) results?</p> http://mathoverflow.net/questions/107472/minimum-of-two-probability-densities minimum of two probability densities Alekk 2012-09-18T13:52:25Z 2012-09-20T01:40:46Z <p>Consider a smooth probability density $\pi(x)$ on $\mathbb{R}^d$. I am looking for natural for the integral $\iint_{u,v} \ \min\big(\pi(u), \pi(v) \big) \ du \ dv$ to be finite. If $\pi$ is a radially decreasing density, this is equivalent to the condition $\mathbb{E}\big[ \|X\|^{d} \big] &lt; \infty$. Are there smooth densities verifying this moment condition such that $\iint_{u,v} \ \min\big(\pi(u), \pi(v) \big) \ du \ dv = \infty$ ?</p> <p>No answer given on <a href="http://math.stackexchange.com/questions/198079/minimum-of-two-probability-densities" rel="nofollow">math.stackexchange</a>. This integral appeared while studying a Metropolis-Hastings Markov chain.</p> http://mathoverflow.net/questions/100254/positive-estimator Positive estimator Alekk 2012-06-21T15:39:16Z 2012-06-22T11:02:42Z <p>Suppose that one knows how to generate (independent) random samples $X_1, X_2, \ldots$ distributed as the random varable $X$ with $\mathbb{E}[X]=\mu \in \mathbb{R}$. It is then easy to construct an unbiased estimator of the quantity $e^{\mu}$. Indeed, it suffices to generate an integer random variables $N$ such that $\mathbb{P}[N \geq k] = \frac{1}{k!}$. The random variable $$Y=1 + X_1 + X_1X_2 + \ldots + \prod_{k \leq N-1} X_k + \prod_{k \leq N} X_k$$ satisfies $\mathbb{E}[Y]=e^{\mu}$.</p> <p><strong>Question:</strong> is it possible to construct an unbiased estimator of $e^{\mu}$ that is positive with probability $1$. If the random variable $X$ is lower bounded by a constant $C$ one can Taylor expand $\exp(C) \cdot \exp(x-C)$ and use the same idea as above. What about the case where $X$ is not lower bounded? One could try to Taylor expand $\exp(m) \cdot \exp(x-m)$ where $m = \min(X_1, \ldots, X_N)$ but in this case the estimator does not satisfy $\mathbb{E}[Y]=e^{\mu}$ anymore due to the dependence between the random variable $m$ and $(X_1, \ldots, X_N)$.</p> http://mathoverflow.net/questions/93427/birds-on-wire-type-problem "birds on wire" type problem Alekk 2012-04-07T15:10:54Z 2012-04-08T01:56:20Z <p>Consider $n$ individuals {$1,2, \ldots, n$}. For each (unordered) pair of individuals $i \neq j$ we consider a random variable $X_{i,j}$ that can be thought of as the distance between $i$ and $j$. Each individual kills its closest neighbour (everything happens at the same time). Can we say anything about the distribution of the number of survivors in the limit $n \to \infty$?</p> <p>The case $X_{i,j} = |Y_i-Y_j|$ where $Y_1, \ldots,Y_N$ are $n$ i.i.d random variables uniformly distributed on $[0,1]$ is the famous "birds on wire" problem. </p> <p>What about the case where the random variables $X_{i,j}$ are independent and exponentially distributed, say? Has it been studied in the literature?</p> http://mathoverflow.net/questions/83802/correlations-in-last-passage-percolation/83819#83819 Answer by Alekk for Correlations in last-passage percolation Alekk 2011-12-18T19:44:55Z 2011-12-18T19:44:55Z <p>For those who wonder how the geodesics look like, here is a quick simulations (with exponential weights): <img src="http://linbaba.files.wordpress.com/2011/12/geodesic.png" alt="alt text"></p> http://mathoverflow.net/questions/19406/constructing-bernoulli-random-variables-with-prescribed-correlation Constructing Bernoulli random variables with prescribed correlation Alekk 2010-03-26T11:37:04Z 2011-11-08T23:49:40Z <p>For which $n \times n$ correlation matrix $C$ can one construct Bernoulli random variables $(B_1, \ldots, B_n)$ with correlation $C$ ?</p> <p>Following the approach described in this MO <a href="http://mathoverflow.net/questions/18268/discrete-stochastic-process-exponentially-correlated-bernoulli" rel="nofollow">thread</a>, one can think of the following construction. Define independent Bernoulli random variables $B_{k_1, \ldots, k_n}$ for $(k_1, \ldots, k_n) \in \mathbb{Z}^n$ and another independent $\mathbb{Z}^k$-valued random variable $I=(I_1, \ldots, I_n)$. Then $(B_{I_1}, \ldots, B_{I_n})$ is a correlated Bernoulli vector.</p> <p>1: Is there any example of correlation structure that cannot be obtained this way ?</p> <p>2: Any easy example of correlation matrix $C$ that cannot be the correlation matrix of a $\{0,1\}^n$ valued random vector ?</p> http://mathoverflow.net/questions/19020/brownian-motion-and-spheres Brownian motion and spheres Alekk 2010-03-22T14:54:00Z 2011-08-15T17:24:46Z <p>Consider a Brownian motion on $[0;1]$. A (finite) discrete approximation of this Brownian motion consists of $N$ iid Gaussian random variables $\Delta W_i$ of variance $\frac{1}{N}$: $$W\left(\frac{k}{N}\right) = \sum_{i=1}^k \Delta W_i.$$ The vector $V_N = (\Delta W_1, \ldots, \Delta W_N) \in \mathbb{R}^N$ has a norm approximately equal to $1$ since the random variable $\|V_N\|^2$ has a variance equal to $\frac{C}{N}$ and $\frac{C}{N} \to 0$ (basic concentration of measure results can make this statement more precise). This is why (?) one can approximately say that in order to sample a Brownian path, it suffices to sample a point uniformly on the unit sphere of $\mathbb{R}^N$.</p> <p><strong>Question</strong>: letting $N$ go to $\infty$, how can one formalize (if possible and/or correct) the idea that a Brownian path on $[0;1]$ is like a point uniformly chosen on the unit sphere of an infinite dimensional Banach space ?</p> http://mathoverflow.net/questions/53073/diffusion-sample-paths-as-deformed-brownian-sample-paths/69261#69261 Answer by Alekk for Diffusion sample paths as deformed Brownian sample paths Alekk 2011-07-01T13:58:40Z 2011-07-02T12:14:31Z <p>As other have said, in the one dimensional case at least, you can suppose that the volatility is constant. Then the solution of the SDE is nothing else than a solution of the integral equation $$X(t) = \int_0^t \mu(X_s) ds + \sigma W_t \qquad \forall t \in [0,T].$$ You can then check that if $\mu(\cdot)$ is a Lipschitz function, say, then the function $\Psi$ that maps $(W_t)_{t \in [0,T]}$ to the solution of the above integral equation is continuous (Gronwall Lemma) on $C([0,T],\mathbb{R})$ with the supremum norm. Hence you can indeed write $X = \Psi(W)$ and see the path $(X_t)_{t \in [0,T]}$ as a 'deformation' of the Brownian path $(W_t)_{t \in [0,T]}$. The function $\Psi: C([0,T],\mathbb{R}) \to C([0,T],\mathbb{R})$ is sometimes called the 'Ito map' in the literature.</p> http://mathoverflow.net/questions/69005/law-of-iterated-logrithm/69010#69010 Answer by Alekk for law of iterated logrithm Alekk 2011-06-28T08:07:52Z 2011-06-28T08:07:52Z <p>Girsanov's theorem tells you that on any <em>finite</em> interval $[0,T]$ you can find an equivalent probability that makes $t+B_t$ a Brownian motion. You just gave the proof that it cannot be done on the whole real line.</p> http://mathoverflow.net/questions/49243/comparing-diffusions comparing diffusions Alekk 2010-12-13T11:07:19Z 2011-05-04T14:35:14Z <p>Consider a probability distribution $\pi$ on the real axis that has a density (w.r.t Lebesgue) proportional to $e^{-V(x)}$, where $V(\cdot)$ is a potential function. For any reasonable volatility function $\sigma:\mathbb{R} \to (0:+\infty)$ the diffusion $$dX^{\sigma}_t = [ -\frac{1}{2} \sigma(X_t^{\sigma})^2 V'(X_t^{\sigma}) + \sigma(X_t^{\sigma}) \sigma'(X_t^{\sigma}) ] dt + \sigma(X_t^{\sigma}) \, dW_t$$ has $\pi$ as unique invariant distribution. </p> <p><strong>Question:</strong> Given two volatility functions $\sigma_1, \sigma_2$, are there tractable ways of comparing the speed of convergence to equilibrium of the two associated diffusions?</p> <p>For example, if $\sigma_2(x) = \alpha \cdot \sigma_1(x)$, the diffusion $X^{\sigma_2}$ is just $X^{\sigma_1}$ slowed down by a factor $\alpha$: any ways of comparing the two diffusions should say that if $\alpha > 1$ then $X^{\sigma_2}$ converges 'faster' than $X^{\sigma_1}$. Spectral Gaps work but are not very tractable when comparing two non-proportional diffusions. Is it hopeless ?</p> <p><strong>Motivations:</strong> I consider several MCMC algorithms with target density $\pi$: each one of them, after some time-rescaling, looks like a diffusion $X^{\sigma}$. Which algorithm is the best $i.e.$ what diffusion $X^{\sigma}$ mixes the fastest ?</p> http://mathoverflow.net/questions/54557/weighted-poincare-inequality weighted Poincare inequality Alekk 2011-02-06T19:46:58Z 2011-04-14T04:32:01Z <p>Consider a probability distribution $\pi$ with density $e^{-H(x)}$ on $\mathbb{R}$. Let us say that there is a Poincare inequality with weight $w$ if for any smooth function $\phi$ satisfying $\int \phi(x) \pi(dx) = 0$ the following inequality holds, $$\int \phi'(x)^2 w^2(x) \pi(dx) \geq \int \phi(x)^2 \pi(dx).$$</p> <p><strong>Question:</strong> given a positive function $h:\mathbb{R} \to (0;+\infty)$, can one compute the optimal weight function $w$ in the sense that $w$ minimizes $\int w^2(x) h^2(x) \pi(dx)$.</p> <p><strong>Example:</strong> if $\pi$ is a Gaussian measure ($i.e$ with $H(x) = \frac{1}{2} x^2$) and $h(x)=1$, playing around with Hermite polynomials, it does not seem very hard to check that $w(x)=\text{Cst}$ is optimal.</p> <p>In the more general case, it seems like the optimal weight $w_0$ and associated test function $\phi_0$ defined by $\int \phi_0'(x)^2 w_0^2(x) \pi(dx) = \int \phi_0(x)^2 \pi(dx)$ must satisfy $\phi_0'(x)^2 = \lambda h^2(x)$ and $h$ is an eigenfunction of a certain differential operator involving $w_0$. I have not been able to explicitly find $w_0$ by continuing in this direction.</p> <p><strong>Motivations:</strong> given a metric on $\mathbb{R}$ ($i.e$ function $w^2$), one can consider the associated Langevin diffusion that has $\pi$ as invariant distribution. Among all the metric that satisfy certain conditions, which one maximizes the speed of convergence ($i.e$ spectral gap) of the Langevin diffusion towards $\pi$.</p> http://mathoverflow.net/questions/60417/will-a-random-walk-on-0-inf-tend-to-infinity/60428#60428 Answer by Alekk for Will a random walk on [0, inf) tend to infinity? Alekk 2011-04-03T11:58:01Z 2011-04-03T11:58:01Z <p>As it has been said:</p> <ol> <li>if $p=\frac{1}{2}$ this is more or less the same thing as the absolute value of the standard symmetric random walk on $\mathbb{Z}$, wich is recurrent.</li> <li>if $p > \frac{1}{2}$, the law of large numbers immediately shows you that it tends to $+\infty$.</li> <li>if $p &lt; \frac{1}{2}$, you can even check the detailed balance equations and find the invariant distribution: the Markov chain is positive recurrent.</li> </ol> http://mathoverflow.net/questions/59713/probability-estimates-for-beans-boxes/59720#59720 Answer by Alekk for Probability estimates for "beans & boxes" Alekk 2011-03-27T12:36:24Z 2011-03-27T12:49:47Z <p>A classical way of tackling such kind of problems is via Poisson approximations. For example, consider a Poisson point process in $(0,1) \times (0,\infty)$ with unit intensity. The number $N_k(T)$ of points in $(\frac{k}{P},\frac{k+1}{P}) \times (0,T)$ is distributed as a Poisson random variable with mean $\frac{T}{P}$: this represents an approximation of the number of beans in the $k$-th box at time $T$. Indeed, the advantage of this Poissonization is that the random variables $N_k(T)$ are now independent - this was not the case in the original problem. The probability that at time $T$ each box contains at least $N$ beans is thus given by $\big(\mathbb{P}[\text{Poiss}(T/P) \geq N] \big)^P$, and you can then do all kind of asymptotic estimates.</p> <p>I doubt that you will find a very tractable answer to your original question. Are you interested in the limit $N,P \to \infty$ ?</p> http://mathoverflow.net/questions/59257/examples-of-lyapunov-functions-for-markov-processes/59274#59274 Answer by Alekk for Examples of Lyapunov functions for Markov processes Alekk 2011-03-23T09:14:12Z 2011-03-23T09:14:12Z <p>This is called a "drift condition" in the applied probability literature -- this is used quite often when dealing with MCMC simulations, for example.</p> <p>In continuous time, what about the good old Ornstein-Uhlenbeck process $dz = -zdt + \sqrt{2}dW$ and generator $L \phi(x) = -x \phi'(x) + \phi^{''}(x)$: the Lyapunov function $V(x) = e^{\alpha |x|}$ works for any $\alpha > 0$.</p> http://mathoverflow.net/questions/58785/optimal-coupling optimal coupling Alekk 2011-03-17T21:39:38Z 2011-03-17T21:50:47Z <p>Given probability distributions $(\mu_1, \ldots, \mu_n)$ on a nice state space $E$ is it always possible to find a random vector $(X_1, \ldots, X_n)$ such that $(X_k, X_{k+1})$ is an optimal coupling of $\mu_k$ and $\mu_{k+1}$ for any $1 \leq k \leq n-1$? For example, this is true for Gaussian distributions $\mu_k \sim \mathcal{N}(\alpha_k, \sigma_k^2)$.</p> http://mathoverflow.net/questions/57808/correlated-brownian-motion-and-poisson-process/57855#57855 Answer by Alekk for Correlated Brownian motion and Poisson process Alekk 2011-03-08T16:50:45Z 2011-03-08T17:48:33Z <p>At least you can do that on your computer: take a time discretization parameter $\Delta t$ and an iid sequence of random variables $(\xi_k, P_k)$ where $\delta_k$ is $Poisson(\Delta t)$ and $\xi$ is centred Gaussian with variance $\Delta t$ and define $W_{t} = \sum_{k \Delta t &lt; t} \xi_k$ and $N_t = \sum_{k \Delta t &lt; t} P_k$. </p> <p>There are many non-trivial coupling $(\xi,P)$, and each one of them gives you a non-trivial approximation of what you are looking for. I would not be surprised if a limiting argument $\Delta t \to 0$ gives you a genuine example of a coupling of a Brownian motion and a Poisson process adapted to the same filtration: nevertheless, this does not seem to be a very tractable way of defining things -- this might be good for simulation purposes though, as I am guessing that there are some maths-finance questions related to this construction.</p> <p>: it seems like that we careful coupling $(\xi,P)$, you might be able to get a limiting process that has a generator equal to $$\mathcal{L}f(x,y) = f(x,y+1)-f(x,y) + \frac{1}{2} \partial^2_{xx}f(x,y) + K \cdot \Big(\partial_x f(x,y) - \partial_x f(x,y+1) \Big)$$ where $K \neq 0$ is a constant. I have not checked that $\mathcal{L}$ is actually a generator and that one can then define a Markov process from such a generator. If this happens to work, it seems like this is a good way to define such a coupling of a Brownian motion and a Poisson process.</p> http://mathoverflow.net/questions/40294/potts-model-simulation Potts model simulation Alekk 2010-09-28T10:23:28Z 2011-03-05T00:57:56Z <p>I was wondering what were the state-of-the-art methods to simulate low temperature configurations of Potts-like models that exhibit a discontinuous phase transition. For models with a continuous phase transition, annealing methods (parallel tempering, simulated tempering and their friends) work pretty well: nevertheless, for discontinuous phase transition, these methods are typically not satisfying because a huge number of intermediate temperatures are needed.</p> <p>Is there any other approach that has proven efficient?</p> http://mathoverflow.net/questions/53975/exact-simulation-of-sde Exact simulation of SDE Alekk 2011-02-01T11:23:18Z 2011-02-01T16:32:25Z <p>Consider a one dimensional SDE of the form $dX_t = \mu(X_t) dt + \sigma dW_t$, where $\sigma>0$ is a <strong>constant</strong>. Under mild regularity assumptions on $\mu(\cdot)$, one can exactly simulate trajectories of this SDE: because $\sigma$ is constant, one can first exactly simulate a (scaled) Brownian motion $dY_t = \sigma dW_t$ and use the fact that (Girsanov) $\text{Law}(x)$ and $\text{Law}(Y)$ are equivalent to do some kind of <a href="http://en.wikipedia.org/wiki/Rejection_sampling" rel="nofollow">rejection sampling</a> on the Wiener space. See <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aoap/1133965767" rel="nofollow">here</a> for more details.</p> <p>If $\sigma(\cdot)$ is not constant, in the one dimensional case, one can always find a function $\Psi$ such that $Z_t = \Psi(W_t)$ is of the form $dZ_t = \hat{\mu}(Z_t) dt + \sigma(Z_t) dW_t$: this follows from the fact that any $1$-dimensional continuous function is a derivative. This shows that a large class of $1$-dimensional SDE can be exactly simulated.</p> <p><strong>Question</strong>: the situation is quite different in $\mathbb{R}^d$ for $d \geq 2$: is there any diffusion $dX_t = \mu(X_t)dt + \sigma(X_t) \cdot dW_t$ that can be exactly simulated and that cannot be obtained through rejection sampling based on the process $Z_t = \Psi(W_t)$ for a well chosen function $\Psi:\mathbb{R}^n \to \mathbb{R}^d$.</p> http://mathoverflow.net/questions/52635/maximum-variance-unfolding maximum variance unfolding Alekk 2011-01-20T15:32:30Z 2011-01-20T16:45:24Z <p>Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the configuration of $n$ vectors $X_1, \ldots, X_n \in \mathbb{R}^n$ that maximizes the weighted sum $$V(X_1, \ldots, X_n) = \pi_1 \|X_1\|^2 + \ldots + \pi_n \| X_n\|^2$$ under the constraints $\|X_{i+1}-X_i\| \leq d_i$ for $i=1, 2, \ldots, n-1$ and $\sum_i \pi(i) X_i = 0$.</p> <p><strong>Motivation:</strong> as described in this <a href="http://www.cis.upenn.edu/~taskar/courses/cis700-sp08/papers/maxvar_unfold.pdf" rel="nofollow">article</a>, this is another formulation of the following problem: among all possible reversible Markov chain in continuous time that have $\Pi=(\pi_1, \ldots, \pi_n)$ as invariant distribution on ${ 1, \ldots, n}$ and that can only jump on neighbouring sites, find the one that has maximum spectral gap, under a certain (linear) constraint on the jump intensities.</p> <p><strong>Remarks:</strong> </p> <ul> <li>one can consider the more general problem where the constraints are $\|X_i-X_j\| \leq d_{i,j}$: one can show that this is equivalent to a semidefinite programming optimization problem. It seems in general hard to solve; see above mentioned article.</li> <li>the case $\pi(1) = \ldots = \pi(n)$ is exactly solvable and an optimal configuration is a set of $n$ collinear vectors $X_i = \alpha_i U$, where the $\alpha_i$'s are easily computable; in this case, the problem is equivalent to maximizing $\sum_{i,j} \|X_i-X_j\|^2$.</li> </ul> http://mathoverflow.net/questions/51090/change-of-time-or-change-of-measure/51109#51109 Answer by Alekk for Change of time or change of measure Alekk 2011-01-04T11:23:46Z 2011-01-04T11:23:46Z <p>for example, if $\sigma$ is a constant, then $Y$ satisfies $dY_t = \sqrt{a} \sigma dW_t$ so that the law $\mathbb{Q}_Y$ and $\mathbb{Q}_X$ of the processes $Y$ and $X$ on the Wiener space $C([0;T],\mathbb{R})$ are generaly singular: in other words $\frac{d \mathbb{Q}_Y}{d \mathbb{Q}_X} = 0$ if $|a| \neq 1$.</p> http://mathoverflow.net/questions/39491/a-point-process-is-characterized-by-its-void-probabilities a point process is characterized by its void probabilities Alekk 2010-09-21T12:54:19Z 2010-12-08T16:16:23Z <p>Consider a planar point process $X$ and call $N_A = \text{Card}\big( X \cap A\big)$ the number of points inside the subset $A \subset \mathbb{R}^2$. If one knows the law of <code>$(N_{A_1}, \ldots, N_{A_r})$</code> for any sets $A_1, \ldots, A_r$, then the process is completely characterized. I recently learned that it in fact suffices to know $f(A)=P(N_A=0)$ (called the void-probability function) for any set $A$ in order to completely characterize the law of $X$.</p> <p>Intuitively, I do not understand why such a result is true. Indeed, the knowledge of the function $f$ brings some information in the correlation structure of the process $X$: nevertheless, I still fail to understand how the function $f$ can encode the whole correlation structure of the process. Any thoughts on this ?</p> http://mathoverflow.net/questions/45238/scalar-diffusions-are-reversible scalar diffusions are reversible Alekk 2010-11-07T23:47:36Z 2010-11-08T17:16:59Z <p>It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for multidimensional diffusions. The usual proofs consists in writing down generators, speed functions etc...</p> <p>I am trying to intuitively understand this result, and the only (not very satisfying) argument that I have found is the following. It is straightforward to check that any Markov chain on $\mathbb{Z}$ that has an invariant probability $\pi$ and that can only make jumps of size $+1$ or $-1$ is reversible: notice for example that $$F(k) = \pi(k)p(k,k+1)-\pi(k+1)p(k+1,k)$$ is independent of $k$ and is thus equal to $0$. If $a(\cdot)$ and $\sigma(\cdot)$ are regular enough, a diffusion can be seen as a limit of such Markov chains on $\epsilon \mathbb{Z}$ so that this makes the result plausible.</p> <p><strong>question</strong>: what are arguments/proofs/examples that could shed light on why a one dimensional ergodic diffusion is automatically reversible.</p> http://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin/45100#45100 Answer by Alekk for When do 3D random walks return to their origin? Alekk 2010-11-06T21:30:08Z 2010-11-06T21:30:08Z <p>No, any true 3d random walk is transient. (true in the sense that this is not a 2d random walk in disguise)</p> http://mathoverflow.net/questions/42594/concavity-of-det1-n-over-hpd-n/42760#42760 Answer by Alekk for Concavity of $\det^{1/n}$ over $HPD_n$. Alekk 2010-10-19T09:33:12Z 2010-10-19T09:33:12Z <p>An easy reduction shows that one can suppose that one of the matrices is the identity and the other diagonal: the inequality then reduced to the convexity of $f(x)=\ln(1+e^x)$.</p> http://mathoverflow.net/questions/23969/initial-condition-of-a-diffusion-approximation initial condition of a diffusion approximation Alekk 2010-05-08T23:01:25Z 2010-09-29T04:48:54Z <p>I am trying to prove that a certain sequence of Markov chains $x^N_k$ converges towards a diffusion process. The invariant measure of $x^N$ is $\pi^N$ and the Markov chain $x^N$ is started in stationarity $x^N_0 \sim \pi^N$. It is also assumed that $\pi^N$ converges (in laws) to a limiting probability distribution $\pi$.</p> <p>The idea of the diffusion approximation is then pretty simple, and runs roughly as follows: we can write $$x^N_{k+1}-x^N_k = \mu(x^N_k) \Delta_N + m^N_k \sqrt{\Delta_N}$$ where $\Delta_N$ is a time step that goes to zero as $N \to \infty$ and $\mu(\cdot)$ is a deterministic function and $m^N_k$ is a martingale difference with respect to the natural filtration generated by $x^N$. It happens that a martingale central limit theorem applies in this case and that it can be shown that $$W^N(t) = \sqrt{\Delta_N} \sum_{k &lt; [\frac{t}{\Delta_N}]} m^N_k$$ converges in laws to a Brownian motion $W$. This is why the sequence of rescaled Markov chain $U^N(t) = x^N(t/\Delta_N)$ should converge in laws to the diffusion $$dU_t = \mu(U_t) \ dt + dW_t, \quad U_0 \sim \pi,$$ where $W$ is independent from the initial position $U_0$.</p> <p>If we can show that the couple $(x^N_0, W^N)$ converges in laws to $(U_0,W)$ where $U_0$ is independent from $W$, a continuous mapping argument gives the conclusion.</p> <p><strong>Question:</strong> in short, it is assumed that $x^N_0 \sim \pi^N$ converges in law to $U_0 \sim \pi$ and it can be shown that $W^N \to W$. This seems always true that $W$ is independent from $U_0$, is it ? How can one ensure that $W$ is adapted to a filtration $\mathcal{F}_t$ with $U_0 \in \mathcal{F}_0$ ?</p> <p><strong>Rephrasing:</strong> consider a sequence of martingales $M^N$, not starting from $0$, adapted to the filtrations $\mathcal{F}^N$. Let us also assume that the distribution $\pi^N$ of $M^N_0$ converges in law to a distribution $\pi$. If a martingale invariance principle applies to the sequence of martingales $X^N_k = M^N_k - M^N_0$, is it true that the original sequence $M^N$ also converges in laws to a modified "Brownian motion" $W$ with $W_0 \sim \pi$ ?</p> <p>Ps: the whole point of this pedestrian approach is to avoid the usual generator-based theorems that ensure that a diffusion approximation is valid.re</p> http://mathoverflow.net/questions/34745/connection-between-the-gaussian-and-the-cauchy-distribution connection between the Gaussian and the Cauchy distribution Alekk 2010-08-06T08:31:30Z 2010-08-21T14:27:12Z <p>I have always been surprised by the fact that the quotient of two independent Gaussian random variables is a Cauchy Random variable - as this is often the case, coincidence in mathematics are not accidental: is there any deep explanations behind this connection between the Gaussian and the Cauchy distribution ?</p> <p><strong>other examples:</strong></p> <ul> <li>if a $2$-dimensional Brownian motion $(X_t, Y_t)$ is started at $(0,1)$ and stopped the first time $T$ that it hits the real axis, then $X_T$ is also distributed as a Cauchy distribution.</li> <li>the Cauchy distribution also shows up when studying how a complex brownian motion winds around the origin.</li> </ul> http://mathoverflow.net/questions/30149/examples-where-physical-heuristics-led-to-incorrect-answers Examples where physical heuristics led to incorrect answers? Alekk 2010-07-01T07:10:20Z 2010-07-09T13:42:09Z <p>I have always been impressed by the number of results conjectured by physicist, based on mathematically non-rigorous reasoning, then (much) later proved correct by mathematicians. A recent example is the $\sqrt{2+\sqrt{2}}$ connective constant of the honeycomb lattice, derived non rigorously by the physicist B. Nienhuis in 1982 and rigorously <a href="http://www.unige.ch/~smirnov/papers/saw.pdf" rel="nofollow">proved</a> this year by S. Smirnov and H. Duminil-Copin.</p> <p>I would be interested in knowing examples of results conjectured by physicists and later proved wrong by mathematicians. Furthermore it would be interesting to understand <em>why</em> physical heuristics can go wrong, and how wrong they can go (for example, were the physicists simply missing an important technical assumption or was the conjecture unsalvagable).</p> http://mathoverflow.net/questions/131156/how-can-i-randomly-draw-an-ensemble-of-unit-vectors-that-sum-to-zero/131183#131183 Comment by Alekk Alekk 2013-05-20T02:18:25Z 2013-05-20T02:18:25Z Any rough guess on the order of magnitude of the mixing time of this Markov chain? http://mathoverflow.net/questions/131156/how-can-i-randomly-draw-an-ensemble-of-unit-vectors-that-sum-to-zero Comment by Alekk Alekk 2013-05-20T01:58:18Z 2013-05-20T01:58:18Z suppose that you have computed the densities $d_2(\cdot)$ and $d_3(\cdot)$ of the law of the sum of $2$ and $3$ unit vectors. You can first simulate the sum $\sum_1^3 v_i$ conditionally on $\sum_1^6 v_i=0$ by simulating from a distribution proportional to $d_3^2$ (rejection sampling). You can then simulate $v_1$ and $\sum_1^5 v_i$ conditionally on the value of $X$ by simulating from a density on the unit sphere that is proportional to $d_2(X-v)$ (again, rejection sampling). Remains then to simulate $\sum_1^2 v_i$ and $\sum_1^4 v_i$ by the same approach. http://mathoverflow.net/questions/123665/the-limiting-behavior-of-geometric-random-walk Comment by Alekk Alekk 2013-03-06T09:06:23Z 2013-03-06T09:06:23Z silly remark: the case d=2 leads to usual Brownian scaling by considering the chain at even times (this is a usual random walk on Z^2). http://mathoverflow.net/questions/110721/invertibility-of-a-matrix-with-a-gaussian-perturbation Comment by Alekk Alekk 2012-10-26T09:06:07Z 2012-10-26T09:06:07Z You can write $det(A+G)$ has a polynomial in $G_{ij}$ and the set of zeroes of $det(A+X)$ has null Lebesgue measure on $\mathbb{R}^{n^2}$. Since $(G_{ij})_{ij}$ can be seen as a standard Gaussian in $\mathbb{R}^{n^2}$, the result follows. http://mathoverflow.net/questions/110659/hitting-probability-for-integrated-ornstein-uhlenbeck-process Comment by Alekk Alekk 2012-10-25T16:28:53Z 2012-10-25T16:28:53Z Since $V$ can stay an arbitrarily long time in any ball of R^d isn't it obvious that H(r)=1 if H(r) is the probability that X ever hit S_r. http://mathoverflow.net/questions/110559/contraction-property-for-conditioned-sdes/110600#110600 Comment by Alekk Alekk 2012-10-25T14:20:12Z 2012-10-25T14:20:12Z Thank you Fedja, I now understand what is going on and can cook up simple examples where one can see why the contractive coupling cannot be constructed. Many thank!. http://mathoverflow.net/questions/110559/contraction-property-for-conditioned-sdes Comment by Alekk Alekk 2012-10-25T12:17:10Z 2012-10-25T12:17:10Z adding this correction the drift then reads $-\nabla U(X) + c(X)$ and this leads to $d \|X-Y\|^2 = -2\langle X-Y, \nabla U(X)-\nabla U(Y) -c(X)+c(Y)\rangle$ which has no reason to be negative. http://mathoverflow.net/questions/110559/contraction-property-for-conditioned-sdes Comment by Alekk Alekk 2012-10-25T10:09:47Z 2012-10-25T10:09:47Z Thanks TheBridge: yes, but to get the expression for the conditioned SDE you typically need to have analytical expressions for the transition probabilities (and then do a h-transform), which is not the case in general. Will have a look at the mentioned references. http://mathoverflow.net/questions/110559/contraction-property-for-conditioned-sdes/110600#110600 Comment by Alekk Alekk 2012-10-25T09:02:06Z 2012-10-25T09:02:06Z Thank you Fedja. I afraid I do not completely understand your comments, though. Are you talking about the non-conditioned case. Your potential verifies $\lambda = \inf_x U^{′′}(x)=0$ so one can only say that $F(t)$ can be made non-increasing (and tend to $0$). Also, my question was asking if it were possible to find a coupling $(X,Y)$ such that conditioned on $(X_0,Y_0)=(x_-,y_-)$ and $(X_T,Y_T)=(x_+,y_+)$ the difference $|X_{T/2}-Y_{T/2}|$ is on average less than $\frac{1}{2}(|x_--y_-|+|x_+-y_+|)$. I am sorry if I misunderstood your comment. http://mathoverflow.net/questions/110585/modification-of-doob-inequality Comment by Alekk Alekk 2012-10-24T21:59:28Z 2012-10-24T21:59:28Z How do you know that this inequality holds? http://mathoverflow.net/questions/110346/if-two-probability-distributions-have-the-same-weak-limit-and-one-of-them-satisfi Comment by Alekk Alekk 2012-10-22T19:18:34Z 2012-10-22T19:18:34Z two sequences can converge to the same limit but at very different speed. http://mathoverflow.net/questions/110092/ising-model-on-a-cycle/110222#110222 Comment by Alekk Alekk 2012-10-21T10:39:52Z 2012-10-21T10:39:52Z Thank, that's a great answer. I was trying the other day to see how long it would take to couple an all +1 configuration with an all -1 configuration, and one can see that the coupling time stays bounded wrt $d$. http://mathoverflow.net/questions/110092/ising-model-on-a-cycle Comment by Alekk Alekk 2012-10-19T15:26:43Z 2012-10-19T15:26:43Z Thank you for the comment, I have updated the notations. As you said, I really meant &quot;size&quot; instead of &quot;dimension&quot;. And I should not have written that the mixing time does not depend on d; what I really meant is that the mixing time $\tau(d)$ seems to stay bounded as $d$ goes to infinity. http://mathoverflow.net/questions/107472/minimum-of-two-probability-densities Comment by Alekk Alekk 2012-09-18T19:51:20Z 2012-09-18T19:51:20Z @George: great! I can't believe that I missed that. I did notice that the whole thing was invariant by rearrangement but did not see that $E \|X\|^d$ was decreasing. Many thanks! http://mathoverflow.net/questions/100254/positive-estimator Comment by Alekk Alekk 2012-06-24T22:37:05Z 2012-06-24T22:37:05Z to put it another way: I know how to simulate random samples from the random variable $X$ that has $\mu$ as mean (it takes a finite amount of computer time for each draw) and I would like to generate a random sample from a random variable Y that has $e^\mu$ as a mean. The cost of generating the random variable $Y$ must take a finite amount of computer time (on average).