이연결정의 원칙
Principle of deferred decision |
이연 결정의 원칙은 무작위화된 알고리즘의 분석에 사용되는 기법이다.
정의
무작위화된 알고리즘은 일련의 무작위 선택을 만든다.이러한 무작위 선택은 분석하기 어렵게 만드는 복잡하게 연관되어 있을 수 있다.이러한 많은 경우에 이연 결정의 원칙이 사용된다.원칙의 이면에 있는 생각은 무작위 선택의 전체 세트가 미리 만들어지는 것이 아니라 알고리즘에 공개되는 대로 고정된다는 것이다.
적용들
시계 카드놀이
이 원칙은 카드 한 벌로부터 "승리" 확률을 평가하고 결정하기 위해 사용된다.무작위 선택이 펼쳐지도록 하고, 반복이 52세에 끝날 때까지, 여기서 네 번째 카드가 "K"라고 표시된 그룹에서 뽑히면 게임이 종료된다.[citation needed]
참조
원천
- M. Mitzenmacher와 E. 업팔. 확률과 계산 : 무작위화된 알고리즘과 확률론적 분석2005년 뉴욕 (NY), 케임브리지 대학 출판부.섹션 1.3, 9페이지.
