조건부 확률법

수학과 컴퓨터 과학에서 확률론적 방법은 원하는 조합 특성을 가진 수학 물체의 존재를 증명하는 데 사용된다.그 증거는 확률론적이다 - 그것들은 어떤 확률 분포에서 선택한 임의의 물체가 양의 확률로 원하는 속성을 가지고 있다는 것을 보여주면서 작용한다.결과적으로, 그것들은 비건설적이다 - 그들은 원하는 물체를 계산하는 효율적인 방법을 명시적으로 설명하지 않는다.

조건부 확률의 방법(Spensor 1987), (Raghavan 1988)은 그러한 증거를 "매우 정밀한 의미"로, 원하는 특성을 가진 물체를 계산하도록 보장된 효율적인 결정론적 알고리즘으로 변환한다.즉, 그 방법은 증거를 희석시킨다.기본적인 생각은 무작위 실험에서 각 무작위 선택을 결정론적 선택으로 대체하여 지금까지의 선택사항으로 볼 때, 실패의 조건부 확률을 1 이하로 유지하는 것이다.

이 방법은 특히 무작위 반올림의 맥락에서 관련된다(확률론적 방법을 사용하여 근사 알고리즘을 설계한다).

조건부 확률의 방법을 적용할 때 기술 용어 비관적 추정기는 입증의 기초가 되는 실제 조건부 확률(또는 조건부 기대) 대신에 사용되는 양을 말한다.

개요

(Ragavan 1988)은 다음과 같은 설명을 제공한다.

우리는 먼저 확률론적 방법을 사용하여 입증 가능한 좋은 근사 해결책의 존재를 보여준다.[우리는 그때] 확률론적 존재 증거가 매우 정확한 의미에서 결정론적 근사 알고리즘으로 변환될 수 있음을 보여준다.

(Ragavan은 무작위 반올림이라는 맥락에서 방법을 논의하고 있지만, 일반적으로 확률론적 방법으로 작동한다.)

확률론적 입증에 이 방법을 적용하려면, 증명에서 무작위로 선택한 물체는 "작은" 무작위 선택 순서에 따라 구성된 무작위 실험으로 선택할 수 있어야 한다.

여기 그 원리를 설명하기 위한 사소한 예가 있다.

보조정리: 꼬리가 최소 2개 이상 되도록 동전 세 개를 뒤집는 것이 가능하다.

확률론적 증거.3개의 동전을 무작위로 뒤집으면 예상 꼬리는 1.5개가 된다.따라서 꼬리의 수가 적어도 1.5가 되도록 어떤 결과(동전을 돌리는 방법)가 있어야 한다.꼬리의 수는 정수기 때문에, 그러한 결과에는 적어도 2개의 꼬리가 있다.QED

이 예에서 무작위 실험은 세 개의 페어 코인을 뒤집는 것으로 구성된다.실험은 인접한 다이어그램에 뿌리가 있는 나무로 묘사되어 있다.각각 나무의 잎에 해당하는 여덟 가지 결과가 있다.무작위 실험의 시도는 뿌리(동전이 뒤집히지 않은 나무의 맨 위 노드)에서 나뭇잎으로 무작위 산책을 하는 것에 해당한다.성공적인 결과는 적어도 두 개의 동전이 꼬리를 물고 나온 것이다.나무의 내부 노드는 부분적으로 결정된 결과에 해당하며, 여기서 지금까지 동전의 0, 1, 2개만 뒤집혔다.

조건부 확률의 방법을 적용하기 위해서는 실험이 단계별로 진행되는 동안 선택 사항들을 고려하여 실패의 조건부 확률에 초점을 맞춘다.도표에서 각 노드에는 이 조건부 확률이 붙어 있다.(예를 들어 첫 번째 코인만 뒤집어서 꼬리가 올라오면, 그것은 뿌리의 둘째 아이에 해당한다.이 부분적인 상태에서 조건화하면, 고장 확률은 0.25이다.

조건부 확률의 방법은 무작위 실험에서 무작위 뿌리-잎 워크를 결정론적 뿌리-잎 워크로 대체하며, 여기서 각 스텝은 다음과 같은 불변성을 유도적으로 유지하도록 선택된다.

현재 상태를 감안할 때 조건부 고장 확률은 1보다 작다.

이렇게 하면 라벨 0, 즉 성공적인 결과를 얻을 수 있는 잎사귀가 보장된다.

원래 증거가 (조건 없는) 실패 확률이 1보다 작다는 것을 보여주었기 때문에 불변성은 처음에 (근본적으로) 유지한다.내부 노드의 조건부 확률은 하위 노드의 조건부 확률의 평균이다.후자의 속성은 조건부 확률이 1 미만인 내부 노드는 조건부 확률이 1 미만인 자녀가 적어도 한 명 이상 있음을 의미하기 때문에 중요하다.따라서 어떤 내부 노드에서든 불변성을 유지하기 위해 항상 걸어갈 아이를 선택할 수 있다.불변자가 마지막에 버티고 있기 때문에, 산책로가 잎에 도착하고 모든 선택이 결정되었을 때, 이런 식으로 도달한 결과는 반드시 성공적이어야 한다.

효율성

방법의 일반적인 적용에서, 일반적으로 가능한 결과의 수가 크더라도, 그 결과는 합리적으로 효율적인 알고리즘(일반적으로 "효율적"이라는 단어는 다항식 시간에 실행되는 알고리즘을 의미한다)에 의해 결과 결정론적 프로세스를 구현할 수 있는 것이 목표다.예를 들어, 동전 던지기 작업을 고려하되, 큰 n의 경우 동전 던지기까지 확장한다.

이상적인 경우, 부분 상태(트리의 노드)가 주어진 경우, 조건부 고장 확률(노드의 라벨)은 효율적이고 정확하게 계산될 수 있다.(위의 예는 다음과 같다.)만약 그렇다면, 알고리즘은 현재 노드의 각 자식에서 조건부 확률을 계산하고 조건부 확률이 1 미만인 아이로 이동하여 다음 노드를 선택할 수 있다.위에서 논의한 바와 같이, 그러한 노드가 있을 것이 보장된다.

불행히도, 대부분의 애플리케이션에서, 조건부 실패 확률은 효율적으로 계산하기가 쉽지 않다.이에 대처하기 위한 두 가지 표준 및 관련 기법이 있다.

• 조건부 기대 사용:많은 확률론적 증거는 다음과 같이 작용한다: 무작위 변수 Q를 암묵적으로 정의하고, (i) Q에 대한 기대가 최대(또는 최소한) 임계값이고, (ii) Q가 최대(적어도) 이 임계값인 어떤 결과에서든 결과는 성공이다.그렇다면 (i) Q가 최대 임계값에 있는 결과가 존재한다는 것을 의미하며, 이것과 (ii)는 성공적인 결과가 있음을 의미한다.(위의 예에서 Q는 꼬리의 수로서 적어도 임계값 1.5가 되어야 한다.많은 애플리케이션에서 Q는 주어진 결과에서 발생하는 "나쁜" 사건(필수적으로 분리되는 것은 아님)의 수입니다. 여기서 각각의 나쁜 사건은 실험이 실패할 수 있는 한 가지 방법에 해당하며, 예상되는 나쁜 사건의 수는 1개 미만이다.)

이 경우, 실패의 조건부 확률을 1 이하로 유지하기 위해서는 Q의 조건부 기대치를 임계값(또는 그 이상) 이하로 유지하는 것으로 충분하다.이를 위해 알고리즘은 장애의 조건부 확률을 계산하는 대신 Q의 조건부 기대치를 계산하여 그에 따라 진행한다. 각 내부 노드에서 조건부 기대치가 최대 (적어도) 노드의 조건부 기대인 일부 어린이가 있다. 알고리즘은 현재 노드에서 그러한 어린이, thu로 이동한다.s 조건부 기대치를 임계값보다 낮게 유지한다.

• 비관적 추정기 사용:Q의 정확한 조건부 기대치에 대한 대용으로서, 비관적 추정기라고 하는 적절히 타이트한 바운드를 사용하는 경우도 있다.비관적 추정기는 현 상태의 함수다.현재 상태가 주어진 Q의 조건부 기대치에 대한 상한(또는 하한)이어야 하며, 실험의 각 무작위 단계에서 기대치가 상승(또는 하락)되지 않아야 한다.전형적으로, 좋은 비관적 추정기는 원본 증명 논리를 정밀하게 해체하여 계산할 수 있다.

조건부 기대치 사용 예제

이 예는 조건부 기대치를 사용한 조건부 확률의 방법을 보여준다.

맥스 컷 보조정리

모든 비방향 그래프 G = (V, E)의 경우, 최대 절단 문제는 그래프의 각 꼭지점에 검은색 또는 흰색 중 하나로 색칠하여 끝점의 색상이 다른 가장자리 수를 최대화하는 것이다.(그런 엣지가 잘려나간다고 말해라.

최대 절단 보조정리:그래프 G = (V, E)에서 적어도 E /2 에지는 절단할 수 있다.

확률론적 증거.페어 코인을 뒤집어서 각각의 꼭지점에 검정색이나 흰색을 칠하라.계산에 의해, E의 어떤 에지 e에 대해서, 그것이 절단될 확률은 1/2이다.따라서 기대의 선형성에 의해 예상되는 가장자리 절단 수는 E /2이다.따라서 적어도 E /2 가장자리를 자르는 색상이 존재한다.QED

조건부 기대치가 있는 조건부 확률의 방법

조건부 확률의 방법을 적용하려면 먼저 랜덤 실험을 작은 랜덤 단계의 순서로 모형화하십시오.이 경우 각 단계를 특정 정점에 대한 색상 선택으로 간주하는 것이 자연스럽다(그러므로 V 단계가 있다).

다음으로, 각 단계에서 무작위 선택을 결정론적 선택으로 대체하여 지금까지 색칠된 정점들을 고려하여 조건부 고장 확률을 1 이하로 유지한다(여기서 실패는 최종적으로 E/2 에지보다 적게 절단됨을 의미한다).

이 경우 조건부 고장 확률은 계산하기가 쉽지 않다.실제로, 원래의 증명은 직접 고장 확률을 계산하지 않았다. 대신, 예상되는 절단 가장자리 수가 적어도 E /2라는 것을 보여줌으로써 증명이 효과가 있었다.

랜덤 변수 Q를 절단된 가장자리 수로 유지하십시오.실패의 조건부 확률을 1 이하로 유지하기 위해서는 Q의 조건부 기대치를 임계값 E /2 이상으로 유지하는 것으로 충분하다(Q의 조건부 기대치가 적어도 E /2인 이상 Q가 적어도 E /2인 경우에는 여전히 도달할 수 있는 어떤 결과가 있어야 하기 때문에 그러한 아웃코에 도달할 수 있는 조건부 확률은 충분하기 때문이다).나는 긍정적이다.)Q의 조건부 기대를 E /2 이상으로 유지하기 위해 알고리즘은 각 단계에서 Q의 결과적 조건부 기대치를 최대화하기 위해 고려 중인 정점을 색칠한다.이는 조건부 기대가 최소한 현재 상태의 조건부 기대(따라서 적어도 E /2)인 어떤 아이가 있어야 하기 때문에 충분하다.

정점 중 일부는 이미 색이 칠해져 있는 것을 감안하면, 이 조건부 기대는 무엇인가?원본 증명 논리대로라면 절단된 가장자리 수에 대한 조건부 기대치는 다음과 같다.

지금까지 끝점의 색상이 다른 가장자리 수

+ (1/2)*(아직 색상이 지정되지 않은 끝점이 하나 이상 있는 가장자리 수).

알고리즘.

알고리즘은 위의 조건부 기대치의 결과값을 최대화하기 위해 각 꼭지점에 색상을 입힌다.이는 조건부 기대치를 E /2 이상으로 유지할 것을 보장하며, 따라서 실패의 조건부 확률을 1 이하로 유지할 것을 보장하며, 이는 결국 성공적인 결과를 보장한다.계산에 의해 알고리즘은 다음과 같이 단순화된다.

1. V의 각 꼭지점 u에 대해(순서에 상관없이): 2.이미 색이 있는 u. 3. 이 정점들 중에서 더 많은 것이 흰색보다 검은색이면 u. u. 4.그렇지 않으면 검은색으로 칠하십시오. 

이 결정론적 알고리즘은 파생되기 때문에 주어진 그래프의 가장자리 절반 이상을 잘라낼 수 있다. (이것은 맥스컷에 대한 0.5 근사 알고리즘이 된다.)

비관적 추정기 사용 예제

다음 예는 비관적 추정기의 사용을 보여준다.

투란의 정리

투란의 정리를 진술하는 한 가지 방법은 다음과 같다.

모든 그래프 G = (V, E)는 최소 V /(D+1) 크기의 독립된 집합을 포함하며, 여기서 D = 2 E / V는 그래프의 평균 수준이다.

투란의 정리 확률론적 증거

독립 집합 S를 구성하기 위해 다음과 같은 랜덤 프로세스를 고려하십시오.

1. 빈 세트가 되도록 S를 초기화한다.V의 각 꼭지점 u에 대해 랜덤 순서로: 3만약 당신이 S에 이웃이 없다면, S4에 당신을 추가하라. S로 돌아가라.

분명히 그 과정은 독립적인 집합을 계산한다.모든 이웃보다 먼저 고려되는 정점 u는 S에 추가될 것이다.따라서 d(u)가 u의 정도를 나타내도록 하면, u가 S에 추가될 확률은 적어도 1/(d(u)+1이다.기대 선형성에 의해 S의 예상 크기는 최소한

${\displaystyle \sum _{u\in V}{\frac {1}{d(u)+1}1}~\geq~{\frac {V }{D+1}.}$

(위의 불평등은 1/(x+1)가 x로 볼록하기 때문에 따라서 왼쪽이 최소화되며, 각 d(u) = D = 2 E / V일 때 2 E로 고정되는 정도의 합이 된다.) QED

비관적 추정기를 이용한 조건부 확률의 방법

이 경우 무작위 프로세스에는 V 단계가 있다.각 단계는 정점 u로 간주되지 않는 일부 사항을 고려하며, 아직 S에 이웃이 추가되지 않은 경우 u를 추가한다.랜덤 변수 Q를 S에 추가된 정점의 개수로 한다.그 증거는 E[Q] ≥ V /(D+1)라는 것을 보여준다.

Q의 조건부 기대치를 V /(D+1) 이상으로 유지하는 결정론적 단계로 각 무작위 단계를 대체한다.이렇게 하면 성공적인 결과, 즉 독립 집합 S가 적어도 V/(D+1)를 가지고 투란의 정리에서의 바운드를 실현하는 성공적인 결과를 보장할 것이다.

첫 번째 t 단계가 취해진 것을 감안하여 S는^(t) 지금까지 추가된 정점을 나타내도록 한다.R은^(t) 아직 고려되지 않은 정점을 나타내며, S에^(t) 이웃이 없는 정점을 가리킨다. 첫 번째 t단계를 감안할 때, 원본 증명에서의 추론에 따라 R에^(t) 주어진 정점 w는 S에 추가될 수 있는 최소 1/(d(w)+1)의 조건부 확률을 가지고 있으므로 Q의 조건부 기대치는 최소한 1/(d)(w)이다.

${\displaystyle S^{(t)} ~+~\sum _{w\in R^{(t)}}{\frac {1}{d(w)+1}}}$

Q는^(t) 위의 수량을 나타내며, 이를 조건부 기대치에 대한 비관적 추정기라고 한다.

그 증거는 비관적 추정기가 적어도 초기에는 V /(D+1)라는 것을 보여주었다. (즉⁽⁰⁾, Q v V / (D+1)알고리즘은 비관적 추정기가 감소하지 않도록 하기 위해, 즉 각 t에 대해^(t+1) Q ≥ Q를^(t) 선택한다.비관적 추정기는 조건부 기대치에 대한 하한값이기 때문에 조건부 기대치가 V/(D+1) 이상에 머물도록 보장할 것이고, 이는 다시 실패의 조건부 확률을 1 이하로 유지하도록 보장할 것이다.

다음 (t+1)-st 단계에서 알고리즘이 고려하는 꼭지점이 되게 한다.

만약 당신이 이미 S에 이웃을 가지고 있다면, 당신은 S에 추가되지 않고 (Q의^(t) 검사에 의해) 비관적 추정기는 변하지 않는다.만약 당신이 S에 이웃이 없다면, 당신은 S에 추가된다.

계산에 의해, 나머지 정점으로부터 임의로 u를 선택하는 경우, 비관적 추정기의 예상 증가치는 음이 아니다.[계산.R에서^(t) 꼭지점을 선택하는 조건으로, 비관적 추정기의 합에서 주어진 용어 1/(d(w)+1)이 삭제될 확률은 최대 (d(w)+1)/ R이다^(t). 따라서 합계의 각 항의 예상 감소량은 최대 1/R이다^(t). 합계에 R 항이^(t) 있다.따라서 예상되는 총액 감소량은 최대 1이다.한편, S의 크기는 1.]씩 증가한다.

따라서 비관적 추정자가 줄어드는 것을 막는 u의 어떤 선택이 존재해야 한다.

비관적 추정기 최대화 알고리즘

아래의 알고리즘은 결과적 비관적 추정기를 최대화하기 위해 각 꼭지점 u를 선택한다.이전의 고려사항들에 따르면, 이것은 비관적인 추정치가 감소하는 것을 막아주고 성공적인 결과를 보장한다.

아래의^(t) N(u)는 R에서^(t) u의 이웃(S에도 없고 S에도 이웃이 없는 u의 이웃)을 가리킨다.

1. 빈 세트가 되도록 S를 초기화한다.While there exists a not-yet-considered vertex u with no neighbor in S: 3.     Add such a vertex u to S where u minimizes ${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}}$. 4. Return S.

비관적 추정기를 최대화하지 않는 알고리즘

조건부 확률 방법이 작동하려면 알고리즘이 비관적 추정기의 감소(또는 증가, 적절하다면 증가)를 막는다면 충분하다.알고리즘이 반드시 비관적 추정기를 최대화(또는 최소화)할 필요는 없다.이것은 알고리즘을 도출하는데 약간의 유연성을 준다.다음 두 알고리즘은 이를 예시한다.

1. 빈 세트가 되도록 S를 초기화한다.S: 3. 그래프에 이웃이 없는 정점 u가 있는 동안. 그런 정점 u를 S에 더하면 d(u)(초기 u)를 최소화할 수 있다. 4. Return S.

1. 빈 세트가 되도록 S를 초기화한다.나머지 그래프는 비어 있지 않지만: 3.S에 정점 u를 추가하라. 여기서 u는 나머지 그래프에서 최소의 학위를 가지고 있다. 4. u와 그 주변의 모든 것을 그래프에서 삭제하라. 5. 반환 S.

각 알고리즘은 전과 동일한 비관적 추정기로 분석한다.두 알고리즘의 각 단계에서 비관적 추정기의 순증가는 다음과 같다.

${\displaystyle 1-\sum _{w\in N^{(t)}\cup \{u\}}}}{{1}{d(w)+1},}$

여기서 N^(t)(u)은 나머지 그래프(R^(t))에서 u의 이웃을 나타낸다.

첫 번째 알고리즘의 경우, 순증가는 음수가 아니다. 왜냐하면, u의 선택에 의해,

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u)+1){\frac {1}{d(u)+1}}=1}$,

여기서 d(u)는 원래 그래프에서 u의 정도를 말한다.

두 번째 알고리즘의 경우, 순증가는 음이 아니다. 왜냐하면, u의 선택에 의해,

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u)+1){\frac {1}{d'(u)+1}}=1}$,

여기서 d′(u)는 나머지 그래프에서 u의 정도를 나타낸다.

참고 항목

• 확률론적 방법
• 디랜도믹스
• 랜덤화 반올림

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2012년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

참조

• Spencer, Joel H. (1987), Ten lectures on the probabilistic method, SIAM, ISBN 978-0-89871-325-1

• Raghavan, Prabhakar (1988), "Probabilistic construction of deterministic algorithms: approximating packing integer programs", Journal of Computer and System Sciences, 37 (2): 130–143, doi:10.1016/0022-0000(88)90003-7.

추가 읽기

• Alon, Noga; Spencer, Joel (2008). The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization (Third ed.). Hoboken, NJ: John Wiley and Sons. pp. 250 et seq. ISBN 978-0-470-17020-5. MR 2437651. (제2판, ISBN 9780471653981)

• Motwani, Rajeev; Raghavan, Prabhakar (25 August 1995). Randomized algorithms. Cambridge University Press. pp. 120–. ISBN 978-0-521-47465-8.

• Vazirani, Vijay (5 December 2002), Approximation algorithms, Springer Verlag, pp. 130–, ISBN 978-3-540-65367-7

외부 링크

• 확률론적 방법 - 조건 확률의 방법, Neal E에 의한 블로그 항목.Young, 2012년 10월 19일에 액세스.