두 집합 사이의 거리에 대한 두 증명

두 유한집합 에 대해, 의 값을 다음과 같이 정의한다. (단 둘 다 공집합인 경우는 제외한다)

이 값은 두 집합 사이의 상관관계를 나타내는 척도가 된다. 예컨대 이면 0이 되고, 인 경우는 1이 되는 등, 상대적으로 겹치는 정도가 클 수록 0에 가까워져 일종의 거리처럼 생각할 수 있게 된다. 이것이 실제로 수학에서 정의되는 거리(metric)가 되려면 다음과 같은 삼각부등식이 성립해야함을 증명해야 한다.

이 는 식물학자 Paul Jaccard의 이름을 따 Jaccard metric/Jaccard distance라 불리며, 위 삼각부등식은 현재까지도 복잡한 증명에서부터 간단한 증명까지 여러 새로운 증명이 발견되고 있다. 여기에서는 간단하면서도 그 성격과 맥락이 매우 대조적인 두 증명을 소개하고자 한다.

먼저 가장 직설적인 증명부터. StackExchange에 올라왔던 증명이다. 세 집합 로 만들어지는 벤다이어 그램에서 위와 같이 일곱 개의 각각의 영역에 해당하는 부분의 원소의 개수를 으로 둔다. 여기서 첨자는 각각의 부분이 에 포함되는지 안 되는지 여부를 가리키는데, 예컨대 은 에는 속하나 에는 안 속하는 의 원소의 개수가 됨. 그러면 증명하고자 하는 부등식을 다음과 같이 표현할 수 있다.

이 식을 전개하면 모든 계수가 양수인 다항식이 나와 증명이 끝난다.

두 번째 증명. 먼저, 편의상 의 원소를 $1, 2, \ldots, n$으로 둔다. 이 때 순열 에 대해, 에 를 적용하면 가 된다고 생각할 수 있다. 예컨대 이고 인 경우 가 된다. 순열 가 에서 균일하게 랜덤으로 선택된다고 생각한다. 그러면 두 집합 에 대해 와 의 최솟값이 같을 확률이 가 됨을 알 수 있다. (순서대로 나열해서 표현했을 때 의 원소가 아닌 것들은 고려할 필요가 없으니 다 지우고, 가장 처음으로 등장하는 원소가 의 원소여야 하므로) 즉 일 확률은 가 된다.

이제 인 사건을 각각 라 둔다. 그러면 라는 사건이 일어난다면 나 둘 중 하나가 일어나야 하므로, 가 되어 증명이 끝난다. Minhashing을 이용한 증명으로, Mining of Massive Datasets 등의 텍스트에서 찾아볼 수 있다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2018/12/23)

61. 두 유한집합 A,B가 주어져 있을 때 J_δ(A,B)를 다음과 같이 정의한다. (단 A와 B가 동시에 공집합인 경우는 제외한다.) 이 때 다음 부등식이 성립한다. pic.twitter.com/Ms5bd4spX1

— Elegant Math (@elegant_math) December 23, 2018