Proposal for EPSRC postdoctoral fellowship in applied probability by Dr. Matthew I. Roberts

概率一直是一个数学领域，在现实世界中有许多应用：赌博策略、动物数量的增长、疾病的传播或金融市场的表现。最近，随着知识和计算能力的增长，出现了新的感兴趣的领域，其中许多依赖于类似树或大型网络结构的结构。举三个具体的例子，现在可以研究物种DNA的进化；拥有有效的方法来组织我们计算机上的大量数据；以及理解组成互联网的大型计算机集群。DNA的进化和分枝布朗运动植物学家罗伯特·布朗在观察花粉颗粒在水中移动时描述了布朗运动。他注意到，水分子撞击颗粒造成的微小变化会导致花粉粒缓慢、宏观、随机的移动。DNA串极其复杂。即使是最简单的生物体也可以含有数百万个分子。单元格每次分割时，都会为该数据的每一位创建两个副本。错误不可避免地会发生，但这些错误中的大多数都会产生微小的影响，因为细胞中内置了额外的信息。尽管如此，这些微小的波动慢慢地沉淀下来，创造出有助于物种进化的大规模变化。这些由微小错误引起的随机运动使布朗运动成为这个过程的一个很好的模型。因此，一个生物体的DNA的进化可以用布朗运动来建模；但每个生物体也会繁殖，创造其DNA的副本，然后独立地变异和进化。这种描述使我们考虑一种称为分枝布朗运动的模型，它是一种树状结构，其中每个分支根据布朗运动在空间中运动。概率论者广泛地研究了这一过程的整体传播：用生物学的术语来说，一个物种如果听任自己的设备进化会有多快。如果一个物种没有随着环境的变化而进化得那么快，那么它很快就会灭绝。然后我们可以问这个物种能存活多久，以及种群增长的速度有多快。数据结构和排序算法由于需要越来越大的文件来存储我们计算机上的海量数据，因此以一种易于访问的方式组织这些数据是很重要的。一种这样的方法被计算机科学家称为快速排序，并得到了广泛的研究。该过程的工作原理是将数据分类到树状结构中，然后通过在树的分支点进行相对较少的检查来快速访问该结构。关于这棵树的高度，现在已经知道了非常细微的细节，这对应于必须进行多少次检查才能找到最难到达的数据片段。然而，几乎没有人知道有多少数据必须存储在树的最高层，这将告诉我们必须多久访问驱动器最远(和最慢)的角落。互联网和大型随机网络互联网由连接在一起的大量计算机(和网页)组成。这创造了一个正在永久变化的复杂结构。网络的连接属性对互联网的速度非常重要：在本地范围内，这归结为一台计算机是否可以连接到另一台计算机，以及建立这种连接需要多少链接。同样的想法可以用于研究其他相关结构，如社交网站。这里有大量的点，通过链接相互连接。随着时间的推移，这些链接中的每一个都可能出现或消失。非常微小的变化可能会导致系统的大规模行为突然改变，影响数据共享的速度。从细菌到蓝鲸，从BBC Micro到宽带互联网，概率论为研究所有这些结构提供了工具。

Probability has always been a field of mathematics with many applications in the real world: gambling strategies, growth of animal populations, spread of disease, or the performance of financial markets. More recently, with increases in knowledge and in computing power, new areas of interest have appeared, many of which rely on structures that resemble trees or large networks. To name three specific examples, it is now feasible to study the evolution of the DNA of species; to have efficient methods of organising the large amounts of data on our computers; and to understand the large clusters of computers that make up the internet.Evolution of DNA and branching Brownian motionBrownian motion was described by the botanist Robert Brown as he watched particles of pollen moving in water. He noticed that small changes caused by water molecules hitting the particles caused a slow, macroscopic, random movement of the pollen grains.DNA strings are extremely complex. Even the simplest organisms can contain millions of molecules. Each time a cell divides it creates two copies of every bit of this data. Inevitably mistakes occur, but most of these mistakes have a tiny effect given the extra information built into the cell. Nonetheless these small fluctuations slowly precipitate to create large-scale changes which contribute to the evolution of the species. These random movements caused by tiny mistakes make Brownian motion a good model for this process.So the evolution of the DNA of one organism can be modelled using Brownian motion; but each organism also breeds, creating copies of its DNA that then independently mutate and evolve. This description leads us to consider a model called branching Brownian motion, which is a tree-like structure in which each branch moves in space according to a Brownian motion. Probabilists have extensively studied the overall spread of this process: in biological terms, how fast a species will evolve if left to its own devices. If a species does not evolve as fast as its environment is changing then it will quickly become extinct. We can then ask how long the species will survive for, and how fast the population will grow.Data structures and sorting algorithmsAs larger and larger files are required to store the enormous amounts of data on our computers, it is important for that data to be organised in such a way that it can be easily accessed. One such method is known to computer scientists as quicksort, and has been extensively studied.The process works by sorting the data into a tree-like structure, which can then be accessed at speed by making a relatively small number of checks at the branch points of the tree. Very fine detail is now known about the height of this tree, which corresponds to how many checks must be made to find the hardest-to-reach bits of data. However, almost nothing is known on how much of the data must be stored at the highest levels of the tree, which would tell us how often we have to access the furthest (and slowest) corners of our drives.The internet and large random networksThe internet is made up of huge numbers of computers (and web pages) linked together. This creates a complicated structure that is permanently changing. The connectivity properties of the network are very important for the speed of the internet: on the local scale this boils down to whether one computer can reach another, and how many links it takes to make that connection.The same ideas can be used to examine other related structures like social networking sites. There are a large number of points, connected to each other by links. As time progresses each of these links may appear or disappear. Very small alterations can cause the large-scale behaviour of the system to change suddenly, affecting the speed at which data can be shared.From bacteria to blue whales, the BBC Micro to broadband internet, probability theory provides tools for studying all of these structures.