  The margin of victory of an election is a useful measure to capture the
robustness of an election outcome. It also plays a crucial role in determining
the sample size of various algorithms in post election audit, polling etc. In
this work, we present efficient sampling based algorithms for estimating the
margin of victory of elections.
  More formally, we introduce the \textsc{$(c, \epsilon, \delta)$--Margin of
Victory} problem, where given an election $\mathcal{E}$ on $n$ voters, the goal
is to estimate the margin of victory $M(\mathcal{E})$ of $\mathcal{E}$ within
an additive factor of $c MoV(\mathcal{E})+\epsilon n$. We study the
\textsc{$(c, \epsilon, \delta)$--Margin of Victory} problem for many commonly
used voting rules including scoring rules, approval, Bucklin, maximin, and
Copeland$^{\alpha}.$ We observe that even for the voting rules for which
computing the margin of victory is NP-Hard, there may exist efficient sampling
based algorithms, as observed in the cases of maximin and Copeland$^{\alpha}$
voting rules.
