ในการเขียนโปรแกรมเชิงสุ่ม ช่องว่าง ความสัมพันธ์คืออัตราส่วนกรณีที่เลวร้ายที่สุดระหว่างต้นทุนเมื่อตัวแปรสุ่มมีความสัมพันธ์กันกับต้นทุนเมื่อตัวแปรสุ่มเป็นอิสระต่อกัน^{[ 1 ]}

ตัวอย่างเช่น^{[ 1 ] : 6} พิจารณาปัญหาการหาค่าเหมาะสมที่สุดต่อไปนี้ ครูต้องการทราบว่าควรมาสอนหรือไม่ มี นักเรียนที่เป็นไปได้ nคน สำหรับนักเรียนแต่ละคน มีความน่าจะเป็น 1/ nที่นักเรียนจะมาเรียน หากมีนักเรียนมาเรียนอย่างน้อยหนึ่งคน ครูจะต้องมาสอนและค่าใช้จ่ายของครูคือ 1 หากไม่มีนักเรียนมาเรียนเลย ครูสามารถอยู่บ้านได้และค่าใช้จ่ายของครูคือ 0 เป้าหมายของครูคือการทำให้ค่าใช้จ่ายของเขาน้อยที่สุด นี่คือปัญหาการเขียนโปรแกรมเชิงสุ่ม เนื่องจากข้อจำกัดไม่ได้ทราบล่วงหน้า – รู้เพียงความน่าจะเป็นของข้อจำกัดเท่านั้น ตอนนี้มีสองกรณีเกี่ยวกับความสัมพันธ์ระหว่างนักเรียน:

• กรณีที่ 1: นักเรียนไม่มีความสัมพันธ์กัน: นักเรียนแต่ละคนตัดสินใจว่าจะมาเรียนหรือไม่โดยการโยนเหรียญด้วยความน่าจะเป็นโดยเป็นอิสระจากผู้อื่น ต้นทุนที่คาดหวังในกรณีนี้คือ${\displaystyle 1/n}$${\displaystyle 1-(1-1/n)^{n}\approx 1-1/e}$
• กรณีที่ 2: นักเรียนมีความสัมพันธ์กัน กล่าวคือ นักเรียนหนึ่งคนถูกสุ่มเลือกให้มาเรียน ในขณะที่คนอื่นๆ อยู่บ้าน โปรดทราบว่าความน่าจะเป็นที่นักเรียนแต่ละคนจะมาเรียนยังคงเป็น 0 อย่างไรก็ตาม ในกรณีนี้ค่าใช้จ่ายคือ 1${\displaystyle 1/n}$

ช่องว่างความสัมพันธ์คือต้นทุนในกรณีที่ 2 หารด้วยต้นทุนในกรณีที่ 1 ซึ่งก็คือ. ${\displaystyle e/(e-1)}$

^{[ 1 ]}พิสูจน์ว่าช่องว่างความสัมพันธ์มีขอบเขตในหลายกรณี ตัวอย่างเช่น เมื่อฟังก์ชันต้นทุนเป็นฟังก์ชันเซตย่อยโมดูลาร์(ดังตัวอย่างข้างต้น) ช่องว่างความสัมพันธ์จะมีค่าสูงสุดเพียง(ดังนั้นตัวอย่างข้างต้นจึงเป็นกรณีที่เลวร้ายที่สุด) ${\displaystyle e/(e-1)}$

ขอบเขตบนของช่องว่างความสัมพันธ์หมายถึงขอบเขตบนของความสูญเสียที่เกิดจากการละเลยความสัมพันธ์นั้น ตัวอย่างเช่น สมมติว่าเรามีปัญหาการเขียนโปรแกรมเชิงสุ่มที่มีฟังก์ชันต้นทุนแบบซับโมดูลาร์ เราทราบความน่าจะเป็นส่วนต่างของตัวแปร แต่เราไม่ทราบว่าตัวแปรเหล่านั้นมีความสัมพันธ์กันหรือไม่ หากเราละเลยความสัมพันธ์และแก้ปัญหาเสมือนว่าตัวแปรเป็นอิสระต่อกัน ผลลัพธ์ที่ได้จะเป็นการประมาณค่า -approximation ของคำตอบที่เหมาะสมที่สุด ${\displaystyle (e-1)/e}$

ช่องว่างความสัมพันธ์ถูกใช้เพื่อจำกัดการสูญเสียรายได้เมื่อใช้การกำหนดราคาที่เหมาะสมแบบเบย์เซียนแทนการประมูลที่เหมาะสมแบบเบย์เซียน^{[ 2 ]}

• การเพิ่มประสิทธิภาพที่แข็งแกร่ง
• ทฤษฎีการตัดสินใจช่องว่างข้อมูล