- 注册
- 2005-09-21
- 消息
- 8,913
- 荣誉分数
- 460
- 声望点数
- 0
Question 2: Let A be a Monte Carlo algorithm that, for any given input, outputs either
YES or NO. (For example, YES could indicate that the input is a prime number, whereas
NO could indicate that the input is not a prime number.) You are told that with probability
2/3, the output is correct.
For a large odd integer k, consider the following algorithm B:
• Run algorithm A k times.
• Return the most frequent output obtained in these k runs.
Use the Chernoff bound to show that the output of algorithm B is correct with probability
at least
1 − e−k/48.
YES or NO. (For example, YES could indicate that the input is a prime number, whereas
NO could indicate that the input is not a prime number.) You are told that with probability
2/3, the output is correct.
For a large odd integer k, consider the following algorithm B:
• Run algorithm A k times.
• Return the most frequent output obtained in these k runs.
Use the Chernoff bound to show that the output of algorithm B is correct with probability
at least
1 − e−k/48.
又遇到知音了^^
