User jon peterson - MathOverflow

Answer by Jon Peterson for Empirical distribution of a collection of iid Markov chains

2013-04-15T13:00:11Z

The model of $N$ independent 2-point Markov chains as you have describes is essentially what is known as the Ehrenfest urn chain. Much is known about this Markov chain and you can probably find what you're interested in already in the literature.

Answer by Jon Peterson for What is the order of the lower tail of a Chi-Squared distribution?

2013-02-25T13:22:46Z

You can get the correct exponential order of the decay of the probability from a large deviation principle. If $X_n$ has chi-squared distribution with $n$ degrees of freedom then $$X_n = Z_1^2 + Z_2^2 + \cdots Z_n^2,$$ where the $Z_i$ are independent standard normal random variables. Then, Cramer's theorem gives the exponential order of decay for both the left and right tails. That is, $$ \lim_{n\rightarrow\infty} \frac{1}{n} \log P( X_n < c n ) = - I(c), \quad 0 < c < 1, $$ and $$ \lim_{n\rightarrow\infty} \frac{1}{n} \log P( X_n > c n ) = - I(c), \quad 1 < c < \infty, $$ where $$ I(c) = \frac{c-1-\ln(c)}{2}. $$

Since you said that you're looking for an upper bound, it should also be noted that an examination of the proof of Cramer's theorem shows that you can actually get uniform exponential upper bounds (and not just asymptotics as stated above). In fact, $$ P(X_n < cn) \leq e^{-n I(c)}, \quad \forall n\geq 1, \text{ and } 0 < c < 1. $$

Answer by Jon Peterson for How to prove ergodic property from aperiodicity and positive recurrence

2013-02-23T18:15:38Z

You should be able to find a proof of this fact in any undergraduate stochastic processes books. Durrett's book Essentials of Stochastic Processes has a good proof of this.

I'll give an outline of how to prove it. Suppose that the Markov chain starts at $X_0=x$. Let $0 = R_0 < R_1 < R_2 < \ldots$ be the sequence of return times to the site $x$. Since the Markov chain is positive recurrent $E[R_n - R_{n-1}] = E[R_1] < \infty$. Next, let be the number of returns that have occurred by time $n$ (that is $R_{N_n} \leq n < R_{N_n+1}$). Finally, let $Y_k = \sum_{i=R_{k-1}+1}^{R_k} X_i$. With this notation then we have that $$ \frac{1}{n} \sum_{k=1}^{N_n} Y_k \leq \frac{1}{n} \sum_{i=1}^n X_i \leq \frac{1}{n} \sum_{k=1}^{N_n} Y_k + \frac{Y_{N_n+1}}{n}. $$

Next, note that the renewal theorem implies that $$ \lim_{n\rightarrow\infty} \frac{N_n}{n} = \frac{1}{E[R_1]}, $$ and so $$ \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{k=1}^{N_n} Y_k = \lim_{n\rightarrow \infty} \frac{N_n}{n} \frac{1}{N_n} \sum_{k=1}^{N_n} Y_k = \frac{E[Y_1]}{E[R_1]}, $$ where the last equality also follows from the fact that the $Y_k$ are i.i.d. Now, it can also be shown that $Y_{N_n+1}/n \rightarrow 0$ and so the upper and lower bounds on $n^{-1} \sum_{i=1}^n X_i$ given above imply that $$ \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{i=1}^n X_i = \frac{E[Y_1]}{E[R_1]}. $$

The last step of the proof is to show that $ \frac{E[Y_1]}{E[R_1]} = E^\pi[X_0]$, where $\pi$ is the unique stationary distribution. This can be shown by noting that the stationary distribution $\pi$ has the formula $$ \pi(y) = \frac{1}{E[R_1]} E\left[ \sum_{i=1}^{R_1} \mathbf{1}_{X_i = y} \right]. $$

Answer by Jon Peterson for Maximal directed crossing of a box using uniform random variables

2013-02-18T15:08:10Z

The problem that you are asking is actually very well known in probability theory. First of all, notice that $M(n)$ has the same distribution as the longest increasing subsequence in a random permutation of $S_n$. To see this, note that if the $n$ points are ordered according to their $x$-coordinate values, then the corresponding orders of the $y$-coordinates gives a random permutation and all permutations are equally likely.

A lot of very interesting research has been done on the distribution of $M(n)$ for large $n$. In particular, to answer your question it is known that $$\lim_{n\rightarrow \infty} \frac{E[M(n)]}{\sqrt{n}} = 2. $$ Much more, however, is known about the distribution of $E[M(n)]$. For instance, the paper "On the distribution of the length of the longest increasing subsequence of random permutations" by Baik, Deift, and Johansson (1999) is a very important result, showing that the distribution of $\frac{M(n) - 2\sqrt{n}}{n^{1/6}}$ converges in distribution to the Tracy-Widom distribution from random matrix theory.

Answer by Jon Peterson for Concerning Jump process (Lévy process)

2013-01-31T18:44:18Z

I don't think there should be any problem with the definition of $Z_t$, but of course showing that moments are finite can be tricky. You are trying to take exponential moments of $X_t$ and so you need fast enough exponential decay for the (right) tails of $X_t$. I'd need to review some stuff on Levy triples to be sure, but I suspect that the $e^{-\lambda x}$ term in the Levy measure $\nu$ implies that $Z_t$ has finite first moment if $\lambda>1$ and finite second moment if $\lambda > 2$.

Answer by Jon Peterson for Covariance sign

2011-06-03T15:24:27Z

Here is a simple proof I think. Let $\mu_f=E[f(X)]$ and $\mu_g = E[g(X)]$. Then, by expanding the interior of the expectation, it is easy to see for any $c \in \mathbb{R}$ that $$Cov(f(X),g(X)) = E[(f(X)-\mu_f)(g(X)-\mu_g)]=E[(f(X)-c)(g(X)-\mu_g)].$$ Now, let $x_0$ be the infimum of all $x$ such that $g(x) \geq \mu_g$ and choose $c=f(x_0)$. Therefore, $(f(x)-c)(g(x)-\mu_g) \geq 0$ for all $x$ and so the covariance is non-negative.

Answer by Jon Peterson for Probability inequalities

2011-05-26T20:13:06Z

This is a standard exercise in large deviations. The exponential rate of decay for the large deviations of sums of i.i.d. random variables can be derived using Cramer's Theorem (see section 2.2 in Dembo and Zeitouni's book).

In the statement of the problem above, Cramer's theorem gives that $$P(|X| > \epsilon ) = e^{ - N I(\epsilon) + o(N) }, $$ where $I(x)$ is the large deviation rate function. In this example (unless I screwed up in my calculation) $$ I(x) = \frac{1}{2}\left( \sqrt{1+4x^2}-1+\log(\sqrt{1+4x^2}-1)-\log(2x^2) \right) .$$

Answer by Jon Peterson for Coordinatizing the disk via Brownian motion

2010-10-29T16:12:02Z

Use a conformal mapping to transform the circle to the upper half plane. Since Brownian motion is conformally invariant you have reduced the problem to studying the probability that a Brownian motion started in the upper half plane hits hits the x-axis in a given interval. However, the distribution of the hitting location of the x-axis is a Cauchy distribution with centering and scaling depending on the starting location in the upper half-plane (see the related Math Overflow question).

Answer by Jon Peterson for Integration problem: $\int_{-\pi}^{\pi} | \log( | 1 + \exp(- I \nu ) | ) | \mathrm{d}\nu < \infty$

2010-10-22T14:28:17Z

The key is to understand the behavior of $A(\nu)$ near the singularity $\nu=0$. Using Taylor expansion we know that for $\nu$ small $A(\nu) = 1+e^{-I \nu} \approx -I\nu$. Therefore, $\log|A(\nu)| \approx \log|-I \nu| = \log |\nu|$. Note that $\int_{-\pi}^\pi \log|\nu| d\nu = 2 \int_{0}^\pi \log \nu d\nu < \infty$. To make this precise you need to control the error terms in the Taylor approximation.

Answer by Jon Peterson for is there an interpretation to the inverse of $I-M$ in multitype branching process, where $M$ is the mean matrix?

2010-10-19T12:44:35Z

See Chapter V of the book "Branching Processes" by Athreya and Ney. In particular, in section 2 of that chapter is the interpretation of $M^k$ that you give above.

The sum $A=\sum_{k=0}^\infty M^k = (I-M)^{-1}$ is correct if $\rho < 1$, where $\rho$ is the maximal eigenvalue of the matrix $M$. As is shown in Chapter V, section 3 of Athreya and Ney's book, the maximal eigenvalue $\rho$ plays the role of the critical parameter for the multi-type branching process. That is, the multi-type branching process dies out with probability 1 if and only if $\rho\leq 1$.

Answer by Jon Peterson for Undergraduate Probability Topics

2010-09-02T13:05:52Z

If you talk about Markov chains at some point there are a lot of cool applications to baseball. For instance using available batting statistics you can construct a team consisting of 9 Alex Rodriguez's and compute (or simulate really) how many runs such a team would score in 9 innings. You can do more detailed analysis of players as well. One place to look for more details about this (and other fun applications in sports) is the book "Mathletics" by Wayne Winston.

http://www.amazon.com/Mathletics-Gamblers-Enthusiasts-Mathematics-Basketball/dp/069113913X/ref=sr_1_1?ie=UTF8&s=books&qid=1283432632&sr=8-1

Answer by Jon Peterson for connection between the Gaussian and the Cauchy distribution

2010-08-06T13:31:15Z

Robin, a simple explanation for why the 2-dim Brownian motion stopped when hitting the real line is that Brownian motion is conformally invariant. Let $f:\Omega \rightarrow \Omega'$ be a conformal mapping and $B_{z,\Omega}(t)$ be a Brownian motion started at $z\in \Omega$ and stopped at the first time $T$ when it hits the boundary of $\Omega$. The conformal invariance of Brownian motion is the fact that $f(B_{z,\Omega}(t))$ for $t\in[0,T]$ has the same distribution as a Brownian motion in $\Omega'$ started at $f(z)$ and stopped when reaching the boundary of $\Omega'$ for the first time.

To connect this with the problem above of a Brownian motion started at $(0,1)$ and stopped when hitting the real line, just map the upper half plane onto the unit circle in such a way that $(1,0)$ is mapped to the origin. A Brownian motion started from the center of the circle obviously hits the boundary of the circle and a uniformly distributed point $P'$ on the boundary of the circle. Thus, the angle of the line from the center of the circle to $P'$ with another fixed line through the center of the circle is uniformly distributed between $-\pi$ and $\pi$. Since the conformal map from the upper half-plane to the circle maps lines through $(0,1)$ to lines through the origin, then conformal invariance of Brownian motion implies that the angle between the $y$-axis and the line from $(0,1)$ to the point $P$ where the Brownian motion hits the $x$-axis is also uniform between $-\pi$ and $\pi$.

Answer by Jon Peterson for Probability of random permutation having certain cycles

2010-08-04T12:07:42Z

The following paper may be what you're looking for:

Schramm, Oded. Compositions of random transpositions. Israel J. Math. 147 (2005), 221--243. MR2166362 (2006h:60024)

http://www.springerlink.com/content/f572513876635mj5/

This paper is concerned with the distribution of a random permutation in $S_n$ generated by $c n$ random transpositions (where $c>1/2$). Schramm calculates the limiting distribution of the cycle lengths (ordered from largest to smallest).

A recent paper of Nathanael Berestycki, Oded Schramm, and Ofer Zeitouni has extended the techniques of Schramm's earlier paper to the case where the random permutation is generated by random $k$-cylces. I don't know if this recent paper answers the same questions, but it might be relevant.

http://arxiv.org/abs/1001.1894

Answer by Jon Peterson for "Square root" of Beta(a,b) distribution

2010-07-26T19:26:22Z

If you're only interested in the existence of a solution Jeff's suggestion of looking at the logarithms seems to be the correct approach. Let $Z$ have Beta$(a,b)$ distribution. Suppose that there is a solution to the "square root" problem in this case, and let $X$ be a random variable with this distribution. Then, if $\phi(u) = E[e^{i u \log(Z)}] = E[Z^{i u}]$ and $\psi(u) = E[X^{i u}]$ are the characteristic functions (or Fourier transforms) of $\log(Z)$ it must be the case that $\psi(u)^2 = \phi(u)$ for all $u\in\mathbb{R}$.

Because we know a lot about Beta distributions we can actually solve explicitly that $\phi(u) = \frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)} \frac{\Gamma(\alpha+i u)}{\Gamma(\alpha+\beta+i u)}$. Then we can prove the existence of a solution by defining $\psi(u) = \sqrt{\phi(u)}$ and then letting $X$ be a random variable with distribution $\psi(u)$.

There are a couple of issues that need to be smoothed over. First of all, $\phi(u)$ is a complex-valued function so we need to be careful with the square root. However, since $\phi(u)\neq 0$ for all $u\in\mathbb{R}$ we can take the square root in a continuous manner. The bigger issue is that we need to be able to prove that $\psi(u)$ is a characteristic function of some probability distribution. For this we need some Fourier inversion theorems.

Theorem 14 in A Modern Approach to Probability Theory by Fristedt and Gray gives sufficient conditions for a function to be the characteristic function of a real-valued random variable. There are several conditions to check. First, that $\psi(0)=1$ and $\psi$ is continuous. These are obviously satisfied. Next, that $\psi(u)$ is "positive definite". That is, $\sum_{k=1}^n \sum_{j=1}^n \psi(u_k-u_j)z_j\bar{z}_k \geq 0$ for any complex $n$-tuple $(z_1,\ldots, z_n)$ and real $n$-tuple $(u_1,\ldots, u_n)$. I don't know how to check to see if this is true. The final condition is that $\int| \psi(u)| du < \infty$. I'm not an expert in the $\Gamma$ function, so I plotted $\psi(u)$ with Mathematica and it looks like $|\psi(u)|$ decays roughly like $|u|^{-b}$ as $|u|\rightarrow \infty$ so that $\int |\psi(u)| du < \infty$ if $b>1$.

I still can't think of how to check the "positive definite" condition, but if one can check that the problem would be solved for $b>1$.

Comment by Jon Peterson

2013-05-21T14:45:38Z

If $n$ is large, then the distribution of the path should converge to that of a $d$-dimensional Brownian bridge (essentially a Brownian motion conditioned to end back at the origin).

Comment by Jon Peterson

2013-05-17T13:39:54Z

@Ori: There is an error in your application here. The process is completed either when all balls become the one color. Thus, you should be looking for the the expected time for the random walk to reach either the vertex $00\ldots 0$ or the vertex $11\ldots 1$. I did a few computations, and it appears that this is equal to $2^{n-1}-1$.

Comment by Jon Peterson

2013-05-17T11:01:07Z

@Rhett Butler: One more comment. The fraction of wins up until a random time isn't even the correct thing to look at in roulette. Under the strategy above, even though the expected fraction of wins would be 53% by the time of the 10-th win, the expected actual winnings would be 0 dollars (assuming the casino pays out even money, which is of course wrong). This is because $B_n-G_n$ is a martingale.

Comment by Jon Peterson

2013-05-17T10:35:39Z

@Rhett Butler: You misunderstand what it means to have a "winning strategy." A winning strategy is one which guarantees you win money in the long run. Using this as a roulette strategy only gives a strategy where the expected fraction of wins is 53% for a short period of time (up to the 10-th black). If you try this repeatedly, then you essentially have increased the number of "families" and the answer approaches 50%. Therefore, this strategy will (not surprisingly) not guarantee you make money.

Comment by Jon Peterson

2013-05-14T13:00:18Z

@Russ: I like the proof. However, I think the explanation would be more clear if you had given a better definition of the random variable $X_i$. I think from the way you're using it in your proof, $X_i$ is the number of times when color $i$ is one of the two colors chosen. This makes it clear that $1/2 \sum_i X_i$ is the random variable of interest and makes it easy to see why each $X_i$ is just a gamblers ruin problem.

Comment by Jon Peterson

2013-05-14T10:54:04Z

@Rhett Butler: You never addressed the main point of my remark - that $\frac{G_n}{B_n + G_n}$ is not a martingale. My point is that agreeing that Douglas's answer is correct does not imply that one has a "winning roullete strategy." Secondly, I agree that when $n$ is large this fraction is very unlikely to deviate from $1/2$. However, you go too far when you say "the population will never deviate by more than the statistical fluctuations from the 50:50 equipartition." This is plainly false. In fact the law of the iterated logarithm shows that there will always be some such deviations.

Comment by Jon Peterson

2013-05-13T12:36:07Z

@Rhett: I'm not sure I understand your comment about the "winning roulette strategy," but maybe this will explain things. You seem to want to apply some martingale theory where it isn't appropriate. The fraction of girls in the population is not a martingale. That is, let $G_n$ and $B_n$ be the number of girls and boys respectively in the first $n$ births, and let $X_n = \frac{G_n}{B_n+G_n} = \frac{G_n}{n}$. It's easy to see that $E[X_n] = \frac{1}{2}. However, $X_n$ is not a martingale, since $E[X_n | X_{n-1} ] = \frac{n}{n+1}X_n + \frac{1}{2(n+1)}$.

Comment by Jon Peterson

2012-02-24T12:08:42Z

Maybe you could call P(x) a "measure generating function" instead of a "probability generating function" when the coefficients of $P(x)$ are non-negative but $P(1) \neq 1$.

Comment by Jon Peterson

2011-05-27T19:54:27Z

Actually, in this case the coefficients are decaying so fast, the infinite random sum $\sum_{i=1}^\infty \alpha_i w_i v_i$ actually converges almost surely. Therefore, $P(|X|>\epsilon)$ doesn't decay at all but converges to a non-zero constant.

Comment by Jon Peterson

2011-05-27T14:42:52Z

If the $\alpha_i$ coefficients decay fast enough that you expect exponential decay, then I would expect that they Chernoff bound is the best that you can do. To this end, it might also be useful to look at the Gartner-Ellis Theorem (Section 2.3 in "Large Deviations Techniques and Applications" by Dembo and Zeitouni).

Comment by Jon Peterson

2011-05-27T14:42:36Z

Farzad, I just noticed that I didn't read your question carefully enough. The bound I gave is correct if all of the $\alphi_i = 1/N$. If the random variables are i.i.d. with exponential moments this gives the correct rate of exponential decay. In order to get a good inequality, I would need to know more about the coefficients $\alpha_i$. For instance, if the $\alpha_i = 1/\sqrt{N}$ then the central limit theorem states that $|X|$ converges in distribution to a Normal random variable, in which case $P(|X|\geq \epsilon)$ won't decay exponentially.

Comment by Jon Peterson

2011-05-26T20:28:42Z

Farzad, in your comment above you mentioned that you needed an upper bound. An examination of the proof of the upper bound in Cramer's theorem shows that the exponential rate of decay given by the large deviation rate function is a strict upper bound. That is, $ P(|X| > \epsilon ) \leq e^{-N I(\epsilon)} $ for all $\epsilon>0$ and all $N\geq 1$.

Comment by Jon Peterson

2011-05-26T20:20:41Z

Cramer's theorem just gives exponential rate of decay. More precise asymptotics are $$P(|X| > \epsilon ) \sim \frac{C}{\sqrt{N}} e^{-N I(\epsilon)},$$ where the constant $C$ depends on $\epsilon$ and can be explicitly calculated in this case (see Theorem 3.7.4 in Dembo and Zeitouni's book).

Comment by Jon Peterson

2010-10-29T15:59:36Z

I was told recently by Firas Rassoul-Agha that 1) is the reason for the name. One of the French translations above (I'm not sure which since my French is bad) emphasizes that the theorem is the Central (i.e., fundamental) limit theorem in probability. Firas claimed that the other French translation arose by translating Central Limit Theorem back from English to French - thus obscuring the original meaning.

Comment by Jon Peterson

2010-10-27T14:41:07Z

@could-not-log-in: I think there is actually a reason why math majors should be better than the average graduate in logical reasoning (maybe not drastically better, but at least a little better). At some point in their undergraduate studies they should have had to learn about proofs: how to write a proof, what are common logical fallacies, how to prove something by proving the contrapositive. These skills are mostly presented in a mathematical context, but I think they do transfer over some to non-mathematical reasoning.