  We investigate the problem of computing the probability of winning in an
election where voter attendance is uncertain. More precisely, we study the
setting where, in addition to a total ordering of the candidates, each voter is
associated with a probability of attending the poll, and the attendances of
different voters are probabilistically independent. We show that the
probability of winning can be computed in polynomial time for the plurality and
veto rules. However, it is computationally hard (#P-hard) for various other
rules, including $k$-approval and $k$-veto for $k>1$, Borda, Condorcet, and
Maximin. For some of these rules, it is even hard to find a multiplicative
approximation since it is already hard to determine whether this probability is
nonzero. In contrast, we devise a fully polynomial-time randomized
approximation scheme (FPRAS) for the complement probability, namely the
probability of losing, for every positional scoring rule (with polynomial
scores), as well as for the Condorcet rule.
