Probabilistic causes in Markov chains

DOI10.1007/978-3-030-88885-5_14zbMATH Open1497.68356arXiv2104.13604OpenAlexW3211017378MaRDI QIDQ2147196FDOQ2147196

Simon Jantsch, Jakob Piribauer, Robin Ziemek, Christel Baier, Florian Funke

Publication date: 22 June 2022

Abstract: The paper studies a probabilistic notion of causes in Markov chains that relies on the counterfactuality principle and the probability-raising property. This notion is motivated by the use of causes for monitoring purposes where the aim is to detect faulty or undesired behaviours before they actually occur. A cause is a set of finite executions of the system after which the probability of the effect exceeds a given threshold. We introduce multiple types of costs that capture the consumption of resources from different perspectives, and study the complexity of computing cost-minimal causes.

Full work available at URL: https://arxiv.org/abs/2104.13604

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Logic in computer science (03B70)

Cites Work

• CP-logic: A language of causal probabilistic events and its relation to logic programming
• Title not available (Why is that?)
• Probabilistic Causality
• Title not available (Why is that?)
• Computational Complexity of Probabilistic Turing Machines
• An Analysis of Stochastic Shortest Path Problems
• PP is as Hard as the Polynomial-Time Hierarchy
• Embracing Events in Causal Modelling: Interventions and Counterfactuals in CP-Logic
• A Proposed Probabilistic Extension of the Halpern and Pearl Definition of ‘Actual Cause’
• Explaining Counterexamples Using Causality
• Title not available (Why is that?)
• The complexity of the \(K\)th largest subset problem and related problems
• Title not available (Why is that?)
• Explanation in artificial intelligence: insights from the social sciences
• Causes and explanations in the structural-model approach: Tractable cases
• Complexity results for explanations in the structural-model approach
• Monitoring Temporal Properties of Stochastic Systems
• What causes a system to satisfy a specification?
• On the expressiveness and complexity of randomization in finite state monitors
• Spanning the spectrum from safety to liveness
• An LTL Proof System for Runtime Verification
• Faster statistical model checking for unbounded temporal properties
• Partial and conditional expectations in Markov decision processes with integer weights
• The Odds of Staying on Budget
• Monitoring the Full Range of ω-Regular Properties of Stochastic Systems
• The Cost of Exactness in Quantitative Reachability

Cited In (5)

• On probability-raising causality in Markov decision processes
• Probabilistic causation in branching time
• Operational causality -- necessarily sufficient and sufficiently necessary
• Temporal causality in reactive systems
• Probabilistic Causality

Uses Software

• CP-logic

   Recommendations

• Continuous-time, constant causative Markov chains 👍 👎
• Probabilistic Causality 👍 👎
• Markov properties of nonrecursive causal models 👍 👎
• Probabilistic causation in branching time 👍 👎
• Advances in Artificial Intelligence 👍 👎
• Markov Chains 👍 👎

This page was built for publication: Probabilistic causes in Markov chains

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