User paul tupper - MathOverflow

Answer by Paul Tupper for Properties of the Euler Discretization of a diffusion

2012-11-17T16:10:33Z

What you call the Euler discretization is sometimes called the Euler-Maruyama discretization. There is a lot of literature about its convergence properties. One place to look is the classic book by Kloeden and Platen (Numerical Solution of Stochastic Differential Equations). Another is Milstein and Tretyakov (Stochastic Numerics for Mathematical Physics). A very convenient and readable introduction is the paper by Des Higham http://epubs.siam.org/doi/pdf/10.1137/S0036144500378302.

Is this a situation where triple mutual information is always non-negative?

2012-02-13T18:45:44Z

Suppose I have three identically-distributed homogeneous continuous-time discrete state space Markov chains $X_1(t), X_2(t), X_3(t)$, $t\geq 0$. They evolve independently but share a common random variable $X_0$ as an initial condition. I let $$X_1=X_1(t_1), \ \ \ X_2=X_2(t_2), \ \ \ X_3=X_3(t_3)$$ for some times $t_1, t_2, t_3\geq 0$.

I want to show that $$ I(X_1; X_2; X_3) \geq 0 $$ where $I$ is the multivariate mutual information (or information interaction) $$ I(A,B,C)= H(A,B,C) -H(A,B) - H(B,C) - H(A,C) + H(A) + H(B) + H(C) $$ where $H$ is the usual Shannon entropy.

Background/Motivation

There are well-known situations where $I(A;B;C)<0$, a famous one being if $A$ and $B$ are independent random variables, each $\pm 1$ with probability $1/2$, and $C=AB$. But I conjecture that in the case I have described above $I(X_1;X_2;X_3)\geq 0$. I believe that the Markov chains being continuous-time and homogeneous is essential.

The more general motivation is that I want to find very general situations where multivariate mutual information is non-negative. (One well-known example is if $A,B,C$ form a Markov chain.)

Answer by Paul Tupper for Metric properties for $d:X\times X\times...X\rightarrow\mathbb R$

2012-06-21T04:06:39Z

There are quite a few people who have tried to generalize metrics to more than two variables. I once tried to track down all the references on this subject for a paper. Here are some:

There is an extensive literature on 2-metrics, in which $d$ takes 3 arguments. This appears to have been introduced by Gahler. Here is a recent example with some references.

What James Cranch mentions in his answer is (I think) originally due to Menger (K. Menger, Untersuchungen uber allgemeine Metrik, Math. Ann. 100.). Menger takes $d$ to be the volume of an $n$-simplex in Euclidean space. Then he tries to abstract away from that. (I can't read German so take this summary with a grain of salt.)

Three recent papers that seek such generalizations are by Deza and Rosenberg (Small cones of $m$-hemimetrics), by Chepoi and Fichet (A note on three-way dissimilarities and their relationship with two-way dissimilarities), and by Warren ($n$-way metrics).

My impression from all of these is that there is no one natural way to extend metrics to take more than 2 arguments.

Time reversibility of Stratonovich Diffusion: Reference Request

2012-04-25T20:22:26Z

Please consider the Stratonovich stochastic differential equation (SDE) $$ dX = b(X)\circ dB $$ where $B$ is standard Brownian motion and $X(0)=X_0$. This corresponds to the Ito (SDE) $$ dX = \frac{1}{2} b(X) b'(X) dt + b(X) dB. $$

I would like a reference showing (or even just stating) that trajectories of this equation are time-reversible in the following sense: that for all $m\geq 1$ and $t_m > t_{m-1} > \ldots > t_1 >0$, the joint distribution of $$ (X(t_1), \ldots, X(t_m) ) $$ is identical to the joint distribution of $$ (X(-t_1), \ldots, X(-t_m) ). $$

Also, is there a particular term for this kind of time-reversibility? People also use time-reversibility to mean detailed balance for systems in equilibrium, which is different from this.

Motivation In a paper I am listing advantages of expressing diffusions in terms of the Stratonovich convention. I want to be able to briefly state that if the drift coefficient in a Stratonovich SDE is 0, then the equation is time-reversible in the sense I state above.

Edit: Further Explanation Here is a clarification of what I mean above, as well as a justification of my claim.

Let $B(t)$ for $t \in \mathbb{R}$ be two-sided Brownian motion with $B(0)=0$. Let $X(t)$ solve the above Stratonovich SDE. Let $Y(t)=X(-t)$. Then $$ dY(t) = dX(-t) = -b(X(-t)) \circ dB(-t) = b(Y(t)) \circ d\tilde{B}(t) $$ where $\tilde{B}(t) = -B(-t)$ is also a Brownian motion. So $Y$ solves the same equation as $X$ with a different Brownian motion. These formal manipulations can be justified by letting $B$ be approximated by smooth stochastic processes and then taking the limit using the Wong-Zakai result.

Thanks for any help!

Answer by Paul Tupper for Solving SDE's on subsets of $R^n$.

2012-03-16T20:58:27Z

One idea is to approach the problem through stochastic differential equations with reflections off the boundary of domains. For example, this paper by Tanaka (1979) considers a stochastic differential equation with reflections off the boundary of a convex set. They prove existence and uniqueness for coefficients defined on the domain only, and as far as I can see, in the proof they don't extend the coefficients to all of $\mathbb{R}^d$. If unique solutions exist with reflecting boundary conditions for all time, then presumably the original equation has a solution up to hitting the boundary. A more recent reference is Lions and Sznitman (1984).

This is a bit inelegant in that an SDE stopped at the boundary should be simpler than an SDE reflected off a boundary. But a least you don't need to extend the domain of the coefficients.

Answer by Paul Tupper for Is this a situation where triple mutual information is always non-negative?

2012-02-20T02:33:29Z

My conjecture in the original question is false.

Let $X_i(t)$ be continuous time Markov chains with two states 0 and 1, such that the rate of transition from 0 to 1 and from 1 to 0 is $1$. Let $X_0$ be 0 with probability $0.9$ and 1 with probability $0.1$. Choose $t_1=t_2=t_3$ such that the probability that $X_i=X_0$ is $3/4$ for all $i$.

Then for all $i$, $$ H(X_i)=0.88129 \ldots, $$ and for all $i\neq j$, $$ H(X_i,X_j)= 1.75448 \ldots, $$ and $$ H(X_1,X_2,X_3)=2.61812 \ldots $$ This gives $$ I(X_1;X_2;X_3) = -0.00144 \ldots < 0. $$

I don't yet have any insight into why the triple mutual information is negative. This is about as negative as I could make it with the two state symmetric Markov chain.

Answer by Paul Tupper for A nonlinear system with special structure

2011-09-27T19:38:58Z

It seems unlikely that your problem is going to have a solution in the generality you've described but here goes. There are two approaches you could try.

(1) Discretize the partial derivatives using finite differences on the grid. At every point on the grid your PDE will give you a nonlinear equation. You will have a total of $n^2$ equations in $n^2$ unknowns. But each equation will only contain a small number of unknowns. You can use a variant Newton's method to solve these equations. But you have to work with the restrictions that you probably don't want to code up the Jacobian for the system, and you could not use a direct method to calculate the solution even if you did. I would recommend looking at a Jacobian-Free Newton-Krylov method.

(2) Exploit the method of characteristics. Rewrite your equation as $$ (cz+d) z_x - (az+b) z_y = 0. $$ This gives characteristic equations $$ \frac{dx}{dt}=cz+d, \ \ \ \frac{dy}{dt}=a z+b, \ \ \ \frac{dz}{dt}= 0. $$ There are numerical methods for solving nonlinear hyperbolic equations exploiting characteristics. Sethian and Vladimirsky have a nice one. Your problem does not quite fit into their scheme but their paper might help give you ideas.

So, if you problem does have a solution, one of these might work. I would expect (1) to be more robust than (2), but also more expensive.

Isometries between metric spaces

2011-08-21T04:11:59Z

I have three questions about when you can show there is an isometry between metric spaces.

(1) If there is an injective non-expanding map from $X$ to $Y$ and an injective non-expanding map from $Y$ to $X$, are $X$ and $Y$ isometric?

I think the answer must be no, just let $X=[0,1]$ and $Y=[0,1/2]$ with the Euclidean metric on each and let the morphisms just shrink each of the intervals by a 1/2. But $X$ and $Y$ are not isometric as metric spaces. The only reason I ask is that this question seems to imply that this is true for compact metric spaces. So maybe I am just missing something.

(2) If there is an isometric embedding from $X$ to $Y$ and an isometric embedding from $Y$ to $X$ is it true that $X$ and $Y$ are isometric?

Here by an isometric embedding I mean a map that preserves the metric.

(3) If the answer to (2) is yes, is there something to be said about which concrete categories this result holds for, with respect to embeddings?

Here I am taking the definition of concrete categories and embeddings from Adámek, Herrlich, Strecker.

I know this question sounds a lot like this question, but unless I am confused, they are talking about injective maps (monomorphisms) which make sense in any category, whereas I am talking about embeddings which are only defined for concrete categories.

EDIT: Edited to remove jargon and make clearer.

Thanks very much for any information.

Answer by Paul Tupper for How long does it take a Brownian particle to achieve a uniform probability distribution across a space?

2011-08-10T17:37:09Z

Let $\rho(t,x)$ be the probability that the particle is at location $x$ at time $t$. $\rho$ satisfies the equation $\rho_t = \rho_{xx}$, with $\rho(0,x)=\delta(x-x_0)$ where $x_0$ is the starting position. You have Neumann boundary conditions on the boundary of your domain. Suppose the eigenfunctions of the negative Laplacian of your domain with Neumann boundary conditions are $\phi_0, \phi_1, \ldots$ with corresponding eigenvalues $\lambda_0 \leq \lambda_1 \leq \lambda_2 \cdots$. $\phi_1$ is constant with $\lambda_0=0$. The solution to the equation is $$ \rho(t,x)= \sum_{j=0}^\infty c_j e^{- \lambda_j t} \phi_j (x) $$ where $c_j$ is the inner product of $\delta(x-x_0)$ with $\phi_j$ which gives $c_j=\phi_j(x_0)$. When $t$ goes to infinity you just get a constant for $\rho$. Your question is (I think) equivalent to asking how long does it take for all the $j>0$ terms to die out. Assuming $c_1 \neq 0$, this will be determined by $\lambda_1$; a bigger $\lambda_1$ means faster approach to uniform probability. There is not going to be an explicit formula for $\lambda_1$ for most domains. But you can get some intuition. As Alice says, if you have two equal volumes with a narrow connection, then $\lambda_1$ is going to be very small and it will take a long time for $\rho$ to be flat. (Unless you start exactly midway between the two volumes. This corresponds to $c_1=0$.)

Answer by Paul Tupper for Are there any physical phenomena of the heat transfer critically depending on diffusion coefficient?

2011-08-09T04:16:59Z

What you describe is very much expected from the statistical physics principle "there is no phase transition in one-dimensional systems with short-range interactions at $T>0$." See Lower Critical Dimension in Wikipedia. Since you have a PDE your interactions are short-range. Since you have noise, this corresponds to $T>0$, i.e. non-zero temperature. The principle states that you should not observe a phase transition when you vary $\nu$ in 1 dimension, but you may in 2 or 3 dimensions.

Answer by Paul Tupper for Comparing eigenvalues of A+B and A where both A and B are positive definite matrices

2011-07-29T04:48:23Z

Yes. Weyl's inequality for matrices shows that what you say is true.

Answer by Paul Tupper for Residency time of a spherical Brownian particle in a cylindrical container with another spherical particle at a fixed position

2011-07-17T04:49:45Z

You can use the Feynman-Kac formula to get the Moment Generating Function of the time it takes the particle to leave.

I will consider the case where you fix $P_1$ and let $P_2$ move. Whatever the geometry of your problem, you can get an equivalent problem with a point particle diffusing in some region in space, where there is one wall that it reflects off (let's call it $\Gamma_0$) and another where it is absorbed (let's call it $\Gamma_1$.) Let $X(t)$ be the position of the particle at time $t$. Let $T$ be the time at which the process first hits $\Gamma_1$. Let $f(x,\lambda) =E [ e^{\lambda T} | X(0)=x]$. Then Feynman-Kac gives you that $f$ satisfies $\nabla^2 f/2 + \lambda f =0$ with $\frac{\partial f}{\partial n} = 0$ on $\Gamma_0$ and $f=1$ on $\Gamma_1$. This is the Helmholtz equation on your domain with mixed boundary conditions. $f(x,\lambda)$ is the moment generating function of $T$ with $X(t)=x$, evaluated at $\lambda$. So now you can compute the mean of $T$, etc.

One geometry for your problem for which you can get an exact solution for each $\lambda$ is if you have one sphere fixed at the middle of the big sphere and you are tracking a point particle that diffuses, bounces off the small sphere and is absorbed by the big sphere. In that case the solutions to the PDE are spherical Bessel functions.

Does the random Lorenz gas have a non-trivial diffusion coefficient?

2011-07-13T03:13:41Z

For the periodic Lorenz gas Sinai showed that rescaling the trajectory of the tracer particle yields Brownian motion in the limit. Does there exist a similar result for the random Lorenz gas? If not, do people believe that there is such a limit?

By the random Lorenz gas I mean: take circular scatterers distributed uniformly at random in the plane conditioned on the scatterers not overlapping. The scatterers are fixed. The tracer particle is a point that moves with constant speed and has perfectly elastic collisions with the scatterers. An initial condition is chosen at random (say, by picking an initial point away from a scatterer and then picking the initial angle uniformly on $[0,2\pi)$.)

The numerical experiments in Dettmann and Cohen, 2000 suggest that there is diffusive behaviour for the random Lorenz gas. This article by Bunimovich states that it is believed that velocity autocorrelation decays polynomially, but does not mention whether it decays fast enough for there to be a finite diffusion coefficient.

Comment by Paul Tupper

2012-11-19T19:24:17Z

Also, I'm not sure what you're looking for, but Chapter 5 of Milstein and Tretyakov is "Simulation of space and space-time bounded diffusions". Subsection 5.4.3 is "Approximation of exit point" for SDEs.

Comment by Paul Tupper

2012-11-19T19:20:33Z

I see that Dan has already answered this, but the proof of convergence in the sup norm is in Theorem 9.6.2 of the 1st edition of Kloeden and Platen.

Comment by Paul Tupper

2012-11-12T18:27:38Z

The following paper might help you identify situations where there is an explicit expression for the moment generating function of the integral arxiv.org/abs/0710.1599 (Albanese and Lawi, 2007.)

Comment by Paul Tupper

2012-09-14T14:47:38Z

One place to look is the papers of David E. Stewart. The main application area he works in is rigid body dynamics.

Comment by Paul Tupper

2012-08-27T20:42:51Z

Thanks for these references, and your comments. I will contact you in an e-mail.

Comment by Paul Tupper

2012-07-04T15:12:28Z

Do you mean to write "with slope nearly R/n"? Isn't n the variable on the x-axis?

Comment by Paul Tupper

2012-06-21T15:38:41Z

@Kamran I guess you could look at journals that have recently published articles on bitopological spaces and try sending your work there.

Comment by Paul Tupper

2012-03-14T17:25:53Z

Why would your $\tau$ have expectation $\infty$? Wouldn't it be dominated by the expected time until $X_t$ leaves $[-1,1]$?

Comment by Paul Tupper

2012-03-08T23:58:16Z

This might be a good lead: arxiv.org/abs/math/0401382 by Chen and Griffin. In particular, see Figure 3 on page 42.

Comment by Paul Tupper

2012-02-17T05:34:37Z

You also might want to check out this article: [Unitary integrators and applications to continuous orthonormalization techniques](jstor.org/pss/2158162) by Dieci, Russell, and van Vleck.

Comment by Paul Tupper

2012-02-13T18:55:55Z

It's not clear to me what you mean by "$\nu(t)$ is a stochastic variable". You have to specify what the covariance is between $\nu(t)$ and $\nu(s)$. In his answer, Jon has interpreted $\nu(t)$ to be Gaussian white noise. Is this what you meant?

Comment by Paul Tupper

2011-11-26T21:35:17Z

This is a tridiagonal symmetric Toeplitz matrix. There are explicit expressions for its eigenvectors and eigenvalues. For example, they are in Iserles' A First Course in the Numerical Analysis of Differential Equations. Is this for a course you are taking?

Comment by Paul Tupper

2011-10-25T04:03:59Z

In some of the places where you write $f(s,x)$ do you mean $f(s,y)$? For example, in your first equation can't you just bring the $f(s,x)$ out of the integral?

Comment by Paul Tupper

2011-09-24T16:15:50Z

Doesn't the process $W_t=0$ for all $t$ almost surely satisfy all the conditions and also have continuous paths? What book is this?

Comment by Paul Tupper

2011-09-01T03:41:01Z

What are your boundary conditions? Are you sure that the equation has a unique solutions?