Google应用PageRank算法给每个网站分配了一个从0～10的数字，它代表了一个网站的重要性。PageRank根据网页之间的超链接来确定一个页面的等级。大家在我博客的右边栏中搜索框的下方可以看到我博客的PageRank，也可以在一些信息查询网站上查询任意网站的PageRank。那么，这个数值是如何计算出来的呢？
其实，PageRank算法的计算过程可以形象的看作“投票”过程。比如我的网站上挂了Wikipedia的超链接，那么我就给Wikepedia投了一票，那么他的PageRank值就会升高。粗略的说，每个网站的PageRank值就是其他各个网站给它“投票”的总和。如果简单的把每一个网站所投的票都看成相同的，这样又会不公平。因为重要的网站所投的票应该有较大的分量。那么，如何确定哪个网站重要，哪个网站不重要呢？还是要根据PageRank。这就产生了一个看似矛盾的过程，我们需要用PageRank值来衡量一个网站的重要性，而它本身的计算中又需要用到PageRank值！
这听起来很像递归，或迭代。PageRank的算法正是基于这种思考产生的。
我们定义PR(A)为A网站的PageRank。为了叙述方便，我们不再使用google的0~10度量，而是使用0~1度量。这和概率的取值范围是一致的。事实上，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，google才更改了度量。
在计算的开始，我们假设考虑的所有网站的PageRank是均匀分布的。这意味着，如果互联网上共有N个网站，那么每个网站的PageRank都是1/N。现在，假设我们仅仅考虑4个网站A,B,C,D组成的一个小网络。初始时，它们的PageRank都是1/4。假如B,C,D的网站上都有且仅有A的链接，那么它们每个人都为A贡献了0.25的PageRank。
（图1）
定义

则PR(A)=0.75
现在假设B网站上还有C的链接，网站D上有其它三个网站的链接。如下图所示：
（图2）
此时，对于B来讲，他把自己的总价值分散投给了两个网站A和C，那么每个网站就应该得到一半的PageRank，即0.125。只有1/3的PR(D)给了A。在这种情况下，

所以，按如此定义，一个网站X上有网站Y的链接，那么它给Y贡献的PageRank等于它的PageRank除以它网站的所有外部链接。（在这里我们做了一个假定，即X网站上对Y站的多个链接不重复计算。不难发现，这样的假定是很合理的。否则像http://worlds-highest-website.com/这样的一个网站上从头到尾全是www.charlesgao.com的链接，那我博客的PageRank就不会这么惨了。—–当然，这是不公平的。）
一个网站u的PageRank的普遍表达式为：

其中B_u是所有链接到u的网站的集合。v为相应网站所链接到的网站总数。
有一点值得注意的是：所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：
初始：所有网站的PageRank均等
第一次迭代：每个网站得到了一个新的PageRank
第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRank
…
我们最关心的问题是：
如此迭代下去，这些网站的PageRank值最终会收敛么？
大家再回头看我们一开始提到的两个例子。对于图1所示的例子来说，很显然第二次迭代所有的PageRank就都是0了。过程如下：

图2所示的情况也将导致最后所有网站的PageRank变为0。因为没有网站链接到D，那么第一次迭代后PR(D)=0。这将导致PR(B)=0，继而导致PR(C)=0,and then PR(A)=0:

咦？如果PageRank算法是这样的话，那岂不是每个网站的PR都是0了？
为了讨论上面情况发生的条件，我们暂时抛开网站，把问题抽象出来——研究有向图。
首先说明一点，对于如下这种不连通的图：

我们可以分别研究每一部分，而并不影响各个部分的收敛性。 Read the rest of this entry »

如果你在学生会工作，想了解同学们在考试中舞弊的严重程度，当然不好找到一些同学问：“你们中谁有舞弊行为？”下面介绍一种估计严重程度的数学方法。
假定要在100位同学中作调查，就做100张小纸条，其中40张纸条上写：你有舞弊行为吗？剩下60张纸条上写：你没有舞弊行为吗？让被调查的同学像抓阄那样每个人任取一张小纸条，并回答“是”或“不是”：一个有舞弊行为的同学，他如果拿到的是问题：你有舞弊行为吗？他应该回答：是。如果拿到另一个问题则回答：不是。也就是大家都如实回答问题。你的工作就是记录有多少人回答“是”，有多少人回答“不是”。假定有45人回答“是”，剩下55个人回答“不是”，你如何根据这样的方法算出舞弊学生所占的比例？

Read the rest of this entry »

还记得我写过的那篇用概率计算π的文章么？今天又学到了点东西(From Prof.Xiang)。原来用概率模拟来计算一些问题，这种方法是有名字的。名字就是本文标题。以下内容摘自百度百科：

——————————————————————————————————————————–

蒙特卡罗(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于”随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的”曼哈顿计划”。该计划的主持人之一、数学家冯?诺伊曼用驰名世界的赌城-摩纳哥的Monte Carlo-来命名这种方法，为它蒙上了一层神秘色彩。

Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的”频率”来决定事件的”概率”。19世纪人们用投针试验的方法来决定圆周率π。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。

考虑平面上的一个边长为1的正方形及其内部的一个形状不规则的”图形”，如何求出这个”图形”的面积呢？Monte Carlo方法是这样一种”随机化”的方法：向该正方形”随机地”投掷N个点落于”图形”内，则该”图形”的面积近似为M/N。

可用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。

科技计算中的问题比这要复杂得多。比如金融衍生产品（期权、期货、掉期等）的定价及交易风险估算，问题的维数（即变量的个数）可能高达数百甚至数千。对这类问题，难度随维数的增加呈指数增长，这就是所谓的”维数的灾难”(Course Dimensionality)，传统的数值方法难以对付（即使使用速度最快的计算机）。Monte Carlo方法能很好地用来对付维数的灾难，因为该方法的计算复杂性不再依赖于维数。以前那些本来是无法计算的问题现在也能够计算量。为提高方法的效率，科学家们提出了许多所谓的”方差缩减”技巧。

另一类形式与Monte Carlo方法相似，但理论基础不同的方法-”拟蒙特卡罗方法”(Quasi-Monte Carlo方法)-近年来也获得迅速发展。我国数学家华罗庚、王元提出的”华-王”方法即是其中的一例。这种方法的基本思想是”用确定性的超均匀分布序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法中的随机数序列。对某些问题该方法的实际速度一般可比Monte Carlo方法提高数百倍，并可计算精确度。

——————————————————————————————————————————–

下面我来举几个具体例子：
1 还是求π
这次的方法要简单一点，不用绕那么多弯子。在[0,1]×[0,1]中任取点，该点可能落在单位圆内的概率为圆的面积比上整个矩形的面积。我们知道这个比值是π/4。那么，只要这个概率求出来了，再乘以4就是π。在用计算机模拟的时候，限制条件用x^2+y^2<1。这里究竟要不要取等号是没有关系的。因为面是由无数条线组成。一条线的包括与否不会影响到整体效果。
我用matlab模拟，做了一百万次(即共取1000000个点)，结果为3.1403。

2 求定积分
比如y=x^2(对x)从0积到1。结果就是下图红色部分的面积：

注意到函数在(1,1)点的取值为1，所以整个红色区域在一个面积为1的正方形里面。所以所求区域的面积即为 在正方形区域内任取点，点落在所求区域的概率。这个限制条件是y<x^2。
我用matlab模拟，做了一百万次(即共取1000000个点)，结果为0.3328。
再比如求重积分

，其中D={(x,y)|x^2+y^2<=1}

函数z=sin(x+y)/(x+y)的图像大致如下：

这个积分代表函数曲面与平面z=0和柱面x^2+y^2=1所围成的体积。所以我们要求的概率就是： Read the rest of this entry »

π=3.1415926…
关于圆周率π的计算，追溯历史，最早用科学方法寻求这一数值的人是阿基米德，他用圆内接和外切正多边形的周长确定圆周长的上下界，从正六边形开始，逐次加倍计算到正96边形，开创了圆周率计算的几何方法。中国数学家刘徽在注释《九章算术》（263年）时只用圆内接正多边形就求得π的近似值，得出精确到两位小数的π值，他的方法被后人称为割圆术。他用割圆术一直算到圆内接正192边形…
这些都是我们熟知的办法，但是，你知道还可以用一个事件的概率来求π吗？请看下面的问题：
在平面上画一组间距为d的平行线（如图），把一根长度为L的针任意扔到这个平面上(L<d)，问针触及其中一条直线的概率是多大？ Read the rest of this entry »