马尔科夫链蒙特卡洛采样从微规范双部分图集的不可能结果
Giulia Preti1, Gianmarco De Francisci Morales1, Matteo Riondato2
1CENTAI, Corso Inghilterra 3, 10138 Turin, Italy.
Physical review. E
|June 22, 2024
概括
马尔科夫链蒙特卡洛 (MCMC) 算法在采样双部分图表方面面临一些局限性. 一个通用的重新连接策略是不可能的,阻碍了对这些图集的高效MCMC算法开发.
科学领域:
- 图形理论 图形理论
- 计算数学 计算数学 计算数学
- 统计物理 统计物理
背景情况:
- 马尔科夫链蒙特卡洛 (MCMC) 算法是采样图集的标准.
- 边缘重新连接是定义图形状态空间中的邻居的常见操作.
- 对于许多集合,比如具有固定度序列的双部分图,双边重新连接可以确保状态空间连接.
研究的目的:
- 调查MCMC算法的局限性,用于采样特定的双部分图集.
- 确定是否存在一个通用常数"c"用于重新布线操作,以确保状态空间连接.
主要方法:
- 构建了一个具有相同度序和蝶计数的二分位图对家族.
- 每一对被自然数"c"所索引.
- 证明将一个图形转换为其对需要至少一次涉及"c"边缘的重新连接操作.
主要成果:
- 证明对于重新布线操作来说,没有普遍的常数"c",以保证这些合集的完整状态空间连接.
- 表明可能需要任意大规模的重新布线操作.
- 这么大规模的重新布线操作是否足以实现连接仍然是一个悬而未决的问题.
结论:
- 有效的,无图形的MCMC算法对于具有固定度序列和蝶计数的双部分图集是不可行的.
- 大规模重新布线操作的必要性可能会阻碍MCMC采样效率.
- 这凸显了将MCMC应用于复杂图形结构的根本挑战.
相关概念视频
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.1K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.1K
Probability in Statistics
12.6K
Probability is the likelihood of an event occurring. The term event is defined as a collection of results of a procedure. An event is a simple event when an outcome cannot be divided into simpler parts.
An example of a simple event is a coin toss. The result of a coin toss is either a head or a tail. Here, head and tail are two simple events. These two simple events make up the sample space. Further, the probability of an event occurring falls within the range of 0 to 1. The probability of an...
An example of a simple event is a coin toss. The result of a coin toss is either a head or a tail. Here, head and tail are two simple events. These two simple events make up the sample space. Further, the probability of an event occurring falls within the range of 0 to 1. The probability of an...
12.6K
Alternative Sets of Equilibrium Equations
387
When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
One example of such a situation can be observed in a...
387
Binomial Probability Distribution
10.4K
A binomial distribution is a probability distribution for a procedure with a fixed number of trials, where each trial can have only two outcomes.
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
10.4K
Sampling Theorem
324
In signal processing, the analysis of continuous-time signals, denoted as x(t), often involves sampling techniques to convert these signals into discrete-time signals. This process is essential for digital representation and manipulation. A critical component in sampling is the train of impulses, characterized by the sampling interval and the sampling frequency. The relationship between these parameters and the original signal's properties dictates the success of the sampling process.
324
Probability Distributions
6.9K
The probability of a random variable x is the likelihood of its occurrence. A probability distribution represents the probabilities of a random variable using a formula, graph, or table. There are two types of probability distribution– discrete probability distribution and continuous probability distribution.
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson...
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson...
6.9K


