로빈스 문제

확률론에서는 허버트 로빈스의 이름을 딴 로빈스의 최적 정지 문제를 제4비서 문제 또는 완전한 정보로 예상 계급을 최소화하는 문제로 언급하기도 한다.그 진술은 다음과 같다.

X₁, ..., X는_n 독립적이고, 동일하게 분포된 랜덤 변수를 [0, 1]에서 균일하게 한다.우리는_k X의 순서를 관찰하고 그 중 하나에서 정확히 멈춰야 한다.선행 관찰에 대한 리콜은 허용되지 않는다.선택한 관측치의 예상 순위를 최소화하는 중지 규칙은 무엇이며 해당 값은 얼마인가?

이 전체 정보 예상 순위 문제에 대한 일반적인 해결책은 알려지지 않았다.가장 큰 어려움은 문제가 전적으로 역사에 의존한다는 것, 즉 최적의 규칙은 모든 이전 가치에 따라 매 단계마다 달라지며, 이것들에 대한 더 간단한 충분한 통계에 의존하지 않는다는 것이다.한계치 v는 n이 무한대로, 즉 1.908 < v < 2.329가 되는 것으로만 알려져 있다.문제의 잘린 버전에 대한 추가 계산을 통해 하한을 개선할 여지가 있는 것으로 알려져 있다.메모리 없는 임계값 규칙의 하위 클래스에서 비롯되는 상한선을 어떻게 개선할 것인지는 여전히 알려져 있지 않다.

중요도

로빈스의 문제를 연구하게 된 동기 중 하나는 그 해결책으로 모든 고전적인(4개) 비서 문제가 해결될 것이라는 점이다.그러나 주요한 이유는 (의견스러울 정도로 쉬워 보이는) 문제에서 완전한 역사 의존에 어떻게 대처해야 하는가를 이해하는 것이다.이에 따라 이스라엘에서 열린 에스테르 도서 국제회의(2006)에서 로빈스의 문제는 최적 정지 및 순차 분석 분야에서 가장 중요한 네 가지 문제 중 하나로 선정되었다.

역사

허버트 로빈스는 1990년 암허스트에서 열린 국제 검색 및 선택 회의에서 위에서 설명한 문제를 발표했다.그는 내가 죽기 전에 이 문제가 해결되기를 바라는 말로 그의 연설을 끝맺었다.최적 정지 분야에서 일하는 과학자들은 그 이후로 이 문제를 로빈스의 문제라고 불렀다.

참조

• Chow, Y.S.; Moriguti, S.; Robbins, H.; Samuels, S.M. (1964). "Optimal Selection Based on Relative Rank". Israel Journal of Mathematics. 2 (2): 81–90. doi:10.1007/bf02759948.
• "전체 정보로 예상 순위를 최소화하는 것", F. 토마스 브루스와 토마스 S. 퍼거슨, 적용 확률 볼륨 30, 1위(1993) 페이지 616–626
• 예상 순위 최소화, F. T. Bruss와 T. S. 퍼거슨, 통계 제1권의 Springer 강의 노트 J.M. Gani, (1996), 페이지 1–17.
• "비서 문제, 무작위 변수와 함께 예상 순위 최소화" D.아사프와 E. 사무엘 칸, 어드밴스. 앱. 프로브 28권, (1996), 페이지 828–852 고양이.이니스트
• "로빈스의 문제에 대해 알려진 것은 무엇인가?" F. 토마스 브루스, 응용 확률 제 42권, #1(2005), 페이지 108–120 유클리드
• "로빈스의 예상 순위를 최소화하는 문제에 대한 연속 시간 접근" F. 토마스 브루스와 이브 카오임힌 스완, 응용 확률권 제46권 제1, 1–18, (2009년)