ในทางคณิตศาสตร์ การเดินสุ่มแบบลบวงวน ( loop-erased random walk)เป็นแบบจำลองของเส้นทางสุ่มแบบง่าย ที่มีการประยุกต์ใช้ที่สำคัญในคณิตศาสตร์เชิง การจัดเรียง ฟิสิกส์และทฤษฎีสนามควอนตัมมันมีความเชื่อมโยงอย่างใกล้ชิดกับต้นไม้แผ่ขยายสม่ำเสมอ (uniform spanning tree ) ซึ่งเป็นแบบ จำลองของ ต้นไม้ สุ่ม และเป็นกรณีหนึ่งของหัวข้อทั่วไปของ การ เดิน สุ่ม

สมมติให้Gเป็นกราฟและเป็นเส้นทางที่มีความยาวnบนGกล่าวอีกนัยหนึ่งคือ เป็นจุดยอดของGที่และเชื่อมต่อกันด้วยขอบการลบวงวนของจะสร้างเส้นทางแบบง่ายใหม่โดยการลบวงวนทั้งหมดของ ตามลำดับเวลา ในทางคณิตศาสตร์ เรากำหนดดัชนีแบบอุปนัย โดย ใช้ ${\displaystyle \gamma }$${\displaystyle \gamma (1),\dots ,\gamma (n)}$${\displaystyle \gamma (i)}$${\displaystyle \gamma (i+1)}$${\displaystyle \gamma }$${\displaystyle \gamma }$${\displaystyle i_{j}}$

${\displaystyle i_{1}=1\,}$

${\displaystyle i_{j+1}=\max\{k:\gamma (k)=\gamma (i_{j})\}+1\,}$

โดยที่ "สูงสุด" ในที่นี้หมายถึงความยาวสูงสุดของเส้นทางการเหนี่ยวนำจะหยุดลงเมื่อมี ค่าบางค่าเท่ากับ 0 ${\displaystyle \gamma }$${\displaystyle i_{j}}$${\displaystyle \gamma (i_{j})=\gamma (n)}$

กล่าวคือ ในการค้นหาเราถือไว้ในมือข้างหนึ่ง และใช้มืออีกข้างลากย้อนกลับจากจุดสิ้นสุดจนกระทั่งเราพบค่าใดค่าหนึ่งซึ่งในกรณีนี้เราจะกำหนดค่าหรือเราสิ้นสุดที่ค่าซึ่งในกรณีนี้เราจะกำหนดค่า ${\displaystyle i_{j+1}}$${\displaystyle \gamma (i_{j})}$${\displaystyle \gamma (n),\gamma (n-1),...}$${\displaystyle \gamma (k)=\gamma (i_{j})}$${\displaystyle i_{j+1}=k+1}$${\displaystyle \gamma (i_{j})}$${\displaystyle i_{j+1}=i_{j}+1}$

สมมติว่าการเหนี่ยวนำหยุดที่Jนั่นคือ เป็นจุดสุดท้ายดังนั้นการลบวงจรของซึ่งแทนด้วยคือเส้นทางแบบง่ายที่มีความยาวJซึ่งกำหนดโดย ${\displaystyle \gamma (i_{J})=\gamma (n)}$${\displaystyle i_{J}}$${\displaystyle \gamma }$${\displaystyle \mathrm {LE} (\gamma )}$

${\displaystyle \mathrm {LE} (\gamma )(j)=\gamma (i_{j}).\,}$

ให้Gเป็นกราฟใดๆ ให้vเป็นจุดยอดของGและให้Rเป็นการเดินสุ่มบนGที่เริ่มต้นจากvให้Tเป็นเวลาหยุดของR การเดินสุ่ม ที่ลบวงวนออกจนถึงเวลาTคือ LE( R ([1, T ])) กล่าวอีกนัยหนึ่งคือ นำRจากจุดเริ่มต้นจนถึงT  — นั่นคือเส้นทาง (แบบสุ่ม) — ลบวงวนทั้งหมดตามลำดับเวลาดังที่กล่าวมาข้างต้น — คุณจะได้เส้นทางแบบสุ่มที่เรียบง่าย

เวลาหยุดTอาจถูกกำหนดไว้ตายตัว เช่น อาจทำไปnขั้นตอนแล้วจึงลบวงวน อย่างไรก็ตาม โดยทั่วไปแล้ว การกำหนดให้Tเป็นเวลาที่กระทบกับเซตใดเซตหนึ่งจะดูเป็นธรรมชาติมากกว่า ตัวอย่างเช่น ให้Gเป็นกราฟZ ²และให้Rเป็นการเดินสุ่มที่เริ่มต้นจากจุด (0,0) ให้Tเป็นเวลาที่Rกระทบกับวงกลมรัศมี 100 เป็นครั้งแรก (ในที่นี้เราหมายถึง วงกลม ที่ถูกแบ่งเป็นส่วนๆ ) LE( R ) เรียกว่าการเดินสุ่มที่ลบวงวนแล้ว โดยเริ่มต้นที่ (0,0) และหยุดที่วงกลม

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

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

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

อีกหนึ่งรูปแบบของการเดินสุ่มแบบลบวงวน มาจากคำตอบของสมการลาปลาสแบบไม่ต่อ เนื่อง ให้Gเป็นกราฟ และให้vและwเป็นจุดยอดสองจุดในGสร้างเส้นทางสุ่มจากvไปยังwแบบอุปนัยโดยใช้ขั้นตอนต่อไปนี้ สมมติว่าเราได้กำหนดไว้แล้วให้fเป็นฟังก์ชันจากGไปยังRที่สอดคล้องกับ ${\displaystyle \gamma (1),...,\gamma (n)}$

${\displaystyle f(\gamma (i))=0}$สำหรับทุกคนและ${\displaystyle i\leq n}$${\displaystyle f(w)=1}$

fเป็นฮาร์มอนิก แบบไม่ต่อ เนื่องในทุกที่อื่น

โดยที่ฟังก์ชันfบนกราฟจะเป็นฟังก์ชันฮาร์มอนิกแบบไม่ต่อเนื่องที่จุดx ถ้า f ( x )เท่ากับค่าเฉลี่ยของfบนจุดข้างเคียงของx

เมื่อกำหนดf แล้ว ให้เลือก โดยใช้fที่เพื่อนบ้านของเป็นน้ำหนัก กล่าวอีกนัยหนึ่ง ถ้าเป็นเพื่อนบ้านเหล่านี้ ให้เลือกด้วยความน่าจะเป็น ${\displaystyle \gamma (n+1)}$${\displaystyle \gamma (n)}$${\displaystyle x_{1},...,x_{d}}$${\displaystyle x_{i}}$

${\displaystyle {\frac {f(x_{i})}{\sum _{j=1}^{d}f(x_{j})}}.}$

เมื่อดำเนินการตามกระบวนการนี้ต่อไป โดยคำนวณค่าf ใหม่ ในแต่ละขั้นตอน จะส่งผลให้ได้เส้นทางแบบสุ่มอย่างง่ายจากvไปยังwซึ่งการกระจายของเส้นทางนี้จะเหมือนกับการกระจายของเส้นทางสุ่มแบบลบวงวนจากvไปยัง w

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

สิ่งสำคัญที่ควรสังเกตคือ แม้ว่าการพิสูจน์ความเท่าเทียมกันจะค่อนข้างง่าย แต่แบบจำลองที่เกี่ยวข้องกับฟังก์ชันฮาร์มอนิกหรือมาตรวัดที่เปลี่ยนแปลงแบบไดนามิกนั้นโดยทั่วไปแล้ววิเคราะห์ได้ยากมาก แทบไม่มีใครรู้ข้อมูลใดๆ เกี่ยวกับการเดินแบบ p-Laplacianหรือการรวมกลุ่มที่จำกัดการแพร่กระจายเลยแบบจำลองที่เกี่ยวข้องอีกอย่างหนึ่งคือนักสำรวจฮาร์มอนิก

สุดท้ายนี้ ยังมีอีกหนึ่งความเชื่อมโยงที่ควรกล่าวถึง คือทฤษฎีบทของ Kirchhoffซึ่งเชื่อมโยงจำนวนต้นไม้แผ่คลุมของกราฟGกับค่าลักษณะเฉพาะของ ตัว ดำเนินการลาปลาเซียน แบบไม่ต่อเนื่อง ดูรายละเอียดเพิ่มเติมได้ ที่ ต้นไม้ แผ่คลุม (spanning tree )

ให้dเป็นมิติ ซึ่งเราจะสมมติว่ามีค่าอย่างน้อย 2 พิจารณาZ ^d ie จุดทั้งหมดที่มี d เป็นจำนวนเต็มนี่คือกราฟอนันต์ที่มีดีกรี 2d เมื่อคุณเชื่อมต่อแต่ละจุดกับจุดเพื่อนบ้านที่ใกล้ที่สุด จากนี้ไปเราจะพิจารณาการเดินสุ่มแบบลบวงวนบนกราฟนี้หรือกราฟย่อยของมัน ${\displaystyle (a_{1},...,a_{d})}$${\displaystyle a_{i}}$

กรณีที่วิเคราะห์ได้ง่ายที่สุดคือมิติที่ 5 ขึ้นไป ในกรณีนี้ ปรากฏว่าจุดตัดนั้นเป็นเพียงจุดตัดเฉพาะที่เท่านั้น การคำนวณแสดงให้เห็นว่า หากเราใช้การเดินแบบสุ่มที่มีความยาวnการลบวงวนจะมีขนาดความยาวอยู่ในลำดับเดียวกัน นั่นคือnเมื่อปรับขนาดตามนั้น ปรากฏว่าการเดินแบบสุ่มที่ลบวงวนแล้วจะลู่เข้าสู่การเคลื่อนที่แบบบราวน์ (ในความหมายที่เหมาะสม) เมื่อnเข้าสู่ค่าอนันต์ มิติที่ 4 นั้นซับซ้อนกว่า แต่ภาพรวมทั่วไปยังคงเป็นจริง ปรากฏว่าการลบวงวนของการเดินแบบสุ่มที่มีความยาวnมีจุดยอดประมาณแต่หลังจากปรับขนาด (ซึ่งคำนึงถึงปัจจัยลอการิทึม) การเดินที่ลบวงวนแล้วจะลู่เข้าสู่การเคลื่อนที่แบบบราวน์อีกครั้ง ${\displaystyle n/\log ^{1/3}n}$

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

${\displaystyle G:=D\cap \varepsilon \mathbb {Z} ^{2},}$

นั่นคือ ตารางที่มีด้านยาว ε จำกัดอยู่ภายในDให้vเป็นจุดยอดของGที่อยู่ใกล้x มากที่สุด ลองพิจารณาการเดินสุ่มแบบลบวงวนที่เริ่มต้นจากvและหยุดเมื่อชนกับ "ขอบเขต" ของGนั่นคือ จุดยอดของGที่สอดคล้องกับขอบเขตของDแล้วข้อสันนิษฐานจะเป็นดังนี้

• เมื่อ ε เข้าใกล้ศูนย์ การกระจายของเส้นทางจะลู่เข้าสู่การกระจายบางอย่างบนเส้นทางแบบง่ายจากxไปยังขอบเขตของD (ซึ่งแตกต่างจากการเคลื่อนที่แบบบราวน์แน่นอน — ใน 2 มิติ เส้นทางของการเคลื่อนที่แบบบราวน์ไม่ใช่เส้นทางแบบง่าย) การกระจายนี้ (เราจะใช้สัญลักษณ์ แทน) เรียกว่าขีดจำกัดการปรับขนาดของการเดินสุ่มแบบลบวงวน${\displaystyle S_{D,x}}$
• การแจกแจงเหล่านี้ไม่เปลี่ยนแปลงภายใต้การแปลงเชิงคอนฟอร์มัล กล่าวคือ ถ้า φ เป็นแผนที่รีมันน์ระหว่างDและโดเมนที่สองEแล้ว

${\displaystyle \phi (S_{D,x})=S_{E,\phi (x)}.\,}$

• มิติเฮาส์ดอร์ฟของเส้นทางเหล่านี้มีค่าเท่ากับ 5/4 เกือบแน่นอน

การโจมตีครั้งแรกต่อสมมติฐานเหล่านี้มาจากทิศทางของการปูพื้นแบบโดมิโนการนำต้นไม้แผ่ขยายของGมาบวกกับคู่ระนาบ ของมัน จะได้ การปูพื้น แบบโดมิโนของกราฟอนุพันธ์พิเศษ (เรียกว่าH ) แต่ละจุดยอดของHสอดคล้องกับจุดยอด ขอบ หรือหน้าของGและขอบของHแสดงให้เห็นว่าจุดยอดใดอยู่บนขอบใด และขอบใดอยู่บนหน้าใด ปรากฏว่าการนำต้นไม้แผ่ขยายแบบสม่ำเสมอของGนำไปสู่การปูพื้นแบบโดมิโนแบบสุ่มที่มีการกระจายอย่างสม่ำเสมอของHจำนวนการปูพื้นแบบโดมิโนของกราฟสามารถคำนวณได้โดยใช้ดีเทอร์มิแนนต์ของเมทริกซ์พิเศษ ซึ่งช่วยให้สามารถเชื่อมโยงกับฟังก์ชันกรีน แบบไม่ ต่อเนื่องซึ่งมีความคงที่เชิงคอนฟอร์มัลโดยประมาณ ข้อโต้แย้งเหล่านี้ทำให้สามารถแสดงได้ว่าค่าที่วัดได้บางอย่างของการเดินสุ่มแบบลบวงวน (ในขีดจำกัด) มีความคงที่เชิงคอนฟอร์มัล และ จำนวนจุดยอด ที่คาดหวังในการเดินสุ่มแบบลบวงวนที่หยุดที่วงกลมรัศมีrนั้นมีลำดับของ^{[ 1 ]}${\displaystyle r^{5/4}}$

ในปี 2002 ข้อสันนิษฐานเหล่านี้ได้รับการแก้ไข (ในเชิงบวก) โดยใช้ การวิวัฒนาการแบบสุ่ม ของโลว์เนอร์ (Stochastic Löwner evolution ) โดยคร่าวๆ แล้ว มันคือสมการเชิงอนุพันธ์สามัญแบบสุ่มที่ไม่เปลี่ยนแปลงตามการแปลงเชิงคอนฟอร์มัลซึ่งช่วยให้สามารถจับคุณสมบัติของมาร์คอฟ (Markov property) ของการเดินสุ่มแบบลบวงวน (loop-erased random walk) (และกระบวนการความน่าจะเป็นอื่นๆ อีกมากมาย) ได้

ขีดจำกัดการปรับขนาดมีอยู่และไม่เปลี่ยนแปลงภายใต้การหมุนและการขยาย^{[ 2 ]}ถ้าแทนจำนวนจุดยอดที่คาดหวังในการเดินสุ่มแบบลบวงวนจนกว่าจะถึงระยะทางrแล้ว ${\displaystyle L(r)}$

${\displaystyle cr^{1+\varepsilon }\leq L(r)\leq Cr^{5/3}\,}$

โดยที่ ε, cและCเป็นจำนวนบวกบางจำนวน^{[ 3 ]} (ในทางทฤษฎีแล้ว สามารถคำนวณจำนวนเหล่านี้ได้จากการพิสูจน์ แต่ผู้เขียนไม่ได้ทำ) ซึ่งแสดงให้เห็นว่าขีดจำกัดการปรับขนาดควรมีมิติเฮาส์ดอร์ฟระหว่างและ 5/3 เกือบแน่นอน การทดลองเชิงตัวเลขแสดงให้เห็นว่าควรจะเป็น^{[ 4 ]}${\displaystyle 1+\varepsilon }$${\displaystyle 1.62400\pm 0.00005}$