聊聊大选

  今天我也说一段大选的事情。这个大选不是美国的大选，是我们学校学生会的大选。这不是一个故事，但其实我是想从这一连串的故事讲一个问题。

  我们就先说说这个主线故事吧。X学校的每年学生会选举，两组人马全上全下，方式就是大家公投，三年级的票权只有一票但二年级相对权重大有两票（毕竟他们是学校主体，三年级不久就毕业了）。裁判标准就是一周的好吃好喝活动表演。

  今年的不同之处是我的直系学妹在某一队里，好多年了终于又有中国同学参选了。学妹人缘应该算是不坏：办活动也积极，人也热心。传统上，中国同学中很热心去当干部的，会被大多数人觉得有点官腔，或者觉得就是过度热心政治，毕竟大学里靠这些活动攒资历的也是有的。不过学妹不管怎么说，办事的时候还是一板一眼大家还算认可的。我自己觉得嘛，不管怎么说选个中国同学到学生会里也算是一件大事，大家至少应该是要上点心的。

  末了开票了，学妹的那一队没赢，而且最后知道其实输的也不多，输了10票。因为票数实在接近(667:657)，最后还复查了好多遍甚至推迟了开票时间。

  这个10票，被我不幸言中了，连学妹自己最后都承认，还不如输了40票痛快呢。

  原因就是这个票，不是免费的。说起来就是公民和人民的关系，要有投票权么平时也要支持学生会工作，大多数人每月大约都会交上个20欧的样子，被戏称为“保护费”吧。而时间拨回一年前，好多现在三年级的中国学生，当年觉得这个费交的不值，因为自己参加活动不多么，所以就没有交。好一笔经济账啊！

  我不想就经济账和政治账这两件事情多展开了。本来么，也没人说非要把咱们中国代表投上去对吧？我这动不动上纲上线什么民族荣誉感，肯定有人觉得不舒服（不过如果要定个性，我也毫无疑问给他们扣个没有民族荣誉感的帽子）。即使不谈这些，连话语权都不想要了吗？我当然可以接受说，大家拿着票不投自己同学，觉得那一组不够好，可是放弃投票权又是怎么一回事？这不是大家羡慕了好久的自由民主吗？直接就不要了？说真的，我从去年到今年，就觉得为了这两票的民主，“保护费”还是值得的，哪来没有成本的民主呢？

  我要说的第二个故事是关于去找实习的。快到实习季了么，大家都忙。我早早定了实习也就给大家创造机会来个顺水人情，组织一趟去华为数学所参观的活动。我就偶然碰上他们所长的，聊数学聊得开心，然后就提出来了这么一个想法。报名期间拖过ddl的，集合迟到的，这些我就不提了，算大家和我熟也就无所谓了。参观到最后，还有最后一个实验的时候，走了一半人。我当时在想，说好的要来找实习呢？华为现在的水平世界上也排得上号了啊，最后再看一个实验会很久吗？为什么就要抢着那么几分钟就离开了呢？

  我要说的第三个故事，关于我们这里一位同学的，当年来法时拿的埃菲尔奖学金，这个奖学金非常丰厚，说起来平日里大家都是很羡慕他们的。我们这位同学今年没有办公交卡，因为觉得今年出门次数不多，平日就管我借吧。我也没说什么，借就借呗。今天这位同学在路上后来被查了，得罚钱，她挺不乐意的，僵了好一会儿，后来在同学提醒下想起卡是我的毕竟还要有交代，才勉强交了钱。

  当我讲到第三个故事的时候，我真的已经不知道对于很多人而言，生活除了实习、工作、收入、房子、车子、结婚、生子还有别的吗？

  我听过很多故事，比如“人生不能只有眼前的苟且，还有诗和远方”。

  比如我初中那年，两位语文老师分别和我们读过“沉默的大多数”和“集体无意识”两个故事，前者说的是文革，后者说的是南京大屠杀。

  比如我大学毕业那年，老师和我说出国了要做三件事：读好书，学习了解当地文化和语言，做好组织工作（大家要团结，不能窝里斗）。

  时下有文章抨击当下制度培养的所谓精英，大多只是一群“精致的利己主义者”，说更多人似乎得了“空心病”，纯当我是一个不幸的人在异国他乡这么几天里碰上了诸多极端事件。只盼着，这一切都只是妄言，而大多数年轻人如新闻联播里描述的那样，满怀理想和朝气，将时代精神、民族复兴和个人追求结合在一起奋发图强吧。

How to get out of the prison?

[Question]: A and B are jailed in two  room and throw a coin independently. Then they  give a guess, if at least one of them get the right answer, then they can get out, Do they have a strategy to get out of the prison.

[Answer]: Yes.  If we let A give the answer as it is, and B reverse the  answer, we have four situations: (A, B) = (1,0), (1,1), (0,0), (0,1) and their answer (F(B), F(A)) = (1, 1), (0,1), (1,0), (0,0), at least one will be right.

If we analyse a little, we will find no matter what happens, the expectation of right answer is just 1, what we need to do is to reduce the 0. So we need to make their prediction as two random variable correlated. This is the strategy and we make some try to get the right answer.

Random Graph : Erdos-Renyi Graph

OK, Finally I finish finding the way to add maths equation into the blog and this will be my first blog with the beautiful equations.

Recently, in the course of MAP554, we talk about different types of random graphs, a branch very active in maths and its applications since the appearance of the social network. In fact, there exists various types of random graphs to simulate different situations, we will start one by one and in this post we concentrate on Erdos-Renyi Graph

Definition of Erdos-Renyi graph

The definition of Erdos-Renyi graph is very simple. In graph $G(n, p)$, each edge between vertex $u,v$ has probability $p$ to appear, and for different edges, they are independent. This model simulates well the situation the propagation of virus in the society, or the diffusion of message in a small environment, where every one is same and no limit of distance.

We consider a concrete question: Now the ads is diffused, what's the probability that all the people are influenced? What's the possible size of the largest connected component?

The emergence of great connected component

We simulate the propagation of the information in the way like the random walk associated with Watson-Galton branching movement. Each step, we deactiver a vertex and add all the vertex non-explored who has connection with that one. If we note $A_k$ the number active and $D_k$ the number explored in the k-th time. That is
$$
A_k = A_{k-1} + D_{k} - 1
$$
where $D_k$ follows the distribution of $Bin(n - A_{k-1} - k + 1)$.

This description is the most important way and we will repeat that many and many times in the proof. The estimation about the size of Watson-Galton is very standard by the Chernoff inequality:
$$
\mathbb{P}(C > k) \leq \mathbb{P}(A_k > 0) = \mathbb{P}(D_1 + D_2 + \dots D_k > k)
\leq  e^{-\theta k } \mathbb{E}[e^{\theta(D_1 + D_2 + \dots D_k )}]
$$
Then, we use the technique to minimize the right term.

We declare directly the conclusion : In the case sub-critical, $np < 1$, the largest connected component is of the order $\log{n}$ with a large probability. In the case super-critical, $np > 1$, with large probability, the largest connected component is of the order $O(n)$, but the second one is of the order $\log{n}$.

The probability of a connected graph   

The conclusion: $\lim_{n \rightarrow \infty} np - \log{n} = c$, then the probability that the graph is connected is $e^{-e^{-c}}$.

The proof of this theorem uses the first and second moment method, the approximation of Poisson distribution (little number theorem). Something amazing is that in fact, this probability is very close to that of non isolated vertex in the graph. That is to say, when $n$ is big enough, we can consider the two equivalent.

Conclusion: The Erdos-Renyi graph is the simplest model of random graph, since there are no geometric structures, which makes it simple and accessible. When the probability is so small, there are high probability that the graph isn't connected and when it rises, the probability of connectivity climbs, the biggest connected component will also grow from the $\log{n}$ to $O(n)$. Moreover, in some more complicated model like Ising model or percolation, there are also the similar conclusion like sub-critical and super-critical.

Phase transition, the critical point, the asymptotic behavior, scaling limit and continuous model associated, the random walk on the random graph, the mixing time of the former...These will compose my future research. Exciting!

BS formula, PDE and Mote-Carlo

In mathematical finance, a key problem is the price of the derivative, for example the price of the option. This semester, I take a standard master course in X, which gives me so much impression: How a system can train the mathematics financial engineer as quickly as possible. After all, there are beautiful maths in it. Here, I would like to take some point.

Preparation: Martingale, Brownian motion, Ito calculus

Before beginning the study of mathematical finance, some basic knowledge is necessary. Basic probability, large number theory and central limit is far from sufficient, but the the theory Martincale is also important. We can find a previous article in my blog. Then, the trajectory most common in maths-finance is the standard BM. Yes, we can generate some others like Poisson process, Markov process, Levy process and branching process, but the most basic one is the BM, the scaling limit of the simple random walk, who simulate the behavior of large number of investor in the market.

Personally, I believe the research about the random curve itself is interesting enough, but in maths-finance, what makes sense is the Ito calculus, which makes the integration along a random trace has sense. The integration can be defined for H^2 space, local martingale and even semi-martingale, considering adding one term of finite variation. The construction of these space and integration can be seen as a special application of real analysis and functional analysis.

Mathematics weapons: PDE vs Proba, Numeric vs Mote-Carlo, Feyman-Kac

A key formula who plays an important role and make connection of maths-finance with other domain is the Feyman-Kac formula. This formula tells us that, for calculating the expectation of some random variable, we can study a PDE associated using the generator. The inverse procedure is also correct: to treat a type of parabolic equation, we can also study the associated random process. 

In practice, these two branches also lead to different realization: numerical solution or Mote-Carlo method. Personally, the Mote-Carlo method is easier to implement, but is it necessarily better? No idea, because after we will see other examples.

Feyman-Kac can also treat the Dirichlet question, which associate not a heat equation but a Poisson equation.

Application in the context of finance

The maths-finance is not a course pure probability, so we cannot ignore the part practical. For example, in the pricing, what's the principal? If we do not make it clear, those weapons will be abused. 

There are two principle, one is no arbitrage and the other is perfect replication. The perfect replication is simple, there is no option in the nature, so when we vend one option, we have to prepare  some strategy to produce these service so that we can  give the money. However, the production procedure follows also one condition self-finance, from what we see the final PDE. Then, the no arbitrage principal makes sense. That is the price should be exact the expectation. If not, the other has arbitrage principal to make money.

When we draw conclusion, we always say that the price is the expectation after actualization under the risk neutral measure. This simple phrase uses the change of probability, the PDE and other knowledge. We pay attention that the price does not depend on the change of the stock! But just the volatility. The drift is in fact erased in the neutral risk. We know, the final object of pricing is that equilibrium but not profit!

Beyond the Feyman-Kac

From the technique part, but also the maths-financial part, the Feyman-Kac is not enough since the generator is always linear. But for some general case? For example, the optimization problem, what we do?

The answer is BSDE, an advanced method that give a backward method to solve the equation.

In addition, some other option can make the pricing totally into a maths game. The existence and uniqueness of the SDE has also some practical meaning: the count cannot be infinite in debt. So the  finance and maths interact one with the other, just like my tutor Pierre does.