확률론적 방법
Probabilistic method확률론적 방법은 비건설적인 방법으로, 주로 조합에 사용되며, 규정된 종류의 수학적 물체의 존재를 증명하기 위해 폴 에르드스가 개척했다. 특정 등급의 물체를 무작위로 선택하는 경우, 그 결과가 규정된 종류일 확률은 0보다 절대적으로 크다는 것을 보여줌으로써 효과가 있다. 비록 증명에는 확률을 사용하지만, 최종 결론은 어떠한 오류도 없이 확실하게 결정된다.
이 방법은 이제 컴퓨터 공학(예: 무작위 반올림), 정보 이론뿐만 아니라 숫자 이론, 선형 대수학, 실제 분석과 같은 수학의 다른 분야에도 적용되었다.
소개
개체 집합의 모든 개체가 특정 속성을 갖지 못하면 수집에서 선택한 임의 개체가 해당 속성을 가질 확률은 0이다.
마찬가지로 확률이 (엄정히) 1보다 작다는 것을 보여주는 것은 규정된 성질을 만족시키지 못하는 물체의 존재를 증명하는 데 사용될 수 있다.
확률론적 방법을 사용하는 또 다른 방법은 일부 랜덤 변수의 기대값을 계산하는 것이다. 무작위 변수가 기대값보다 작은 값을 가질 수 있다는 것을 보여줄 수 있다면, 이는 랜덤 변수가 기대값보다 큰 값을 가질 수도 있다는 것을 증명한다.
또는 확률론적 방법을 사용하여 계산된 기대값보다 크거나 같은 값을 갖는 표본 공간에 원하는 원소의 존재를 보장할 수도 있다. 그러한 원소의 존재는 표본 공간의 모든 원소가 기대값보다 작다는 것을 의미하기 때문이다.
확률론적 방법에 사용되는 일반적인 도구로는 마르코프의 불평등, 체르노프 바운드, 로바스츠 지방 보조정리 등이 있다.
Erdős로 인한 두 가지 예
비록 그의 이전의 다른 사람들이 확률론적 방법(예를 들어, 많은 수의 해밀턴 사이클을 포함하는 토너먼트가 존재한다는 Szelle의 1943년 결과)을 통해 이론들을 증명했지만, 이 방법을 사용하는 가장 잘 알려진 많은 증거들은 Erdős 때문이다. 아래 첫 번째 예는 Ramsey 번호 R(r, r)에 대한 하한을 증명하는 1947년도의 결과를 설명한다.
첫 번째 예
정점에 대한 전체 그래프가 있다고 가정합시다. 단색(모든 가장자리가 동일한 색상으로 칠해진) r 정점에 완전한 하위 그래프가 없도록 그래프 가장자리를 두 가지 색상(빨간색 및 파랑색)으로 색칠할 수 있다는 것을 (n의 작은 값에 대해) 보여주고자 한다.
그렇게 하기 위해서, 우리는 그래프를 무작위로 색칠한다. 빨간색일 확률 1/2과 파란색일 확률 1/2로 각 모서리를 독립적으로 색칠하십시오. r 정점에 예상되는 단색 서브그래프의 수는 다음과 같이 계산한다.
그래프에서 정점의 에 대해 정점 사이의 모든 에지가 동일한 색상이면 X를 1로 정의하고, 그렇지 않으면 0으로 정의하십시오. Note that the number of monochromatic -subgraphs is the sum of over all possible subsets . For any individual set , the expected value of S ( , ) {\ S_{에 있는 C( , 2 에지가 동일한 색일 확률이다.
(두 가지 색상이 있기 때문에 2의 인자가 온다.)
This holds true for any of the possible subsets we could have chosen, i.e. ranges from 1 to . So we have that the sum of over all 이다
기대치의 합은 총액에 대한 기대치(변수의 독립 여부에 관계 없음)이므로 총액에 대한 기대치( 단색 r } -subgraphs의 예상 개수)는 다음과 같다.
이 값이 1보다 작을 경우 어떻게 되는지 고려하십시오. 예상되는 단색 r-서브그래프의 수가 절대적으로 1보다 적기 때문에 단색 r-서브그래프의 수가 절대적으로 1보다 적다는 조건을 만족시키는 색소가 존재한다. 이 랜덤 컬러링에서 단색 r-하위그래프의 수는 음이 아닌 정수이므로 0이어야 한다(0은 음이 아닌 유일한 정수 1보다 작음). 다음과 같다.
(예를 들어, n=5 및 r=4)의 경우 단색 r-서브그래프가 없는 색상이 존재해야 한다. [a]
Ramsey 번호의 정의에 따르면, 이는 R(r, r)이 n보다 커야 함을 의미한다. 특히 R(r, r)은 r과 함께 최소한 기하급수적으로 커야 한다.
이 주장의 약점은 그것이 전적으로 비건설적이라는 것이다. (1.1)r 정점에 있는 전체 그래프의 거의 모든 색상이 단색적 r-하위계를 포함하지 않음을 (예를 들어) 증명하더라도, 그러한 색상의 명시적인 예는 제시하지 않는다. 이런 색채를 찾는 문제는 50년 넘게 열려 있다.
- ^ 같은 사실은 다음과 같은 간단한 계산 논거를 사용하여 확률 없이 증명할 수 있다.
- 총 r-subgraph 수는( r) \선택 r입니다
- 각 r-subgraph는 ( ) {r 한 \한 2개의 다른 방법으로 색칠할 수 있다.
- 이러한 컬러링 중 오직 2가지 컬러링만이 해당 서브그래프(모든 정점이 빨간색 또는 모든 정점이 파란색인 컬러링)에 대해 '나쁨'이다.
- 따라서 일부(적어도 하나 이상) 하위 그래프에 나쁜 총 색상 수는 최대 r이다
- 따라서 ( r)> ( r 하위 그래프에 대해 '나쁘지 않은' 색상이 적어도 하나 이상 존재해야 한다
두 번째 예
1959년 Erdős 논문(아래 인용 참조)은 그래프 이론에서 다음과 같은 문제를 다루었다: g와 k의 양의 정수를 감안할 때 G의 색도 수가 적어도 k가 되도록 g의 길이 사이클만 포함하는 그래프 G가 존재하는가?
어떤 g와 k에 대해서도 그러한 그래프가 존재한다는 것을 보여줄 수 있으며, 그 증거는 상당히 간단하다. n은 매우 커지게 하고 G의 모든 에지가 확률 p = n으로1/g−1 존재하는 n 꼭지점에서 랜덤 그래프 G를 고려한다. 우리는 긍정적인 확률로 G가 다음의 두 가지 특성을 만족한다는 것을 보여준다.
- 속성 1. G는 길이가 g보다 작은 최대 n/2 사이클을 포함한다.
증명. x를 g보다 작은 길이의 숫자 주기가 되게 하라. n 꼭지점의 전체 그래프에서 길이 i의 주기 수는
그리고 각각 확률i p와 함께 G로 존재한다. 마르코프의 불평등 때문에
- 따라서 n이 충분히 큰 경우, 속성 1은 1/2 이상의 확률로 보유한다.
- 속성 2. G에는 크기 {\}의 독립된 세트가 포함되어 있지 않다
증거. Y는 G에서 가장 큰 독립 집합의 크기가 되게 하라. 분명히, 우리는
할 때
- = y 따라서 n이 충분히 크면 속성 2가 1/2 이상의 확률로 유지된다.
충분히 큰 n의 경우, 분포의 그래프가 두 속성을 모두 가질 확률은 양수인데, 이러한 속성에 대한 사건은 분리될 수 없기 때문이다(만약 그렇다면, 그들의 확률은 1보다 더 많이 합해질 것이다).
여기서 요령이 나온다: G는 이 두 가지 속성을 가지고 있기 때문에, 우리는 G에서 최대 n/ 정점을 제거하여 적어도 g 길이의 사이클만 포함하는 n / 2 n정점에 새로운 그래프 G′을 얻을 수 있다. 우리는 이 새로운 그래프의 크기 ⌉ {\의 독립된 세트가 없음을 알 수 있다 G′은 적어도 k개의 독립된 세트로만 분할할 수 있으며, 따라서 색도수가 적어도 k이다.
이 결과는 왜 그래프의 색수 계산이 그렇게 어려운지에 대한 힌트를 준다: 그래프가 많은 색을 필요로 하는 지역적 이유(작은 사이클 등)가 없어도 색수는 여전히 임의로 클 수 있다.
참고 항목
참조
- 알론, 노가; 스펜서, 조엘 H. (2000) 확률론적 방법(2개) 뉴욕: 와일리-인터사이언스. ISBN0-471-37046-0.
- Erdős, P. (1959). "Graph theory and probability". Can. J. Math. 11: 34–38. doi:10.4153/CJM-1959-003-9. MR 0102081.
- Erdős, P. (1961). "Graph theory and probability, II". Can. J. Math. 13: 346–352. CiteSeerX 10.1.1.210.6669. doi:10.4153/CJM-1961-029-9. MR 0120168.
- J. 마투셰크, J. 본드락. 확률론적 방법. 강의 노트.
- 알론, N, 크리벨레비치, M(2006)이다. 극단적 및 확률적 결합론
- 엘리사코프 I, 구조 이론의 확률론적 방법: 재료의 무작위 강도, 무작위 진동 및 좌굴, 세계 과학, 싱가포르, ISBN 978-981-3149-84-7, 2017
- 엘리사코프 I, Lin Y.K. 및 Ju L.P. , 음향 흥분 구조물의 확률적 및 볼록 모델링, Exvier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0