User alekk - MathOverflow

Answer by Alekk for The limiting behavior of geometric random walk

2013-03-06T09:32:08Z

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

contraction property for conditioned SDEs

2012-10-24T16:31:05Z

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 $(*)$.

Question: 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<\beta<\frac12$ is some constant that does not depend on $(x_-,x^+,y_-,y^+)$. Is this known or have already been studied? Any reference welcome.

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

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

Ising model on a cycle

2012-10-19T13:05:51Z

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.

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?

[1] Chapter 14 of Markov Chains and Mixing Times by D. Levin, Y. Peres and E. Wilmer

Brownian motion inside a domain

2012-09-30T14:19:03Z

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?

minimum of two probability densities

2012-09-18T13:52:25Z

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] < \infty$. Are there smooth densities verifying this moment condition such that $\iint_{u,v} \ \min\big(\pi(u), \pi(v) \big) \ du \ dv = \infty$ ?

No answer given on math.stackexchange. This integral appeared while studying a Metropolis-Hastings Markov chain.

Positive estimator

2012-06-21T15:39:16Z

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

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

"birds on wire" type problem

2012-04-07T15:10:54Z

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

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.

What about the case where the random variables $X_{i,j}$ are independent and exponentially distributed, say? Has it been studied in the literature?

Answer by Alekk for Correlations in last-passage percolation

2011-12-18T19:44:55Z

For those who wonder how the geodesics look like, here is a quick simulations (with exponential weights):

Constructing Bernoulli random variables with prescribed correlation

2010-03-26T11:37:04Z

For which $n \times n$ correlation matrix $C$ can one construct Bernoulli random variables $(B_1, \ldots, B_n)$ with correlation $C$ ?

Following the approach described in this MO thread, 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.

1: Is there any example of correlation structure that cannot be obtained this way ?

2: Any easy example of correlation matrix $C$ that cannot be the correlation matrix of a $\{0,1\}^n$ valued random vector ?

Brownian motion and spheres

2010-03-22T14:54:00Z

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

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

Answer by Alekk for Diffusion sample paths as deformed Brownian sample paths

2011-07-01T13:58:40Z

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.

Answer by Alekk for law of iterated logrithm

2011-06-28T08:07:52Z

Girsanov's theorem tells you that on any finite 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.

comparing diffusions

2010-12-13T11:07:19Z

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.

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

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 ?

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

weighted Poincare inequality

2011-02-06T19:46:58Z

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

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

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

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.

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

Answer by Alekk for Will a random walk on [0, inf) tend to infinity?

2011-04-03T11:58:01Z

As it has been said:

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.
if $p > \frac{1}{2}$, the law of large numbers immediately shows you that it tends to $+\infty$.
if $p < \frac{1}{2}$, you can even check the detailed balance equations and find the invariant distribution: the Markov chain is positive recurrent.

Answer by Alekk for Probability estimates for "beans & boxes"

2011-03-27T12:36:24Z

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.

I doubt that you will find a very tractable answer to your original question. Are you interested in the limit $N,P \to \infty$ ?

Answer by Alekk for Examples of Lyapunov functions for Markov processes

2011-03-23T09:14:12Z

This is called a "drift condition" in the applied probability literature -- this is used quite often when dealing with MCMC simulations, for example.

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

optimal coupling

2011-03-17T21:39:38Z

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

Answer by Alekk for Correlated Brownian motion and Poisson process

2011-03-08T16:50:45Z

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 < t} \xi_k$ and $N_t = \sum_{k \Delta t < t} P_k$.

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.

[Edit]: 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.

Potts model simulation

2010-09-28T10:23:28Z

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.

Is there any other approach that has proven efficient?

Exact simulation of SDE

2011-02-01T11:23:18Z

Consider a one dimensional SDE of the form $dX_t = \mu(X_t) dt + \sigma dW_t$, where $\sigma>0$ is a constant. 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 rejection sampling on the Wiener space. See here for more details.

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.

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

maximum variance unfolding

2011-01-20T15:32:30Z

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

Motivation: as described in this article, 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.

Remarks:

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

Answer by Alekk for Change of time or change of measure

2011-01-04T11:23:46Z

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

a point process is characterized by its void probabilities

2010-09-21T12:54:19Z

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 $(N_{A_1}, \ldots, N_{A_r})$ 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$.

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 ?

scalar diffusions are reversible

2010-11-07T23:47:36Z

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

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.

question: what are arguments/proofs/examples that could shed light on why a one dimensional ergodic diffusion is automatically reversible.

Answer by Alekk for When do 3D random walks return to their origin?

2010-11-06T21:30:08Z

No, any true 3d random walk is transient. (true in the sense that this is not a 2d random walk in disguise)

Answer by Alekk for Concavity of $\det^{1/n}$ over $HPD_n$.

2010-10-19T09:33:12Z

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

initial condition of a diffusion approximation

2010-05-08T23:01:25Z

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

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

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.

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

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

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

connection between the Gaussian and the Cauchy distribution

2010-08-06T08:31:30Z

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 ?

other examples:

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.
the Cauchy distribution also shows up when studying how a complex brownian motion winds around the origin.

Examples where physical heuristics led to incorrect answers?

2010-07-01T07:10:20Z

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 proved this year by S. Smirnov and H. Duminil-Copin.

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

Comment by Alekk

2013-05-20T02:18:25Z

Any rough guess on the order of magnitude of the mixing time of this Markov chain?

Comment by Alekk

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.

Comment by Alekk

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

Comment by Alekk

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.

Comment by Alekk

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.

Comment by Alekk

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

Comment by Alekk

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.

Comment by Alekk

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.

Comment by Alekk

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.

Comment by Alekk

2012-10-24T21:59:28Z

How do you know that this inequality holds?

Comment by Alekk

2012-10-22T19:18:34Z

two sequences can converge to the same limit but at very different speed.

Comment by Alekk

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

Comment by Alekk

2012-10-19T15:26:43Z

Thank you for the comment, I have updated the notations. As you said, I really meant "size" instead of "dimension". 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.

Comment by Alekk

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!

Comment by Alekk

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