오즈 알고리즘

오즈-알고리즘은 최적의 정지 문제의 영역에 속하는 일련의 문제들에 대한 최적의 전략을 계산하기 위한 수학적 방법이다. 그들의 해결책은 승산 전략에서 따르며, 승산 전략의 중요성은 아래에서 설명한 바와 같이 최적성에 있다.

승산-알고리즘은 마지막 성공-문제라고 불리는 일련의 문제들에 적용된다. 형식적으로, 이러한 문제들의 목적은 특정 기준("특정 사건")을 만족하는 마지막 사건에서 순차적으로 관찰된 독립 사건의 순서로 식별하는 확률을 최대화하는 것이다. 이 식별은 관찰 시에 수행해야 한다. 이전의 관찰에 대한 재조회는 허용되지 않는다. 일반적으로 특정 사건은 의사 결정자에 의해 "정지"라는 관점에서 이해관계가 있는 사건으로 정의되어 명확한 행동을 취하게 된다. 그러한 문제들은 여러 상황에서 직면한다.

예

두 가지 다른 상황은 마지막 특정 사건에서 멈출 확률을 최대화하는 것에 대한 관심을 예시한다.

자동차가 최고 입찰자에게 판매 광고를 낸다고 가정합시다(최고의 "오퍼"). 잠재 구매자 중 한 명이 응답하여 차를 보고자 한다. 각자는 입찰에 응할지 말지 판매자의 즉각적인 결정을 주장한다. 이전의 모든 입찰보다 좋은 경우 1로, 그렇지 않은 경우 0으로 코드화된 입찰을 흥미롭고 코드화된 입찰은 흥미롭고 코드화된 입찰로 정의한다. 입찰은 0초와 1초의 무작위 순서를 형성할 것이다. 오직 1초만이 판매자에게 관심을 가지며, 판매자는 각 연속 1이 마지막이 될지도 모른다고 두려워할 수 있다. 그것은 바로 마지막 1이 가장 높은 입찰이라는 정의에서 따온 것이다. 따라서 지난 1일 판매 확률을 극대화하는 것은 가장 잘 팔릴 확률을 극대화하는 것을 의미한다.
의사는 특별한 치료를 사용하는 경우 성공적인 치료를 위해 코드 1을 사용할 수 있으며 그렇지 않은 경우 0을 사용할 수 있다. 의사는 일련의 n명의 환자를 같은 방식으로 치료하며, 고통을 최소화하고, 그 과정에서 반응하는 모든 환자를 치료하기를 원한다. 0초와 1초의 무작위 시퀀스에서 마지막 1에서 멈추는 것은 이 목표를 달성할 것이다. 의사는 선지자가 아니기 때문에 마지막 1에서 멈출 확률을 최대화하는 것이 목표다.(인정적 사용 참조)

정의들

$n$ 의 n{\ $displaystyle$ n}개의 $n$ 독립 이벤트를 고려하십시오. 이 시퀀스와 다른 시퀀스 $I_{1},\,I_{2},\,\dots ,\,I_{n}$ $I_{1},\,I_{2},\,\dots ,\,I_{n}$ , $I_{1},\,I_{2},\,\dots ,\,I_{n}$ $I_{1},\,I_{2},\,\dots ,\,I_{n}$ , $I_{1},\,I_{2},\,\dots ,\,I_{n}$ … $I_{1},\,I_{2},\,\dots ,\,I_{n}$ ${\$ 을(를) 1 또는 0과 $I_{1},\,I_{2},\,\dots ,\,I_{n}$ 연결하십시오. 여기서 $\,I_{k}=1$ 이라고 $\,I_{k}=1$ 하는 $\,I_{k}=1$ k $\,I_{k}=1$ = 1 {\ $displaystyle$ }=1 $}$ 은(는) k번째 관찰이 흥미롭다는(의사결정자가 정의한 대로), $\,I_{k}=0$ k $\,I_{k}=0$ = $\,I_{k}=0$ $\,I_{k}=0$ 을(는) 이벤트를 $\,I_{k}=0$ 의미한다. 독립 랜덤 변수 $I_{1},\,I_{2},\,\dots ,\,I_{n}$ $I_{1},\,I_{2},\,\dots ,\,I_{n}$ , $I_{1},\,I_{2},\,\dots ,\,I_{n}$ I $I_{1},\,I_{2},\,\dots ,\,I_{n}$ , $I_{1},\,I_{2},\,\dots ,\,I_{n}$ … $I_{1},\,I_{2},\,\dots ,\,I_{n}$ I $I_{1},\,I_{2},\,\dots ,\,I_{n}$ ${\$ 을 순차적으로 $I_{1},\,I_{2},\,\dots ,\,I_{n}$ 관찰하여 마지막 성공을 선택하고자 한다.

$\,p_{k}=P(\,I_{k}\,=1)$ $\,p_{k}=P(\,I_{k}\,=1)$ = $\,p_{k}=P(\,I_{k}\,=1)$ ( $\,p_{k}=P(\,I_{k}\,=1)$ $\,p_{k}=P(\,I_{k}\,=1)$ = 1 $\,p_{k}=P(\,I_{k}\,=1)$ ) ${\displaystyle \,p_{k}=P(\,I_{k}\,=1)$ 를 k번째 사건이 흥미로울 확률로 한다 $\,p_{k}=P(\,I_{k}\,=1)$ . 추가로 $\,q_{k}=\,1-p_{k}$ $\,q_{k}=\,1-p_{k}$ k $\,q_{k}=\,1-p_{k}$ = $\,q_{k}=\,1-p_{k}$ - $\,q_{k}=\,1-p_{k}$ k ${\$ r $\,r_{k}=p_{k}/q_{k}$ = $\,r_{k}=p_{k}/q_{k}$ $\,r_{k}=p_{k}/q_{k}$ / $\,r_{k}=p_{k}/q_{k}$ k {\ $displaystyle \,r_{k}=p_{k}/q_{k$ $\,r_{k}$ $\,r_{k}$ ${\$ 은(는) k번째 이벤트가 흥미롭게 판명될 확률을 나타내며 $\,r_{k}$ , 오즈 알고리즘의 이름을 설명한다는 점에 유의하십시오.

알고리즘 절차

오즈 알고리즘은 역순으로 오즈를 요약한다.

r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,

이 합계가 처음으로 값 1에 도달하거나 초과할 때까지. 인덱스 s에서 이런 일이 발생하면 s와 해당 합을 저장한다.

R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}\,

승산의 합이 1에 도달하지 못하면 s = 1을 설정한다. 동시에 그것은 계산한다.

Q_{s}=q_{n}q_{n-1}\cdots q_{s}\,

출력은

$\,s$ ${\displaystyle \,s$ 중지 임계값
$\,w=Q_{s}R_{s}$ = $\,w=Q_{s}R_{s}$ $\,w=Q_{s}R_{s}$ $\,w=Q_{s}R_{s}$ ${\$ 승산 확률.

오즈-전략

오즈-전략은 이벤트를 차례로 관찰하고 인덱스 s 이후(있는 경우)부터 첫 번째 흥미로운 이벤트에서 중지하는 규칙이다. 여기서 s는 출력 a의 정지 임계값이다.

승산-전략의 중요성과 그에 따른 승산-알고리즘은 다음과 같은 승산-테마에 있다.

오즈-테움

잡동사니에는 다음과 같이 말하고 있다.

승산 전략은 최적, 즉 마지막 1에서 정지할 확률을 최대화한다.
승산 전략의 승산 확률은 w $\,w=Q_{s}R_{s}$ = $\,w=Q_{s}R_{s}$ $\,w=Q_{s}R_{s}$ $\,w=Q_{s}R_{s}$ $\,w=Q_{s}R_{s}$ ${\$ 과 같다.
$\,R_{s}\geq \,1$ $\,R_{s}\geq \,1$ $\,R_{s}\geq \,1$ $\,R_{s}\geq \,1$ ${\displaystyle \,R_{s}\geq \$ 1,1}인 경우 $\,R_{s}\geq \,1$ $\,w$ 은(는) $\,1/e=0.368\dots$ 최소 $\,w$ 1 $\,1/e=0.368\dots$ / $\,1/e=0.368\dots$ = $\,1/e=0.368\dots$ … $\,1/e=0.368\dots$ 이고 $\,1/e=0.368\dots$ 이 하한도가 가장 좋다.

특징들

오즈 알고리즘은 최적 전략과 최적 승산 확률을 동시에 계산한다. 또한 오즈-알고리즘의 운용 횟수는 n으로 (하위)선형이다. 따라서 모든 시퀀스에 대해 더 빠른 알고리즘이 존재할 수 없기 때문에 오즈 알고리즘은 동시에 알고리즘으로 최적이다.

원천

Bruss 2000은 이상한 알고리즘을 고안했고, 그 이름을 만들었다. 브루스알고리즘(전략)으로도 알려져 있다. 무료 구현은 웹에서 찾을 수 있다.

적용들

판매 문제, 비서 문제, 포트폴리오 선택, (단방향) 검색 전략, 궤적 문제, 주차 문제 등에 대한 임상 시험의 의학적 질문에서 온라인 유지보수 문제 등에 이르기까지 응용 프로그램이 도달한다.

같은 정신에서 포아송 과정(Bruss 2000)과 같은 독립적 증분을 갖는 연속 시간 도착 프로세스에 대한 오즈-테오가 존재한다. 오즈알고리즘의 적용이 직접 가능하지 않기 때문에 (위의 사례 2와 같이) 반드시 오즈알고리즘을 사전에 알 수 없는 경우도 있다. 이 경우 각 단계는 오즈의 순차적 추정치를 사용할 수 있다. 이는 알 수 없는 모수의 수가 관측치 수 n과 비교하여 크지 않은 경우에 의미가 있다. 그러나 최적성의 문제는 더 복잡하고 추가적인 연구가 필요하다. 오즈 알고리즘을 일반화하면 정지 실패와 잘못된 정지에 대해 서로 다른 보상을 얻을 수 있을 뿐만 아니라 더 약한 것에 의한 독립성 가정을 대체할 수 있다(Ferguson(2008)).

변형

Bruss & Peindaveine 2000은 $마지막$ k $k$ 성공 선택 $k$ 문제를 논의했다.

Tamaki 2010은 마지막 $[\displaystyle \ell }$ 성공에서 $\ell$ 정지하는 문제를 다루는 승산성 정리를 증명했다. 마쓰이&아노 2014가 우승 확률을 타이트하게 낮춘다.

마쓰이&아노 2017은 마지막 $({\displaystyle \ell })$ 성공 $\ell$ 사례 $k$ 중 $k$ $k$ 를 선정하는 문제를 논의했고, 승산이 크게 낮아졌다. ℓ $\ell =k=1,$ = $\ell =k=1,$ = $\ell =k=1,$ , $\ell =k=1,$ 일 때 문제는 $\ell =k=1,$ 브루스의 승산 문제와 동일하다. 만약 ℓ $\ell =k\geq 1,$ = $\ell =k\geq 1,$ $\ell =k\geq 1,$ $\ell =k\geq 1,$ , ${\displaystyle \ell$ = $k\geq$ 1 $,}$ 이 $\ell =k\geq 1,$ (가) 문제가 Bruss & Peindaveine 2000의 문제와 동일하다. 타마키 2010이 논의한 문제는 $\ell \geq k=1.$ $\ell \geq k=1.$ $\ell \geq k=1.$ = 1 ${\displaystyle \ell \geq k=1$ 을 설정하여 얻는다 $.$ $}$

객관식 문제: $r$ 는 r $r$ 선택권이 $r$ 허용되며, 어떤 선택이 마지막 성공일 경우 승리한다. 고전적인 비서 문제에 대해, 길버트 & 모스텔러 1966은 $r=2,3,4$ = $r=2,3,4$ , $r=2,3,4$ , $r=2,3,4$ 4 $(\디스플레이$ 스타일 $r=2,3,4})$ 의 사례에 대해 토론했다 $r=2,3,4$ $r=2,3$ = $r=2,3$ , $r=2,3$ (\ $디스플레이 스타일 r=2,3})$ 의 확률 문제는 아노, 카키누마 & 미요시 2010에 의해 논의되었다 $r=2,3$ . 오즈 문제의 추가 사례는 마츠이 & 아노 2016을 참조한다.

최적 전략은 임계값 번호 집합 $1$ }, $(a_{1},a_{2},...,a_{r})$ . $(a_{1},a_{2},...,a_{r})$ . $(a_{1},a_{2},...,a_{r})$ ) ${\displaystyle(a_{1},a_{2$ }, $...,a_{r$ 여기서 $a_{1}<a_{2}<\cdots <a_{r}$ < $a_{1}<a_{2}<\cdots <a_{r}$ < $a_{1}<a_{2}<\cdots <a_{r}$ > $a_{1}<a_{2}<\cdots <a_{r}$ < $a_{1}<a_{2}<\cdots <a_{r}$ ${\$ 에 의해 정의된 전략 클래스에 속한다 $a_{1}<a_{2}<\cdots <a_{r}$ 첫 번째 선택은 $a_{1}$ ${\$ $displaystyle a_{1$ } th $a_{1}$ $a_{1}$ 로 시작하는 첫 번째 후보자에게 사용되며, 일단 첫 번째 선택이 사용되면 두 $a_{2}$ 선택권은 2 {\displaystyle $a_{2$ }} $a_{2}$ 지원자 등으로 시작하는 첫 번째 후보자에게 사용된다.

r;2{\displaystyle r=2}, 아노, Kakinuma &amp게 국가 주의적 관점에서 서술 미요시 2010년은 승리 확률의 하한 e − 1+e32− 같습니다.{\displaystyle e^{)}+e^{-{\frac{3}{2}}}.}일반적인 긍정적인 정수 r{r\displaystyle}, 마쓰이 및;아노 2016년 승리 probabilit의 하한을 논의했다 보여 주었다.y When $r=3,4,5$ , tight lower bounds of win probabilities are equal to $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}$ , ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^$ ${-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$ and $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},$ respectively. $r=6,...,10$ = $r=6,...,10$ , $r=6,...,10$ . $r=6,...,10$ . $r=6,...,10$ , $r=6,...,10$ ${\displaystyle r=6$ , $...,10}$ 의 추가 사례는 마츠이 & 아노 2016을 참조한다 $r=6,...,10$

참고 항목

참조

Ano, K.; Kakinuma, H.; Miyoshi, N. (2010). "Odds theorem with multiple selection chances". Journal of Applied Probability. 47 (4): 1093–1104. doi:10.1239/jap/1294170522. S2CID 17598431.
Bruss, F. Thomas (2000). "Sum the odds to one and stop". The Annals of Probability. Institute of Mathematical Statistics. 28 (3): 1384–1391. doi:10.1214/aop/1019160340. ISSN 0091-1798.
-: "최적 정지 오즈의 테오렘에 대한 경계", 확률 연보 제31권, 1859–1862, (2003.
—: "올바른 결정의 기술", 유럽수학협회 뉴스레터, 이슈 62, 14–20, (2005)
T. S. 퍼거슨: (2008, 미발표)
Bruss, F. T.; Paindaveine, D. (2000). "Selecting a sequence of last successes in independent trials" (PDF). Journal of Applied Probability. 37 (2): 389–399. doi:10.1239/jap/1014842544.
Gilbert, J; Mosteller, F (1966). "Recognizing the Maximum of a Sequence". Journal of the American Statistical Association. 61 (313): 35–73. doi:10.2307/2283044. JSTOR 2283044.
Matsui, T; Ano, K (2014). "A note on a lower bound for the multiplicative odds theorem of optimal stopping". Journal of Applied Probability. 51 (3): 885–889. doi:10.1239/jap/1409932681.
Matsui, T; Ano, K (2016). "Lower bounds for Bruss' odds problem with multiple stoppings". Mathematics of Operations Research. 41 (2): 700–714. arXiv:1204.5537. doi:10.1287/moor.2015.0748. S2CID 31778896.
Matsui, T; Ano, K (2017). "Compare the ratio of symmetric polynomials of odds to one and stop". Journal of Applied Probability. 54: 12–22. doi:10.1017/jpr.2016.83.
슈렌 시오와 징루. 양: "마코프 종속 시험의 마지막 성공 선택", Journal of Applied Probability, Vol. 93, 271–281, (2002)
Tamaki, M (2010). "Sum the multiplicative odds to one and stop". Journal of Applied Probability. 47 (3): 761–777. doi:10.1239/jap/1285335408. S2CID 32236265.
다마키 미쓰시: "궤도와 투표 문제에서 최적 정지", 제38권, 946–959권(2001)의 적용 확률 저널.
E. 토마스, E. 레브랏, B. Iung: "L'algorithme de Bruss comme 기여 an neu maintenance preventive," Science et Technologies de l'automation, vol. 4, 13-18 (2007)

외부 링크

Bruss-Algorithmus http://www.p-roesler.de/odds.html

Search