무작위 알고리즘의 속성 (Monte Carlo, Las Vegas)

Question

나는 지금 라스베가스와 몬테카를로 알고리즘을 배우고 있으며, 두 가지 질문은 간단하지만 누군가가 나를 도울 수 있다면 나는 대답 할 수 없다 ... 감사합니다. 미리

1. 몬테카를로는 그의 예상 실행 시간 대부분 T (N)에있을 확률 Y (n)를 가진 정확한 솔루션을 생산 크기 n의 임의의 인스턴스에 문제 P 용을 알고리즘을 고려한다. P에 대한 해가 주어진다고 가정하면, 시간 t (n)에서 그 정확성을 검증 할 수 있습니다. 항상 P에 정확한 답을주고 예상 시간 (T (n) + t (n))/y (n)에 달하는 라스베가스 알고리즘을 얻는 방법을 보여줍니다.

2. 는 < ε2 < ε1 < 1.0 상관없이 입력의 확률 적어도 1 ε1 문제에 대한 정확한 솔루션을 제공하는 몬테카를로 알고리즘을 생각 해보자. 이 알고리즘의 독립적 인 실행은 입력에 관계없이 1-ε2 이상의 정확한 솔루션을 얻을 확률을 높이기에 충분합니까?

Answer 1

1. 은 그냥 알고리즘을 실행하고 당신이 정확한 답을 얻을 때까지 결과를 테스트를 반복합니다. 각각의 런과 체크는 (T (n) + t (n)) 시간 단위를 취하고, 런의 수는 평균 1/y (n)을 갖는 기하학적 랜덤 변수이다.

2. 하나의 실행에 실패 할 확률은 얼마입니까? 2 회의 달리기? 실행됩니까? n 개의 런에 대해 실패 확률을 e2와 같게 설정하고 n을 구하십시오.