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

概率一直是数学的一个领域，在真实的世界中有许多应用：赌博策略、动物种群的增长、疾病的传播或金融市场的表现。最近，随着知识和计算能力的增加，出现了新的感兴趣的领域，其中许多依赖于类似于树或大型网络的结构。举三个具体的例子，现在研究物种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.