모자 문제 [2편]

 

 

 

지난 1편에서는 원탁에서의 모자 문제에서, 죄수가 3명일 때까지의 상황을 다루어 보았다. 이번 2편에서는 죄수($n$)이 4명일 때를 분석해보고, 이를 통해 일반화에 대한 아이디어를 얻어보자.

 

$n=4$인 경우

Upper bound가 이 경우 $0.8$로 설정된다. 이 때의 상황을 생각해보면, 이기는 횟수 ($X$)의 최댓값은 $2^{4}\times 0.8=12.8$이다. 그러나 $X$는 정수이므로 이 경우 $X$의 최댓값은 12이다. 따라서 사실상의 Upper bound는 $n=3$일 때와 마찬가지로 $0.75$이다. 

 

그러면, 죄수가 이기는 확률이 $0.75$가 되는 전략을 찾는 것은 생각보다 간단하다. 바로 4명 중 한 명을 투명인간 취급하는 것이다. 즉, 4명 중 한 명은 언제나 입을 꾹 닫고 있고, 나머지 세 명만 게임에 참여하고 있는 것으로 생각한다. 그들 3명은 '$n=3$'일 때와 마찬가지의 전략으로 그들끼리 게임을 플레이한다. 적어도 한 명은 모자색을 말할테니 입을 꾹 닫은 그 한 명이 모자색을 말해줄 필요는 없다. 그러면 그 3명의 모자색이 가질 수 있는 총 경우의 수 8가지 중 6가지에서 죄수팀이 승리하였다. 다른 한 명의 모자색은 Black일수도, White일수도 있지만, 그것이 승패에 영향을 끼치지 않는다. 그러므로 총 $6\times2=12$가지의 승리 방식이, $2\times2=4$가지의 패배 방식이 등장한다. 그러므로, 승리 확률은 여전히 $0.75$이다.

 

여기서 한 가지 통찰이 등장한다. 죄수 수가 많아지면 승리 확률은 최소한 떨어지지는 않는다는 것이다. 이렇게 몇 명의 죄수를 무시하는 전략만 써도 이전 수에서의 승리 확률은 보전되기 때문이다. 

 

그렇다면 $n=5$, $n=6$, 점점 죄수의 수가 많아지면 승리 확률은 1에 점근할까? 그것은 다른 얘기임에는 틀림없다. 이제부터 새로운 방식을 활용하여 이 명제의 참/거짓 여부를 확인해보고자 한다. 더불어, 몇 가지 죄수의 수에 대하여 일반화된 최선의 승리 확률값을 계산해보고자 한다. 이 방식은 수학의 각 분야가 가진 유기성을 여러분들에게 보여주기 충분할 것이다. 

 

Hamming code

---

데이터 과학에서 수신되는 정보는 4bit, 8bit, 16bit, 이와 같이 2의 거듭제곱의 바이트(byte) 수를 가지고 있다. 초창기 정보의 수신에서는 전기 통신의 정확도가 떨어져 송수신 과정에서 오류가 종종 벌어졌다. 예를 들어, 1011의 code가 1001으로 변할 수 있다. 정보를 받는 입장에서 1001이 올바른 정보인지, 오류난 정보인지를 판단할 방법이 없다. 수학자들은 code 송수신 시 오류가 벌어졌는지, 벌어졌다면 어디에서 벌어졌는지 판단하기 위하여 Hamming code라는 것을 조직하였다. 아래에서 Hamming code에 대한 원리를 자세히 설명한다.

---

$N$-dimensional binary vector space ($N$차원 이진공간)

선형대수학에서 학습하는 대부분의 벡터공간(Vector space)은 체(Field)가 실수, 복소수 등 무한 체 (Infinite field)인 것에 한정된다. 그러나 체의 원소가 유한하더라도, 그것이 체의 성질을 만족하고, 그것에서 정의된 벡터공간이 벡터공간의 성질만 만족한다면 아무런 문제가 되지 않는다. $N$-dimensional binary vector space는 선형대수 개론에서 학습한 벡터공간에 대한 고정관념을 완벽히 타파시켜주는 훌륭한 예시이다. 

• 체(Field): $F_2=\left\{0,1 \right\}$
• $N$-dimensional binary vector space의 원소는 일반적으로 $v=\left\{c_1,c_2, \cdots, c_n \right\}$ 형태로 구성되어 있다. 각각의 $c_i$들은 모두 이진수이다.
• 덧셈(Addition)의 정의: $v_1$과 $v_2$는 모두 $N$-dimensional binary vector space 의 원소이고,  $v_1=\left\{ a_1, a_2, a_3, \cdots , a_n\right\}$, $v_2=\left\{ b_1, b_2, b_3, \cdots , b_n\right\}$ 일 때 (벡터의 n개의 각 성분은 모두 체 $F_2=\left\{0,1 \right\}$의 원소이다.) 이때 $v_1+v_2=\left\{ a_1+b_1, a_2+b_2, a_3+b_3, \cdots , a_n+b_n\right\}$ 으로 정의한다. 이진수의 덧셈은 아래 그림 참조.
• 스칼라곱 (Scalar Multiplication)의 정의: $v_1$은 $N$-dimensional binary vector space 의 원소이고, $v_1=\left\{ a_1, a_2, a_3, \cdots , a_n\right\}$ 이다. 스칼라 $c$는 체 $F_2=\left\{0,1 \right\}$의 원소이다. 이때, 스칼라곱 $cv_1=\left\{ ca_1, ca_2, ca_3, \cdots , ca_n\right\}$이다. 이진수의 곱셈은 아래 그림 참조.

 

이진수의 덧셈과 곱셈

 

위 연산과 체를 가지는 벡터들이 벡터공간을 이룸을 벡터 공간의 axiom을 통해 보이는 과정은 생략하겠다. 여튼, 앞서 소개한 Hamming code에서 다루는 $n$-bit 데이터들은 모두 $n$-dimensional binary vector space의 원소가 된다. 즉, 이 벡터공간을 활용하여 Hamming code에 대한 이해를 해볼 수 있다.

 

Hamming weight와 Hamming distance

Hamming code와 관련한 두 가지 표기법을 소개한다.

• The Hamming weight of a vector $ \overrightarrow{c}\in F_{2}^{n}$, $w(\overrightarrow{c})$ is the number of non-zero digits in the vector.
• The Hamming distance between $\overrightarrow{c_{1}}, \overrightarrow{c_{2}}\in F_{2}^{n}$ is $d(\overrightarrow{c_{1}}, \overrightarrow{c_{2}})=w(\overrightarrow{c_{1}}-\overrightarrow{c_{2}})$. This distance is the number of bits that must be flipped to switch one vector into the other.

 

Hamming distance는 거리함수의 세 조건 (거리함수의 크기는 언제나 음이 아닌 수, 거리함수의 대칭성, 삼각부등식)을 만족하므로, 역시 거리함수의 일종이다. 그것을 보이는 절차는 본 문제와 관계가 크게 없으므로 생략하겠다.

$\overrightarrow{c_{1}}, \overrightarrow{c_{2}}\in F_{2}^{3}$ 인 $\overrightarrow{c_{1}}=(0,0,1)$, $\overrightarrow{c_{2}}=(1,1,1)$에 대하여 두 벡터 사이 Hamming distance는 2이다. (참고. 이진수의 뺄셈은 두 성분이 다를 경우 1, 같을 경우 0으로 생각한다.)

 

위와 같은 기초적 내용은 Hamming code 및 그것의 아이디어를 차용한 모자 문제를 해결하기 위해 반드시 알아야 할 내용들이다. Hamming code의 본격적인 수학적 원리는 모자 문제 [3편]에서, Hamming code를 통해 모자 문제에 대한 일반적인 해법 및 죄수의 수 ($N$)이 커짐에 따라 승리 확률의 추세가 어떻게 변하는가를 알아내는 것은 모자 문제 [4편]에서 만나볼 수 있다.