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

มีความแตกต่างระหว่างอัลกอริธึมที่ใช้ข้อมูลป้อนเข้าแบบสุ่มเพื่อให้ได้คำตอบที่ถูกต้องเสมอ แต่เวลาในการทำงานที่คาดหวังนั้นมีจำกัด (เช่นอัลกอริธึมลาสเวกัสเช่นควิกซอร์ต^{[ 1 ]} ) และอัลกอริธึมที่มีโอกาสให้ผลลัพธ์ที่ไม่ถูกต้อง ( เช่น อัลกอริธึมมอนเตคาร์โลเช่น อัลกอริธึมมอนเตคาร์โลสำหรับปัญหาMFAS ^{[ 2 ]} ) หรือล้มเหลวในการสร้างผลลัพธ์ไม่ว่าจะโดยการส่งสัญญาณความล้มเหลวหรือล้มเหลวในการสิ้นสุด ในบางกรณี อัลกอริธึมเชิงความน่าจะเป็นเป็นวิธีการเดียวที่ใช้งานได้จริงในการแก้ปัญหา^{[ 3 ]}

ในทางปฏิบัติทั่วไป อัลกอริทึมแบบสุ่มมักจะใช้ตัวสร้างเลขสุ่มเทียมแทนแหล่งกำเนิดบิตสุ่มที่แท้จริง ซึ่งการใช้งานในลักษณะนี้อาจเบี่ยงเบนจากพฤติกรรมทางทฤษฎีและข้อรับประกันทางคณิตศาสตร์ที่คาดหวังไว้ ซึ่งอาจขึ้นอยู่กับการมีอยู่ของตัวสร้างเลขสุ่มที่แท้จริงในอุดมคติ

เพื่อเป็นตัวอย่างกระตุ้นความคิด ลองพิจารณาปัญหาการค้นหาค่า ' a ' ในอาร์เรย์ที่มีองค์ประกอบ n ตัว

อินพุต : อาร์เรย์ที่มี องค์ประกอบ n ≥ 2 ตัว โดยครึ่งหนึ่งเป็น ' a ' และอีกครึ่งหนึ่งเป็น ' b '

ผลลัพธ์ : ค้นหาตัวอักษร ' a ' ในอาร์เรย์

เราได้นำเสนออัลกอริทึมสองเวอร์ชัน ได้แก่อัลกอริทึมลาสเวกัสและอัลกอริทึมมอนเตคาร์โล

อัลกอริทึมลาสเวกัส:

findingA_LV ( array A , n ) begin repeat สุ่มเลือกองค์ประกอบหนึ่งตัวจากn องค์ประกอบจนกว่าจะพบ'a ' end

อัลกอริทึมนี้สำเร็จด้วยความน่าจะเป็น 1 จำนวนรอบการทำซ้ำจะแตกต่างกันไปและสามารถมีขนาดใหญ่ได้ตามต้องการ แต่จำนวนรอบการทำซ้ำโดยเฉลี่ยคือ

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

เนื่องจากเป็นค่าคงที่ เวลาการทำงานโดยเฉลี่ยเมื่อเรียกใช้งานหลายครั้งจึงเป็น. (ดูสัญลักษณ์ Big Theta ) ${\displaystyle \Theta (1)}$

อัลกอริทึมมอนเตคาร์โล:

findingA_MC ( array A , n , k ) begin i := 0 repeat สุ่มเลือกองค์ประกอบหนึ่งตัวจากn องค์ประกอบi : = i + 1 จนกว่าi = k หรือพบ'a ' end

ถ้า พบตัวอักษร' a ' แสดงว่าอัลกอริทึมทำงานสำเร็จ มิฉะนั้นอัลกอริทึมจะล้มเหลว หลังจากวนซ้ำ kครั้ง ความน่าจะเป็นที่จะพบตัวอักษร ' a ' คือ:

อัลกอริทึมนี้ไม่รับประกันความสำเร็จ แต่เวลาในการทำงานมีขอบเขตจำกัด จำนวนรอบการทำซ้ำจะน้อยกว่าหรือเท่ากับ k เสมอ เมื่อกำหนดให้ k เป็นค่าคงที่ เวลาในการทำงาน (ทั้งที่คาดหวังและแบบสัมบูรณ์) คือ. ${\displaystyle \Theta (1)}$

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

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

ทฤษฎีความซับซ้อนของการคำนวณจำลองอัลกอริทึมแบบสุ่มเป็นเครื่องจักรทัวริงเชิงความน่าจะเป็น มีการพิจารณาทั้ง อัลกอริทึม ลาสเวกั ส และมอนเตคาร์โล และมีการศึกษา คลาสความซับซ้อน หลายประเภท คลาส ความซับซ้อนแบบสุ่มพื้นฐานที่สุดคือRPซึ่งเป็นคลาสของปัญหาการตัดสินใจที่มีอัลกอริทึมแบบสุ่มที่มีประสิทธิภาพ (เวลาพหุนาม) (หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น) ซึ่งรู้จักกรณีที่เป็น NO ด้วยความแน่นอนอย่างสมบูรณ์ และรู้จักกรณีที่เป็น YES ด้วยความน่าจะเป็นอย่างน้อย 1/2 คลาสส่วนเติมเต็มของ RP คือ co-RP คลาสปัญหาที่มีอัลกอริทึม (อาจไม่สิ้นสุด) ที่มี เวลาการทำงานเฉลี่ยเป็น พหุนามและ ผลลัพธ์ถูกต้องเสมอเรียกว่าอยู่ในZPP

กลุ่มปัญหาที่อนุญาตให้ระบุทั้งคำตอบ "ใช่" และ "ไม่ใช่" ได้โดยมีข้อผิดพลาดบ้าง เรียกว่าBPP ( Browser Process) กลุ่มปัญหานี้เปรียบเสมือนP ในรูปแบบสุ่ม กล่าว คือ BPP เป็นตัวแทนของกลุ่มอัลกอริธึมแบบสุ่มที่มีประสิทธิภาพ

อัลกอริทึม QuickSortถูกค้นพบโดยTony Hoareในปี พ.ศ. 2492 และตีพิมพ์เผยแพร่ในเวลาต่อมาในปี พ.ศ. 2504 ^{[ 4 ]}ในปีเดียวกันนั้น Hoare ได้ตีพิมพ์อัลกอริทึม QuickSelect [ ^{5 ] ซึ่ง}ค้นหาองค์ประกอบค่ามัธยฐานของรายการในเวลาเชิงเส้นที่คาดหวัง จนถึงปี พ.ศ. 2516 ยังคงเป็นที่ถกเถียงกันอยู่ว่ามีอัลกอริทึมเชิงเส้นแบบกำหนดได้หรือไม่^{[ 6 ]}

ในปี พ.ศ. 2460 Henry Cabourn Pocklingtonได้นำเสนออัลกอริทึมแบบสุ่มที่เรียกว่าอัลกอริทึมของ Pocklingtonสำหรับการค้นหารากที่สอง ของ โมดูลัสจำนวนเฉพาะ อย่างมีประสิทธิภาพ ^{[ 7 ]} ในปี พ.ศ. 2513 Elwyn Berlekampได้นำเสนออัลกอริทึมแบบสุ่มสำหรับการคำนวณรากของพหุนามเหนือฟิลด์จำกัดอย่างมีประสิทธิภาพ^{[ 8 ]}ในปี พ.ศ. 2520 Robert M. SolovayและVolker Strassen ได้ค้นพบ การทดสอบความเป็นจำนวนเฉพาะแบบสุ่มในเวลาพหุ นาม (เช่น การกำหนดความเป็นจำนวนเฉพาะของจำนวน) ไม่นานหลังจากนั้นMichael O. Rabin ได้แสดงให้เห็นว่า การทดสอบความเป็นจำนวนเฉพาะของ Millerในปี พ.ศ. 2519 สามารถเปลี่ยนเป็นอัลกอริทึมแบบสุ่มในเวลาพหุนามได้เช่นกัน ในขณะนั้น ยังไม่มีอัลกอริทึมเชิงกำหนดที่ พิสูจน์ได้ว่าใช้เวลาพหุนาม สำหรับการทดสอบความเป็นจำนวนเฉพาะ

หนึ่งในโครงสร้างข้อมูลแบบสุ่มที่เก่าแก่ที่สุดคือตารางแฮช ซึ่ง Hans Peter LuhnจากIBMได้แนะนำในปี 1953 [ ^{9 ] ตาราง}แฮชของ Luhn ใช้การเชื่อมโยงเพื่อแก้ไขการชนกัน และยังเป็นหนึ่งในแอปพลิเคชันแรกๆ ของรายการเชื่อมโยง อีก ด้วย^{[ 9 ]}ต่อมาในปี 1954 Gene Amdahl , Elaine M. McGraw , Nathaniel RochesterและArthur SamuelจากIBM Researchได้แนะนำการสอบถามเชิงเส้น^{[ 9 ]}แม้ว่าAndrey Ershovจะมีแนวคิดเดียวกันนี้โดยอิสระในปี 1957 ^{[ 9 ]}ในปี 1962 Donald Knuthได้ทำการวิเคราะห์การสอบถามเชิงเส้นอย่างถูกต้องเป็นครั้งแรก^{[ 9 ]}แม้ว่าบันทึกที่มีการวิเคราะห์ของเขาจะไม่ได้ถูกตีพิมพ์จนกระทั่งอีกนานต่อมา^{[ 10 ]}การวิเคราะห์ที่ตีพิมพ์ครั้งแรกเป็นผลงานของ Konheim และ Weiss ในปี 1966 ^{[ 11 ]}

งานในช่วงแรกเกี่ยวกับตารางแฮชนั้นสันนิษฐานว่าสามารถเข้าถึงฟังก์ชันแฮชแบบสุ่มได้อย่างสมบูรณ์ หรือสันนิษฐานว่าคีย์เองก็เป็นแบบสุ่ม^{[ 9 ]}ในปี พ.ศ. 2522 คาร์เตอร์และเวกแมนได้แนะนำฟังก์ชันแฮชสากล [ ^{12 ] ซึ่งพวกเขาแสดงให้เห็น ว่า}สามารถใช้ในการสร้างตารางแฮชแบบลูกโซ่โดยมีเวลาเฉลี่ยคงที่ต่อการดำเนินการ

งานวิจัยในช่วงแรกเกี่ยวกับโครงสร้างข้อมูลแบบสุ่มยังขยายไปไกลกว่าตารางแฮช ในปี 1970 Burton Howard Bloom ได้นำเสนอโครงสร้างข้อมูลสมาชิกโดยประมาณที่เรียกว่าBloom filter ^{[ 13 ]}ในปี 1989 Raimund SeidelและCecilia R. Aragonได้นำเสนอต้นไม้ค้นหาแบบสมดุลแบบสุ่มที่เรียกว่าtreap [ ^{14 ]}ในปีเดียวกันนั้น William Pughได้นำเสนอต้นไม้ค้นหาแบบสุ่มอีกแบบหนึ่งที่เรียก^{ว่าskip} list [ ^{15 ]}

ก่อนที่อัลกอริธึมแบบสุ่มจะแพร่หลายในวิทยาศาสตร์คอมพิวเตอร์Paul Erdősได้ทำให้การใช้การสร้างแบบสุ่มเป็นเทคนิคทางคณิตศาสตร์เพื่อพิสูจน์การมีอยู่ของวัตถุทางคณิตศาสตร์เป็นที่นิยม เทคนิคนี้กลายเป็นที่รู้จักในชื่อวิธีการเชิงความน่าจะเป็น [ ^{16 ] Erdős}ได้นำวิธีการเชิงความน่าจะเป็นมาประยุกต์ใช้ครั้งแรกในปี 1947 โดยใช้การสร้างแบบสุ่มอย่างง่ายเพื่อพิสูจน์การมีอยู่ของกราฟ Ramsey ^{[ 17 ]}เขาได้ใช้อัลกอริธึมแบบสุ่มที่ซับซ้อนกว่าในปี 1959 เพื่อพิสูจน์การมีอยู่ของกราฟที่มีเส้นรอบวงและจำนวนสีสูง^{[ 18 ] [ 16 ]}

QuickSortเป็นอัลกอริทึมที่คุ้นเคยและใช้กันทั่วไป ซึ่งความสุ่มสามารถเป็นประโยชน์ได้ อัลกอริทึมเวอร์ชันเชิงกำหนดหลายเวอร์ชันต้องการ เวลา O ( n² ⁾ในการเรียง ลำดับตัวเลข nตัวสำหรับกลุ่มอินพุตที่กำหนดไว้อย่างชัดเจน (เช่น อาร์เรย์ที่เรียงลำดับแล้ว) โดยกลุ่มอินพุตเฉพาะที่ทำให้เกิดพฤติกรรมนี้จะถูกกำหนดโดยโปรโตคอลสำหรับการเลือกตัวหลัก อย่างไรก็ตาม หากอัลกอริทึมเลือกองค์ประกอบตัวหลักแบบสุ่มอย่างสม่ำเสมอ จะมีโอกาสสูงที่จะเสร็จสิ้นใน เวลา O ( n  log  n ) โดยไม่คำนึงถึงลักษณะของอินพุต

ในเรขาคณิตเชิงคำนวณเทคนิคมาตรฐานในการสร้างโครงสร้าง เช่นconvex hullหรือDelaunay triangulationคือการสลับตำแหน่งจุดอินพุตแบบสุ่ม แล้วแทรกจุดเหล่านั้นทีละจุดลงในโครงสร้างที่มีอยู่ การสุ่มทำให้มั่นใจได้ว่าจำนวนการเปลี่ยนแปลงที่คาดหวังของโครงสร้างที่เกิดจากการแทรกนั้นน้อย ดังนั้นเวลาการทำงานที่คาดหวังของอัลกอริทึมจึงสามารถจำกัดจากด้านบนได้ เทคนิคนี้เรียกว่าการสร้างแบบเพิ่มทีละน้อยแบบสุ่ม^{[ 19 ]}

อินพุต : กราฟG ( V , E )

ผลลัพธ์ : การตัดแบ่งจุดยอดออกเป็นLและRโดยมีจำนวนขอบน้อยที่สุดระหว่าง LและR

โปรดจำไว้ว่า การยุบรวมโหนดสองโหนดuและvในกราฟ (หลายโหนด) จะได้โหนดใหม่u ' ซึ่งมีขอบที่เป็นผลรวมของขอบที่เชื่อมต่อกับuหรือvยกเว้นขอบที่เชื่อมต่อระหว่างuและvรูปที่ 1 แสดงตัวอย่างการยุบรวมจุดยอดAและBหลังจากการยุบรวม กราฟที่ได้อาจมีขอบขนาน แต่ไม่มีวงวนในตัวเอง

อัลกอริทึมพื้นฐาน ของ Karger ^{[ 20 ]}

เริ่ม i = 1 ทำซ้ำทำซ้ำ เลือกขอบแบบสุ่ม (u,v) ∈ E ใน G แทนที่ u และ v ด้วยคำย่อ u' จนกระทั่งเหลือเพียง 2 โหนด รับผลลัพธ์การตัดที่สอดคล้องกัน C i i = i + 1 จนกระทั่ง i = m แสดงผลการตัดขั้นต่ำระหว่าง C 1 , C 2 , ..., C m . end

ในการทำงานของลูปภายนอกแต่ละครั้ง อัลกอริทึมจะทำซ้ำลูปภายในจนกว่าจะเหลือโหนดเพียง 2 โหนด ซึ่งจะได้ค่าการตัดที่สอดคล้องกัน เวลาในการทำงานของการทำงานหนึ่งครั้งคือและnแทนจำนวนจุดยอด หลังจาก การทำงานของลูปภายนอก mครั้ง เราจะแสดงค่าการตัดที่เล็กที่สุดในบรรดาผลลัพธ์ทั้งหมด รูปที่ 2 แสดงตัวอย่างการทำงานของอัลกอริทึมหนึ่งครั้ง หลังจากการทำงาน เราจะได้ค่าการตัดที่มีขนาด 3 ${\displaystyle O(n)}$

ความน่าจะเป็นที่อัลกอริทึมจะสำเร็จคือ 1 ลบด้วยความน่าจะเป็นที่ความพยายามทั้งหมดล้มเหลว เนื่องจากความเป็นอิสระ ความน่าจะเป็นที่ความพยายามทั้งหมดล้มเหลวคือ $${\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}$$

จากเลมมาที่ 1 ความน่าจะเป็นที่C _i = Cคือความน่าจะเป็นที่ไม่มีขอบใดของCถูกเลือกในระหว่างการวนซ้ำครั้งที่ iพิจารณาลูปภายในและให้G _jแทนกราฟหลังจากมีการหดตัวของขอบj ครั้ง โดยที่ j ∈ {0, 1, …, n − 3} G j _มีจุด ยอด n − jจุด เราใช้กฎลูกโซ่ของความเป็นไปได้แบบมีเงื่อนไข ความน่าจะเป็นที่ขอบที่เลือกในการวนซ้ำครั้งที่jไม่อยู่ในCเมื่อกำหนดว่าไม่มีขอบใดของCถูกเลือกมาก่อน คือโปรดทราบว่าG _jยังคงมี min cut ที่มีขนาดk ดังนั้นจากเลมมาที่ 2 มันจึงยังคงมี ขอบ อย่างน้อย${\displaystyle 1-{\frac {k}{|E(G_{j})|}}}$${\displaystyle {\frac {(nj)k}{2}}}$

ดังนั้น, . ${\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{nj}}={\frac {nj-2}{nj}}}$

ดังนั้นตามกฎลูกโซ่ ความน่าจะเป็นที่จะพบค่าตัดต่ำสุดCคือ $${\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}$$

การยกเลิกทำให้ได้ดังนั้นความน่าจะเป็นที่อัลกอริทึมจะสำเร็จอย่างน้อยที่สุดคือสำหรับสิ่งนี้เทียบเท่ากับอัลกอริทึมจะค้นหา min cut ด้วยความน่าจะเป็นในเวลา ${\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}$${\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}$${\displaystyle m={\frac {n(n-1)}{2}}\ln n}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle O(mn)=O(n^{3}\log n)}$

ความสุ่มสามารถมองได้ว่าเป็นทรัพยากร เช่นเดียวกับพื้นที่และเวลา การลดความสุ่มจึงเป็นกระบวนการของการกำจัดความสุ่ม (หรือใช้ให้น้อยที่สุดเท่าที่จะเป็นไปได้) ^{[ 21 ] [ 22 ]}ปัจจุบันยังไม่เป็นที่ทราบแน่ชัดว่าอัลกอริธึมทั้งหมดสามารถลดความสุ่มได้โดยไม่ทำให้เวลาในการทำงานเพิ่มขึ้นอย่างมีนัยสำคัญหรือไม่^{[ 23 ]}ตัวอย่างเช่น ในความซับซ้อนของการคำนวณยังไม่ทราบว่าP = BPPหรือ ไม่ ^{[ 23 ]}กล่าวคือ เราไม่ทราบว่าเราสามารถนำอัลกอริธึมแบบสุ่มใดๆ ที่ทำงานในเวลาพหุนามด้วยความน่าจะเป็นของข้อผิดพลาดเล็กน้อย และลดความสุ่มเพื่อให้ทำงานในเวลาพหุนามโดยไม่ต้องใช้ความสุ่มได้หรือไม่

มีวิธีการเฉพาะที่สามารถนำมาใช้เพื่อลดความเป็นสุ่มของอัลกอริทึมแบบสุ่มบางอย่างได้:

• วิธีการของความน่าจะเป็นแบบมีเงื่อนไขและการขยายความของวิธีการนี้ รวมถึงตัวประมาณค่าแบบมองโลกในแง่ร้าย
• ทฤษฎีความคลาดเคลื่อน (ซึ่งใช้ในการลดความสุ่มของอัลกอริทึมทางเรขาคณิต)
• การใช้ประโยชน์จากความเป็นอิสระที่จำกัดในตัวแปรสุ่มที่ใช้โดยอัลกอริทึม เช่นความเป็นอิสระแบบคู่ที่ใช้ในการแฮชแบบสากล^{[ 24 ]}
• การใช้กราฟขยาย (หรือตัวกระจายโดยทั่วไป) เพื่อขยายความสุ่มเริ่มต้นที่มีอยู่อย่างจำกัด (แนวทางสุดท้ายนี้เรียกอีกอย่างว่าการสร้าง บิต สุ่มเทียมจากแหล่งกำเนิดสุ่ม และนำไปสู่หัวข้อที่เกี่ยวข้องกับความสุ่มเทียม)
• การเปลี่ยนอัลกอริธึมแบบสุ่มให้ใช้ฟังก์ชันแฮชเป็นแหล่งกำเนิดความสุ่มสำหรับงานของอัลกอริธึม จากนั้นจึงทำการลดความสุ่มของอัลกอริธึมโดยการค้นหาค่าพารามิเตอร์ (seed) ที่เป็นไปได้ทั้งหมดของฟังก์ชันแฮชด้วยวิธีแบบบรูทฟอร์ซ เทคนิคนี้มักใช้ในการค้นหาพื้นที่ตัวอย่างอย่างครบถ้วนและทำให้อัลกอริธึมเป็นแบบกำหนดได้ (เช่น อัลกอริธึมกราฟแบบสุ่ม)

เมื่อแบบจำลองการคำนวณถูกจำกัดไว้ที่เครื่องจักรทัวริงปัจจุบันยังเป็นคำถามที่เปิดกว้างอยู่ว่า ความสามารถในการเลือกแบบสุ่มจะช่วยให้สามารถแก้ปัญหาบางอย่างได้ในเวลาพหุนาม ซึ่งไม่สามารถแก้ไขได้ในเวลาพหุนามหากปราศจากความสามารถนี้หรือไม่ นี่คือคำถามที่ว่า P = BPP หรือไม่ อย่างไรก็ตาม ในบริบทอื่นๆ มีตัวอย่างเฉพาะของปัญหาที่การสุ่มให้ผลลัพธ์ที่ดีขึ้นอย่างเห็นได้ชัด

• จากตัวอย่างเริ่มต้นที่กระตุ้นให้เกิดความคิด: เมื่อกำหนดสตริงที่มีความยาวแบบเลขชี้กำลัง 2k ^ตัวอักษร โดยครึ่งหนึ่งเป็น a และอีกครึ่งหนึ่งเป็น b เครื่องจักรแบบเข้าถึงแบบสุ่มจะต้องใช้การค้นหา 2k ^{−1ครั้ง}ในกรณีที่เลวร้ายที่สุดเพื่อหาดัชนีของaหากอนุญาตให้เลือกแบบสุ่ม เครื่องจักรจะสามารถแก้ปัญหานี้ได้ในจำนวนการค้นหาที่คาดหวังเป็นพหุนาม
• วิธีการตามธรรมชาติในการดำเนินการคำนวณเชิงตัวเลขในระบบฝังตัวหรือระบบไซเบอร์-กายภาพคือการให้ผลลัพธ์ที่ประมาณค่าผลลัพธ์ที่ถูกต้องด้วยความน่าจะเป็นสูง (หรือการคำนวณที่ถูกต้องโดยประมาณที่น่าจะเป็นไปได้ (PACC)) ปัญหาที่ยากที่เกี่ยวข้องกับการประเมินการสูญเสียความคลาดเคลื่อนระหว่างการคำนวณโดยประมาณและการคำนวณที่ถูกต้องสามารถแก้ไขได้อย่างมีประสิทธิภาพโดยการใช้การสุ่ม^{[ 25 ]}
• ในความซับซ้อนของการสื่อสารความเท่าเทียมกันของสตริงสองสตริงสามารถตรวจสอบได้ด้วยความน่าเชื่อถือในระดับหนึ่งโดยใช้บิตของการสื่อสารด้วยโปรโตคอลแบบสุ่ม โปรโตคอลแบบกำหนดใดๆ ก็ตามต้องการบิตหากป้องกันคู่ต่อสู้ที่แข็งแกร่ง^{[ 26 ]}${\displaystyle \log n}$${\displaystyle \Theta (n)}$
• ปริมาตรของวัตถุนูนสามารถประมาณได้ด้วยอัลกอริทึมแบบสุ่มด้วยความแม่นยำตามอำเภอใจในเวลาพหุนาม^{[ 27 ]} BárányและFürediแสดงให้เห็นว่าไม่มีอัลกอริทึมแบบกำหนดที่สามารถทำเช่นเดียวกันได้^{[ 28 ]}นี่เป็นความจริงโดยไม่มีเงื่อนไข กล่าวคือโดยไม่ต้องอาศัยสมมติฐานทางทฤษฎีความซับซ้อนใดๆ โดยถือว่าวัตถุนูนสามารถสอบถามได้เฉพาะในฐานะกล่องดำเท่านั้น
• ตัวอย่างเชิงทฤษฎีที่ซับซ้อนกว่าของสถานที่ที่ความสุ่มดูเหมือนจะช่วยได้คือคลาสIP IP ประกอบด้วยภาษาทั้งหมดที่สามารถยอมรับได้ (ด้วยความน่าจะเป็นสูง) โดยการโต้ตอบที่ยาวพอลินอมิอัลระหว่างผู้พิสูจน์ที่ทรงพลังทั้งหมดและผู้ตรวจสอบที่ใช้ขั้นตอนวิธี BPP IP = PSPACE ^{[ 29 ]} อย่างไรก็ตาม หากจำเป็นต้อง ให้ผู้ตรวจสอบเป็นแบบกำหนดได้ IP = NP
• ในเครือข่ายปฏิกิริยาเคมี (ชุดปฏิกิริยาที่จำกัด เช่น A+B → 2C + D ที่ดำเนินการกับโมเลกุลจำนวนจำกัด) ความสามารถในการไปถึงสถานะเป้าหมายที่กำหนดจากสถานะเริ่มต้นสามารถตัดสินได้ ในขณะที่แม้แต่การประมาณความน่าจะเป็นของการไปถึงสถานะเป้าหมายที่กำหนด (โดยใช้ความน่าจะเป็นตามความเข้มข้นมาตรฐานสำหรับปฏิกิริยาที่จะเกิดขึ้นต่อไป) ก็ไม่สามารถตัดสินได้ โดยเฉพาะอย่างยิ่ง เครื่องจักรทัวริงแบบจำกัดสามารถจำลองได้ด้วยความน่าจะเป็นสูงตามอำเภอใจที่จะทำงานได้อย่างถูกต้องตลอดเวลา ก็ต่อเมื่อใช้เครือข่ายปฏิกิริยาเคมีแบบสุ่มเท่านั้น ด้วยเครือข่ายปฏิกิริยาเคมีแบบไม่กำหนดอย่างง่าย (ปฏิกิริยาใดๆ ก็สามารถเกิดขึ้นต่อไปได้) พลังการคำนวณจะถูกจำกัดไว้ที่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม^{[ 30 ]}

• อัลกอริทึมการนับโดยประมาณ
• อัลกอริทึมแอตแลนติกซิตี้
• โบโกซอร์ท
• นับ-นาที สเก็ตช์
• ไฮเปอร์ล็อกล็อก
• อัลกอริทึมของคาร์เกอร์
• อัลกอริทึมลาสเวกัส
• อัลกอริทึมมอนเตคาร์โล
• หลักการตัดสินใจแบบเลื่อนออกไป
• การวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึม
• แผนงานเชิงความน่าจะเป็น
• อัลกอริทึมแบบสุ่มในฐานะเกมผลรวมเป็นศูนย์