Why Do Random Walks Get Lost in 3D? — Transcript

Full transcript

1. 0:00imagine standing at the origin of an
2. 0:02infinite number line
3. 0:03you begin flipping a fair coin that
4. 0:05tells you where you should move
5. 0:07if you get tails you take one step to
6. 0:09the left and if you get heads
7. 0:11one step to the right this is a random
8. 0:14walk in one dimension and more
9. 0:16specifically this is a symmetric
10. 0:18random walk where we have equal
11. 0:19probability of moving in either
12. 0:21direction
13. 0:23we can generalize this type of walk to
14. 0:25any number of dimensions
15. 0:27randomly selecting a unit step in any
16. 0:29axis direction
17. 0:31so in two dimensions we can take a step
18. 0:33along the x or y axis
19. 0:35and in three dimensions along the x y or
20. 0:37z axis
21. 0:41in the early 1900's hungarian
22. 0:43mathematician
23. 0:44george poglia was interested in the
24. 0:46following question
25. 0:48once we begin our random walk are we
26. 0:50guaranteed to eventually return
27. 0:52to where we started we might think that
28. 0:56if we walk forever we'll surely come
29. 0:58back at some point
30. 1:00however long it takes but when it comes
31. 1:02to infinity
32. 1:03our intuitions can mislead us it turns
33. 1:06out while this is correct in the
34. 1:08one and two dimensional cases in three
35. 1:10dimensions this is suddenly no
36. 1:12longer true and in fact it's more likely
37. 1:14that we never return
38. 1:16our probability of returning drops from
39. 1:18a clean one
40. 1:19to .34 as it's often summarized
41. 1:23a drunk man will find his way home but a
42. 1:25drunk bird
43. 1:26may get lost forever now you're probably
44. 1:30asking why
45. 1:31why this abrupt change in behavior as we
46. 1:34jump from two dimensions
47. 1:35to three sure as we move to higher
48. 1:38dimensional space we have
49. 1:39more choices for our steps and it makes
50. 1:42sense that it would probably take
51. 1:43longer to return but to never return
52. 1:46that's strange in this video
53. 1:49we'll try to gain some intuition about
54. 1:51this awesome result
55. 1:53known as polia's recurrence theorem
56. 1:56let's first formalize the question a bit
57. 1:59let s
58. 1:59n be our location at step n then
59. 2:02sn is the sum of each of our individual
60. 2:05steps x
61. 2:05i as i ranges from 1 to n
62. 2:09each step x i is drawn uniformly among
63. 2:12the axis aligned unit steps
64. 2:14so for a given dimension d there are two
65. 2:17times d
66. 2:18possible steps and each has an equal
67. 2:20chance of selection
68. 2:23now familiarity with markov chains won't
69. 2:26be required to understand anything in
70. 2:28this video
71. 2:29but if you have seen them before you
72. 2:30know that we can view the walk as a
73. 2:32markov chain
74. 2:33with an infinite set of possible states
75. 2:36every d
76. 2:36dimensional lattice point with
77. 2:38transition probabilities 1 over 2d
78. 2:41for jumping to each neighboring state
79. 2:43and 0 for jumping to any farther state
80. 2:46we're concerned with this probability
81. 2:49the probability
82. 2:50of returning to the origin at least once
83. 2:53if this probability equals 1 the origin
84. 2:55will be called a recurrent state
85. 2:57but if there's some non-zero chance of
86. 2:59never returning
87. 3:00it's transient suppose the origin is
88. 3:04known to be recurrent
89. 3:05then when we eventually do return we
90. 3:08will basically begin a brand new walk
91. 3:10again with the guarantee of returning
92. 3:13naturally we might expect to visit the
93. 3:15origin
94. 3:15infinitely many times over an infinite
95. 3:17time frame
96. 3:19for these types of systems this
97. 3:21condition turns out to be both necessary
98. 3:23and sufficient
99. 3:24we have recurrence if and only if the
100. 3:27expected number of returns
101. 3:28is infinite let's take a look at some
102. 3:31walks in one dimension
103. 3:33and see if we notice anything about
104. 3:34their behavior
105. 3:36we'll set a hundred walkers to each take
106. 3:3810 steps and record their final
107. 3:44positions
108. 3:50one thing we see of course is that since
109. 3:52we had an even number of time steps
110. 3:54we have zero walkers on the odd
111. 3:56coordinates but there also seems to be a
112. 3:58higher concentration of walkers near the
113. 4:00origin
114. 4:02let's try a thousand steps with ten
115. 4:04thousand walkers
116. 4:06our walkers are more spread out now but
117. 4:08we still see this bell-shaped curve
118. 4:10which may remind you of a normal or
119. 4:12gaussian distribution
120. 4:14the central limit theorem tells us that
121. 4:17the distribution of the sum
122. 4:18of independent and identically
123. 4:20distributed random variables
124. 4:22with finite mean and variance ultimately
125. 4:24converges to a normal distribution
126. 4:27well we definitely meet those conditions
127. 4:29here the mean of our two step choices
128. 4:32is zero and our squared step length is
129. 4:34always one
130. 4:36so if the sum of our individual steps is
131. 4:38approaching a normal distribution
132. 4:40what is its width how far do we expect
133. 4:43to get
134. 4:45let's compute the average squared
135. 4:47distance from the origin at step n
136. 4:49this is also equivalent to the variance
137. 4:51of sn because
138. 4:53sn is a centered random variable the
139. 4:55expected position
140. 4:57no matter how many steps we take is
141. 4:59still zero the origin
142. 5:04the squared distance will just be the
143. 5:05square of the sum of our steps
144. 5:11linearity of expectation allows us to
145. 5:13bring the expectation operator
146. 5:15inside these two summations
147. 5:19we already know that the square of each
148. 5:21step length is one
149. 5:22but what is the expectation of x i times
150. 5:25xj
151. 5:26that is the product of two independent
152. 5:28steps
153. 5:30well half the time the step directions
154. 5:32will be the same
155. 5:33and half different likewise the product
156. 5:36is
157. 5:36negative one or one with equal frequency
158. 5:39so the expectation of this product is
159. 5:41zero and overall
160. 5:43we end up with a sum of n ones
161. 5:46so our average square distance is just n
162. 5:49and our root mean squared distance the
163. 5:52standard deviation of sn
164. 5:54is the square root of n you're likely
165. 5:57familiar with the
166. 5:586895 99.7 rule
167. 6:01where we expect 68 95 and 99.7
168. 6:05of the values of a normal distribution
169. 6:08to lie within one
170. 6:09two and three standard deviations of the
171. 6:11mean respectively
172. 6:13so let's first think heuristically about
173. 6:15our probability of being at the origin
174. 6:17at a given step since it's only possible
175. 6:20to return
176. 6:21in an even number of steps we'll ask
177. 6:24what's the probability of returning on
178. 6:26step
179. 6:262n well if our distribution is
180. 6:29approximately normal
181. 6:31we expect to end up within one standard
182. 6:33deviation of the mean
183. 6:34the majority of the time for two n steps
184. 6:38our standard deviation is radical two n
185. 6:40and there are about
186. 6:41two times radical two n positions within
187. 6:43this distance from the origin
188. 6:45with half of them being even if we treat
189. 6:48these options uniformly
190. 6:50we might guess that our probability of
191. 6:52being at the origin is on the order of
192. 6:541 over radical 2n now this constant is
193. 6:57probably a bit off because
194. 6:59we only expect to be within this
195. 7:00interval 68
196. 7:02of the time and in truth we should have
197. 7:04a bit more probability mass
198. 7:06for positions closer to the origin but
199. 7:08it turns out this is a pretty good
200. 7:10approximation
201. 7:11to be a little more accurate let's
202. 7:13determine how many possible trajectories
203. 7:15there are
204. 7:16of length two n for each step we have
205. 7:19two choices
206. 7:20negative and positive so that's two
207. 7:22raised to the two nth power
208. 7:24distinct trajectories how many of these
209. 7:27have us back at the origin
210. 7:28at step 2 n well such a trajectory would
211. 7:32be required to have exactly as many
212. 7:34negative steps
213. 7:35as positive steps we can simply focus on
214. 7:38which steps will be designated as
215. 7:40positive while the rest will be negative
216. 7:43so how many ways are there to select n
217. 7:45indices out of 2n
218. 7:47total indices that would be the binomial
219. 7:50coefficient
220. 7:512n choose n so our probability of being
221. 7:54back at the origin
222. 7:55is 2n choose n over 2 to the 2n
223. 7:59the number of suitable trajectories
224. 8:01divided by the total number of
225. 8:03trajectories
226. 8:04great but now we have several factorials
227. 8:07which are difficult to evaluate
228. 8:09to help we can bring in sterling's
229. 8:11formula which is known to be
230. 8:12asymptotically equivalent to the
231. 8:14factorial
232. 8:16the derivation for sterling's formula is
233. 8:18a bit involved and deserves its own
234. 8:20separate video
235. 8:21at the moment let's just take it off the
236. 8:23shelf and plug it in
237. 8:33after simplifying we end up with this
238. 8:34one over radical pi
239. 8:36n so we were pretty close the
240. 8:39probability decreases proportionally
241. 8:41to 1 over radical n with this in hand
242. 8:44let's evaluate the expectation of the
243. 8:47number of visits
244. 8:48in one dimension the summand here is an
245. 8:51indicator variable where it equals 1 if
246. 8:54s2n
247. 8:55is the origin and 0 otherwise
248. 9:04we end up with a p series where p our
249. 9:07power
250. 9:08is one half if we remember from calculus
251. 9:11a p
252. 9:11series with p less than or equal to one
253. 9:14ends up diverging because the summand
254. 9:16decreases too slowly
255. 9:17regardless of any constant factor
256. 9:19multiplying it
257. 9:21the expected number of returns to the
258. 9:22origin is therefore infinite
259. 9:24and our probability of returning is one
260. 9:28what happens in two dimensions consider
261. 9:31two one-dimensional walkers taking steps
262. 9:33simultaneously
263. 9:35one confined to the x-axis and the other
264. 9:37to the y-axis
265. 9:39this is actually equivalent to a single
266. 9:42two-dimensional walk
267. 9:43but rotated by 45 degrees and slightly
268. 9:48rescaled
269. 9:50back to the origin requires both walkers
270. 9:52to return
271. 9:53at the exact same time step if we take
272. 9:56the expected number of returns now
273. 9:58our p series has power one grows like
274. 10:01the harmonic series
275. 10:03and diverges again
276. 10:08you might guess where this is going is a
277. 10:10three-dimensional walk equivalent to
278. 10:12three simultaneous one-dimensional walks
279. 10:16well it isn't exactly an actual
280. 10:18three-dimensional walk has six
281. 10:20options at each step two for each of the
282. 10:23three axes
283. 10:24but three one-dimensional walks have
284. 10:26eight possible options at each step
285. 10:29still for the purposes of recurrence the
286. 10:31behavior is equivalent
287. 10:33we won't do the full derivation here
288. 10:34which is a bit more involved than in one
289. 10:36and two dimensions
290. 10:38but the return probability for the
291. 10:39three-dimensional walk on step two n
292. 10:41ends up decreasing proportionally to n
293. 10:44to the negative three halves
294. 10:46our p series now has a power greater
295. 10:48than one and converges
296. 10:51in 3d we expect to only return a finite
297. 10:54number of times
298. 10:57in these calculations we focused on the
299. 10:59origin but it's easy to see that in
300. 11:01one and two dimensions every other
301. 11:03location will be visited as well
302. 11:06why consider some point a and a single
303. 11:09path from the origin
304. 11:11to a for example in one dimension this
305. 11:14could be the straight line path from the
306. 11:16origin to a
307. 11:18well every time we're at the origin
308. 11:20we'll have
309. 11:21some positive probability of following
310. 11:23this path
311. 11:24and therefore visiting a if we view this
312. 11:27as a bernoulli trial
313. 11:28where success is defined as following
314. 11:31this path
315. 11:32we'll have probability of one of getting
316. 11:34a success over an infinite number of
317. 11:36trials
318. 11:37and when we do reach a we can view it as
319. 11:39the initial state of a new walk
320. 11:42so in one and two dimensions we have
321. 11:44probability one
322. 11:45of visiting every point with infinite
323. 11:48expected visits for each
324. 11:50recurrence at the origin implies
325. 11:52recurrence everywhere
326. 11:55now algebraically this all might be
327. 11:57convincing
328. 11:58but still why this abrupt change from
329. 12:01two to three dimensions
330. 12:03what ultimately clicked for me was
331. 12:05understanding that higher dimensional
332. 12:07walks
333. 12:08only behave like two-dimensional objects
334. 12:10expanding over time
335. 12:13alright what does that mean
336. 12:16to understand let's revisit the question
337. 12:18of average distance traveled
338. 12:21before we proved that the root mean
339. 12:23squared distance of a one-dimensional
340. 12:25walker's position
341. 12:26at step n is root n
342. 12:29it turns out that this square root
343. 12:31relationship holds in any number of
344. 12:33dimensions
345. 12:34let s n i be the i-coordinate of the
346. 12:37walker at step n
347. 12:40the expected squared distance along the
348. 12:42i-axis
349. 12:43will be equal to the number of steps
350. 12:45taken along that axis
351. 12:48so the expected squared total distance
352. 12:50is n
353. 12:51regardless of the dimensionality of the
354. 12:53walk
355. 12:55what if we ask a related question when
356. 12:57we first reach a distance r
357. 12:59how many steps do we expect to have
358. 13:01taken
359. 13:02similarly this ends up being r squared
360. 13:05steps
361. 13:06this is really the key suppose that
362. 13:09optimistically
363. 13:10when a three-dimensional walk reaches
364. 13:12distance r
365. 13:14all of its r-squared expected steps
366. 13:16visited distinct points
367. 13:17with zero repeats but the total number
368. 13:21of points within this distance will grow
369. 13:23like r
370. 13:23cubed as time goes on the walk will
371. 13:26cover an ever decreasing fraction of
372. 13:28these points
373. 13:29proportional to r squared over r cubed
374. 13:32or one over r and won't be able to catch
375. 13:35up
376. 13:36so the rate at which three-dimensional
377. 13:38walks move away from the origin
378. 13:40is too great relative to this coverage
379. 13:42rate
380. 13:43in the limit even though a
381. 13:44three-dimensional walk will visit
382. 13:46infinitely many points
383. 13:47it will only visit zero percent of the
384. 13:50entire state space
385. 13:52the origin can't be recurrent because we
386. 13:54know
387. 13:55as with the one and two dimensional
388. 13:56cases recurrence would imply
389. 13:59visiting every point and while sure it's
390. 14:02possible for it to return to the origin
391. 14:04a few times by chance
392. 14:05eventually it will get lost forever the
393. 14:08walk is like
394. 14:09an expanding two-dimensional object
395. 14:11because they exhibit similar ratios of
396. 14:14distance reached versus expected
397. 14:16coverage
398. 14:17if a circle lying on the z equals zero
399. 14:20plane begins expanding
400. 14:21when it reaches distance r it will only
401. 14:24have encompassed roughly
402. 14:25pi r-squared points an ever-decreasing
403. 14:28fraction of the bounding sphere
404. 14:30of radius r in two dimensions
405. 14:34the expected r squared steps ensure that
406. 14:36the walk never falls too far behind
407. 14:39the coverage rate ends up being
408. 14:41sufficient to eventually visit all the
409. 14:42points
410. 14:43infinitely many times with probability
411. 14:451.
412. 14:47for some more on random walks and
413. 14:49various proofs of polio's recurrence
414. 14:51theorem
415. 14:51check out the links in the description
416. 14:53thanks for watching