AF: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Economics

AF：计算机科学、统计物理和经济学问题的马尔可夫链算法

• 批准号: 1219020
• 负责人: Dana Randall
• 金额: $ 27.91万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219020&HistoricalAwards=false
• 关键词: AF; Markov; Chain; Algorithms; Problems

The PI's research explores fundamental relationships between physical systems and the efficiency of algorithms, looking at applications in Economics, Nanotechnology, Computing and Physics that can benefit from this joint lens. For instance, the Schelling model of segregation was developed in the economics community in 1971. In this model, residents within a community assess their personal comfort with the racial distribution in their local neighborhood and they are more inclined to move if they are dissatisfied. Schelling showed that even if every member of the community is satisfied with having half of their neighbors be of the opposite race, even small preference for one's own race leads to global segregation. Thus, micromotives can bring about macrobehavior without any centralized influence. The PI will explore variants of this model for 2-dimensional models using insights from computing and physics.The PI will also consider natural stochastic processes occurring in the context of self-organizing lists and nanotechnology. The first is a fundamental question about biased permutations arising from list update algorithms for minimizing total search costs. The problem can be modeled as a question about permutations under nearest-neighbor transpositions in which items are biased to be put in the correct order. The second is a nanotechnology problem concerning growth processes arising in the context of tile-based self-assembly, where tiles are constructed from DNA. The rates of convergence of these two sampling algorithms are closely related, and the PI has developed new approaches to try to better understand their convergence properties.Last, the award addresses fundamental questions at the interface of computing and physics. Determining the mixing time of Markov chains is often the vital step in proving the efficiency of many approximation algorithms based on random sampling. One of the richest sources for sampling problems is statistical physics, where the state space of the Markov chain represents the states of a physical system and sampling lends insight into the thermodynamic properties of the model. By exploring parallels between phase transitions in both fields, the PI will address fundamental questions about physical systems while searching for better approaches to sampling.

PI的研究探索了物理系统和算法效率之间的基本关系，研究了可以从这种联合透镜中受益的经济学，纳米技术，计算和物理学应用。例如，1971年经济学界提出了谢林隔离模型。在这个模型中，社区内的居民评估他们对当地社区种族分布的个人舒适度，如果他们不满意，他们更倾向于搬家。谢林表明，即使社区的每个成员都对有一半的邻居是相反的种族感到满意，即使对自己种族的微小偏好也会导致全球隔离。因此，微观动机可以在没有任何集中影响的情况下带来宏观行为。PI将利用计算和物理学的见解探索该模型的二维模型变体。PI还将考虑自组织列表和纳米技术背景下发生的自然随机过程。第一个是一个基本的问题所产生的列表更新算法，以最大限度地减少总搜索成本的偏见置换。这个问题可以被建模为一个关于最近邻置换下的排列的问题，其中项目被偏向于以正确的顺序放置。第二个是纳米技术的问题，涉及的增长过程中产生的上下文中的瓷砖为基础的自组装，瓷砖是从DNA构建。这两种采样算法的收敛速度密切相关，PI开发了新的方法来更好地理解它们的收敛特性。最后，该奖项解决了计算和物理界面上的基本问题。 确定马尔可夫链的混合时间通常是证明许多基于随机抽样的近似算法有效性的关键步骤。采样问题最丰富的来源之一是统计物理学，其中马尔可夫链的状态空间表示物理系统的状态，采样有助于深入了解模型的热力学性质。通过探索这两个领域中相变之间的相似之处，PI将解决有关物理系统的基本问题，同时寻找更好的采样方法。