On the expected probability of constraint violation in sampled convex programs

In this note, we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see Calafiore and Campi (2005) and (2006) for definitions and an introduction to this topic). This result is obtained using a simple technique based on cardinality count. In the note, we also use a Chernoff bounding technique on the upper tail violation probability expression derived in Campi and Garatti (2008) to obtain one of the tightest available explicit bounds on the sample complexity of sampled convex programs.