서지주요정보
Random sampling of continuous objects : can we computably generate brownian motions? = 브라운 운동을 포함한 연속적 객체 확률추출의 계산가능성
서명 / 저자 Random sampling of continuous objects : can we computably generate brownian motions? = 브라운 운동을 포함한 연속적 객체 확률추출의 계산가능성 / HyunWoo Lee.
발행사항 [대전 : 한국과학기술원, 2020].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8036005

소장위치/청구기호

학술문화관(도서관)2층 패컬티라운지(학위논문)

MCS 20027

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

Randomization is a very powerful tool which can reduce the complexity of a lot of algorithms in practice. However, to implement a randomized algorithm, sampling procedure from the fixed probability distribution is essential. In this paper, we formalized the sampling procedure from continuous probability distribution in the sense of Type-2 Theory of Effectivity which is theoretical framework to handle the computation over continuous data. We first show that every Borel probability measure on second countable $T_0$ spaces is just a push-forward measure of Canonical probability measure on Cantor Space. This is the extension of the result by Simpson and Schr$\ddot{o}$der, 2006. Second result is concerned with Brownian motion as the probability measure on the space of continuous function $f$ :[0,1]-> $\mathbb{R}$ with $f$(0)=0. We figure out the condition when such a measure can be sampled. This measure can be sampled if and only if its family of modulus of continuity can be sampled.

확률화는 많은 실용적인 상황에서 다양한 알고리즘의 복잡도를 낮출수 있는 강력한 도구이다. 하지만 이러한 알고리즘을 구현하는데에 있어서는 주어진 확률분포로 부터 확률추출의 과정이 필수적이다. 본 논문에서는 연속 확률분포로부터의 확률추출을 연속적 데이터에 대한 계산을 다루기 위한 체계인 유형-2 계산이론의 관점에서 형식화하였다. 첫번째로 우리는 제 2 가산 $T_0$ 공간위의 확률측도는 단지 칸토어 공간 위의 일반적인 확률 측도의 전진측도에 불과하다는 것을 발견하였다. 이는 Simpson 과 Schr$\ddot{o}$der 의 2006년 결과의 확장이다. 본 논문의 두번째 결과는 브라운 운동을 $f$(0)=0 를 만족하는 연속함수 $f$:[0,1]-> $\mathbb{R}$ 들의 공간위에 주어진 확률측도로 생각하는 것으로부터 시작한다. 우리는 이러한 측도가 확률추출 가능한 조건을 규명하였다. 이 측도가 확률추출 가능하다는 것이 해당하는 함수들의 연속률의 모임으로부터 확률추출이 가능하다는 것과 동치임을 증명하였다

서지기타정보

서지기타정보
청구기호 {MCS 20027
형태사항 iii, 17 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이현우
지도교수의 영문표기 : Martin Ziegler
지도교수의 한글표기 : 마틴 지글러
학위논문 학위논문(석사) - 한국과학기술원 : 전산학부,
서지주기 Including reference.
주제 Computable Analysis
Type-2 Theory of Effectivity
Random sampling
Probability Theory
Random Variable
Wiener Process
Brownian motion
계산 해석학
유형-2 계산이론
확률추출
확률론
확률변수
위너 확률과정
브라운 운동
QR CODE qr code