How the TCP works ?

In the course probabilistic algorithm, we talk about how the TCP works. In fact, what we do on the course is a reverse engineering, that is, we know the policy taken in our reality and then try to find the philosophy behind.

What the TCP does?

What TCP does is very simple. When we send the pocket on Internet, there are always limits for the bandwidth. The PC will increase the number sent if it receives a success signal in order to accelerate the speed, but divide by 2 to avoid the traffic problem if it receives a signal of failure.  Intuitively, this is a good strategy, but what it achieves?

A general model

Inspired by the model in economics, we apply the model of optimization. In this model, we aim at a function of utility and some limits. In our problem, the limit is clearly the physical limit: the sum of flux cannot be greater than the admissible one. But the goal function, in fact, can be very different. There are max-min, proportional function, alpha weight function. The TCP is just one specific case of alpha weighted function.

Technique part 1: primal algorithm

The next problem is that what can we do when facing a general optimization problem. We ca ignore the condition and just treat the relaxed question and apply the primal algorithm. The Lyapunov function and ODE theory assures that this method converges.

Technique part 2: Lagrange  multiplier and dual method

A second method which treat the problem directly is the theory of optimization. Maybe we know always the method of Lagrange multiplier method, it is correct and always correct given a good function. However, the most profound theory is Kuhn-Tucker theory and a dual problem. If we would like to minimiser the function, we can minimiser given the parameter, and then maximiser the parameter. This procedure always works if we find the Kuhn-Tucker vector, this is true when it has control from the lower bound. So this idea propose the dual algorithm for our question.

Greedy algorithm for viral marketing is good engough

The viral marketing is a very mathematical question. We assume that each client has some probabilities to distribute the information to other places, then we need to calculate the minimum number to ensure that all the network is infected after some time. We can just simplify the question such that we choose a community and then consider its neighborhood. Then a naive method is to find the vertex who will add the most number into the community. Is this method smart enough?

The answer is amazing, Yes! If we do like this, we can achieve a solution that infected the network at least constant times of the optimal solution.

In the following, we list the main steps in the proof. We denote F(A) the number of vertex connected. Then a key formula is 

F(A \union B) + F(A \intersection B) <= F(A) + F(B)

Then, in the stream of greedy algorithm C_i, the increment is not so bad. That is 

F(C_{i+1}) - F(C_i) >= 1\k * (F(C) - F(C_i))

If we change a little this formula, we will get 

F(C) - F(C_i) <= (1 - 1\k)^k * (F(C) - F(0))

So the greedy algorithm attends at least 1 - 1/e = 0.632 times the optimal solution, a result good enough in certain situation. 

OK, greedy algorithm is not always the best but not bad.

To be or not to be? 何去何从？

我就十分偶尔地写一篇文章，来讲讲今天的种种，关于我，关于我的职业，和我的未来。

第一个故事是我和Y老师的日常谈话，她问我为什么数学这么好？我说父母也都没有接受过高等教育，就是小时候去妈妈办公桌上玩玩计算器，然后后来偶然一次学校里竞赛考到了第三名，感觉在人生中的一无是处里找到了那么一点点属于自己的天地。之后的故事也有起起伏伏，终究这么过来了，瓶颈也是一次次地突破过去的，谁说没有撞天花板呢。而且现在感觉也是状态最好的时候，每天都在学习新的知识，不说一日千里吧至少节节高，感觉以后还是能做得不错呢。

第二个故事是看到USNEWS我旦数学再创新高。说实在的，现在对排名这个东西已经无感了：就是个牌子找找工作用的。真的内行人还会有很多标准来衡量水平，这年头骗不了人，而事实上我自己也并没有能力去衡量各位教授的工作，最多从自己喜好和专业出发说上那么一两点。P大同学说他们学校现在有点停滞，祝我们早日冲上前十，我自然客气的说咱们可以携手共进把哈佛普林拉下马啊！但这肯定要靠我们一代啦！

然后我就被第三个故事啪啪啪打脸了。

第三个故事是关于北京拼娃的，无非又是老三样：奥数难，学生苦，然而学校背地里依然以此作为选拔标准。我当时随手转发，评价道：就是清北复交都进了世界前十依旧解决不了这个供需关系啊。

我觉得我的背景对这个问题是颇有发言权的：首先理论上我是竞赛的受益者，但事实上普通教育我又一门没落下的全收了。现在数学也在慢慢转变成职业。我觉得选拔人才无可厚非，但把大家都逼上绝境人人自危这就不对了。大家都在说教育资源不公平，可是那些教竞赛的老师应该水平都不错吧？为什么没有补充到不充裕的教育资源里去呢？如果均贫富，或者至少资源相对平衡，那么不至于发展到这个地步啊。

如果所有人都把稀缺资源作为一种最终变现的手段，那么最终只剩下恶性竞争和内耗而没有真正的发展和进步了。

但故事到了自己身上，又真的不是那么容易了。

第四个故事是今天下午去听报告，挺学长讲了讲博士经历。忽然让我觉得现在正一个劲的想进入的领域，做了那么多工作，会不会也有一天因为掉到物理大坑里，然后大家发现所做的一切都是徒劳？又或者看着科研领域还是重重风险，是不是要及时撤出，找一份体面的工作，领一份丰厚的收入？

说着人到了最后，还是不免会想要自身利益最大化吧？好嘲讽啊。

末了回来的时候，我看到好多同学给我各种留意，又趴在电脑前自我折腾了好一会儿，我想我应该还是不会放弃的吧。

人们说数学的好处的时候，多半会说可以转行啊，教育、计算机、金融、数据科学、通信等等。他们大概也不会知道，在真正选择做数学的时候，也得把这些外在的物质上的诱惑一一抛弃了……

如果说读博士是个高风险，低收益的行当，我们为什么会选择？

人有很多状态，有些状态是人的状态，喜怒哀乐，斤斤计较，当我问这个问题的时候，显然也就是在这个状态。

可是我知道我还有另外一种状态：虽然世界很复杂，人生很艰难，但此时此刻，我只需要专心做一件事情，就是思考。然后就只剩下我和问题，还有为了真理的决斗！

我想，至少读个博，可以有充足的时间，去体验这样一种状态吧。

至于之后呢？我还是相信，在千锤百炼之后，大脑会更加灵光，或许也会洞察很多世间的规律吧，毕竟数学也源于生活么。

到那一天，我应该有足够的能力去改变这个世界吧。至少，让娃娃们小时候能有个快乐的童年，等长大了，咳咳，我教他们真正的数学。

P.S: 新赛季开始了，我最爱的小卡又涨球了。你说篮球打得好也不见得玩得了排球，小前打得好也不见得干得过中锋，前锋位置上历史上还有呆呆老詹，后卫位置上追一辈子帮主唠嗑也未必够得上，努力是为什么呢？可是我还是希望小卡能成为最棒的啊！

Voila, 一样的道理么。数学家练到顶级也不见得能填掉其他方向的坑，分析概率练到化境估计还是不懂代数，可是我依然觉得能把喜欢的事情做到顶级是件很棒的事情！不要拦着我！

Complex analysis: a review

Recently, I pay two days to review the most basic one variable complex analysis. I have to say that, in fact, I have learned this topic in 2012 (OK, I have learned system in 2011 even earlier but I still have to review them in this year), but in that time, I find that difficult to understand this topic and I got even the worst result during my undergraduate in this course. However, for most people, complex analysis is easier than real analysis. Really?

I think that maybe the difficulty is that, the real analysis is more quantitative but complex analysis has more structure. If we have well understood the differential calculus and some topology, this topic will be obvious. I recommend this Note as a reference.

0. Angle, multiple value function, logarithm
The first difficulty is to define the logarithm. The angle of a complex is clear, but why we need complex logarithm to make it sense by striping one line? In fact, we always hope to make a function continuous, but since the angle is a multiple value function, to achieve we have to pay something. Then the log is well defined and so is the power.

1. Differential, analytic, confromal, holomorphic function
This four words represent in fact the same sense in complex analysis. The derivative can be understood as the form on C and if we know the sense in Banach space, we know that it is just a linear approximation in distance. But in complex situation, it has other senses, like the Cauchy-Riemann equation, the conformal map keeps the angle and the real part and imaginary part are all harmonic, so we have all the property from harmonic function.

Thanks to the Cauchy integral, we pass the differential to analytic. So the regularity is not C^1, C^2 but C^infinity. What an amazing result! So we would like to know how to prove that a function is analytic? A strong weapon is Motel lemma, who says that if the integral along any triangle is 0, this function is analytic. We can develop other methods from this, like passing the limit from a series of functions.

2. Singularities and Laurent series
The opposite side of analytic is singularity. What the other side of analytic? There are three type, removable singularity,  pole and essential singularity. The removable singularity says that we can redefine the value on the singularity. The pole is the case that limit infinity so its inverse is 0. The essential singularity says the value around it is dense in C! Notice that all the case discussed above is the isolated singularity. Well, to define something in any form makes no sense.

Then the Laurent series give a criteria for these singularities. If it has only positive part, it is analytic. If it has some negative part, it is pole. But if it has infinite negative term, it is an essential singularity.

3. More about integral - homotopy and residue theorem
A theorem, which is always correct says that along two homotopic trajectories the integral is the same. This strong property makes the connection between the complex analysis and topology. So we have a stronger version of Cauchy integral and even the residue theorem. That is when we make the integral, we do this only in the part around the singularity.

We apply this technique also in counting the zeros and the argument of angle.

4. Reimann mapping theorem
Last but not the least, a powerful theorem, any simply connected  domain have a conformal mapping to disk.

Why I revise complex analysis? Recently, the probability theorem has a strong connection with the complex analysis. I believe that these basic elements will help me understand those delicate theory.