Markov Chains and Spectral Graph Theory: Interactions and Applications

马尔可夫链是一种特定类型的概率模型，这些模型在科学和工程中无处不在，在计算药物设计，车辆交通网络和网页排名等不同领域中找到应用。Kemeny常数是与马尔可夫链相关的关键量，在某种意义上，它提供了马尔可夫链整体短期效率的全局度量。尽管凯梅尼常数早在50多年前就被引入，但人们对凯梅尼常数的了解相对较少，拟议的研究计划将对该常数进行彻底的调查。通过阐明Kemeny常数的数学性质，我希望能为设计具有理想效率性质的马尔可夫链提供一些见解。 图（或网络）是一种数学结构，记录有关以某种方式相关的对象（称为顶点）的信息。例子包括通过“友谊”联系的Facebook用户，一起执行某些功能的细胞中的蛋白质，以及通过电阻器连接的电气网络中的终端。有一种自然的方式可以将马尔可夫链与任何图联系起来，事实证明，马尔可夫链的某些参数可以用来衡量每个顶点在图中的中心位置。这种马尔可夫链中心性已被实证研究，但目前几乎没有严格的理论对这个问题的方式。拟议的研究方案将发展这种马尔可夫链中心的数学理论，从而提高对该中心所反映的图论性质的理解，并在实际应用中使用该中心。 量子行走的概念起源于所谓的量子线--一种量子计算机内部的信息传输模型。量子漫步的保真度测量信息沿着量子线沿着正确传输的概率。该研究计划还将调查保真度对信息传输所需时间的敏感性，以及与量子线相关的物理参数。这些结果将有助于量子行走的设计和实现。 这项研究计划预计将在几个不同的领域产生影响。从理论方面研究马尔可夫链的研究人员，以及在实际环境中应用马尔可夫链技术的科学家和工程师（例如流量建模、迁移模型和网络分析）将受益于对凯梅尼常数的研究，因为该量将变得更加深入了解，因此将成为一个更有用的工具。对马尔可夫链中心性的研究，通过发展中心性的数学理论，将对网络科学及其众多应用产生影响。最后，量子行走的研究将在量子计算领域产生影响。

A Markov chain is a certain type of probabilistic model, and these models are ubiquitous in science and engineering, finding applications in such diverse areas as computational drug design, vehicle traffic networks, and ranking of web pages. The Kemeny constant is a key quantity associated with a Markov chain, and it provides, in some sense, a global measure of the overall short term efficiency of the Markov chain. Despite having been introduced more than 50 years ago, relatively little is known about the Kemeny constant, and the proposed research programme will undertake a thorough investigation of that quantity. By illuminating the mathematical properties of the Kemeny constant, I hope to provide insights into the design of Markov chains with desirable efficiency properties. A graph (or network) is a mathematical structure that records information about objects (called vertices) that are related in some way. Examples include Facebook users that are related by 'friendship', proteins in a cell that perform some function together, and terminals in an electrical network that are connected by resistors. There is a natural way to associate a Markov chain with any graph, and it turns out that certain parameters of the Markov chain can be used to measure how central each vertex is in the graph. This Markov chain centrality has been investigated empirically, but at present there is little in the way of rigorous theory on the topic. The proposed programme of research will develop the mathematical theory of this Markov chain centrality, thus enhancing the understanding of the graph-theoretic properties that are reflected by that centrality, and informing the use of that centrality in practical applications. The notion of a quantum walk arises in a so-called quantum wire -- a model for information transport inside a quantum computer. The fidelity of a quantum walk measures the probability that the information is transferred correctly along the quantum wire. This research programme will also investigate the sensitivity of the fidelity in terms of the time taken for the information to transfer, and the physical parameters associated with the quantum wire. The results will help to inform the design and implementation of quantum walks. This programme of research is expected to have impact in several different domains. Researchers working on Markov chains from the theoretical side, as well as scientists and engineers applying Markov chain techniques in practical settings (such as traffic modelling, migration models and network analysis) will benefit from the research on the Kemeny constant, as that quantity will become more deeply understood, and will hence be a more useful tool. The research on Markov chain centrality will, by developing the mathematical theory of that centrality, have an impact on network science and its numerous applications. Finally the research on quantum walks will have an impact in the area of quantum computing.