ในทฤษฎีความน่าจะเป็น ปัญหา การหยุดที่เหมาะสมที่สุดของ Robbins ^{[ 1 ]}ซึ่งตั้งชื่อตามHerbert Robbinsบางครั้งเรียกว่าปัญหาเลขานุการคน ที่สี่ หรือปัญหาการลด อันดับ ที่คาดหวังด้วยข้อมูลครบถ้วน^{[ 2 ]}

ให้และ เป็นตัวแปรสุ่มอิสระ ที่มีการแจกแจงเหมือนกัน และ มีการแจกแจง แบบเอกรูปบนช่วงเราสังเกตค่าตามลำดับและต้องหยุดที่ค่าใดค่าหนึ่งเท่านั้น ไม่อนุญาตให้ระลึกถึงค่าที่สังเกตได้ก่อนหน้า กฎการหยุดแบบใดที่ทำให้ค่าอันดับที่คาดหวังของค่าที่เลือกมีค่าน้อยที่สุด และค่าที่สอดคล้องกับกฎนั้นคืออะไร${\displaystyle X_{1},\cdots ,X_{n}}$${\displaystyle [0,1]}$${\displaystyle X_{k}}$

วิธีแก้ปัญหาทั่วไปสำหรับปัญหาอันดับที่คาดหวังที่มีข้อมูลครบถ้วนนี้ยังไม่เป็นที่ทราบแน่ชัด ความยากลำบากหลักคือปัญหานี้ขึ้นอยู่กับประวัติอย่างสมบูรณ์ กล่าวคือ กฎที่เหมาะสมที่สุดขึ้นอยู่กับค่าก่อนหน้าทั้งหมดในทุกขั้นตอน ไม่ใช่เพียงแค่สถิติที่เพียงพอที่ง่ายกว่าเท่านั้น มีเพียงขอบเขตที่ทราบสำหรับค่าจำกัดvเมื่อnเข้าสู่ค่าอนันต์ นั่นคือขอบเขตเหล่านี้ได้มาจากการศึกษาที่เรียกว่ากลยุทธ์ไร้ความจำ กล่าวคือ กลยุทธ์ที่การตัดสินใจที่จะหยุดขึ้นอยู่กับค่าของ เท่านั้นไม่ใช่ประวัติการสังเกตเป็นที่ทราบกันว่ามีช่องว่างในการปรับปรุงขอบเขตล่างโดยการคำนวณเพิ่มเติมสำหรับเวอร์ชันที่ตัดทอนของปัญหาภายในกลุ่มของกลยุทธ์ไร้ความจำ ยังไม่เป็นที่ทราบแน่ชัดว่าจะปรับปรุงขอบเขตบนสำหรับค่าจำกัดได้อย่างไร และไม่ว่าจะใช้กลยุทธ์ใดก็ตาม^{[ 3 ] [ 4 ] [ 5 ]}${\displaystyle 1.908<v<2.329}$${\displaystyle X_{k}}$${\displaystyle X_{k}}$${\displaystyle X_{1},\cdots ,X_{k-1}}$

ความพยายามอีกประการหนึ่งที่เสนอเพื่อความก้าวหน้าในปัญหาคือเวอร์ชันเวลาต่อเนื่องของปัญหาที่การสังเกตเป็นไปตามกระบวนการมาถึงแบบปัวซงที่มีอัตราคงที่ 1 ภายใต้สมมติฐานที่ไม่รุนแรงบางประการ ฟังก์ชันค่าที่สอดคล้องกันจะมีขอบเขตและต่อเนื่องแบบลิปชิตซ์ และสมการเชิงอนุพันธ์สำหรับฟังก์ชันค่านี้จะถูกหาได้^{[ 6 ]}ค่าลิมิตของแสดงถึงคำตอบของปัญหาของร็อบบินส์ แสดงให้เห็นว่าสำหรับค่า ขนาดใหญ่การประมาณนี้สอดคล้องกับขอบเขตที่กล่าวถึงข้างต้น ${\displaystyle w(t)}$${\displaystyle w(t)}$${\displaystyle t}$${\displaystyle 1\leq w(t)\leq 2.33183}$

ข้อดีของวิธีการแบบเวลาต่อเนื่องคือ คำตอบสามารถแสดงได้ในรูปของผลเฉลยของสมการเชิงอนุพันธ์ กล่าวคือ คำตอบอยู่ในรูปแบบปิด อย่างไรก็ตาม เนื่องจากสมการเชิงอนุพันธ์ที่ได้นั้น นอกจากฟังก์ชันเป้าหมายแล้ว ยังมีฟังก์ชันที่ไม่ทราบค่าอีกตัวหนึ่ง (ขนาดเล็ก) วิธีการนี้จึงดูเหมือนจะยังไม่ให้ข้อได้เปรียบที่เด็ดขาดในการหาค่าจำกัดที่เหมาะสมที่สุด

Krieger & Samuel-Cahn ได้เสนอกฎย่อยที่ไม่เหมาะสมอย่างง่าย ซึ่งทำงานได้ดีเกือบเท่ากับกฎที่เหมาะสมที่สุดภายในกลุ่มของกฎการหยุดแบบไม่มีหน่วยความจำ^{[ 7 ]}กฎนี้จะหยุดเมื่อมีค่าน้อยที่สุดโดยที่สำหรับค่าคงที่ c ที่กำหนด โดยที่คือลำดับสัมพัทธ์ของการสังเกตที่ i และ n คือจำนวนรายการทั้งหมด กฎนี้มีความยืดหยุ่นเพิ่มขึ้น สามารถใช้เวอร์ชันที่ย่อลงเพื่อเลือกรายการที่มีความน่าจะเป็นที่กำหนดกฎนี้สามารถใช้เพื่อเลือกสองรายการขึ้นไป ปัญหาของการเลือกเปอร์เซ็นต์คงที่ของn ก็ได้รับการพิจารณาเช่นกัน ${\displaystyle i}$${\displaystyle R_{i}<ic/(n+i)}$${\displaystyle R_{i}}$${\displaystyle P}$${\displaystyle P<1}$${\displaystyle \alpha }$${\displaystyle 0<\alpha <1}$

หนึ่งในแรงจูงใจในการศึกษาปัญหาของ Robbins คือ หากสามารถแก้ปัญหานี้ได้ปัญหาเลขานุการ แบบคลาสสิกทั้งสี่ ก็จะได้รับการแก้ไข แต่เหตุผลหลักคือการทำความเข้าใจวิธีการรับมือกับการพึ่งพาประวัติอย่างสมบูรณ์ในปัญหา (ที่ดูเหมือนง่ายแต่ซับซ้อน) ในการประชุมนานาชาติ Ester's Book ที่ประเทศอิสราเอล (2006) ปัญหาของ Robbins จึงได้รับการยกย่องให้เป็นหนึ่งในสี่ปัญหาที่สำคัญที่สุดในสาขาการหยุดที่เหมาะสมและ การ วิเคราะห์ ลำดับ

เฮอร์เบิร์ต ร็อบบินส์นำเสนอปัญหาที่อธิบายไว้ข้างต้นในการประชุมนานาชาติว่าด้วยการค้นหาและการเลือกในเวลาจริง^{[หมายเหตุ 1 ]}ที่เมืองแอมเฮิร์สต์ในปี 1990 เขาปิดท้ายการบรรยายด้วยคำพูดที่ว่า " ผมอยากเห็นปัญหานี้ได้รับการแก้ไขก่อนที่ผมจะตาย"นักวิทยาศาสตร์ที่ทำงานในสาขาการหยุดที่เหมาะสมที่สุดจึงเรียกปัญหานี้ว่าปัญหาของร็อบบินส์น่าเสียดายที่ความปรารถนาของเฮอร์เบิร์ต ร็อบบินส์ ไม่เป็นจริง เขาเสียชีวิตในปี 2001

ปัญหาการหยุดที่เหมาะสมอีกปัญหาหนึ่งที่มีชื่อของ Robbins (และไม่ควรสับสนกับปัญหาของ Robbins) คือเกม Chow–Robbins: ^{[ 8 ] [ 9 ]}

กำหนดให้มีลำดับอนันต์ของตัวแปรสุ่ม อิสระและมีการกระจายเหมือนกัน (IID)ที่มีการแจกแจงแบบจะตัดสินใจอย่างไรว่าจะหยุดเมื่อใด เพื่อให้ได้ค่าเฉลี่ยของตัวอย่างสูงสุด โดยที่ เวลาหยุดคือเวลา ใดความน่าจะเป็นที่จะหยุดในที่สุดต้องเป็น 1 (นั่นคือ คุณไม่สามารถสุ่มตัวอย่างต่อไปโดยไม่หยุดเลย)${\displaystyle X_{1},X_{2},...}$${\displaystyle F}$${\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})}$${\displaystyle n}$

สำหรับการแจกแจงใดๆที่มีโมเมนต์ที่สองจำกัด จะมีกลยุทธ์ที่เหมาะสมที่สุด ซึ่งกำหนดโดยลำดับของตัวเลขกลยุทธ์คือการสุ่มตัวอย่างต่อไปเรื่อยๆจนกว่า^{[ 10 ] [ 11 ]}${\displaystyle F}$${\displaystyle \beta _{1},\beta _{2},...}$${\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})\geq \beta _{n}}$

ถ้าค่าโมเมนต์อันดับสองมีค่าจำกัด หลังจากลบค่าเฉลี่ยและหารด้วยส่วนเบี่ยงเบนมาตรฐานแล้ว เราจะได้การแจกแจงที่มีค่าเฉลี่ยเป็นศูนย์และความแปรปรวนเป็นหนึ่ง ดังนั้นจึงเพียงพอที่จะศึกษาเฉพาะกรณีที่มีค่าโมเมนต์อันดับสองเป็นศูนย์และความแปรปรวนเป็นหนึ่งเท่านั้น ${\displaystyle F}$${\displaystyle F}$

ด้วยเหตุนี้จึงเป็นคำตอบของสมการ^{[หมายเหตุ 2 ]}ซึ่งสามารถพิสูจน์ได้โดยการแก้ปัญหาเดียวกันในเวลาต่อเนื่องด้วยกระบวนการ Wienerเมื่อถึงขีดจำกัดของปัญหาเวลาไม่ต่อเนื่องจะกลายเป็นปัญหาเวลาต่อเนื่องเช่นเดียวกัน ${\displaystyle \lim _{n}\beta _{n}/{\sqrt {n}}\approx \alpha =0.8399236757}$${\displaystyle \alpha }$$${\displaystyle \alpha =\left(1-\alpha ^{2}\right)\int _{0}^{\infty }e^{\lambda \alpha -\lambda ^{2}/2}d\lambda }$$${\displaystyle n\to \infty }$

สิ่งนี้ได้รับการพิสูจน์โดยอิสระ^{[ 12 ]}โดย^{[ 13 ] [ 14 ] [ 15 ]}

เมื่อเกมเป็นการ โยน เหรียญที่ยุติธรรมโดยหัวเป็น +1 และก้อยเป็น -1 ผลลัพธ์ที่ได้จะคมชัดกว่า^{[ 9 ]}โดยที่ฟังก์ชันซีตาของรีมันน์ $${\displaystyle \beta _{n}=\alpha {\sqrt {n}}-1/2+{\frac {(-2\zeta (-1/2)){\sqrt {\alpha }}}{\sqrt {\pi }}}n^{-1/4}+O\left(n^{-7/24}\right)}$$${\displaystyle \zeta }$

เมื่อnมีค่าเล็ก ขอบเขตเชิงอะซิมโทติกจะไม่สามารถใช้ได้ และการหาค่าของจะยากขึ้นมาก แม้แต่กรณีที่ง่ายที่สุด ซึ่งเป็นการโยนเหรียญที่ยุติธรรม ก็ยังไม่สามารถหาคำตอบได้อย่างสมบูรณ์ ${\displaystyle \beta _{n}}$${\displaystyle X_{1},X_{2},...}$

สำหรับการโยนเหรียญที่ยุติธรรม กลยุทธ์เป็นการตัดสินใจแบบไบนารี: หลังจากโยนเหรียญแล้ว ได้หัว k ครั้ง และก้อย (nk) ครั้ง ควรดำเนินการต่อหรือควรหยุด? เนื่องจากการเดินสุ่ม แบบ 1 มิติ เป็นแบบวนซ้ำ เริ่มต้นที่จุดใดๆความน่าจะเป็นที่จะมีหัวมากกว่าก้อยในท้ายที่สุดคือ 1 ดังนั้น ถ้าควรดำเนินการต่อเสมอ อย่างไรก็ตาม ถ้าเป็นการยากที่จะตัดสินใจว่าจะหยุดหรือดำเนินการต่อ^{[ 16 ]}${\displaystyle n}$${\displaystyle k,(n-k)}$${\displaystyle k\leq n-k}$${\displaystyle k>n-k}$

^{[ 17 ]}พบวิธีแก้ปัญหาที่แน่นอนสำหรับทั้งหมด ${\displaystyle n\leq 489241}$

เอลตัน^{[ 9 ]}พบวิธีแก้ปัญหาที่แม่นยำสำหรับทุกอย่างและพบ กฎ การตัดสินใจที่เหมาะสมที่สุด เกือบตลอดเวลา คือการหยุดทันทีที่${\displaystyle n\leq 9.06\times 10^{7}}$${\displaystyle k-(n-k)\geq \Delta k_{n}}$$${\displaystyle \Delta k_{n}=\left\lceil {\alpha {\sqrt {n}}\,\,-1/2\,\,+\,\,{\frac {\left({-2\zeta (-1/2)}\right){\sqrt {\alpha }}}{\sqrt {\pi }}}{n^{-1/4}}}\right\rceil }$$