每年一调整夏令时，巴黎的白天就显得特别长，气温也非常配合地直接进入夏天的节奏，从四月开始，当真是一年中我最喜欢的季节了。
时间好快，现在是2018年了。
四年前的那个剧本如约走到了结局，但其中的变化好像也不曾是当时所想。之前只是想，还是要做个论文，后来觉得概率似乎比分析有意思，再后来迷上了随机几何，心心念念想做这个方向，也听了很多报告学了很多知识还去了一些会。再后来M2开学，发现之前两三年所学都好似花架子没一点真材实料的，心里很慌。
后来小半年时间每天上课记笔记，回来就复习琢磨证明，到现在基本上拿个思路都能够差不多补齐了。最后M2考试成绩也不错。
可是这个时候，老师和我说觉得有些方向人太多了，还是建议换个方向吧。
开始我是有点失落的，但可能就是在这样的过程中吧，对随机是什么，思考越来越多了，发现概率也不只是一个方向，也有很多很多不同的分支，应该都看看的。想到这里，似乎思路就打开了，也就不拘泥说非得做某一个课题了。
然后就到了现在的课题，似乎是之前所有所学的总和呢，也算无心插柳吧。
就是得把分析和方程都捡回来了，不怕，当年我就是从实变泛函助教做起的。
回到开头那个话题，为什么喜欢夏天呢？因为白天很长，有很多时间可以做自己喜欢的事情。恍惚又想到了2015的那个夏天，那个被压抑了特别久，特别想学数学的状态，每天在PC算题目，算到天黑11点，有一次甚至是两三点，然后醒了就继续算。把课后习题一道一道算过去……
写这段的时候，不为了别的什么，就是想让自己回想起那个勇敢的自己。有句歌词说“如果知道这些当时我到底去不去？”
当然去了，这几年挺开心的，也看着理想在实现，自己也在不断强大起来，我还想看看自己还能进化成什么样子呢，拭目以待。
夏天来了，抓紧时间再疯狂一次吧
（立个Flag：每周读至少一个和主线不是那么相关的证明，更新一个博客，还是要保持一点学习的劲头不能变成只会一个方向的傻瓜的。毕竟心里还有一个大问题啊！）
2018年4月26日星期四
2018年4月6日星期五
TCL theorem for one type Riemann integral of Brownian motion
This is one question in the exercise of "Local time and excursion", but I think it is very interesting.
We consider a measurable function $g$ and a Brownian motion $(B_t)_{t \geq 0}$ one integral defined as
$$A_t = \int_0^t g(B_s)ds$$
means the integration along the path. We suppose that $g$ is intégrable then this formula makes sense. Well, if $g$ is continuous this is obvious : although there is random part, it's in fact a Riemann integral (or Lebesgue) of continuous function. In general case, we apply a very useful formule called time of occupation
$$\int_0^t g(B_s)ds = \int g(a) L^a_t(B)da$$
Then, since $\left(L^a_t(B)\right)_{a \geq 0}$ is continuous and zero at infinity, the one has a max so $A_t$ is well defined.
One more remark for this formule : One large advantage of Lebesgue integral is the introduction of measure, so when we compare two integral, we have not to compare it point-wisely, but cut them into blocks. However, the integral like Riemann isn't good, but local time transform it again with the style of Lebesgue one. The stochastic integral face the same problem, luckily we have Ito, Doob, BDG so we can make that one like "one deterministic term + one random error".
One more remark for this formule : One large advantage of Lebesgue integral is the introduction of measure, so when we compare two integral, we have not to compare it point-wisely, but cut them into blocks. However, the integral like Riemann isn't good, but local time transform it again with the style of Lebesgue one. The stochastic integral face the same problem, luckily we have Ito, Doob, BDG so we can make that one like "one deterministic term + one random error".
Our main theorem is to prove that
$$\frac{1}{\sqrt{t}} A_t \Rightarrow \int g(a)da |N|$$
where $N \sim \mathcal{N}(0,1)$. This convergence is in weak sense.
We remark why this formula should be correct. One important observation is one Levy's theorem that
$$\left( L^0_t, |B_t| \right)_{t \geq 0} = (\text{law}) \left( S_t, S_t - B_t \right)_{t \geq 0}$$
So we have obviously $\frac{1}{\sqrt{t}}L^0_t$ has the same law as $|N|$. For the local time at other level, once it is touched, it will behavior like $L^0_t$.
However, the problem is that : the convergence in law of sigle random variable doesn't mean the convergence in law of random process. I make the this phrase red to point out the danger. But we know that $a \rightarrow L^a_t(B)$ is also continuous, so what's the error term ? Could this error disappear after the normalization of $\frac{1}{\sqrt{t}}$ ?
We have to go back to the analysis of the regularity of the local time. Using the Tanaka formule
$$L^a_t(B) = 2(B_t - a)^ + - 2(B_0 - a)^ + - 2\int_{0}^t \mathbb{1}_{\{B_s > a\}} dB_s$$
We obtain that
$$L^a_t(B) - L^0_t(B) = \left[2(B_t - a)^ + - 2(B_0 - a)^ + \right] - \left[2(B_t )^ + - 2(B_0 )^ +\right] + 2\int_{0}^t \mathbb{1}_{\{0 < B_s \leq a\}} dB_s$$
We would like to say that $L^a_t(B) - L^0_t(B)$ is uniformly little. The difficulty is the last one stochastic integration. However, we see that when $s$ grows, it's very rare that the Brownian motion could stay in the interval so it contributes very little to the integral (even in a stochastic one !). The powerful tool like BDG inequality tells totally the moment of this random variable. We estimate the tail so with large probability $1 - \epsilon$, the process will converge uniform to a $|N|$ process. We write down the proof properly by the density argument etc and conclude the proof.
Finally, I have to say once I come to the part of analysis the size of a random variable, the training in the course of statistic helps really a lot. That may be why we say probability and statistics are always together. (Oui, et analyse est aussi son bon amie)
where $N \sim \mathcal{N}(0,1)$. This convergence is in weak sense.
We remark why this formula should be correct. One important observation is one Levy's theorem that
$$\left( L^0_t, |B_t| \right)_{t \geq 0} = (\text{law}) \left( S_t, S_t - B_t \right)_{t \geq 0}$$
So we have obviously $\frac{1}{\sqrt{t}}L^0_t$ has the same law as $|N|$. For the local time at other level, once it is touched, it will behavior like $L^0_t$.
However, the problem is that : the convergence in law of sigle random variable doesn't mean the convergence in law of random process. I make the this phrase red to point out the danger. But we know that $a \rightarrow L^a_t(B)$ is also continuous, so what's the error term ? Could this error disappear after the normalization of $\frac{1}{\sqrt{t}}$ ?
We have to go back to the analysis of the regularity of the local time. Using the Tanaka formule
$$L^a_t(B) = 2(B_t - a)^ + - 2(B_0 - a)^ + - 2\int_{0}^t \mathbb{1}_{\{B_s > a\}} dB_s$$
We obtain that
$$L^a_t(B) - L^0_t(B) = \left[2(B_t - a)^ + - 2(B_0 - a)^ + \right] - \left[2(B_t )^ + - 2(B_0 )^ +\right] + 2\int_{0}^t \mathbb{1}_{\{0 < B_s \leq a\}} dB_s$$
We would like to say that $L^a_t(B) - L^0_t(B)$ is uniformly little. The difficulty is the last one stochastic integration. However, we see that when $s$ grows, it's very rare that the Brownian motion could stay in the interval so it contributes very little to the integral (even in a stochastic one !). The powerful tool like BDG inequality tells totally the moment of this random variable. We estimate the tail so with large probability $1 - \epsilon$, the process will converge uniform to a $|N|$ process. We write down the proof properly by the density argument etc and conclude the proof.
Finally, I have to say once I come to the part of analysis the size of a random variable, the training in the course of statistic helps really a lot. That may be why we say probability and statistics are always together. (Oui, et analyse est aussi son bon amie)
2018年3月16日星期五
Est-ce que le processus Gaussien peut être différentiable ?
Comme le titre, c'est une très bonne question. Hier mon ami me demande cette question et au premier coup, j'avais envie de dire que c'est pas possible après plusieurs raisons.
1. Le modèle très simple est le mouvement brownien, qui n'est pas de classe $C^1$.
2. Un théorème de Dubins-Schwarts nous dit que une martingale locale continuée est presque un mouvement brownien après un changement du temps.
3. Oui, on parle de dérivée bruit blanc, mais c'est toujours de sens faible ou il veut dire intégration stochastique.
Si on dit la "dérivée" dans l'autre sens non standard, bon, c'est toujours possible. Mais finalement, on trouve un exo qui nous dit c'est possible lorsque la covariance $K(s,t)$ est de classe $C^2$ et en fait on a fait cet exo avant.
Argument est comme suivant :
1. $\left\{\frac{G_{t+ \delta - G_t}}{\delta}\right\}_{t \geq 0}$ est un processus Gaussien après la linéarité d'espace Gaussien.
2. On vérifie il est de suite de Cauchy dans $L^2$. Donc il admet une limite comme Gaussien.
3. La limite a une covariance $\partial_s \partial_t K(s,t)$.
Donc, on voit dans le sens de limite $L^2$ il admet la limite. C'est tout de propriété de Gaussien, qui est fermé dans le sens limite.
Mais pourquoi on a tendance de mélanger le cas avec la martingale. Voilà, une martingale est un processus ssi il est de croissance indépendante. Mais ici, le processus a vraiment de mémoire et le cas PAIS ne peut pas avoir dérivée. Donc, même si le processus aléa est souvent fractal, il peut être régulier.
2. Un théorème de Dubins-Schwarts nous dit que une martingale locale continuée est presque un mouvement brownien après un changement du temps.
3. Oui, on parle de dérivée bruit blanc, mais c'est toujours de sens faible ou il veut dire intégration stochastique.
Si on dit la "dérivée" dans l'autre sens non standard, bon, c'est toujours possible. Mais finalement, on trouve un exo qui nous dit c'est possible lorsque la covariance $K(s,t)$ est de classe $C^2$ et en fait on a fait cet exo avant.
Argument est comme suivant :
1. $\left\{\frac{G_{t+ \delta - G_t}}{\delta}\right\}_{t \geq 0}$ est un processus Gaussien après la linéarité d'espace Gaussien.
2. On vérifie il est de suite de Cauchy dans $L^2$. Donc il admet une limite comme Gaussien.
3. La limite a une covariance $\partial_s \partial_t K(s,t)$.
Donc, on voit dans le sens de limite $L^2$ il admet la limite. C'est tout de propriété de Gaussien, qui est fermé dans le sens limite.
Mais pourquoi on a tendance de mélanger le cas avec la martingale. Voilà, une martingale est un processus ssi il est de croissance indépendante. Mais ici, le processus a vraiment de mémoire et le cas PAIS ne peut pas avoir dérivée. Donc, même si le processus aléa est souvent fractal, il peut être régulier.
2017年9月13日星期三
Rappel de probabilité (4) : convergence en loi et TCL
On continue de réviser la base de probabilité et dans cette partie, on veut attaquer le problème de convergence en loi. Peut-être il y déjà un poste sur la convergence dans un espace métrique, mais le TCL et la fonction caractéristique a quand même des intérêts.
$$ F_n(x) \rightarrow F(x) $$
pour tous les points de continuité. Un peu d'analyse nous dit que cette convergence est uniforme. Il y a plusieurs façons de caractériser la convergence. Par exemple, on dit $\mu_n \Rightarrow \mu$ si pour toute la fonction continuée et bornée, on a
$$\mu_n(f) \rightarrow \mu(f)$$
Il y a d'autre critère comme l'ensemble ouvert et fermé.
$$\forall O \text{ouvert}, \liminf \mathbb{P}(X_n \in O) \geq \mathbb{P}(X \in O)$$
Une méthode de mémoriser l'inégalité est une suite de Dirac masse qui converge vers un point dans l’adhérence. La version fermée et bord est aussi facile à décrire.
On remarque dans la démonstration de $\mathbb{R}$, la représentation est assez directe i.e si $X_n \Rightarrow X$, on peut les tous mettre dans un espace en commun tel que $X_n \rightarrow X$ presque sûrement.
D'autre cas spécifique, comme le théorème de Scheffé, qui nous dit si la variable aléatoire a une densité $f_n$ et $f_n \rightarrow f$ ponctuellement, on a aussi la convergence car l'intégration de densité est toujours 1.
$$\sup_n \mathbb{P}(X_n \notin K_{\epsilon}) < \epsilon$$.
L'intérêt de cette propriété est que une suite de mesure est pré-compact si et seulement elle est tendue. Donc, montrer la tension est suivant une partie important de convergence en loi. Une stratégie standard est l'argument "tension + convergence de loi marginal".
$$ \frac{1}{2}(\mu(a) + \mu(b)) + (\mu((a,b)) = \frac{1}{2\pi} \lim_{T \rightarrow \infty} \int_{-T}^{T} \frac{e^{-ita}-e^{-itb}}{it}\phi(t) dt$$
Dans le cas où la fonction caractéristique est intégrable et donc la mesure a une densité, on peut retrouver la densité par la transformée inversée.
$$ f(x) = \frac{1}{2\pi} \int e^{-itx} \phi(t) dt $$
Combiner la propriété de tension et la propriété de fonction caractéristique, si la fonction caractéristique d'une suite de mesure converge, il a une convergence qui s'appelle la convergence vague. i.e la fonction de répartition n'est pas vraiment une fonction de répartition car l'information à limite est perdu. Cependant, si cette fonction a une continuité à 0, la suite a tension donc elle converge vers une mesure.
La convergence vers une loi de Poisson est souvent appelée "le convergence de petite nombre" car il approche la probabilité d'événement rare. On peut aussi mesurer la vitesse de convergence en distance total - qui est une bonne distance de convergence en loi pour l'état discret.
En concernant la loi stable, c'est une situation que variance n'est pas fini. Donc on fait une normalisation différente. Les variables $X$ étudiées dans ce problème a une vitesse de décroissance comme $x^{- \alpha}, 0 < \alpha < 2$. Sa limite $Y$ a une propriété que $\forall n, \exists a_n, b_n$ tel que
$$\frac{\sum_{k=1}^n Y_k - b_n}{a_n} \overset{d}{=} Y$$. Pour la paramètre $\alpha$, la normalisation est $n^{\frac{1}{\alpha}}$.
Dans d'autre espace polonais, certaine définition est aussi bien définie mais certaine ne marche plus, surtout ceux qui utilisent la fonction caractéristique, qui demande l'existence de transformée de Fourier.
Convergence en loi dans $\mathbb{R}$
La définition de convergence en loi dans la situation $\mathbb{R}$ est assez simple et elle est définie par$$ F_n(x) \rightarrow F(x) $$
pour tous les points de continuité. Un peu d'analyse nous dit que cette convergence est uniforme. Il y a plusieurs façons de caractériser la convergence. Par exemple, on dit $\mu_n \Rightarrow \mu$ si pour toute la fonction continuée et bornée, on a
$$\mu_n(f) \rightarrow \mu(f)$$
Il y a d'autre critère comme l'ensemble ouvert et fermé.
$$\forall O \text{ouvert}, \liminf \mathbb{P}(X_n \in O) \geq \mathbb{P}(X \in O)$$
Une méthode de mémoriser l'inégalité est une suite de Dirac masse qui converge vers un point dans l’adhérence. La version fermée et bord est aussi facile à décrire.
On remarque dans la démonstration de $\mathbb{R}$, la représentation est assez directe i.e si $X_n \Rightarrow X$, on peut les tous mettre dans un espace en commun tel que $X_n \rightarrow X$ presque sûrement.
D'autre cas spécifique, comme le théorème de Scheffé, qui nous dit si la variable aléatoire a une densité $f_n$ et $f_n \rightarrow f$ ponctuellement, on a aussi la convergence car l'intégration de densité est toujours 1.
Tension
On liste la notation de tension dehors car elle a un rôle très important et peut être généralisé dans d'autre espace. Gros-moto, une suite est tendue si et seulement $\forall \epsilon > 0,$ il existe un compact $K_{\epsilon}$ tel que$$\sup_n \mathbb{P}(X_n \notin K_{\epsilon}) < \epsilon$$.
L'intérêt de cette propriété est que une suite de mesure est pré-compact si et seulement elle est tendue. Donc, montrer la tension est suivant une partie important de convergence en loi. Une stratégie standard est l'argument "tension + convergence de loi marginal".
Fonction caractéristique
On utilise aussi la fonction caractéristique d'analyser la convergence faible de variable aléatoire. La raison profonde est l'analyse de Fourier car la fonction caractéristique est la transformée de Fourier d'une mesure. Dans le livre de Durret, on voit beaucoup d'application de la fonction caractéristique. En fait, une formule utile est$$ \frac{1}{2}(\mu(a) + \mu(b)) + (\mu((a,b)) = \frac{1}{2\pi} \lim_{T \rightarrow \infty} \int_{-T}^{T} \frac{e^{-ita}-e^{-itb}}{it}\phi(t) dt$$
Dans le cas où la fonction caractéristique est intégrable et donc la mesure a une densité, on peut retrouver la densité par la transformée inversée.
$$ f(x) = \frac{1}{2\pi} \int e^{-itx} \phi(t) dt $$
Combiner la propriété de tension et la propriété de fonction caractéristique, si la fonction caractéristique d'une suite de mesure converge, il a une convergence qui s'appelle la convergence vague. i.e la fonction de répartition n'est pas vraiment une fonction de répartition car l'information à limite est perdu. Cependant, si cette fonction a une continuité à 0, la suite a tension donc elle converge vers une mesure.
TCL, Poisson et loi stable
Finalement, on parle un peu du théorème de TCL et loi stable. La démonstration de TCL est classique est directe par la fonction caractéristique, mais on devrait savoir que c'est juste une situation très idéale. En fait, la convergence en loi est un peu robust, dans le sens que ce théorème est correct sous la condition plus faible. Pour le TCL c'est le théorème de Lendeberg-Feller.La convergence vers une loi de Poisson est souvent appelée "le convergence de petite nombre" car il approche la probabilité d'événement rare. On peut aussi mesurer la vitesse de convergence en distance total - qui est une bonne distance de convergence en loi pour l'état discret.
En concernant la loi stable, c'est une situation que variance n'est pas fini. Donc on fait une normalisation différente. Les variables $X$ étudiées dans ce problème a une vitesse de décroissance comme $x^{- \alpha}, 0 < \alpha < 2$. Sa limite $Y$ a une propriété que $\forall n, \exists a_n, b_n$ tel que
$$\frac{\sum_{k=1}^n Y_k - b_n}{a_n} \overset{d}{=} Y$$. Pour la paramètre $\alpha$, la normalisation est $n^{\frac{1}{\alpha}}$.
Dans d'autre espace polonais, certaine définition est aussi bien définie mais certaine ne marche plus, surtout ceux qui utilisent la fonction caractéristique, qui demande l'existence de transformée de Fourier.
2017年9月1日星期五
Rappel de probabilité (3) : le théorème de grand nombre
La théorème de grand nombre est une théorie très importante dans probabilité, mais sa démonstration peut être assez technique sous différentes conditions. Pour la suite, on raconte quelques histoires sur le théorème de grand nombre.
La théorie plus classique suppose que $\{X_i\}$ sont i.i.d et sa variance est finie. Sous cette condition, on a inégalité de Markov
$$
\mathbb{P}[\frac{S_n}{n} > \epsilon] < \frac{Var(X)}{n \epsilon^2}
$$
qui suffit d’entraîner la loi faible. Concernant la loi forte, on choisit une sous-suite et montre la convergence p.s grâce au lemme de Borel-Cantalli. Puis on contrôle les erreurs entre eux. Cette technique est la base de beaucoup de démonstration.
Pour aller plus loin, une direction est supprimer la condition de variance. Dans ce cas, il faut utiliser la technique de troncature comme
$$
Y_n = X_n \mathbb{I} _{X_n < n}
$$
Cette technique a des propriétés incroyable mais pas évidant :
(1) Avec probabilité 1, il y a que nombre fini de $X_n \neq Y_n$
(2) $\sum_n [Var(Y_n / n)] < \infty$
La première propriété est très utile, il nous dit que l'étude de convergence se réduit comme le comportement de $Y_n$. La deuxième a beaucoup d'application. Soit on suit la même chemin que la méthode classique : montre une convergence de sous-suite et contrôle les erreurs entre eux. Soit on utilise la méthode de Kolmogorov.
La méthode de Kolmogorov est en fait, utiliser l'idée de martingale. En utilisant la convergence de martingale $L^2$, on montre p.s $\sum_n \frac{Y_n}{n}$ converge. Puis, un lemme de Kronecker - un lemme pure d'analyse maths, qui nous dit que dans cette situation, $\frac{\sum_{k=1}^n Y_k}{n}$ converges.
La situation sans $L^1$ est aussi possible d'étudier mais cela dépend de démonstration. La loi faible peut se généraliser dans le cas de variable aléatoire corrélée ou $L^1$ faible. Mais quelques fois, on essaie aussi d'autre normalisation.
La théorie plus classique suppose que $\{X_i\}$ sont i.i.d et sa variance est finie. Sous cette condition, on a inégalité de Markov
$$
\mathbb{P}[\frac{S_n}{n} > \epsilon] < \frac{Var(X)}{n \epsilon^2}
$$
qui suffit d’entraîner la loi faible. Concernant la loi forte, on choisit une sous-suite et montre la convergence p.s grâce au lemme de Borel-Cantalli. Puis on contrôle les erreurs entre eux. Cette technique est la base de beaucoup de démonstration.
Pour aller plus loin, une direction est supprimer la condition de variance. Dans ce cas, il faut utiliser la technique de troncature comme
$$
Y_n = X_n \mathbb{I} _{X_n < n}
$$
Cette technique a des propriétés incroyable mais pas évidant :
(1) Avec probabilité 1, il y a que nombre fini de $X_n \neq Y_n$
(2) $\sum_n [Var(Y_n / n)] < \infty$
La première propriété est très utile, il nous dit que l'étude de convergence se réduit comme le comportement de $Y_n$. La deuxième a beaucoup d'application. Soit on suit la même chemin que la méthode classique : montre une convergence de sous-suite et contrôle les erreurs entre eux. Soit on utilise la méthode de Kolmogorov.
La méthode de Kolmogorov est en fait, utiliser l'idée de martingale. En utilisant la convergence de martingale $L^2$, on montre p.s $\sum_n \frac{Y_n}{n}$ converge. Puis, un lemme de Kronecker - un lemme pure d'analyse maths, qui nous dit que dans cette situation, $\frac{\sum_{k=1}^n Y_k}{n}$ converges.
La situation sans $L^1$ est aussi possible d'étudier mais cela dépend de démonstration. La loi faible peut se généraliser dans le cas de variable aléatoire corrélée ou $L^1$ faible. Mais quelques fois, on essaie aussi d'autre normalisation.
2017年7月15日星期六
A small note on mixing time of Markov chain
This is a small note after the note by Nathanael Berestycki and the object is just for reviewing some interesting story about this model and preparing for the coming summer school. I decide to write it on my blogger since this permit me to write down the idea as quickly as possible without paying too much attention on the detail and technical part.
If we define the Dirichlet energy under the measure $\pi$ as
$$\begin{eqnarray*}E(f,f) &=& \sum_{e}Q(e) \nabla f(e) \nabla f(e)\\ Q(x,y) &=& \pi(x)P(x,y)\end{eqnarray*}$$,
then the classical discrete Poincare inequality gives
$$\boxed{Var(f) \leq \frac{1}{\gamma} E(f,f)}$$.
The constant is optimal so if we have another equality of constant $C$, we have necessarily $t_{rel} \leq C$ so we get the upper bound of mixing time.
Another method comes from the famous Cheeger's inequality, the ratio of expansion is
$$\Phi(A) = \frac{Q(A, A^C)}{\pi(A)}$$
and the ratio of expansion of the graph is
$$\Phi_* = \inf_{\pi(A) \leq 1/2} \Phi(A)$$.
The famous Cheeger's inequality tells that
$$\frac{\Phi_*^2}{2} \leq \gamma \leq 2\Phi_*$$
We remark that one good lower bound for the mixing time is that
$$t_{mix} \geq \frac{1}{4\Phi_*}$$
means that if the graph is not so connected, it will take long time to mix the chain.
$$d(t) \leq \frac{1}{2}d_2(t) = \frac{1}{2}\sqrt{\sum_{j=2}^n e^{-2t\mu_j}} , \mu_j = 1-\lambda_j$$
The comparaison theorem says that for two Markov chains $X,Y$ if $E_X(f,f) \leq AE_Y(f,f)$, then we have $\mu_j^X \leq A \mu_j^Y$. This helps us to give some analysis for a Markov chain given the information of one chain already well understood.
Wilson proposes some interesting algorithm called coupling from the past which gives an exact law of invariant measure in some specific case, for example the Ising model. The simulation requires that the state should have a function to make it ordered. Unlike the MCMC, we will come from the past. The coupling technique says that generally, the invariant measure is the case that a coupling meet. Now we apply check if
The cover time is another concept similar to mixing time which says the time to visit all the state at least once. The Matthews inequality gives the control
$$t_{cov} \leq (1 + \frac{1}{2} + \cdots \frac{1}{n}) t_{hit}$$
Basic notation of mixing time
At first, we have to talk about the motivation of the research of this subject. In abstract measure theory, we talk about the topology of the Radon measure on a metric space and its distance. The distance which induces the weak star convergence is called Levy distance. This theory is very profond, while the situation in discrete state situation is very easy since the topology coincides and we use the total variation distance
$$\| \mu - \nu \| = \sup_{A \subset S} \mu(A) - \nu(A)$$
to represent the distance between two measures, which is very simple and elegant. On the other hand, the study of this subject arise because of the emerging of many computer algorithms : we have to know if they converge and moreover, the quantitative behavior of the convergence. Especially, the cutoff phenomenon tells us sometimes we have to do enough step of Markov chain to make sure that it converge.
There is some other equivalent definition of the total variation distance like
$$\begin{eqnarray*}\| \mu - \nu \| &=& \sup_{A \subset S} \mu(A) - \nu(A) \\ &=& \frac{1}{2}\sum_{x\in S} \mu(x) - \nu(x) \end{eqnarray*}$$
Concerning the distance between a Markov chain, if it has a invariant measure $\pi$, then we use
$$d(t) = \sup_{x \in S}\|P^t(x, \cdot) - \pi(\cdot) \|$$
to describe the distance from the invariant measure. Sometimes it interacts with another definition
$$ \rho(t) = \sup_{x,y \in S}\|P^t(x, \cdot) - P^t(y, \cdot) \| $$
since the two are equivalent
$$ d(t) \leq \rho(t) \leq 2 d(t)$$.
The mixing time is defined as
$$t_{mix}(\epsilon) = \inf \{t | d(t) \leq \epsilon \}$$.
and we use usually $t_{mix} = t_{mix}(1/e)$.
The convergence to the invariant measure is after Perron-Frobenius theorem for irreducible, aperiodic, finite state Markov chain and sometimes we also use the Lyaponov function to treat the infinite state case. However, these criteria isn't so sharp and just give a qualitative description.
Before finishing this section, we recall the phenomenon of cutoff. Generally speaking, that is the $d(t)$ falls drastically near the point of $t_{mix}$. This phenomenon is a little hard to understand since until now, we didn't find a universal method to analyse this phenomenon but just study the model case by case. Moreover, sometimes it happens but sometimes, it can be avoided and we don't see it in the simulation.
Coupling technique
To estimate the speed of convergence, a first technique is called coupling and it may be the most useful and powerful method which apply in all the case. A coupling of measure $\mu, \nu$ is a couple $(X,Y)$ where $X$ has the law of $\mu$ and $Y$ has the law of $\nu$. We remark that the marginal law can never recover the joint distribution, so this condition doesn't fix the law $(X,Y)$.
A third definition of total variation distance is
$$\| \mu - \nu \| = \inf_{couple}\mathbb{P}(X \ne Y)$$.
This formula gives us a upper bound of the $d(t)$ and the upper bound of the $t_{mix}$ since
$$\begin{eqnarray*} d(t) \leq \rho(t) &=& \sup_{x,y \in S}\|P^t(x, \cdot) - P^t(y, \cdot) \| \\&\leq& \sup \mathbb{P}(X_t \ne Y_t) \end{eqnarray*}$$
and a useful technique is to demande that when two Markov chain meet, they move together - this induces that
$$\boxed{d(t) \leq \sup_x \mathbb{P}_x(\tau_{X,Y} > t)}$$
One example is the lazy random walk on the circle $Z / n$. The Markov chain has $1/2$ probability to stay on the same place and $1/4$ to move forward or backward. Then we start two chain $(X,Y)$ and let a first coin to decide which one to move and second one to decide the direction. Once they meet together, the move together. In fact, the meet of two chain is reduced to the ruin of gambler. So using the first moment
$$d(t) \leq \sup_x \mathbb{P}_x(\tau_{X,Y} > t) \leq \frac{\mathbb{E}(\tau_{X,Y})}{t} = \frac{n^2}{t}$$
We induce that
$$t_{mix} \leq e n^2$$.
At the end of this part, we give a small lemma about the log-sub-additivity of the $\rho$ which is
$$\rho(s+t) \leq \rho(s) \times \rho(t)$$
The proof is easy by the coupling technique.
Strong stationary time technique
Strong stationary time is a very special technique : we have a stopping time $\tau$, once we arrive this point, the law becomes naturally invariant law. Thus
$$d(t) \leq \mathbb{P}(\tau \geq t)$$.
This idea sounds crazy but the model fonction like this exists. One famous example is the random Top-to-random shuffle. In this model, the cards under the card at the bottom is uniformly random since there is no order under this one a prior. Therefore, once the card at the bottom comes to the top and once go back to the deck, the card becomes totally random. The mixing time is easy to calculate and is the same as the collection of coupon $t_{mix} \sim n\log n$.
However, this technique just applies in some specific case and requires a good observation.
Spectral technique : viewpoint from operator
The spectral method is especially powerful for the case of reversible Markov chain, which relates the speed of convergence to the gap of eigenvalue. Therefore, the gap of eigenvalue $\gamma$, the convergence of total variation distance, the ration of expansion have been related naturally.
We know that for a irreducible aperiodic finite Markov chain, it has naturally a series of eigenvalue $1 = \lambda_1 > \lambda_2 \geq \lambda_3 \cdots \lambda_n \geq -1$. We can extract a family of eigenvector orthogomal naturally by diagonalisation, however, we would like the orthogomal base in inner product
$$\langle f, g\rangle_{\pi} = \sum_{x \in S} f(x)g(x)\pi(x)$$
instead of the orthogomal base in usual $L^2$ inner product. To realize it, we find the orthogomal base $\phi_i$ of the operator $A$ where
$$A(x,y) = \sqrt{\frac{\pi(x)}{\pi(y)}}P(x,y) \Leftrightarrow A = D^{1/2}PD^{-1/2}$$
who is also symmetric and share the same eigenvalue with $P$ that is
$$A\phi_i = \lambda_i \phi_i$$.
Then we define $f_i = D^{-1/2}\phi_i$, we have
$$\langle f_i, f_j\rangle_{\pi} = \langle \phi_i, \phi_j \rangle = \delta_{ij}$$
$$Pf_i = D^{-1/2}(D^{1/2}PD^{-1/2})\phi_i = D^{-1/2}A\phi_i = \lambda_i D^{-1/2}\phi = \lambda f_i$$
So $f_i$ is the orthomal base wanted. The orthogomal decomposition tells us
$$A = \sum_{i=1}^n \lambda_i \phi_i \phi_i^T $$
when we plug the $f_i$ in, we obtain
$$\boxed{\frac{P(x,y)}{\pi(y)} = \sum_{i=1}^n f_i(x) f_i(y) \lambda_i}$$
One may wonder why we would like find a expression like this. In fact, it has interest since
$$\begin{eqnarray*}d(t) &=& \sup_{x \in S}\|P^t(x, \cdot) - \pi(\cdot)\| \\ &=& \frac{1}{2}\sum_{y \in S}\pi(y) \left|\frac{P(x,y)}{\pi(y) }- 1 \right| \\&=& \frac{1}{2}\|\sum_{i=2}^n f_i(x) f_i \lambda_i \|_{L^1(\pi)} \\ &\leq& \frac{1}{2} \|\sum_{i=2}^n f_i(x) f_i \lambda_i \|_{L^2(\pi)} \\ &=& \sqrt{\sum_{i=2}^n f_i^2(x) \lambda_i^2} \end{eqnarray*}$$
We continue the analysis and obtain the inequality that
$$\boxed{(t_{rel} - 1)\log(\frac{1}{2\epsilon}) \leq t_{mix}(\epsilon) \leq \log(\frac{1}{2\epsilon \sqrt{\pi_{min}}})t_{rel}}$$
where the relax time is defined as
$$t_{rel} = \frac{1}{\gamma}$$
$$t_{rel} = \frac{1}{\gamma}$$
Spectral technique : viewpoint from geometry
The result obtained by the eigenvalue of operator is so powerful since it gives both the upper and lower bound. However, to calculate the gap of eigenvalue is not so easy for general case, so we propose many other method to estimate the gap $\gamma$. Here we list two methods : by the optimal constant of Poincare's inequality and Cheeger's inequality.If we define the Dirichlet energy under the measure $\pi$ as
$$\begin{eqnarray*}E(f,f) &=& \sum_{e}Q(e) \nabla f(e) \nabla f(e)\\ Q(x,y) &=& \pi(x)P(x,y)\end{eqnarray*}$$,
then the classical discrete Poincare inequality gives
$$\boxed{Var(f) \leq \frac{1}{\gamma} E(f,f)}$$.
The constant is optimal so if we have another equality of constant $C$, we have necessarily $t_{rel} \leq C$ so we get the upper bound of mixing time.
Another method comes from the famous Cheeger's inequality, the ratio of expansion is
$$\Phi(A) = \frac{Q(A, A^C)}{\pi(A)}$$
and the ratio of expansion of the graph is
$$\Phi_* = \inf_{\pi(A) \leq 1/2} \Phi(A)$$.
The famous Cheeger's inequality tells that
$$\frac{\Phi_*^2}{2} \leq \gamma \leq 2\Phi_*$$
We remark that one good lower bound for the mixing time is that
$$t_{mix} \geq \frac{1}{4\Phi_*}$$
means that if the graph is not so connected, it will take long time to mix the chain.
Comparaison method and continuous time Markov chain
All the result of mixing time can also be converted to the continuous time, where the jumping time is a Poisson process but the state is still finite. We follow the same routine and get that$$d(t) \leq \frac{1}{2}d_2(t) = \frac{1}{2}\sqrt{\sum_{j=2}^n e^{-2t\mu_j}} , \mu_j = 1-\lambda_j$$
The comparaison theorem says that for two Markov chains $X,Y$ if $E_X(f,f) \leq AE_Y(f,f)$, then we have $\mu_j^X \leq A \mu_j^Y$. This helps us to give some analysis for a Markov chain given the information of one chain already well understood.
Coupling from the past
Wilson proposes some interesting algorithm called coupling from the past which gives an exact law of invariant measure in some specific case, for example the Ising model. The simulation requires that the state should have a function to make it ordered. Unlike the MCMC, we will come from the past. The coupling technique says that generally, the invariant measure is the case that a coupling meet. Now we apply check if
$$G(-t,0)(-1) = G(-t,0)(1)$$
where $-1,1$ represent respectively the minimal and maximal element. If it is the case, we take the value and if not, we add a segment of simulation even before it until it meet. The monotone property says it looks like we simulate from $-\infty$ and all the trajectories meet.
Finally, we remark although this program terminates almost surely, its time is a random variable so it takes risk to take longtime before ending.
Cover time
The cover time is another concept similar to mixing time which says the time to visit all the state at least once. The Matthews inequality gives the control $$t_{cov} \leq (1 + \frac{1}{2} + \cdots \frac{1}{n}) t_{hit}$$
One surprising result is the relation between the cover time and DGFF that
$$t_{cov} \sim |E| (\mathbb{E}(\max_{x \in S} h_x))^2$$.
Others
We conclude that the mixing time has to be estimated carefully. The coupling method has a lot of flexibility but requires good observation and technique while the spectral method looks more like analysis on heat equation. We can also reformulate the subject in the language of electronic network so that we use the analysis of structure to estimate the mixing time.
2017年7月12日星期三
嫌疑犯X的献身
今天在网上看了改编自东野圭吾小说的电影，好像中日韩都改编了，我看的是日版的感觉还不错吧。这里也就随手写点感想。
或许是因为自身专业的缘故，对男主非常有代入感而且基本也能猜到他的做法。这个世界真正热爱数学并且也掌握的人不少，但最后做出划时代成就的也就那么寥寥数人，大多人其实也只是整个进程的参与者。所以自觉壮志难酬、岁月蹉跎的数学家以及最后面对现实变成数学老师的其实也是蛮大的一个群体。做数学的人理性单纯，但其实有时候情感又说不出的强烈，脑子热起来比普通人可以更狂热。但专业特质让他们人际沟通能力或者主客世界观多多少少都有那么一点点问题。
这个问题在哪里呢？就是从数学的角度，理论框架和模型是可以自己构建的，如果不考虑应用，甚至可以忽略掉框架和模型的合理性。这点和物理学家不同：他们或许有时候缺少逻辑的严格性，却不乏敏锐的观察，以及最终目的还是为了解释现象理论不过是辅助罢了。
理解了这些再去解读石神和汤川就更加简单了。石神就是那个脑子发热了，情商不高的数学家。说着做了那么多，其实人家理解吗？接受吗？愿意吗？什么都不闻不问也不去试着了解。设计的阴谋某种意义上也是自己构建的一个局，真把所有人都当齿轮了。最后石神的痛苦我觉得既有感情上一厢情愿付出不得接受的无奈，也是因为觉得队友蠢吧？
说队友蠢是有点过的，此处无意过多贬低女主。人生都有自己选择，难道接受了他人充满不正义的爱意再加上自己的负罪感，真的能过得很舒坦么？
汤川的抉择是无奈的。很多人说他们惺惺相惜，而最后是为了一教高下才说出真相的。我倒觉得惺惺相惜固然有，但和内海的谈话已经表明了他其实自己也明白真相如此残酷，也在纠结是否就这样仍由这个局存在下去呢？但物理本身就是求事实之真，并非逻辑体系严谨自洽就承认是对的。我想因为这样他才选择去揭破这个残忍的局吧。
最后的最后，我觉得本片对于数学系学生思想和心理教育是很有启发式的一部电影。多多少少我们不能只活在自己的世界里。都说爱情是数学的毒药，其实也不至于吧，但如果能为了爱情付出全部甚至自己的未来，为什么就不能选择两个人一起好好活下去？比如石神可以坦诚一切，选择无论如何陪母女两人一起走完剩下的路啊。
订阅：
博文 (Atom)