  Consider the Hitting Set problem where, for a given universe $\mathcal{X} =
\left\{ 1, ... , n \right\}$ and a collection of subsets $\mathcal{S}_1, ... ,
\mathcal{S}_m$, one seeks to identify the smallest subset of $\mathcal{X}$
which has nonempty intersection with every element in the collection. We study
a probabilistic formulation of this problem, where the underlying subsets are
formed by including each element of the universe with probability $p$,
independently of one another. For large enough values of $n$, we rigorously
analyse the average case performance of Lov\'asz's celebrated greedy algorithm
(Lov\'asz, 1975) with respect to the chosen input distribution. In addition, we
study integrality gaps between linear programming and integer programming
solutions of the problem.
