A linear-time algorithm for computing the multinomial stochastic complexity

DOI10.1016/J.IPL.2007.04.003MaRDI QIDQ2379977zbMATH OpenOpenAlexFDO

Authors Petri Kontkanen, Petri Myllymäki

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.04.003

zbMATH Keywords

algorithmscomputational complexitycombinatorial problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Probabilistic Theory of Linear Complexity
• Publication:5111147
• The Probabilistic Theory of the Joint Linear Complexity of Multisequences
• On stochastic complexity estimation: a decision-theoretic approach
• Probabilistic complexity analysis for linear problems in bounded domains
• On polynomial complexity of a stochastic algorithm for mixed zero-one programs.
• Publication:3336692
• Improved results on the probabilistic theory of the joint linear complexity of multisequences
• Publication:4440438
• A combinatorial approach to probabilistic results on the linear- complexity profile of random sequences

Cites work

• scientific article; zbMATH DE number 4068049 (Why is no real title available?)
• scientific article; zbMATH DE number 4095371 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 1504579 (Why is no real title available?)
• A Recurrence Related to Trees
• Asymptotic minimax regret for data compression, gambling, and prediction
• Estimating the dimension of a model
• Fisher information and stochastic complexity
• Modeling by shortest data description
• On the Lambert \(w\) function
• Special issue: Average-case analysis of algorithms
• Strong optimality of the normalized ML models as universal codes and information in data
• The minimum description length principle in coding and modeling

Cited in

(12)

• The Complexity of Strict Minimum Message Length Inference
• Using the Bayesian Shtarkov solution for predictions
• Hierarchical two-part MDL code for multinomial distributions
• On model selection, Bayesian networks, and the Fisher information integral
• Graph Summarization with Latent Variable Probabilistic Models
• scientific article; zbMATH DE number 7204268 (Why is no real title available?)
• scientific article; zbMATH DE number 3977180 (Why is no real title available?)
• Minimum description length revisited
• Fast and fully-automated histograms for large-scale data sets
• Clustgrams: an extension to histogram densities based on the minimum description length principle
• Unsupervised discretization by two-dimensional MDL-based histogram
• The decomposed normalized maximum likelihood code-length criterion for selecting hierarchical latent variable models

This page was built for publication: A linear-time algorithm for computing the multinomial stochastic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379977)