| Few Samples Needed |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Suppose k clauses |
|||||||||||
| l | Then E[sample] > 1/k |
|||||||||||
| » | 1 £ satisfied clauses £ k |
|||||||||||
| » | 1 ³ sample value ³ 1/k |
|||||||||||
| l | Adding
O(k
log n / e2) samples gives |
|||||||||||
| “large” mean |
||||||||||||
| l | So Chernoff says
sample mean is |
|||||||||||
| probably good
estimate |
||||||||||||