Sparsity according to Prony, Average Performance Analysis