การเดินสุ่มแบบกระโดดไปข้างหน้าบนกราฟวงรอบและเวลาการถึงเป้าหมาย

ปัญหาที่งานวิจัยแก้ไข

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

ผู้ได้รับประโยชน์:

• นักวิจัยด้านความน่าจะเป็นและกระบวนการสุ่ม
• ผู้เชี่ยวชาญทฤษฎีกราฟและคณิตศาสตร์เชิงการจัด
• นักวิเคราะห์เครือข่ายและวงจรไฟฟ้า
• ผู้สอนและนักพัฒนาแบบจำลอง

วิธีการ

บนวงรอบที่มี d สถานะ แต่ละก้าวเป็นการกระโดดไปข้างหน้าอิสระ X ในเซต {1,...,m} ด้วยความน่าจะเป็นสม่ำเสมอ งานวิจัยนับเส้นทางเพื่อสร้างฟังก์ชันมวลความน่าจะเป็นของสถานะปลายทางในรูปจำนวนเชิงซ้อน ผลบวกตรีโกณมิติ และสูตรเชิงการจัดหมู่ จากนั้นใช้ความสัมพันธ์เวียนเกิดและฟังก์ชันก่อกำเนิดความน่าจะเป็นเพื่อหาการแจกแจงเวลาการถึงเป้าหมายครั้งแรก ค่าคาดหมาย และความแปรปรวนแบบแม่นตรง พร้อมสาธิตด้วยเกมกระดานวงรอบ 12 สถานะ

ผลการศึกษา

การแจกแจงสถานะปลายทางเข้าใกล้การแจกแจงสม่ำเสมอเร็วขึ้นเมื่อขีดจำกัดการกระโดด m หรือจำนวนก้าว n เพิ่มขึ้น และสม่ำเสมอทันทีเมื่อ m=d สำหรับการทดลองที่ d=12 ค่าคาดหมายของเวลาการถึงเป้าหมายอยู่ระหว่าง 7.75 ถึง 12 ก้าว โดย m=4 เร็วที่สุดและ m=12 นานที่สุด โดยทั่วไปการอนุญาตให้กระโดดไกลขึ้นเพิ่มทั้งค่าเฉลี่ยและความแปรปรวนของเวลาการถึงเป้าหมาย ขณะที่ขนาดกราฟมีอิทธิพลค่อนข้างน้อยในกรณีที่ศึกษา