알고리즘 & 확률/Basic (6) 썸네일형 리스트형 도박꾼의 파산 (Gambler's Ruin) 일확천금을 노리는 한 도박꾼이 있다고 하죠. 이 도박꾼이 참여한 게임은 아주 간단합니다. 매 판마다 이기면 십만 원을 얻고 지면 십만 원을 잃습니다. 이 도박꾼이 오백만 원의 자본금으로 시작해서 천만 원을 더 벌고 싶다고 합시다. 과연 이 도박꾼이 목표를 이룰 확률은 어떻게 될까요? 반대로 이 도박꾼이 파산하게 될 확률은 또 어떻게 될까요? 이는 도박꾼의 파산(gambler's ruin)이라는 이름으로 많이 연구된 문제입니다. 위 상황을 좀더 일반화하면 다음과 같습니다. 도박꾼이 참여하는 게임에서 매 판마다 도박꾼은 \(p\)의 확률로 이기며, \(1 - p\)의 확률로 집니다. 단위를 간소화하기 위해 도박꾼이 이기면 1원을 얻고, 지면 1원을 잃는다고 합시다. 도박꾼은 처음에 \(L\)원의 자본금을 갖.. 랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms) 요새 알고리즘에 어떻게 확률론이 사용되는지를 공부하고 있습니다. 그러면서 예전에는 잘 몰랐거나 어렴풋이만 알던 내용들을 정확히 바로 잡고 있는데요. 그중에서도 가장 기본적인 내용을 하나 가볍게 짚고 넘어 가고자 합니다. 바로 랜덤 알고리즘(randomized algorithm)과 알고리즘의 확률적 분석(probabilistic analysis of algorithm)인데요. 결론을 미리 말씀 드리자면 둘은 서로 다릅니다. 랜덤 알고리즘은 확률 시행이 알고리즘의 내부에서 이루어지는 것을 지칭합니다. 대신 주어지는 입력에 대해서는 어떠한 가정도 존재하지 않죠. 확률 시행이 알고리즘의 내부에서 진행되니, 알고리즘은 동일한 입력에 대해서도 다른 결과를 출력할 수 있습니다. 이러한 알고리즘의 성능을 분석할 때는 .. 체르노프 부등식 (Chernoff Bounds) 여러분의 눈 앞에 총 \(n\)개의 서로 다른 상자가 놓여 있다고 합시다. 각 상자 안에는 흰 공과 검은 공으로만 차 있습니다. 여러분은 각 상자의 흰 공과 검은 공의 비율이 얼마나 되는지 모두 알고 있습니다. 즉, \(i\) 번째 상자에는 \( p_i \)의 비율로 흰 공이 있다고 해 보겠습니다. 여러분이 상자에서 각각 공을 하나씩 뽑는다면 과연 흰 공은 몇 개를 뽑게 될까요? 그 기댓값은 구하기 쉽습니다. 바로 기댓값의 선형성(linearity of expectation)에 의해 \( \sum_{i = 1}^n p_i \) 개가 될 것입니다. 그렇다면 실제로 공을 뽑았을 때, 과연 흰 공의 개수가 기댓값 혹은 기댓값 부근의 값이 될 확률은 얼마나 될까요? 이는 신뢰의 문제입니다. 만약 그 값이 들쭉날.. 지연 결정의 원리 (Principle of Deferred Decisions) 최근 논문을 읽는 중에 "지연 결정의 원리(principle of deferred decisions)"에 대해 알게 되었습니다. 이해가 잘 되지 않아서 인터넷에서도 열심히 찾아 보았으나 국문은 고사하고 영문으로 된 자료도 찾기 어렵더군요. 그나마 있는 자료들도 대부분 학교 수업 자료여서 제가 원하는 수준으로 상세하게 기술되어 있지 않았습니다. 다행히 교과서를 하나 찾게 되어 이 주제를 좀더 깊이 이해할 수 있었습니다. 이번 시간에는 이 원리에 대해서 한번 정리해 보겠습니다. 참고로 번역은 다음에서 "principle of deferred decisions"를 쳤을 때 나오는 거의 유일한 국문 웹페이지에서의 번역을 그대로 가지고 왔습니다. 원리를 이해하기 위해 다음 예제 게임을 함께 생각해 봅시다. 책상 .. 야오의 법칙 (Yao's Principle) 이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정 아래 글이 작성되었다는 점도 밝힙니다. 2019/08/11 - [수학적 도구/Randomness] - Arbitrary & Random Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데.. gazelle-and-cs.tistory.com 지난 시간 'random'을 설명하기 위해서 같이 고민했던.. Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데 어쩔 수 없었습니다. 컴퓨터과학을 전공하신다면 아마 두 단어를 많이 접하셨으리라고 생각합니다. 그만큼 많이 사용되는 단어인데 제대로 아시는 분은 그리 많지 않을 겁니다. 당장에 저만 하더라도 대학교 졸업할 때까지 둘의 차이를 명확하게 알지 못하였습니다. 대학원에 들어오고 나서야 둘의 차이를 구분할 수 있게 되었죠. 이렇게 헷갈리는데 우리말로 이를 제대로 설명한 글은 찾기가 힘들더군요. 우리말로 'arbitrary'는 '임의의'로, 'random'은 '무작위의' 정도로 번역이 되겠습니다. (.. 이전 1 다음
