This paper introduces a theoretical framework for the development of randomized algorithms for quadratic stability of uncertain systems affected by structured and unstructured uncertainty. We propose a general duality setting which deals with a probabilistic version of the classical primal-dual problems. In particular, the probabilistic primal problem is defined so that a Linear Matrix Inequality has a solution with probability one and the probabilistic dual problem is formulated as a solvability problem for a certain matrix integral inequality on the class of positive semidefinite symmetric matrix-valued functions. The main result of the paper establishes a rigorous equivalence between infeasibility of the primal problem and existence of a solution of the dual problem. In the second part of the paper, we study various applications of this result in the context of uncertain systems.