Upper bounding randomized k-SAT solver

Question

Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

---

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is $${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be $$P(\mathit{assignment~is~unsatisfiable}) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.

Answer 1

Hint: Use a union bound.

Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).