ในทางคณิตศาสตร์การเดินสุ่ม (random walk)คือ กระบวนการสุ่มที่อธิบายถึงเส้นทางซึ่งประกอบด้วยลำดับของ การก้าว แบบสุ่มบนปริภูมิทางคณิตศาสตร์ บางอย่าง

ตัวอย่างพื้นฐานของการเดินแบบสุ่มคือการเดินบนเส้นจำนวนเต็มซึ่งเริ่มต้นที่ 0 และในแต่ละขั้นตอนจะเคลื่อนที่ไป +1 หรือ −1 ด้วยความน่าจะ เป็นเท่ากัน ตัวอย่างอื่นๆ ได้แก่ เส้นทางที่โมเลกุลเคลื่อนที่ในของเหลวหรือก๊าซ (ดูการเคลื่อนที่แบบบราวน์ ) เส้นทางการค้นหาของ สัตว์ ที่กำลังหาอาหารหรือราคาของหุ้น ที่ผันผวน และสถานะทางการเงินของนักพนัน การเดินแบบสุ่มมี การประยุกต์ใช้ในด้านวิศวกรรมและสาขาวิทยาศาสตร์หลายสาขา รวมถึงนิเวศวิทยาจิตวิทยาวิทยาการคอมพิวเตอร์ฟิสิกส์เคมีชีววิทยาเศรษฐศาสตร์และสังคมวิทยาคำว่าการเดินแบบสุ่มได้รับการแนะนำครั้งแรกโดย^{Karl Pearson}ในปี1905 [ ¹ ]${\displaystyle \mathbb {Z} }$

การรับรู้การเดินแบบสุ่มสามารถทำได้โดยการจำลองมอนเตคาร์โล^{[ 2 ]}

ในบางบริบท การเดินแบบสุ่มอาจถูกเรียกว่าการเดินของคนเมา

แบบจำลองการเดินสุ่มที่เป็นที่นิยมคือการเดินสุ่มบนโครงตาข่ายปกติ โดยที่ในแต่ละขั้นตอน ตำแหน่งจะกระโดดไปยังไซต์อื่นตามการกระจายความน่าจะเป็นบางอย่าง ในการเดินสุ่มแบบง่ายตำแหน่งสามารถกระโดดไปยังไซต์ข้างเคียงของโครงตาข่ายเท่านั้น ทำให้เกิดเส้นทางโครงตาข่ายในการเดินสุ่มแบบสมมาตรอย่างง่ายบนโครงตาข่ายที่มีขอบเขตจำกัด ความน่าจะเป็นที่ตำแหน่งจะกระโดดไปยังเพื่อนบ้านที่อยู่ติดกันแต่ละแห่งจะเท่ากัน ตัวอย่างที่ได้รับการศึกษามากที่สุดคือการเดินสุ่มบนโครงตาข่ายจำนวนเต็มd มิติ (บางครั้งเรียกว่าโครงตาข่ายไฮเปอร์คิวบิก ) ^{[ 3 ]}นอกจากนี้ หากปริภูมิสถานะมีขอบเขตจำกัด แบบจำลองการเดินสุ่มจะเรียกว่าการเดินสุ่มแบบสมมาตรที่มีขอบเขตอย่างง่ายและความน่าจะเป็นของการเปลี่ยนสถานะจะขึ้นอยู่กับตำแหน่งของสถานะ เนื่องจากการเคลื่อนที่ในสถานะขอบและมุมมีข้อจำกัด^{[ 4 ]}${\displaystyle \mathbb {Z} ^{d}}$

ตัวอย่างพื้นฐานของการเดินสุ่ม คือ การเดินสุ่มบนเส้นจำนวนเต็มซึ่งเริ่มต้นที่ 0 และในแต่ละก้าวจะเคลื่อนที่ไป +1 หรือ −1 ด้วยความน่าจะเป็นเท่ากัน ${\displaystyle \mathbb {Z} }$

สามารถอธิบายกระบวนการนี้ได้ดังนี้ วางเครื่องหมายไว้ที่ศูนย์บนเส้นจำนวน แล้วโยนเหรียญยุติธรรมหนึ่งเหรียญ ถ้าเหรียญออกหัว เครื่องหมายจะเลื่อนไปทางขวาหนึ่งหน่วย ถ้าเหรียญออกก้อย เครื่องหมายจะเลื่อนไปทางซ้ายหนึ่งหน่วย หลังจากโยนเหรียญห้าครั้ง เครื่องหมายอาจอยู่ที่ -5, -3, -1, 1, 3, 5 หากโยนเหรียญห้าครั้งแล้วได้หัวสามครั้งและก้อยสองครั้ง ไม่ว่าจะเรียงลำดับใดก็ตาม เครื่องหมายจะลงที่ 1 มี 10 วิธีที่จะได้ 1 (โดยการโยนเหรียญออกหัวสามครั้งและก้อยสองครั้ง), 10 วิธีที่จะได้ −1 (โดยการโยนเหรียญออกก้อยสามครั้งและหัวสองครั้ง), 5 วิธีที่จะได้ 3 (โดยการโยนเหรียญออกหัวสี่ครั้งและก้อยหนึ่งครั้ง), 5 วิธีที่จะได้ −3 (โดยการโยนเหรียญออกก้อยสี่ครั้งและหัวหนึ่งครั้ง), 1 วิธีที่จะได้ 5 (โดยการโยนเหรียญออกหัวห้าครั้ง), และ 1 วิธีที่จะได้ −5 (โดยการโยนเหรียญออกก้อยห้าครั้ง) ดูภาพด้านล่างเพื่อดูตัวอย่างผลลัพธ์ที่เป็นไปได้จากการโยนเหรียญ 5 ครั้ง

ในการกำหนดการเดินนี้อย่างเป็นทางการ ให้ใช้ตัวแปรสุ่มอิสระโดยแต่ละตัวแปรจะเป็น 1 หรือ −1 ด้วยความน่าจะเป็น 50% สำหรับแต่ละค่า และกำหนดให้และลำดับนี้เรียกว่าการเดินสุ่มอย่างง่ายบนลำดับนี้ (ผลรวมของลำดับของ −1 และ 1) จะให้ระยะทางสุทธิที่เดินได้ หากแต่ละส่วนของการเดินมีความยาวหนึ่ง ค่าคาดหวังของคือศูนย์ นั่นคือ ค่าเฉลี่ยของการโยนเหรียญทั้งหมดจะเข้าใกล้ศูนย์เมื่อจำนวนการโยนเพิ่มขึ้น ซึ่งเป็นผลมาจากคุณสมบัติการบวกแบบจำกัดของค่าคาดหวัง: ${\displaystyle Z_{1},Z_{2},\dots }$${\displaystyle S_{0}=0}$${\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$${\displaystyle \{S_{n}\}}$${\displaystyle \mathbb {Z} }$${\displaystyle E(S_{n})}$${\displaystyle S_{n}}$$${\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}$$

การคำนวณที่คล้ายกัน โดยใช้ความเป็นอิสระของตัวแปรสุ่มและข้อเท็จจริงที่ว่าแสดงให้เห็นว่า: ${\displaystyle E(Z_{n}^{2})=1}$$${\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.}$$

สิ่งนี้บ่งชี้ว่าระยะ การแปล ที่คาดหวังหลังจากnขั้นตอน ควรอยู่ในลำดับของในความเป็นจริง^{[ 5 ]}${\displaystyle E(|S_{n}|)\,\!}$${\displaystyle {\sqrt {n}}}$$${\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}$$

เพื่อตอบคำถามว่าการเดินแบบสุ่มจะข้ามเส้นแบ่งกี่ครั้งหากปล่อยให้เดินต่อไปเรื่อยๆ การเดินแบบสุ่มอย่างง่ายจะข้ามทุกจุดเป็นจำนวนครั้งอนันต์ ผลลัพธ์นี้มีชื่อเรียกหลายชื่อ เช่นปรากฏการณ์การข้ามระดับ การเกิดซ้ำหรือความหายนะของนักพนันเหตุผลของชื่อสุดท้ายมีดังนี้ นักพนันที่มีเงินจำนวนจำกัดจะแพ้ในที่สุดเมื่อเล่นเกมที่ยุติธรรมกับเจ้ามือที่มีเงินไม่จำกัด เงินของนักพนันจะเดินแบบสุ่ม และจะลดลงเหลือศูนย์ในบางจุด และเกมก็จะจบลง ${\displaystyle \mathbb {Z} }$

ถ้าaและbเป็นจำนวนเต็มบวก จำนวนขั้นตอนโดยเฉลี่ยจนกว่าการเดินสุ่มแบบง่ายหนึ่งมิติที่เริ่มต้นที่ 0 จะกระทบกับbหรือ −a ก่อนคือabความน่าจะเป็นที่การเดินสุ่มนี้จะกระทบกับbก่อน −a คือซึ่งสามารถหาได้จากข้อเท็จจริงที่ว่าการเดินสุ่มแบบง่ายเป็นมาร์ติงเกลและค่าเฉลี่ยและความน่าจะเป็นในการกระทบเหล่านี้สามารถคำนวณได้ในห่วงโซ่มาร์คอฟของการเดินสุ่มหนึ่งมิติทั่วไป ${\displaystyle a/(a+b)}$${\displaystyle O(a+b)}$

ผลลัพธ์บางส่วนที่กล่าวถึงข้างต้นสามารถอนุมานได้จากคุณสมบัติของสามเหลี่ยมปาสคาลจำนวนการเดินที่แตกต่างกันnขั้นตอน โดยแต่ละขั้นตอนเป็น +1 หรือ −1 คือ 2n ^{สำหรับ}การเดินแบบสุ่มอย่างง่าย การเดินแต่ละครั้งเหล่านี้มีโอกาสเกิดขึ้นเท่ากัน เพื่อให้S _nเท่ากับจำนวนkจำเป็นและเพียงพอที่จำนวน +1 ในการเดินจะมากกว่าจำนวน −1 อยู่kดังนั้น +1 จะต้องปรากฏ ( n  +  k )/2 ครั้งในnขั้นตอนของการเดิน ดังนั้นจำนวนการเดินที่ตรงตามเงื่อนไขจะเท่ากับจำนวนวิธีในการเลือก ( n  +  k )/2 องค์ประกอบจาก เซตที่มี nองค์ประกอบ^{[ 6 ]}ซึ่งแสดงด้วยเพื่อให้สิ่งนี้มีความหมาย จำเป็นที่n  +  kจะต้องเป็นจำนวนคู่ ซึ่งหมายความว่าnและk ต้อง เป็นจำนวนคู่หรือจำนวนคี่ทั้งคู่ ดังนั้น ความน่าจะเป็นที่เท่ากับโดยการแสดงค่าในสามเหลี่ยมปาสคาลในรูปของแฟกทอเรียลและใช้สูตรของสเตอร์ลิงเราสามารถประมาณค่าความน่าจะเป็นเหล่านี้ได้ดีสำหรับค่า n ที่มีขนาดใหญ่ ${\displaystyle S_{n}=k}$${\textstyle n \choose (n+k)/2}$${\displaystyle S_{n}=k}$${\textstyle 2^{-n}{n \choose (n+k)/2}}$${\displaystyle n}$

ความสัมพันธ์นี้กับสามเหลี่ยมของปาสคาลแสดงให้เห็นได้สำหรับค่าn ที่มีขนาดเล็ก เมื่อหมุนเป็นศูนย์ครั้ง โอกาสเดียวที่จะคงอยู่ที่ศูนย์ อย่างไรก็ตาม เมื่อหมุนหนึ่งครั้ง มีโอกาสหนึ่งครั้งที่จะลงที่ -1 หรือมีโอกาสหนึ่งครั้งที่จะลงที่ 1 เมื่อหมุนสองครั้ง เครื่องหมายที่ 1 สามารถเคลื่อนไปยัง 2 หรือกลับไปที่ศูนย์ได้ เครื่องหมายที่ -1 สามารถเคลื่อนไปยัง -2 หรือกลับไปที่ศูนย์ได้ ดังนั้น จึงมีโอกาสหนึ่งครั้งที่จะลงที่ -2 มีโอกาสสองครั้งที่จะลงที่ศูนย์ และมีโอกาสหนึ่งครั้งที่จะลงที่ 2

เค	−5	−4	−3	−2	−1	0	1	2	3	4	5
${\displaystyle P[S_{0}=k]}$						1
${\displaystyle 2P[S_{1}=k]}$					1		1
${\displaystyle 2^{2}P[S_{2}=k]}$				1		2		1
${\displaystyle 2^{3}P[S_{3}=k]}$			1		3		3		1
${\displaystyle 2^{4}P[S_{4}=k]}$		1		4		6		4		1
${\displaystyle 2^{5}P[S_{5}=k]}$	1		5		10		10		5		1

ทฤษฎีบทลิมิตกลางและกฎของลอการิทึมซ้ำอธิบายลักษณะสำคัญของพฤติกรรมของการเดินสุ่มอย่างง่ายบนเซต n โดย เฉพาะอย่างยิ่ง ทฤษฎีบทลิมิตกลางบ่งชี้ว่า เมื่อnเพิ่มขึ้น ความน่าจะเป็น (ซึ่งเป็นสัดส่วนกับตัวเลขในแต่ละแถว) จะเข้าใกล้การแจกแจงแบบปกติ${\displaystyle \mathbb {Z} }$

กล่าวให้แม่นยำยิ่งขึ้น เมื่อทราบว่าและใช้สูตรของสเตอร์ลิงจะได้ว่า ${\textstyle \mathbb {P} (X_{n}=k)=2^{-n}{\binom {n}{(n+k)/2}}}$

$${\displaystyle {\log \mathbb {P} (X_{n}=k)}=n\left[\left({1+{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1+{\frac {k}{n}}\right)+\left({1-{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1-{\frac {k}{n}}\right)\right]+\log {\frac {\sqrt {2}}{\sqrt {\pi }}}+o(1).}$$

เมื่อแก้ไขการปรับขนาดสำหรับค่าคงที่ และใช้การขยายเมื่อหายไป จะได้ดังนี้ ${\textstyle k=\lfloor {\sqrt {n}}x\rfloor }$${\textstyle x}$${\textstyle \log(1+{k}/{n})=k/n-k^{2}/2n^{2}+\dots }$${\textstyle k/n}$

$${\displaystyle {\mathbb {P} \left({\frac {X_{n}}{n}}={\frac {\lfloor {\sqrt {n}}x\rfloor }{\sqrt {n}}}\right)}={\frac {1}{\sqrt {n}}}{\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}(1+o(1)).}$$

เมื่อพิจารณาลิมิต (และสังเกตว่าสอดคล้องกับระยะห่างของตารางการปรับขนาด) จะพบความหนาแน่นแบบเกาส์เซียนแท้จริงแล้ว สำหรับตัวแปรสุ่มต่อเนื่องอย่างสมบูรณ์ที่มีความหนาแน่นจะเป็น จริง โดยที่สอดคล้องกับระยะห่างที่เล็กมาก ${\textstyle {1}/{\sqrt {n}}}$${\textstyle f(x)={\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}}$${\textstyle X}$${\textstyle f_{X}}$${\textstyle \mathbb {P} \left(X\in [x,x+dx)\right)=f_{X}(x)dx}$${\textstyle dx}$

โดยทั่วไปแล้ว เราสามารถพิจารณาการเดินแบบสุ่มบนโครงตาข่ายผลึก (กราฟคลุมแบบอาเบลอนันต์เท่าบนกราฟจำกัด) ในความเป็นจริงแล้ว เป็นไปได้ที่จะสร้างทฤษฎีบทขีดจำกัดกลางและทฤษฎีบทการเบี่ยงเบนขนาดใหญ่ในบริบทนี้^{[ 7 ] [ 8 ]}

การเดินสุ่มแบบหนึ่งมิติสามารถมองได้ว่าเป็นลูกโซ่ Markovที่มีปริภูมิสถานะกำหนดโดยจำนวนเต็มสำหรับจำนวนp บางจำนวนที่ สอดคล้อง กับเงื่อนไข ความน่าจะเป็นของการเปลี่ยนสถานะ (ความน่าจะเป็นP _i,jของการเปลี่ยนจากสถานะiไปยังสถานะj ) จะกำหนดโดย ${\displaystyle i=0,\pm 1,\pm 2,\dots .}$${\displaystyle \,0<p<1}$$${\displaystyle \,P_{i,i+1}=p=1-P_{i,i-1}.}$$

การเดินสุ่มแบบไม่เป็นเอกพันธ์จะสุ่มหมายเลขหนึ่งในแต่ละช่วงเวลาเพื่อกำหนดความน่าจะเป็นของการกระโดดในแต่ละตำแหน่ง จากนั้นจะสุ่มหมายเลขอีกหมายเลขหนึ่งเพื่อกำหนดทิศทางการกระโดดจริง คำถามหลักคือความน่าจะเป็นที่จะคงอยู่ในแต่ละตำแหน่งหลังจากกระโดด และในขีดจำกัดของความน่าจะเป็นนี้เมื่อมีค่ามาก ๆ ${\displaystyle t}$${\displaystyle t}$

ในมิติที่สูงขึ้น เซตของจุดที่เดินแบบสุ่มจะมีคุณสมบัติทางเรขาคณิตที่น่าสนใจ ในความเป็นจริง จะได้แฟรกทัล แบบไม่ต่อเนื่อง นั่นคือ เซตที่แสดงความคล้ายคลึงกันในตัวเองแบบสุ่มในระดับใหญ่ ในระดับเล็ก สามารถสังเกตเห็น "ความขรุขระ" ที่เกิดจากตารางที่ใช้ในการเดิน วิถีของการเดินแบบสุ่มคือชุดของจุดที่เยี่ยมชม โดยถือว่าเป็นเซตโดยไม่คำนึงถึงเวลาที่การเดินมาถึงจุดนั้น ในมิติเดียว วิถีก็คือจุดทั้งหมดระหว่างความสูงต่ำสุดและความสูงสูงสุดที่การเดินไปถึง (โดยเฉลี่ยแล้วทั้งสองค่าอยู่ในลำดับ) ${\displaystyle {\sqrt {n}}}$

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

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

ความน่าจะเป็นของการเกิดซ้ำโดยทั่วไปคือซึ่งสามารถหาได้จากฟังก์ชันการสร้าง^{[ 11 ]}หรือกระบวนการปัวซง^{[ 12 ]}${\displaystyle p=1-\left({\frac {1}{(2\pi )^{d}}}\int _{[-\pi ,\pi ]^{d}}{\frac {\prod _{i=1}^{d}d\theta _{i}}{1-{\frac {1}{d}}\sum _{i=1}^{d}\cos \theta _{i}}}\right)^{-1}}$

คำถามอีกรูปแบบหนึ่งที่ Pólya ถามไว้เช่นกันคือ "ถ้าคนสองคนออกจากจุดเริ่มต้นเดียวกัน พวกเขาจะพบกันอีกหรือไม่" ^{[ 13 ]}สามารถแสดงได้ว่าความแตกต่างระหว่างตำแหน่งของพวกเขา (การเดินสุ่มอิสระสองครั้ง) ก็เป็นการเดินสุ่มแบบง่ายเช่นกัน ดังนั้นพวกเขาจึงมีโอกาสพบกันอีกครั้งในการเดินแบบ 2 มิติ แต่สำหรับ 3 มิติขึ้นไป ความน่าจะเป็นจะลดลงตามจำนวนมิติPaul Erdősและ Samuel James Taylor ยังแสดงให้เห็นในปี 1960 ว่าสำหรับมิติที่น้อยกว่าหรือเท่ากับ 4 การเดินสุ่มอิสระสองครั้งที่เริ่มต้นจากจุดสองจุดใดๆ จะมีจุดตัดกันเป็นอนันต์อย่างแน่นอน แต่สำหรับมิติที่สูงกว่า 5 พวกเขาจะตัดกันเพียงจำนวนจำกัดครั้งเท่านั้นอย่างแน่นอน^{[ 14 ]}

ฟังก์ชันเชิงอะซิมโทติกสำหรับการเดินสุ่มสองมิติเมื่อจำนวนขั้นตอนเพิ่มขึ้นนั้นกำหนดโดยการแจกแจงเรย์ลีการแจกแจงความน่าจะเป็นเป็นฟังก์ชันของรัศมีจากจุดกำเนิดและความยาวขั้นตอนคงที่สำหรับแต่ละขั้นตอน ในที่นี้ ความยาวขั้นตอนถือว่าเท่ากับ 1, N คือจำนวนขั้นตอนทั้งหมด และ r คือรัศมีจากจุดกำเนิด^{[ 15 ]}

$${\displaystyle P(r)={\frac {2r}{N}}e^{-r^{2}/N}}$$

กระบวนการเวียนเนอร์ (Wiener process ) เป็นกระบวนการสุ่มที่มีพฤติกรรมคล้ายกับการเคลื่อนที่แบบบราวน์ (Brownian motion ) ซึ่งเป็นปรากฏการณ์ทางกายภาพของการแพร่กระจายของอนุภาคขนาดเล็กในของเหลว (บางครั้งกระบวนการเวียนเนอร์ถูกเรียกว่า "การเคลื่อนที่แบบบราวน์" แม้ว่าในทางเทคนิคแล้วจะเป็นการสับสนระหว่างแบบจำลองกับปรากฏการณ์ที่กำลังจำลองอยู่ก็ตาม)

กระบวนการเวียนเนอร์ (Wiener process) คือขีดจำกัดการปรับขนาดของการเดินสุ่มในมิติ 1 หมายความว่า หากมีการเดินสุ่มที่มีขั้นตอนเล็กมาก จะมีการประมาณค่าเป็นกระบวนการเวียนเนอร์ (และโดยประมาณคือการเคลื่อนที่แบบบราวน์) กล่าวให้แม่นยำยิ่งขึ้น หากขนาดขั้นตอนคือ ε จะต้องเดินเป็นระยะทางL /ε² ^{เพื่อ}ประมาณความยาวเวียนเนอร์ที่Lเมื่อขนาดขั้นตอนเข้าใกล้ 0 (และจำนวนขั้นตอนเพิ่มขึ้นตามสัดส่วน) การเดินสุ่มจะลู่เข้าสู่กระบวนการเวียนเนอร์ในความหมายที่เหมาะสม ในทางทฤษฎี หากBคือปริภูมิของเส้นทางทั้งหมดที่มีความยาวLที่มีโทโพโลยีสูงสุด และหากMคือปริภูมิของการวัดเหนือBที่มีโทโพโลยีแบบนอร์ม การลู่เข้าจะเกิดขึ้นในปริภูมิM ในทำนอง เดียวกัน กระบวนการเวียนเนอร์ในหลายมิติคือขีดจำกัดการปรับขนาดของการเดินสุ่มในจำนวนมิติเดียวกัน

การเดินแบบสุ่ม (random walk) เป็นแฟร็กทัลแบบไม่ต่อเนื่อง (ฟังก์ชันที่มีมิติเป็นจำนวนเต็ม; 1, 2, ...) แต่เส้นทางของกระบวนการเวียนเนอร์ (Wiener process trajectory) เป็นแฟร็กทัลที่แท้จริง และมีความเชื่อมโยงระหว่างทั้งสอง ตัวอย่างเช่น การเดินแบบสุ่มจนกระทั่งชนกับวงกลมที่มีรัศมีrคูณด้วยความยาวของแต่ละก้าว จำนวนก้าวเฉลี่ยที่เดินคือr²ข้อเท็จจริงนี้เป็นเวอร์ชันแบบไม่ต่อเนื่อง ของข้อเท็จจริงที่ว่า การเดิน ^ของกระบวนการเวียนเนอร์เป็นแฟร็กทัลที่มีมิติเฮาส์ดอร์ฟเท่ากับ  2

ในสองมิติ จำนวนจุดเฉลี่ยที่การเดินสุ่มเดียวกันมีบนขอบของวิถีคือr ^4/3ซึ่งสอดคล้องกับข้อเท็จจริงที่ว่าขอบของวิถีของกระบวนการ Wiener เป็นแฟรกทัลมิติ 4/3 ซึ่งเป็นข้อเท็จจริงที่ Mandelbrot ทำนายไว้โดย^ใช้การจำลอง แต่ได้รับการพิสูจน์ในปี 2000 โดยLawler , SchrammและWerner เท่านั้น ^{[ 16} ]

กระบวนการเวียนเนอร์มีสมมาตร หลายอย่าง ที่การเดินแบบสุ่มไม่มี ตัวอย่างเช่น การเดินแบบกระบวนการเวียนเนอร์ไม่เปลี่ยนแปลงเมื่อหมุน แต่การเดินแบบสุ่มเปลี่ยนแปลงได้ เนื่องจากโครงสร้างพื้นฐานไม่เปลี่ยนแปลง (การเดินแบบสุ่มเปลี่ยนแปลงได้เมื่อหมุน 90 องศา แต่กระบวนการเวียนเนอร์เปลี่ยนแปลงได้เมื่อหมุน 17 องศาด้วย) นี่หมายความว่าในหลายกรณี ปัญหาในการเดินแบบสุ่มจะแก้ได้ง่ายกว่าโดยการแปลงเป็นกระบวนการเวียนเนอร์ แก้ปัญหาในกระบวนการเวียนเนอร์ แล้วจึงแปลงกลับมา ในทางกลับกัน บางปัญหาก็แก้ได้ง่ายกว่าด้วยการเดินแบบสุ่มเนื่องจากลักษณะที่เป็นแบบไม่ต่อเนื่อง

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

การลู่เข้าของการเดินสุ่มไปสู่กระบวนการไวเนอร์นั้นถูกควบคุมโดยทฤษฎีบทลิมิตกลางและทฤษฎีบทของดอนสเกอร์สำหรับอนุภาคที่อยู่ในตำแหน่งคงที่ที่ทราบ ณ เวลาt  = 0 ทฤษฎีบทลิมิตกลางบอกเราว่า หลังจากจำนวน ขั้นตอน อิสระ จำนวนมาก ในการเดินสุ่ม ตำแหน่งของผู้เดินจะกระจายตัวตามการแจกแจงปกติ ที่ มีความแปรปรวนรวมเท่ากับ:

$${\displaystyle \sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},}$$

โดยที่tคือเวลาที่ผ่านไปนับตั้งแต่เริ่มการเดินแบบสุ่มคือขนาดของก้าวในการเดินแบบสุ่ม และคือเวลาที่ผ่านไประหว่างสองก้าวที่ต่อเนื่องกัน ${\displaystyle \varepsilon }$${\displaystyle \delta t}$

สิ่งนี้สอดคล้องกับฟังก์ชันของกรีนในสมการการแพร่กระจายที่ควบคุมกระบวนการเวียนเนอร์ ซึ่งชี้ให้เห็นว่าหลังจากจำนวนขั้นตอนจำนวนมาก การเดินแบบสุ่มจะลู่เข้าสู่กระบวนการเวียนเนอร์

ในระบบ 3 มิติ ค่าความแปรปรวนที่สอดคล้องกับฟังก์ชันกรีนของสมการการแพร่กระจายคือ: $${\displaystyle \sigma ^{2}=6\,D\,t.}$$

โดยการปรับค่าปริมาณนี้ให้เท่ากับค่าความแปรปรวนที่เกี่ยวข้องกับตำแหน่งของตัวเดินสุ่ม จะได้ค่าสัมประสิทธิ์การแพร่กระจายที่เทียบเท่ากัน ซึ่งจะต้องนำมาพิจารณาสำหรับกระบวนการ Wiener แบบไม่จำกัดระยะ ซึ่งการเดินสุ่มจะลู่เข้าสู่ค่านี้หลังจากจำนวนขั้นตอนจำนวนมาก (ใช้ได้เฉพาะใน 3 มิติเท่านั้น) $${\displaystyle D={\frac {\varepsilon ^{2}}{6\delta t}}}$$

ค่าความแปรปรวนทั้งสองที่แสดงข้างต้น สอดคล้องกับการกระจายตัวที่เกี่ยวข้องกับเวกเตอร์ที่เชื่อมปลายทั้งสองของการเดินแบบสุ่ม ใน 3 มิติ ค่าความแปรปรวนที่เกี่ยวข้องกับแต่ละองค์ประกอบหรือมีค่าเพียงหนึ่งในสามของค่านี้ (ยังคงอยู่ใน 3 มิติ) ${\displaystyle {\vec {R}}}$${\displaystyle R_{x}}$${\displaystyle R_{y}}$${\displaystyle R_{z}}$

สำหรับ 2D: ^{[ 17 ]}

$${\displaystyle D={\frac {\varepsilon ^{2}}{4\delta t}}.}$$

สำหรับ 1D: ^{[ 18 ]}

$${\displaystyle D={\frac {\varepsilon ^{2}}{2\delta t}}.}$$

การเดินแบบสุ่มที่มีขนาดก้าวที่แปรผันตามการแจกแจงแบบปกติ โดยที่ คือค่าเฉลี่ย และคือค่าเบี่ยงเบนมาตรฐาน ถูกนำมาใช้เป็นแบบจำลอง สำหรับ ข้อมูลอนุกรมเวลาในโลกแห่งความเป็นจริงเช่น ตลาดการเงิน ${\displaystyle {\mathcal {N}}(\mu ,\sigma ^{2})}$${\displaystyle \mu }$${\displaystyle \sigma }$

ในที่นี้ ขนาดของขั้นตอนกำหนดโดยการแจกแจงปกติสะสมผกผัน โดยที่เป็นจำนวนสุ่มที่มีการแจกแจงแบบเอกรูป ${\displaystyle \Phi ^{-1}(x,\mu ,\sigma ),}$${\displaystyle x\in \{0,1\}}$

ถ้าไม่เป็นศูนย์ การเดินแบบสุ่มจะแปรผันตามแนวโน้มเชิงเส้น ถ้าคือค่าเริ่มต้นของการเดินแบบสุ่ม ค่าที่คาดหวังหลังจากขั้นตอนจะเป็น ${\displaystyle \mu }$${\displaystyle v_{s}}$${\displaystyle n}$${\displaystyle v_{s}+n\mu }$

สำหรับกรณีพิเศษที่หลังจากขั้นตอนต่างๆ การกระจายความน่าจะเป็นของระยะทางการแปลจะได้รับโดย${\displaystyle \mu =0}$${\displaystyle n}$${\displaystyle {\mathcal {N}}(0,n\sigma ^{2}).}$

บทพิสูจน์: การเดินสุ่มแบบเกาส์เซียนสามารถคิดได้ว่าเป็นผลรวมของลำดับของตัวแปรสุ่มอิสระและมีการแจกแจงเหมือนกัน (ขั้นตอน) จากการแจกแจงปกติสะสมผกผัน โดยที่จากสมมติฐานของการบวกแบบ σนั้น ผลรวมของตัวแปรสุ่มอิสระที่มีการแจกแจงปกติจะมีค่าประมาณของการแจกแจงความน่าจะเป็นแบบปกติของผลรวมของตัวแปรสุ่มอิสระดังนั้น${\displaystyle n}$${\displaystyle x_{i}}$${\displaystyle \mu =0:}$$${\displaystyle X=\sum _{i=0}^{n}{x_{i}},}$$$${\displaystyle X=\sum _{i=0}^{n}{x_{i}}\sim {\mathcal {N}}(0,n\sigma ^{2}).}$$

สำหรับขั้นตอนที่กระจายตามการแจกแจงใดๆ ที่มีค่าเฉลี่ยเป็นศูนย์และความแปรปรวนจำกัด (ไม่จำเป็นต้องเป็นการแจกแจงแบบปกติเท่านั้น) ระยะการแปล เฉลี่ยกำลังสองหลังจากขั้นตอนต่างๆ คือ${\displaystyle n}$$${\displaystyle {\sqrt {Var(S_{n})}}={\sqrt {E[S_{n}^{2}]}}=\sigma {\sqrt {n}}.}$$

แต่สำหรับการเดินสุ่มแบบเกาส์เซียน ค่านี้เป็นเพียงค่าเบี่ยงเบนมาตรฐานของการกระจายระยะการแปลหลังจากขั้นตอนต่างๆ ดังนั้น ถ้าและเนื่องจากระยะการแปลรากกำลังสองเฉลี่ย (RMS) คือหนึ่งค่าเบี่ยงเบนมาตรฐาน จึงมีความน่าจะเป็น 68.27% ที่ระยะการแปล RMS หลังจากขั้นตอนต่างๆ จะอยู่ระหว่าง ในทำนองเดียวกัน มีความน่าจะเป็น 50% ที่ระยะการแปลหลังจากขั้นตอนต่างๆ จะอยู่ระหว่าง${\displaystyle n}$${\displaystyle \mu =0}$${\displaystyle n}$${\displaystyle \pm \sigma {\sqrt {n}}}$${\displaystyle n}$${\displaystyle \pm 0.6745\sigma {\sqrt {n}}.}$

จำนวนไซต์ที่แตกต่างกันที่ผู้เดินสุ่มคนเดียวเยี่ยมชมได้รับการศึกษาอย่างกว้างขวางสำหรับแลตทิซสี่เหลี่ยมและลูกบาศก์และสำหรับแฟรกทัล^{[ 19 ] [ 20 ]}ปริมาณนี้มีประโยชน์สำหรับการวิเคราะห์ปัญหาการดักจับและปฏิกิริยาจลน์ นอกจากนี้ยังเกี่ยวข้องกับความหนาแน่นของสถานะการสั่นสะเทือน^{[ 21 ] [ 22 ]}กระบวนการปฏิกิริยาการแพร่กระจาย^{[ 23 ]} และการแพร่กระจายของประชากรในระบบนิเวศ^{[ 24 ] [ 25 ]}${\displaystyle S(t)}$

อัตราข้อมูลของการเดินสุ่มแบบเกาส์เซียนโดยสัมพันธ์กับระยะทางข้อผิดพลาดกำลังสอง กล่าวคือฟังก์ชันการบิดเบือนอัตรา กำลังสอง จะได้รับพารามิเตอร์โดย^{[ 26 ]} โดยที่ดังนั้น จึงเป็นไปไม่ได้ที่จะเข้ารหัสโดยใช้รหัสไบนารี ที่มีจำนวน บิตน้อยกว่าและกู้คืนโดยมีข้อผิดพลาดกำลังสองเฉลี่ยที่คาดหวังน้อยกว่าในทางกลับกัน สำหรับ ใดๆ จะมีค่า ที่มีขนาดใหญ่พอ และรหัสไบนารีที่มีองค์ประกอบที่แตกต่างกันไม่เกินซึ่งข้อผิดพลาดกำลังสองเฉลี่ยที่คาดหวังในการกู้คืน จากรหัสนี้จะมีค่า ไม่ เกิน$${\displaystyle R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\varphi )/\theta \right)\}\,d\varphi ,}$$$${\displaystyle D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,}$$${\displaystyle S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2}}$${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$${\displaystyle NR(D_{\theta })}$${\displaystyle D_{\theta }}$${\displaystyle \varepsilon >0}$${\displaystyle N\in \mathbb {N} }$${\displaystyle 2^{NR(D_{\theta })}}$${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$${\displaystyle D_{\theta }-\varepsilon }$

ในเศรษฐศาสตร์การเงินสมมติฐานการเดินแบบสุ่มใช้เพื่อสร้างแบบจำลองราคาหุ้นและปัจจัยอื่นๆ^{[ 27 ]} การศึกษาเชิงประจักษ์พบความเบี่ยงเบนจากแบบจำลองทางทฤษฎีนี้ โดยเฉพาะอย่างยิ่งใน ความสัมพันธ์ระยะสั้นและระยะยาว

ในกระบวนการผลิตเซมิคอนดักเตอร์การเดินแบบสุ่ม (random walk) ถูกนำมาใช้ในการวิเคราะห์ผลกระทบของการบำบัดด้วยความร้อนที่ระดับขนาดเล็ก โดยนำไปใช้เพื่อทำความเข้าใจการแพร่กระจายของสารเจือปนข้อบกพร่องและสิ่งเจือปน อื่นๆ ในระหว่างขั้นตอนการผลิตที่สำคัญ การวิเคราะห์ด้วยการเดินแบบสุ่มยังใช้ในการศึกษาการแพร่กระจายของสารตั้งต้น ผลิตภัณฑ์ และพลาสมาในระหว่าง กระบวนการ การตกตะกอนไอสารเคมี (chemical vapor deposition: CVD) การแพร่กระจายแบบต่อเนื่อง (continuum diffusion) ถูกนำมาใช้ในการศึกษาการไหลของก๊าซในระดับมหภาคในเครื่องปฏิกรณ์ CVD อย่างไรก็ตาม ขนาดที่เล็กลงและความซับซ้อนที่เพิ่มขึ้นทำให้เราต้องใช้การวิเคราะห์ด้วยการเดินแบบสุ่ม ซึ่งช่วยให้สามารถวิเคราะห์กระบวนการสุ่ม ได้อย่างแม่นยำ ในระดับโมเลกุลและระดับที่เล็กกว่านั้นในกระบวนการผลิตเซมิคอนดักเตอร์

ในวิทยาการคอมพิวเตอร์การเดินแบบสุ่มถูกนำมาใช้เพื่อประมาณขนาดของเว็บ [ ^{28 ]} ในการเขียนโปรแกรมคอมพิวเตอร์สามารถคำนวณค่าพายด้วยการเดินแบบสุ่ม^{ได้[ 29 ]}

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

ในการแบ่งส่วนภาพจะใช้การเดินแบบสุ่มเพื่อกำหนดป้ายกำกับ (เช่น "วัตถุ" หรือ "พื้นหลัง") ที่จะเชื่อมโยงกับแต่ละพิกเซล^{[ 31 ]}โดยทั่วไปอัลกอริทึมนี้เรียกว่าอัลกอริทึมการแบ่งส่วนแบบ เดินสุ่ม

เว็บไซต์ Twitter ใช้การเดินแบบสุ่มเพื่อแนะนำว่าควรติดตามใคร^{[ 32 ]}

ดังที่กล่าวมาแล้ว ขอบเขตของปรากฏการณ์ทางธรรมชาติที่พยายามอธิบายด้วยการเดินแบบสุ่มนั้นมีมากมาย โดยเฉพาะอย่างยิ่งในสาขาฟิสิกส์^{[ 33 ] [ 34 ]}เคมี^{[ 35 ] วิทยาศาสตร์}วัสดุ [ ^{36 ] [ 37 ]}และชีววิทยา^{[ 38 ] [ 39 ] [ 40 ]}

• แบคทีเรียที่เคลื่อนที่ได้จะเดินแบบสุ่มโดยมีอคติ^{[ 41 ]}
• ในการวิจัยเกี่ยวกับสมองการเดินแบบสุ่มและการเดินแบบสุ่มที่มีการเสริมแรงถูกนำมาใช้เพื่อจำลองลำดับการยิงของเซลล์ประสาทในสมอง
• ในพันธุศาสตร์ประชากรการเดินแบบสุ่มอธิบายถึงคุณสมบัติทางสถิติของการลอยตัวทางพันธุกรรม หรือ การคัดเลือกที่ผันผวนแบบสุ่มในระยะยาว^{[ 42 ]}
• ในนิเวศวิทยาเชิงคณิตศาสตร์การเดินแบบสุ่มถูกนำมาใช้เพื่ออธิบายการเคลื่อนที่ของสัตว์แต่ละตัว เพื่อสนับสนุนกระบวนการแพร่กระจายทางชีวภาพ ในเชิงประจักษ์ และบางครั้งก็ใช้เพื่อจำลองพลวัตของประชากร
• ในวิทยาศาสตร์การมองเห็นการเคลื่อนที่ของดวงตามีแนวโน้มที่จะมีพฤติกรรมเหมือนการเดินแบบสุ่ม^{[ 43 ]}ตามที่ผู้เขียนบางคนกล่าวไว้การเคลื่อนไหวของดวงตาในการจ้องมองโดยทั่วไปก็สามารถอธิบายได้ด้วยการเดินแบบสุ่มเช่นกัน^{[ 44 ]}

• ในทางฟิสิกส์ การเดินแบบสุ่มเป็นพื้นฐานของวิธีการประมาณค่าแบบเฟอร์มิ
• ในวิชาฟิสิกส์การเดินแบบสุ่มถูกใช้เป็นแบบจำลองอย่างง่ายของการเคลื่อนที่แบบบราวน์และการแพร่กระจายทางกายภาพ เช่นการเคลื่อนที่แบบสุ่ม ของโมเลกุลในของเหลวและก๊าซ ดูตัวอย่างเช่น การรวมกลุ่มที่จำกัดด้วยการแพร่กระจาย นอกจากนี้ ในวิชาฟิสิกส์ การเดินแบบสุ่มและการเดินแบบมีปฏิสัมพันธ์กับตัวเองบางประเภทก็มีบทบาทในทฤษฎีสนามควอนตัมด้วย
• ฟิสิกส์ดาราศาสตร์ : แอนติโปรตอนที่สร้างขึ้นจากการแตกตัวในตัวกลางระหว่างดาวจะเคลื่อนที่แบบสุ่มผ่านอวกาศ^{[ 45 ]}
• ในฟิสิกส์พอลิเมอร์การเดินแบบสุ่มอธิบายถึงสายโซ่ในอุดมคติเป็นแบบจำลองที่ง่ายที่สุดในการศึกษาพอลิเมอร์^{[ 46 ]}
• ในสาขาอื่นๆ ของคณิตศาสตร์ การเดินแบบสุ่มถูกนำมาใช้ในการคำนวณหาคำตอบของสมการลาปลาสการประมาณค่าการวัดฮาร์มอนิกและสำหรับการสร้างต่างๆ ในการวิเคราะห์และคณิตศาสตร์เชิงการจัดเรียง

• ในทางจิตวิทยาการเดินแบบสุ่มอธิบายความสัมพันธ์ระหว่างเวลาที่จำเป็นในการตัดสินใจและความน่าจะเป็นที่จะมีการตัดสินใจบางอย่างได้อย่างแม่นยำ^{[ 47 ]}

มีการพิจารณาประเภทของ กระบวนการสุ่มหลายประเภทที่คล้ายกับการเดินสุ่มบริสุทธิ์ แต่โครงสร้างที่เรียบง่ายนั้นสามารถขยายให้ทั่วไปได้มากขึ้น โครงสร้าง บริสุทธิ์สามารถกำหนดลักษณะได้โดยขั้นตอนต่างๆ ถูกกำหนดโดยตัวแปรสุ่มอิสระและมีการกระจายเหมือนกันการเดินสุ่มสามารถเกิดขึ้นได้ในปริภูมิที่หลากหลาย เช่นกราฟจำนวนเต็ม เส้นจำนวนจริง ระนาบหรือปริภูมิเวกเตอร์มิติสูง บนพื้นผิวโค้ง หรือ แมนิโฟลด์รีมันน์มิติสูงและบนกลุ่มนอกจากนี้ยังสามารถกำหนดการเดินสุ่มที่ดำเนินการในเวลาสุ่มได้ และในกรณีนั้น ตำแหน่งX_ทีจะต้องกำหนดนิยามสำหรับทุกช่วงเวลาt ∈ [0, +∞)กรณีเฉพาะหรือขีดจำกัดของการเดินแบบสุ่ม ได้แก่การบินแบบเลวี (Lévy flight)และ แบบจำลอง การแพร่กระจายเช่น การเคลื่อนที่แบบบราวน์ ( Brownian motion )

การเดินสุ่มที่มีความยาวkบนกราฟG ที่อาจเป็นอนันต์ ซึ่งมีรากที่0คือกระบวนการสุ่มที่มีตัวแปรสุ่มโดยที่และ เป็นจุดยอดที่เลือกแบบสุ่มอย่างสม่ำเสมอจากจุดยอดข้างเคียงของแล้วจำนวนคือความน่าจะเป็นที่การเดินสุ่มที่มีความยาวkเริ่มต้นที่vสิ้นสุดที่wโดยเฉพาะอย่างยิ่ง ถ้าGเป็นกราฟที่มีรากที่0คือความน่าจะเป็นที่ การ เดิน สุ่มแบบ k ขั้น กลับมาที่0${\displaystyle X_{1},X_{2},\dots ,X_{k}}$${\displaystyle X_{1}=0}$${\displaystyle {X_{i+1}}}$${\displaystyle X_{i}}$${\displaystyle p_{v,w,k}(G)}$${\displaystyle p_{0,0,2k}}$${\displaystyle 2k}$

โดยอ้างอิงจากการเปรียบเทียบในส่วนก่อนหน้าเกี่ยวกับมิติที่สูงกว่า สมมติว่าเมืองของเราไม่ได้เป็นตารางสี่เหลี่ยมจัตุรัสที่สมบูรณ์แบบอีกต่อไป เมื่อบุคคลของเรามาถึงทางแยกแห่งหนึ่ง เขาจะเลือกถนนที่มีอยู่ต่างๆ ด้วยความน่าจะเป็นเท่ากัน ดังนั้น หากทางแยกมีทางออกเจ็ดทาง บุคคลนั้นจะไปที่แต่ละทางด้วยความน่าจะเป็นหนึ่งในเจ็ด นี่คือการเดินแบบสุ่มบนกราฟ บุคคลของเราจะถึงบ้านหรือไม่ ปรากฏว่าภายใต้เงื่อนไขที่ไม่รุนแรงนัก คำตอบก็ยังคงเป็นใช่^{[ 48 ]}แต่ขึ้นอยู่กับกราฟ คำตอบสำหรับคำถามที่แตกต่างกันว่า 'คนสองคนจะพบกันอีกหรือไม่' อาจไม่ใช่ว่าพวกเขาจะพบกันบ่อยเป็นอนันต์เกือบแน่นอน^{[ 49 ]}

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

ทฤษฎีบท : กราฟจะเป็นกราฟชั่วคราวก็ต่อเมื่อความต้านทานระหว่างจุดหนึ่งกับอนันต์มีค่าจำกัด ไม่สำคัญว่าจะเลือกจุดใดหากกราฟนั้นเป็นกราฟเชื่อมต่อ

กล่าวอีกนัยหนึ่ง ในระบบชั่วคราว เราต้องเอาชนะความต้านทานที่มีค่าจำกัดเท่านั้นจึงจะไปถึงอนันต์จากจุดใดๆ ได้ ส่วนในระบบเวียนเกิด ความต้านทานจากจุดใดๆ ไปถึงอนันต์นั้นมีค่าเป็นอนันต์

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

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

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

ในบริบทของกราฟสุ่มโดยเฉพาะอย่างยิ่งในแบบจำลอง Erdős–Rényiได้มีการค้นพบผลลัพธ์เชิงวิเคราะห์เกี่ยวกับคุณสมบัติบางประการของตัวเดินสุ่ม ซึ่งรวมถึงการกระจายของเวลาการกระทบครั้งแรก^{[ 50 ]}และเวลาการกระทบครั้งสุดท้าย^{[ 51 ]}ของตัวเดิน โดยเวลาการกระทบครั้งแรกจะกำหนดโดยเวลาแรกที่ตัวเดินก้าวเข้าไปในไซต์ที่เคยเยี่ยมชมมาก่อนของกราฟ และเวลาการกระทบครั้งสุดท้ายจะสอดคล้องกับเวลาแรกที่ตัวเดินไม่สามารถทำการเคลื่อนไหวเพิ่มเติมได้โดยไม่ต้องกลับไปเยี่ยมชมไซต์ที่เคยเยี่ยมชมมาก่อน

หนังสือออนไลน์ของAldous และ Fill เป็นแหล่งอ้างอิงที่ดีสำหรับเรื่องการเดินสุ่มบนกราฟ ส่วนเรื่องกลุ่มนั้นดูได้จากหนังสือของ Woess ถ้าเคอร์เนลการเปลี่ยนสถานะเป็นแบบสุ่ม (ขึ้นอยู่กับสภาพแวดล้อม) การเดินสุ่มนั้นจะเรียกว่า "การเดินสุ่มในสภาพแวดล้อมแบบสุ่ม" เมื่อกฎของการเดินสุ่มรวมถึงความสุ่มของกฎนั้นจะเรียกว่ากฎแบบปรับค่า (annealed law) ในทางกลับกัน ถ้าถูกมองว่าคงที่ กฎนั้นจะเรียกว่ากฎแบบดับ (quenched law) ดูได้จากหนังสือของ Hughes, หนังสือของ Revesz หรือบันทึกการบรรยายของ Zeitouni ${\displaystyle p(x,y)}$${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \omega }$

เราสามารถคิดเกี่ยวกับการเลือกขอบที่เป็นไปได้ทั้งหมดด้วยความน่าจะเป็นเท่ากับการเพิ่มความไม่แน่นอน (เอนโทรปี) ให้สูงสุดในระดับท้องถิ่น เรายังสามารถทำได้ในระดับสากล – ในการเดินสุ่มเอนโทรปีสูงสุด (MERW) เราต้องการให้เส้นทางทั้งหมดมีความน่าจะเป็นเท่ากัน หรือกล่าวอีกนัยหนึ่งคือ สำหรับจุดยอดสองจุดใดๆ เส้นทางแต่ละเส้นที่มีความยาวที่กำหนดจะมีความน่าจะเป็นเท่ากัน^{[ 52 ]}การเดินสุ่มนี้มีคุณสมบัติการกำหนดตำแหน่งที่แข็งแกร่งกว่ามาก

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

• การเดินหลีกเลี่ยงตัวเอง^{[ 53 ]}

เส้นทางเดินหลีกเลี่ยงตัวเองที่มีความยาวnบนคือ เส้นทางสุ่ม nขั้นที่เริ่มต้นที่จุดกำเนิด เปลี่ยนผ่านเฉพาะระหว่างไซต์ที่อยู่ติดกันในไม่กลับไปที่ไซต์เดิม และถูกเลือกอย่างสม่ำเสมอในบรรดาเส้นทางดังกล่าวทั้งหมด ในสองมิติ เนื่องจากการดักจับตัวเอง เส้นทางเดินหลีกเลี่ยงตัวเองโดยทั่วไปจึงสั้นมาก^{[ 54 ]}ในขณะที่ในมิติที่สูงกว่านั้นจะยาวเกินขอบเขตทั้งหมด แบบจำลองนี้มักถูกใช้ในฟิสิกส์พอลิเมอร์ (ตั้งแต่ทศวรรษ 1960) ${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle \mathbb {Z} ^{d}}$

• การเดินแบบสุ่มที่ลบวงวน^{[ 55 ] [ 56 ]}
• การเดินแบบสุ่มที่เสริมแรง^{[ 57 ]}
• กระบวนการสำรวจ​
• การ เดิน สุ่มแบบหลายตัวแทน^{[ 58 ]}

การเดินแบบสุ่มที่เลือกเพื่อเพิ่มอัตราเอนโทรปี ให้สูงสุด จะมีคุณสมบัติในการจำกัดบริเวณที่แข็งแกร่งกว่ามาก

การเดินแบบสุ่มซึ่งทิศทางการเคลื่อนที่ในเวลาหนึ่งมีความสัมพันธ์กับทิศทางการเคลื่อนที่ในเวลาถัดไป ใช้เพื่อจำลองการเคลื่อนที่ของสัตว์^{[ 59 ] [ 60 ]}

• การเดินสุ่มแบบแตกแขนง  – กระบวนการสุ่ม
• การเคลื่อนที่แบบบราวน์  – การเคลื่อนที่แบบสุ่มของอนุภาคที่แขวนลอยอยู่ในของเหลว
• กฎของลอการิทึมซ้ำ  – ทฤษฎีบททางคณิตศาสตร์
• การบินแบบเลวี (Lévy flight)  – การเดินแบบสุ่มที่มีความยาวก้าวแบบหางยาว
• สมมติฐานการหาอาหารแบบบินของเลวี
• การเดินสุ่มแบบลบวงวน  – แบบจำลองสำหรับเส้นทางสุ่มแบบง่าย
• การเดินสุ่มแบบเอนโทรปีสูงสุด  – การเดินสุ่มแบบมีอคติประเภทหนึ่งบนกราฟ
• การเดินแบบหลีกเลี่ยงตัวเอง  – ลำดับของการเคลื่อนที่บนโครงตาข่าย
• รากหน่วย  – ลักษณะเฉพาะของกระบวนการสุ่มบางประเภท

• Aldous, David ; Fill, James Allen (2002). Reversible Markov Chains and Random Walks on Graphs . เก็บถาวรจากต้นฉบับเมื่อวันที่ 27 กุมภาพันธ์ 2019
• ดอยล์, ปีเตอร์ จี.; สเนลล์, เจ. ลอรี (1984). การเดินแบบสุ่มและเครือข่ายไฟฟ้า . ตำราคณิตศาสตร์คารัส เล่มที่ 22. สมาคมคณิตศาสตร์แห่งอเมริกา . arXiv : math.PR/0001057 . ISBN 978-0-88385-024-4MR  0920811 .​
• เฟลเลอร์, วิลเลียม (1968), บทนำสู่ทฤษฎีความน่าจะเป็นและการประยุกต์ใช้ (เล่ม 1) ISBN 0-471-25708-7
• ฮิวส์, แบร์รี ดี. (1996), การเดินแบบสุ่มและสภาพแวดล้อมแบบสุ่ม , สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด. ISBN 0-19-853789-1
• นอร์ริส, เจมส์ (1998), โซ่ Markov , สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ISBN 0-521-63396-6
• Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" เก็บถาวรเมื่อ 4 มีนาคม 2016 ที่Wayback Machine , Mathematische Annalen , 84(1–2):149–160, มีนาคม 1921
• Révész, Pal (2013), การเดินแบบสุ่มในสภาพแวดล้อมแบบสุ่มและไม่สุ่ม (ฉบับที่สาม) , สำนักพิมพ์ World Scientific ISBN 978-981-4447-50-8
• Sunada, Toshikazu (2012). Topological Crystallography: With a View Towards Discrete Geometric Analysis . Surveys and Tutorials in the Applied Mathematical Sciences. Vol. 6. Springer. ISBN 978-4-431-54177-6.
• ไวส์ จี. แง่มุมและการประยุกต์ใช้ของการเดินแบบสุ่ม , นอร์ทฮอลแลนด์, 1994.
• Woess, Wolfgang (2000), การเดินแบบสุ่มบนกราฟและกลุ่มอนันต์ , Cambridge tracts in mathematics 138, สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ISBN 0-521-55292-3

• ค่าคงที่การเดินสุ่มของโปลยา
• การเดินแบบสุ่มใน Java Applet เก็บถาวรเมื่อวันที่ 31 สิงหาคม 2550 ที่Wayback Machine
• การเดินสุ่มควอนตัม
• ตัวประมาณการเดินสุ่มแบบเกาส์เซียน
• แบบจำลองการนำไฟฟ้าของอิเล็กตรอนโดยใช้การเดินสุ่มที่มีเอนโทรปีสูงสุดโครงการสาธิตของ Wolfram