Abstract
We consider probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. This paper offers a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
Since a functional dependency \(\mathop {=\!} (\bar{x},\bar{y})\) (i.e. \(\bar{x}\) determines \(\bar{y}\)) and probabilistic independence \(\bar{x}{\perp \!\!\!\!\perp }\bar{y}\) can be expressed with probabilistic conditional independencies \({\bar{y} \perp \!\!\!\!\perp _{\bar{x}} \bar{y}}\) and \({\bar{x} \perp \!\!\!\!\perp _{\emptyset } \bar{y}}\), respectively, this problem and the one considered in this paper are both examples of implication problems for a fragment of probabilistic conditional independencies together with unary marginal identities and marginal distribution equivalences.
- 3.
Note that we do not make a distinction between axioms and inference rules; in this paper they are both called “axioms”.
- 4.
Note that clearly \(|\mathbb {X}_{w=0}|=1\) for all \(w\in \{u_1,\dots ,u_k\}\), and \(|\mathbb {X}_{w=a}|=1/2\) for all \(a\in \{0,1\}\) and \(w\in D\backslash \{x_1,u_1,\dots ,u_k\}\). An easy induction proof shows that \(|\mathbb {X}_{x_1=a}|=1/2\) for all \(a\in \{0,1\}\).
References
Armstrong, W.W.: Dependency structures of data base relationships. In: Proceedings of the IFIP World Computer Congress, pp. 580–583 (1974)
Beeri, C., Bernstein, P.A.: Computational problems related to the design of normal form relational schemas. ACM Trans. Database Syst. 4(1), 30–59 (1979). https://doi.org/10.1145/320064.320066, http://doi.acm.org/10.1145/320064.320066
Casanova, M.A., Fagin, R., Papadimitriou, C.H.: Inclusion dependencies and their interaction with functional dependencies. J. Comput. Syst. Sci. 28(1), 29–59 (1984)
Durand, A., Hannula, M., Kontinen, J., Meier, A., Virtema, J.: Approximation and dependence via multiteam semantics. Ann. Math. Artif. Intell. 83(3–4), 297–320 (2018). https://doi.org/10.1007/s10472-017-9568-4
Durand, A., Hannula, M., Kontinen, J., Meier, A., Virtema, J.: Probabilistic team semantics. In: Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Budapest, Hungary, 14–18 May 2018, Proceedings, pp. 186–206 (2018). https://doi.org/10.1007/978-3-319-90050-6_11
Galliani, P.: Game Values and Equilibria for Undetermined Sentences of Dependence Logic (2008). mSc Thesis. ILLC Publications, MoL-2008-08
Galliani, P.: Inclusion and exclusion dependencies in team semantics: on some logics of imperfect information. Ann. Pure Appl. Log. 163(1), 68–84 (2012)
Geiger, D., Paz, A., Pearl, J.: Axioms and algorithms for inferences involving probabilistic independence. Inf. Comput. 91(1), 128–141 (1991)
Grädel, E., Väänänen, J.: Dependence and independence. Stud. Log. 101(2), 399–410 (2013). https://doi.org/10.1007/s11225-013-9479-2, http://dx.doi.org/10.1007/s11225-013-9479-2
Hannula, M.: Conditional independence on semiring relations (2023). arXiv:2310.01910 [cs.DB]
Hannula, M., Hirvonen, Å., Kontinen, J., Kulikov, V., Virtema, J.: Facets of distribution identities in probabilistic team semantics. In: Calimeri, F., Leone, N., Manna, M. (eds.) JELIA 2019. LNCS (LNAI), vol. 11468, pp. 304–320. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19570-0_20
Hannula, M., Link, S.: On the interaction of functional and inclusion dependencies with independence atoms. In: Pei, J., Manolopoulos, Y., Sadiq, S., Li, J. (eds.) DASFAA 2018. LNCS, vol. 10828, pp. 353–369. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91458-9_21
Hannula, M., Virtema, J.: Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Ann. Pure Appl. Log. 173(10), 103108 (2022). https://doi.org/10.1016/j.apal.2022.103108, https://www.sciencedirect.com/science/article/pii/S0168007222000239, logics of Dependence and Independence
Hirvonen, M.: The implication problem for functional dependencies and variants of marginal distribution equivalences. In: Varzinczak, I. (eds.) Foundations of Information and Knowledge Systems. FoIKS 2022. LNCS, pp. 130–146. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-11321-5_8
Hodges, W.: Compositional semantics for a language of imperfect information. J. Interest Group Pure Appl. Log. 5(4), 539–563 (1997)
Hyttinen, T., Paolini, G., Väänänen, J.: A logic for arguing about probabilities in measure teams. Arch. Math. Log. 56(5–6), 475–489 (2017). https://doi.org/10.1007/s00153-017-0535-x
Li, C.T.: Undecidability of network coding, conditional information inequalities, and conditional independence implication. IEEE Trans. Inf. Theory 69(6), 3493–3510 (2023). https://doi.org/10.1109/TIT.2023.3247570
Väänänen, J.: Dependence Logic. Cambridge University Press, Cambridge (2007)
Acknowledgments
The author was supported by grant 345634 of the Academy of Finland. I would like to thank the anonymous referees for valuable comments, and Miika Hannula, Matilda Häggblom, and Juha Kontinen for useful discussions and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The author has no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hirvonen, M. (2024). Axiomatization of Implication for Probabilistic Independence and Unary Variants of Marginal Identity and Marginal Distribution Equivalence. In: Meier, A., Ortiz, M. (eds) Foundations of Information and Knowledge Systems. FoIKS 2024. Lecture Notes in Computer Science, vol 14589. Springer, Cham. https://doi.org/10.1007/978-3-031-56940-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-56940-1_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-56939-5
Online ISBN: 978-3-031-56940-1
eBook Packages: Computer ScienceComputer Science (R0)