. 第一特征值乃是谱的主阶
第
34卷第6期数学进展Vol.34, No.6
2005
年12月ADVANCES IN MATHEMATICS Dec., 2005
谈谈概率论与其他学科的若干交叉
陈木法
¤
(
北京师范大学数学科学学院, 北京, 100875)
摘要
: 近一二十年以来, 概率论获得了很大发展, 特别是与其他学科交叉融合, 形成了一些
新的学科分支和学科生长点
. 我们首先从2002 年国际数学家大会(ICM2002) 所反映的情况予
以说明
. 作为这种交融的一个侧面, 也概述我们研究群体的三项成果. 最后介绍取得这些成果的
一种数学工具及其与线性规划和非线性偏微分方程等学科的联系
.
关键词
: 概率论; ICM2002; 随机算法; 自由概率; 渗流; 特征值; 遍历理论; 最优运输
MR(1991)
主题分类: 60-XX / 中图分类号: O211
文献标识码
: A 文章编号: 1000-0917(2005)06-661-12
1
从ICM2002 看概率论
1.1
概述
在
ICM2002 的开幕式上, 就可以感受到概率论的气息. 作为Nevalinna 奖的获奖人, M.
Sudan
的两项主要贡献中的第一项就是关于NP 类的概率特征的刻画.
在
20 个一小时报告中, 有六个涉及概率论的. 名单及所代表的领域列表如下:
A. Alon
离散数学
L. A. Ca®arelli
偏微分方程
U. Haagerup
算子代数
S. Goldwasser
计算机科学
H. Kesten
概率
D. Mumford
认知科学
第一个报告介绍两种方法
, 其一是概率方法(随机图论), 另一是代数方法. 最后一个报告贯
穿了概率方法
. 我们将在本文之末说明第二个报告与概率论之间的联系. 对于其他三个报
告
, 将在这一部分的随后几节中予以说明.
在
19 组45 分钟报告中, 除数学教育、数学普及和概率统计3 组外, 有6 组都涉及概率
论
. 其中“计算机科学中的数学”一组, 六个报告中有五个与概率论有关, 而“算子代数与泛
函分析”一组
, 六个报告中有两个“自由概率”, 一个“高斯测度不等式”, 即有三个报告是
概率论的交叉学科方向
.
1.2
概率与随机算法和计算复杂性
收稿日期
: 2004-08-03.
基金项目：国家自然科学基金委员会创新研究群体项目
(No. 10121101)、973 项目和教育部博士点基金项
目
.
E-mail: mfchen@bnu.edu.cn Home page: http://math.bnu.edu.cn/~chenmf
*
本文是第十二次院士大会、数学物理学部的学术报告(2004 年6 月5 日).
662
数学进展34卷
NP
问题的典型例子是
货郎担问题
: 给定全国144 个城市, 找出一条经过所有城市而又不迂回的最短闭路.
总共
144 个城市, 这个数字并不大, 但它经组合起来的闭路则有143! 条. 即使是每秒计
算一亿亿
(1009) 条路的计算机, 也需要100111 年, 因而是一个典型的NP 问题. 在组合最优
化领域里
, 存在大量的这类问题.
如何处理
NP 问题, 自然是一个严峻的挑战！似乎无路可循. 正是在这个人们以为“山
穷水尽疑无路”的地方
, 随机的思想给我们带来了“柳暗花明又一村”. 想法是: 如果允许算
法以小概率犯错误
, 则可将一些NP 问题转化为P 多项式问题. 针对货郎担问题, 有一种模
拟退火算法
(又称为马尔可夫链Monte-Carlo 方法). 目标是求一个函数的最小值. 其原理为
(1)
依函数值的大小确定一个概率分布¹: 函数值越小, 取值越大. 此即是Gibbs 分布
原理
.
(2)
构造一马尔可夫链, 以¹ 为极限分布, 即当时间趋于无穷大时, 这个马尔可夫链趋
于取值为
¹ 的分布.
留心通常的算法是“那里小就往那里走”
, 因而容易掉进局部陷井. 此法的特点是要到处看
看
.
U °
W
j
z
局部陷井
马尔可夫链
Monte-Carlo 方法
当然
, 仍然有一些细节需要处理. 例如, 需要“退火”, 即随时间的发展, ¹ 越来越集中于
整体最小值等等
. 对于上述贷郎担问题, 利用这种方法找到一条长为30421 公里的闭路. 这
与目前所知的最好结果
30380 公里相差无几. 而真正的全局最优解依然是人们力所不能及
的
[4].
我们指出
, 这种算法的有效性取决于马尔可夫链收敛于平稳分布¹ 的速度. 这个速度由
马尔可夫链转移概率矩阵的第一个非平凡特征值所决定
. 更详细的内容可参考R. Kannan
的
45 分钟报告.
人们常说
, 概率论是研究大量偶然现象中的必然性规律. 然而, 这里的研究对象却完全
是确定性的
, 毫无随机性可言. “随机性”思想的主动出击, 在这里得以充分体现. 这也是现
代概率论研究的典型特征之一
.
1.3
自由概率论(Free Probability)
U. Haagerup
的一小时报告的题目是“Random matrices, free probability and the invariant
subspace problem relative to a non Neumann algebra
”. 我们先从随机矩阵谈起. 设AN =
6
期陈木法: 谈谈概率论与其他学科的若干交叉663
(
a(N)
ij
) 是N 阶Hermite 方阵, 假定
³
a
(N)
ii
´
i
;
³
p
2 Re
a(N)
ij
´
i<j
;
³
p
2 Im
a(N)
ij
´
i<j
为独立同分布随机变量
, 服从均值为零、方差为p1
N
的正态分布
. 命
¾
(x;AN) =
1
N
]
f
特征值(可重复) 6 xg
则有优美的
E. Wigner
半圆律(1955-1965): 随机变量¾(x;AN) 弱收敛于一个非随机的函数¾W(x), 其
密度为
¾
0
W
(x) =
(
1
2
¼
p
4
¡ x2; 若jxj 6 2;
0
; 若jxj > 2:
随机矩阵理论有两个重要来源
, 一是矩阵力学, 另一是多元统计. 我国概率统计的前辈
许宝騄先生是这一理论的早期开拓者之一
(1939). 这个理论甚至紧密联系于Riemann 猜想.
若将复共轭视为
¤ 运算, 则随机矩阵自然构成典型的C¤ 代数. 欲将上述半圆律拓广
到
C¤ 代数上, 首先需定义C¤ 代数上的独立性. 这就引进了自由概率的概念: 换言之, 这里
的“自由”即是通常概率论中的“独立性”
. 这个概念及\自由熵" 等首先由D. Voiculescu
(1985)
引入(获2004 年美国国家科学院奖), 并成功地应用于von Neumann 代数的分类问
题
, 导出了\若干革命性成果", 引发了大量的研究. 矩阵论作为非交换数学的基本工具是天
然的
. 然而随机矩阵论作为算子代数的基本工具则多少令人吃惊.
1.4
概率论与物理
40
年来, 概率论与物理(特别是统计物理) 的交融汇合, 产生出若干新的分支学科. 最具
代表性的有随机场、交互作用粒子系统、渗流理论和测度值随机过程
.
(1)
渗流理论(Percolation Theory)
1982
年, H. Kesten 出版了专著\Percolation Theory for Mathematicians", 从数学上系统
总结了已有的
(特别是物理学家) 所取得的成果. 自此以后, 渗流理论成为概率学家的一个
专门的发展领域
. 上世纪末, 渗流理论作为一个基本工具, 解决了交互作用粒子系统的一个
著名难题
.
渗流理论特别象数论
, 问题很好懂、但却很难做. 还是从一个基本模型开始.
考虑
d 维的格子图. 给定每条边开的概率为p (闭的概率为1 ¡ p). 各边开或闭相互独
立
. 如果一条路的依次相互连接的边都是开的, 则称为一个开串. 显然, 若p = 1, 则所有的
边都是开的
, 因而存在无限长的开串. 反之, 若p = 0, 则不存在开串. 这就引出临界值pc 的
定义
p
c
= inffp : 存在包含原点的无穷开串的概率大于零g:
对于二维
(d = 2) 情形, 已知pc = 1
2
. 但当d > 3 时, pc 却是至今无人能够确定的. 若把边的
开、闭换成格点的开、闭，则上述边模型就变成点模型
. 此时，仅当两顶点均开时，所联结
的边才是开的
. 对于二维三角形点渗流, 己知pc 也等于1
2
. 通常, 物理学家知道得更多. 例
664
数学进展34卷
如
, 他们不仅知道三角形点渗流的pc = 1
2
, 而且还知道下式
当
p # pc 时; 原点属于无穷开串的概率= (p ¡ pc)®
中的临界指数
® = 5
36
+ o(1). 这是一种统计物理所研究的普适常数. 然而, 长时期以来, 数
学家对普适常数束手无策
, 研究状况处于完全真空的状态. 直到2001 年, 才由S. Smirnov 取
得突破
(解决了物理学家J. L. Cardy (1992) 基于共形场论的猜想). 他于同年荣获Clay 研
究奖
(颁布百万美元奖金的7 大数学难题的研究所). 所使用的工具是布朗运动与共形映照.
这一点又很象解析数论
, 使用复分析(连续) 来处理数论问题(离散). 这是H. Kesten 的一小
时报告和
G. F. Lawler 的45 分钟报告的主题.
(2)
研究相变的一种新方法
相变现象是统计物理的中心课题之一
. 作为无穷维的数学, 研究相变现象的数学工具并
不多
. 十几年来, 逐步形成了一种新方法, 即以第一(非平凡) 特征值来刻画相变. 例如对格
气模型
(Ising 模型), 一维情形无相变. 事实上，对于算子
Lf
(¾) =
X
x
2
Zd
c
(x; ¾)
£
f
(¾x) ¡ f(¾)
¤
; ¾
2 f¡
1; 1gZd
;
其中
¾x 表示在x 处的自旋,
c
(x; ¾) =
n
1
1 + exp
h
¯¾
(x)
P
j
x¡yj
=1 ¾(y)
io
; x 2 Zd; ¾ 2 f¡1; 1gZd
;
而
¯ > 0 为反温度, R. A. Minlos 和A. G. Trishch (1994) 甚至算出了第一特征值的精确值
1
¡ tanh ¯ > 0. 文章只有两页, 但使用了第二量子化的漂亮技术, 构造此模型的L2 空间与
圆周上的
L2 空间所生成的反对称Fock 空间之间的酉同构.
对于高维情形
, 随着温度的下降, 人们普遍认为第一特征值应由正变为零. 目前已证出:
当温度足够高时
, 第一特征值为正; 而当温度足够低时, 第一特征值为零. 关于后者, 事实上
知道得更多
. 当温度充分低时, 边长为L 的正方体的格子区域内的Ising 模型, 当L 趋于无
穷时
, 其第一特征值有渐近式exp[¡c(¯)Ld¡1], 其中c(¯) 是与维数d 无关的常数[5; 7; 8].
从这一节可以看出物理学对于当代概率论的深刻影响
.
2
特征值估计与遍历性
众所周知
, 谱理论在数学各分支和物理学中均有重要地位. 第一特征值乃是谱的主阶,
因而无疑有重要价值
. 上述的随机算法和相变刻画, 也已显示其重要性.
2.1
问题与难度
考虑如下无限矩阵
Q
= (qij) =
0
BB@
¡
b
0 b0 0 0 : : :
a
1 ¡(a1 + b1) b1 0 : : :
0
a2 ¡(a2 + b2) b2 : : :
...
. . . . . . . . .
1
CCA
6
期陈木法: 谈谈概率论与其他学科的若干交叉665
其中
ak; bk > 0 (k = 0; 1; 2; : : :): 因为仅有处于对角线附近的三条线的元素非零, 故称为三对
角阵
. 有限情形是计算数学处理矩阵特征值计算的最主要对象. 注意矩阵Q 的每一行和为
零
, 因此它与元素恒为1 的常值列向量1 的乘积为元素恒为零的列向量0: Q1 = 0 = 0¢ 1 .
即矩阵
Q 有平凡特征值¸0 = 0. 其次, 若考虑它的前n 阶子矩阵Qn, 则¡Qn 有n 个特征
值
: 0 = ¸0 < ¸1 6 ¢ ¢ ¢ 6 ¸n¡1. 我们所关心的是¸1, 即第一个非平凡特征值.
为使大家对于此问题的难度有点具体的感受
, 让我们看看一些简单例子. 先看四阶情形
(
Q3), 此时有6 个参数: b0; b1; b2; a1; a2; a3. 第一特征值是
¸
1 = D
3
¡
C
3
£ 213
+
2
13
¡
3
B ¡ D2
¢
3
C
;
其中
D;B;C 三个量的表达式并不复杂:
D
= a1 + a2 + a3 + b0 + b1 + b2;
B
= a3 b0 + a2 (a3 + b0) + a3 b1 + b0 b1 + b0 b2 + b1 b2 + a1 (a2 + a3 + b2) ;
C
=
µ
A
+
q
4(3
B ¡D2)3 + A2
¶
13
;
但
A
= ¡2 a31
¡
2 a32
¡
2 a33
+ 3
a23
b
0 + 3 a3 b20
¡
2 b30
+ 3
a23
b
1 ¡ 12 a3 b0 b1 + 3 b20
b
1
+ 3
a3 b21
+ 3
b0 b21
¡
2 b31
¡
6 a23
b
2 + 6 a3 b0 b2 + 3 b20
b
2 + 6 a3 b1 b2 ¡ 12 b0 b1 b2
+ 3
b21
b
2 ¡ 6 a3 b22
+ 3
b0 b22
+ 3
b1 b22
¡
2 b32
+ 3
a21
(
a2 + a3 ¡ 2 b0 ¡ 2 b1 + b2)
+ 3
a22
[
a3 + b0 ¡ 2 (b1 + b2)]
+ 3
a2
£
a
23
+
b20
¡
2 b21
¡
b
1 b2 ¡ 2 b22
¡
a
3(4 b0 ¡ 2 b1 + b2) + 2 b0(b1 + b2)
¤
+ 3
a1
£
a
22
+
a23
¡
2 b20
¡
b
0 b1 ¡ 2 b21
¡
a
2(4 a3 ¡ 2 b0 + b1 ¡ 2 b2)
+ 2
b0 b2 + 2 b1 b2 + b22
+ 2
a3(b0 + b1 + b2)
¤
:
这样
, 诸参数对于¸1 的贡献就完全糊涂了. 当然, 对
No comments:
Post a Comment