2020/11/22 by Cyrus Cousins, Cousins, Cyrus, Shahrzad Haddadan +3
Biochemistry, Genetics and Molecular Biology · Chemistry · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Mass Spectrometry Techniques and Applications #Protein Structure and Dynamics
paper · pdf · doi:10.48550/arxiv.2011.11129
openalex publication_date 2020/11/22 · openalex created_date 2020/12/07 · openalex updated_date 2026/07/31
We introduce a novel statistical measure for MCMC-mean estimation, the inter-trace variance \rm trv^(τrel)(\cal M,f), which depends on a Markov chain \cal M and a function f:S→ [a,b]. The inter-trace variance can be efficiently estimated from observed data and leads to a more efficient MCMC-mean estimator. Prior MCMC mean-estimators receive, as input, upper-bounds on τmix or τrel, and often also the stationary variance, and their performance is highly dependent to the sharpness of these bounds. In contrast, we introduce DynaMITE, which dynamically adjusts the sample size, it is less sensitive to the looseness of input upper-bounds on τrel, and requires no bound on vπ. Receiving only an upper-bound \cal Trel on τrel, DynaMITE estimates the mean of f in \calO(\smash\frac\cal Trel Rε+\fracτrel⋅ \rm trv^(τrel)ε2) steps, without a priori bounds on the stationary variance vπ or the inter-trace variance \rm trv(τrel). Thus we depend minimally on the tightness of \cal Tmix, as the complexity is dominated by τrel\rmtrv^(τrel) as ε → 0. Note that bounding τ\rm rel is known to be prohibitively difficult, however, DynaMITE is able to reduce its principal dependence on \cal Trel to τrel, simply by exploiting properties of the inter-trace variance. To compare our method to known variance-aware bounds, we show \rm trv^(τrel)(\cal M,f) ≤ vπ. Furthermore, we show when f's image is distributed (semi)symmetrically on \cal M's traces, we have \rm trv^(τrel)(\cal M,f)=o(vπ(f)), thus DynaMITE outperforms prior methods in these cases.