통계적 시뮬레이션을 이용한 문제풀이방법.
세상은 discrete하면서도, statistic하다고 할 수도 있겠지만, 이 방법은 가장 통계적인 방법이다. 어떠한 시스템이 있고, 그 시스템의 수학적묘사가 어려울때, 이 방법은 그 수학적묘사 없이도 해를 얻어낼 수 있는 다분히 블랙박스적인 방법이다. 또한 discrete한 컴퓨터는 특히도 정확한 소수의 표현이 어렵기 때문에 생기는 수학적 문제해결방법(수치해석)분야에서도 많은 부분이 활용된다.
이 방법의 가장 유명한 예제는 원주율을 계산하는 방법이다. 가로 2, 세로 2인 정사각형을 그리고, 그안에 꽉차는 원을 그린다면, 정사각형의 넓이는 4이고, 원의 넓이는 파이알제곱, 즉 파이다. 사각형내 원의 넓이의 비율은 파이/4 이게 된다. 이 사각형에 랜덤하게 화살을 쏜다면... 그리고 사각형내에 화살이 균일하게 퍼져있다면, 원 내의 화살수를 사각형전체의 화살수로 나눠 주게되면 이것이 바로 넓이의 비율이고, 파이/4 이므로, 파이의 값을 알아낼 수 있다.
"Buffon's Needle"이라는 방법도 있습니다. 거리 d의 간격으로 평행한 선이 그어져 있는 바닥에 d보다 짧은 길이 l의 바늘을 임의로 던졌을 때 바늘이 선을 건드릴 확률이 (2l)/(d Pi)라는 것에 착안한 방법입니다. 원을 그릴 수 없다면 이 방법이 유용하겠죠. 그냥 마룻바닥에다 바늘을 던지면 되니까...
See
BuffonsNeedleProblem.html http://www.mste.uiuc.edu/reese/buffon/buffon.html.
뷔퐁의 바늘 실험은 기하학적 확률의 효시가 된 문제이기도 합니다. 여러 사람이 실제로 실험을 해 보았는데, 그 가운데 Lazzarini는 3.1415929라는 어마어마하게 정확한 값을 구하기도 했습니다. 놀라운 일이죠. 그러나 최근에 그의 실험이 완전히 날조되었음이 수학적으로 밝혀져 화제가 되기도 했습니다. --Puzzlist
단점또한 존재한다. 현재의 컴퓨터는 정확한 랜덤넘버를 만들어내지 못하며, 무한대역시 표현이 안된다. 주사위 던지기를 무한번하면 3이 나올 확률은 1/6이겠지만, 컴퓨터는 정확하게 1/6을 주지 못한다. 그래서 값이 틀려질 수 있다.See
BuffonsNeedleProblem.html http://www.mste.uiuc.edu/reese/buffon/buffon.html.뷔퐁의 바늘 실험은 기하학적 확률의 효시가 된 문제이기도 합니다. 여러 사람이 실제로 실험을 해 보았는데, 그 가운데 Lazzarini는 3.1415929라는 어마어마하게 정확한 값을 구하기도 했습니다. 놀라운 일이죠. 그러나 최근에 그의 실험이 완전히 날조되었음이 수학적으로 밝혀져 화제가 되기도 했습니다. --Puzzlist
1/6을 만들 수도 있습니다. 1부터 6까지 차례대로 답을 해 주면 되죠. (물론 그래서 random이 아니고요.) 그리고 던지는 횟수를 늘려갈 때 3이 나올 확률이 점점 1/6에 접근하는 것이지, 무한번 던져 1/6이 나오는 것도 아니고요. 수학적으로 정의된 여러 random에 대한 test를 통과하는 pseudo random number generator는 많습니다.
RefactorMe below.
죄송합니다. 단지 통계 비스므리한 것을 공부하는 사람으로서 약간 잘못 사용된 말을 수정합니다. 일단 어떤 시스템을 확률적으로 분석한다는 말은 그 시스템에 관한 기본적 확률을 가정하여야합니다. 물론 신경망등에서는 그런 가정을 거의하지 않지만 이를 두고 통계적 방법이냐 아니냐말이 많은 것으로 알고 있습니다. 따라서 제 생각에는 통계적 시뮬레이션이란 수학적 가정등이 없이 블랙박스처럼 시도되는 것은 아닙니다. 주어진 예도 통계라기보다는 수치해석으로 계산한 근사라는 말이 더 적당하겠네요. 그리고 정확한 랜덤 넘버를 만들지 못한다는 말이 무엇인지 잘 모르겠군요. --아무개
MonteCarloMethod 는 정확한 수학적 모델을 모르거나 혹은 알더라도 사용하지 않고 단지 확률분포로부터 문제에 대한 답의 근사치를 얻어내는 방법입니다. 확률과 통계가 따로 시작되었다고 할 수는 있지만 지금은 따로 분리할 수는 없겠지요. 
기본적인 확률을 가정해야 한다는 것은 Bayesian statistics에서 사용되는 prior probability를 말씀하시는 건가요? 위의 예에서 쓰여진 방법은 순수한 Maximam likelihood estimate로서 기본적 확률로 따로 가정된 부분은 없는 것 같습니다. 그리고 deterministic 한 컴퓨터가 랜덤 넘버를 만들어 내는 것은 수학적으로 매우 어려운 문제입니다. 따라서 여러 가지 꽁수를 써서 랜덤인 것처럼 보이는 숫자들을 만들어 낼 뿐이라 알고 있습니다. --지상은
기본적인 확률을 가정해야 한다는 것은 Bayesian statistics에서 사용되는 prior probability를 말씀하시는 건가요? 위의 예에서 쓰여진 방법은 순수한 Maximam likelihood estimate로서 기본적 확률로 따로 가정된 부분은 없는 것 같습니다. 그리고 deterministic 한 컴퓨터가 랜덤 넘버를 만들어 내는 것은 수학적으로 매우 어려운 문제입니다. 따라서 여러 가지 꽁수를 써서 랜덤인 것처럼 보이는 숫자들을 만들어 낼 뿐이라 알고 있습니다. --지상은Maximum likelihood estimate에서 likelihood를 정의할려면 특정 확률 분포를 가정해야 합니다.그렇지 않고 simple analogue를 통해서 하는 moment estimation도 있습니다. 위의 글에서는 Uniform distribution을 가정했군요.-아무개
수학적 가정이 아예 없을 수는 없을겁니다. 하지만, MonteCarloMethod는 그 정확한 수학적묘사를 통하지 않고 확률적으로 그 해를 구하기 때문에 다분히 블랙박스적이란 표현을 썼던겁니다. 만일 sin(x)함수를 0부터 파이까지 정적분한다고 할때, sin(x)가 -cos(x)+C로 부정적분된다는 정확한 수학적묘사를 통해 그 값을 구할 수 있지만, 만일 직접적분이 어려운 함수이거나, 혹은 그 함수조차 알지 못할때도, 비록 그 수학적묘사는 하지 않지만, 위예제와 비슷한 방법으로 정적분값, 즉 함수 및 부분의 면적을 구할 수 있을 겁니다. 물론, 넓이와 관련된 기본적인 수학적가정들은 사용됩니다만 그 함수를 수식으로 표현못해도 정적분값을 구해내었다는 것이 다분히 블랙박스적인것이 아닐까요? 혹시라도 제가 잘못알고 있는것이 있다면 지적해주시기 바랍니다. 다큐먼트모드의 글이므로, 수정될수 있습니다.1과 10사이를 예로 들었을때, 정확한 랜덤넘버 만들기를 계속하면, 열개의 숫자가 나타나는 빈도는 정확히 똑같으면서도, 절대 예측할 수 없도록 열개의 숫자가 임의로 나타나야 합니다. 그러나, 이를 만족하는 수학적 이론은 없는것으로 알고 있습니다. 따라서 랜덤넘버가 필요하면, 실제로 주사위를 던져보던지, 통계학책뒤의 난수표(이건 어떻게 만든건지 저도 몰겠네요. AnswerMe)를 사용해야합니다. MonteCarloMethod를 위해선 정확한 랜덤넘버의 생성이 생명이라 할수 있겠는데, 이를 만들기 어렵기 때문에 컴퓨터로 pseudorandom numbers를 만듭니다. 제 짧은기억에 아마 컴퓨터의 현재시간의 초단위의 수치를 초기값으로 사용해서 슈도랜덤넘버를 만드는데, 역시나, 이것이 완벽한 랜덤넘버라고 말 할수는 없겠지요. 이것이 MonteCarloMethod의 에러에 어느정도 기여하는 것으로 알고 있습니다. 참고사이트 http://random.mat.sbg.ac.at/links/rando.html --yong27
좀 더 나은 random number를 얻고자 하면 외부 장치를 이용하기도 합니다. 가장 많이 쓰이는 장치는 가이거 계수기. 원자핵의 분열이나 우주방사선 등은 우리가 제어할 수 없으므로 그 발생의 빈도를 이용하여 random number를 만듭니다. - 까리용
![[http]](/ns/imgs/http.png)
몬테카를로를 이해하기에 난해한 문장
{{|
This wide diversity of methods is the reason that Monte Carlo is not Monte Carlo is not Monte Carlo.
|}}
This wide diversity of methods is the reason that Monte Carlo is not Monte Carlo is not Monte Carlo.
|}}
MonteCarloMethod가 몬테카를로적이지 않다는 것이 MonteCarloMethod가 아닌 것은 이 방법의 다양성 때문이다.
몬테카를로 방법은 아주 다양하다. 그런데 이 다양성 때문에, (어떤) 몬테카를로 그 자체를 두고 몬테카를로가 아니라고 말하는 것 그것은 몬테카를로적이지 못하다는 말을 할 수 있는 것이다. 예를 들어, 갑이라는 사람이 XP(ExtremeProgramming) is not XP라고 말했다고 하자. 이때의 의미는 "(현재의) XP는 (내가 생각하는 이상적) XP가 아니다"는 말이 된다. 그런데, 을이라는 사람은 이에 대해, XP is not XP is not XP라고 말을 한다. 그 말은 "네가 하는 그 소리는 XP적이지 못하다"는 뜻이 된다.
따라서 MonteCarloMethod가 확률적이지 않고 deterministic 하다면 MonteCarloMethod 가 아니다. 이런 뜻이 아닐까?몬테카를로는 모나코의 수도입니다. 프랑스 남단 지중해 연안. 유명한 도박의 도시구요. 지상 최대의 카지노가 있답니다.
확률과 통계가 어떻게 발전했는지 아십니까? 도박 때문이랍니다. 어떻게 하면 도박에서 돈을 많이 딸 수 있을까를 연구하다 보니 확률, 통계가 발전했다고 합니다. 그래서 MonteCarloMethod 라는 멋진 이름이 붙었구요. 이런데서 나오는 자료들은 대부분 이산 자료가 됩니다. 동전이라던지, 주사위라던지... 세는 거죠. 이항분포, 다항분포 뭐 그런 것들이 나오게 되죠.
도박에 대해서 빼 놓을 수 없는 도시가 라스베가스죠. 통계학의 시뮬레이션에서도 역시 Las Vegas Method가 있습니다.
이에 비해서 현대통계학은 천문학의 측정에서 발전했다고 합니다. 여기서는 연속 자료가 나오게 되지요. 세는 것과는 틀립니다. 가우스가 대기 굴절에 의해서 별의 위치가 조금씩 변하는 것을 가지고 오차 (error) 의 개념을 만들고, 그 분포로서 Gaussian distribution, 즉 정규분포를 만들었다고 합니다. 이것이 당시로서는 파격적인 것이었다고 하는군요. 우리가 어떤 함수를 적분한다고 합시다. 적분은 면적을 구하기 위해서란 사실을 모두 아시고 계시겠지요. 이 함수가 너무 너무 복잡해서 적분하는데 아주 힘들다. 그렇다면... MonteCarloMethod입니다.
구간을 정하고 그 함수를 그립니다. 컴퓨터 안의 공간에서... 그리고 거기다가 random 하게 화살을 던집니다. 이때 반드시 random number 가 uniform distribution을 이루어야 한다는 가정이 필요하겠지요. 정말 랜덤해야 한다는 뜻입니다. 당연한 거 아니냐? 그러시는 분 계시다면... 컴퓨터는 deterministic 해서 이것이 그렇게 간단한 일이 아니랍니다. 어쨌든... 어떤 화살은 그 함수의 적분되어야 되는 영역 안에 꽂힐 테고... 어떤 화살은 그 밖의 영역에 꼽히겠지요. 전체 던진 화살 분의 영역 안의 꽂힌 화살 개수를 세면... 그 부분의 면적을 구할 수 있습니다. 복잡한 적분을 하지 않고서도... 멋있지 않습니까? 어떤 복잡한 문제도... 근사값을 구해낼 수 있는 방법입니다. 문제 자체의 본질과 실체에 대해서는 고민하고 알 필요가 없습니다. 알고 싶은 것은 뭐든지 확률적인 방법으로 근사치를 알아낼 수 있습니다.
Web 상에서 원주율 구하는 방법을 Monte Carlo method 로 simulation 하는 site 가 있습니다. 관심 있는 분들은 한번 가 보시지요. http://netdb.chungbuk.ac.kr/~jrshin/algorithm/Monte_carlo/index.html
여기 가서 한번 실행해 보다가 언듯 생각난 게 pseudorandom number가 실제로 random한가를 평가하는데 이 MonteCarloMethod가 쓰일수 있지 않을까 하는 생각이 드는군요.(역으로 생각해보는 거죠) 그 simulation 결과가 얼마나 pi에 가까운가를 가지고 random number의 유용성을 평가 할 수 있지 않을까요?
SimulatedAnnealing도 MonteCarloMethod 에 쓰이는 중요한 기법중에 하나입니다.아쉽게도 randomness를 평가하는데 쓰일 수 없습니다.
왜 쓸수 없는지 잘 이해가 가지 않습니다. 될수도 있을듯 한데...--;; 설명부탁드립니다.
randomness를 평가한다는 것 자체가 이해가 잘 안됩니다. random number를 generate하는 function이 실제 random한 수를 내뱉는다는 것을 도데체 어떻게 평가할 수 있나요? --지원제 생각에 randomness의 두가지 성질, 균등한 분포와 예측불가능 중 균등한 분포는 평가할 수 있을 것 같네요. 근데 randomness를 만드는 것이 그렇게 어렵다면, 단순히 좌표를 격자화시켜서 계산하면 되는 거 아닌가 모르겠네요. 적분이 아니라 구간 적분을 하는 거죠. 정확성은 격자의 크기를 줄이면 되고. 그러고 보니, 적분의 경우에 구간 적분보다 크게 유용성 있는지 모르겠네요. (연속인 함수라면.. ^^) Monte Carlo Method가 크게 강한 분야가 어디인가요? --가리오
random이란 말이 무작위적임을 의미하긴 하지만, 사실 무작위적이라는 것 자체가 어떤 규칙을 수반합니다. 그것은 나타나는 랜덤숫자들의 빈도가 같아야 한다는거죠. 만일 그 빈도가 다르다면, 그건 랜덤수가 아닐껍니다. 주사위를 던질때 1이 나올 빈도와 6이 나올 빈도가 같아야만 그것이 랜덤수를 생산한다고 말할수 있으니까요. 따라서, randomness의 평가는 그 빈도수가 같느냐를 보는것일껍니다. 주사위를 6천만번 던졌을때 1이 1천만번, 6이 1천만번 나왔다면 음... 이 주사위는 randomness가 좋군 이라고 말할 수 있겠죠. --yong27
.png ":)")
--지원
랜덤넘버는 단순히 어떤 수가 나오는 빈도가 같을뿐만 아니라 그 규칙성을 알 수 없는 수이어야 합니다. 예측을 할 수 없어야지요. 흔히 랜덤넘버를 생성하는데 점화식을 많이 사용한다고 하는데, 점화식을 사용한다는 것 자체가 규칙성에서 벗어나지 못한다는 것을 보여주겠죠. 그런 면에서 컴퓨터를 이용한 계산을 통한 난수의 발생은 진정한 의미의 난수라고 말하지 않습니다. 하나의 난수표가 진정한 난수표인지를 테스트하는 방법이 있다고 들었는데, 그 테스트를 통과하기가 쉽지 않다는 것을 빼고는 잘 기억이 나지 않네요.
간단한 방법 중에 하나는 충분히 큰 난수표를 충분히 많은 항의 푸리에 시리즈로 전개 했을 때, 오차가 Pi의 소수점 숫자열을 푸리에 시리즈로 전개한 것의 오차보다 큰 지 살펴보는 방법을 쓸 수 있을 겁니다. -- gerecter첫번째는 1, 두번째는 2, 세번째는 3, ..., 여섯번째는 6, 일곱번째는 1, 여덟번째는 2, ..., 1000번째는 4, ...., 12345번째는 3 이 나오는 함수를 보통 사람들은 random하다고 부르지는 않죠. -- 까리용
제가 짐작하기로는, n회 시행하여, 결과로 나오는 확률분포가 편차 내인가를 보는 것을 여러 번 되풀이 할꺼라고 어렴풋이 생각했었는데(통계학에서의 이론을 사용하여..) 그래도 randomness를 실험적으로 평가를 하는 것에 대해서는 좀 이상하다는 느낌은 지울 수 없네요 -- 까리용 --지원랜덤넘버는 단순히 어떤 수가 나오는 빈도가 같을뿐만 아니라 그 규칙성을 알 수 없는 수이어야 합니다. 예측을 할 수 없어야지요. 흔히 랜덤넘버를 생성하는데 점화식을 많이 사용한다고 하는데, 점화식을 사용한다는 것 자체가 규칙성에서 벗어나지 못한다는 것을 보여주겠죠. 그런 면에서 컴퓨터를 이용한 계산을 통한 난수의 발생은 진정한 의미의 난수라고 말하지 않습니다. 하나의 난수표가 진정한 난수표인지를 테스트하는 방법이 있다고 들었는데, 그 테스트를 통과하기가 쉽지 않다는 것을 빼고는 잘 기억이 나지 않네요.