Jorge has lost his car keys! He's not using a very efficient search; in fact, he's doing a
random walk. He starts at 0, and moves 1 unit to the left or right, with equal probability. On the next step, he moves 2 units to the left or right, again with equal probability. For subsequent turns he follows the pattern 1, 2, 1, 2 etc.
His keys, in truth, were right under his nose at point 0. Assuming that he'll spot them the next time he sees them, what is the probability that Jorge will eventually return to 0?
Note: For purposes of the problem, assume that Jorge is not looking while he is merely passing through a point. For example, he will not look for his keys while he passes through 0.
See later comments for corrections to this.
If the step size were always 2, it would be like a random walk of step size 1 while considering only alternate points. In that sort of walk:
"How many times will the random walk cross the line if permitted to continue walking forever? The following, perhaps surprising theorem is the answer: simple random walk will almost surely cross every point an infinite number of times." -- From http://en.wikipedia.org/wiki/Random_walk
But size-1 steps are also allowed. A given pair of moves (a 1 and a 2) are a move of either 3 or 1. So let's consider this as a set of random moves of size 3, but with those of size 1 randomly placed.
On any given return to the origin, there's only a 1/3 probability of hitting the origin exactly rather than jumping over it.
So there's a 1/3 probability of hitting it on the first try. Then of the 2/3 cases where that does not happen, 1/3 the time it will happen on the second try, etc. So the probability of evantual exact return is
1/3 + 2/9 + 4/27 + 8/81 + ... = 1
so he is certain to return to the starting position.
A simulation shows a distribution of how long it will take to return to the starting position exactly:
DEFDBL A-Z
RANDOMIZE TIMER
CLS
FOR trial = 1 TO 900
x = 0: mv = 1: ct = 0
DO
x = x + mv * 2 * mv * (INT(RND(1) * 2) - .5)
mv = 3 - mv
ct = ct + 1
LOOP UNTIL x = 0
PRINT ct;
s = LEN(LTRIM$(STR$(ct)))
dCt(s) = dCt(s) + 1
NEXT trial
PRINT
FOR s = 1 TO 10: PRINT dCt(s); : NEXT
PRINT
Several runs show, sometimes, as many as nearly 17 million moves of size 1 or 2, though the runs below show only up to 7-digit numbers as the number of moves taken to return to the start.
The number of steps to return to the origin is listed and then categorized, for 900 moves in each run:
8660 128 4 55 92 4 883 12 8 4 20 40 4 1084 1207 32 4 92 44
8 52 8 6384 48 16 96 4 224 8 23 15 312 12 4 43 183 4 7 56
8 12 4 4 4 3676 32 44 7 403 39 4 51 215 4 7 496 4 4 4 96
140 24 7 7 4 4 648 4 7991 4 95 603 23 8 244 83 4 4 27 4 12
8 7 27 8 24 43 15 4 15 60 19 24 8 215 8 4 83 4631 16 379
12 35 43 8 71687 32 160 11 4 7 12 15 4 91 91839 24 12 7 287
124 4 24 348 4 4 23 16 11 227 163 1671 72 4 2052 4 4 15 4
44 7 4 4 47 4 120 20 16 71 4 15 4 43 203 44 4 27 11 4 7 4
4 12 252 4 4 8 12 1111 4 7 968 60 11 4 7 16 63 8 4 12
20156 47 4 4 11 12 44 4 15 4 16 8 19 4 11 39 8 4 24 19 24
4 52 7 284 4 4 4 11 36 19 56 7 4 43 76 20 146264 16 4 88
56 12 4 24 4 20 75 379 68 88 767 7 4 28 12 11 96 8 51516
663 211 4540 23 35 4 3947 39 20 17660 4 4 32 143303 4 184 4
23 76 575 124 56 7 20 504 4 31 4 8 119 4 99 20 99 159 11 11
27 4 5612 4963 8 4 72 83 1495 96 16 188 7 1603 71 2411 71 103
4 15 16 39 551 12 8 68 64 4 8 372 4 188 16 4 27 4 12 5464
20 324 47 8 88 146792 56 35 4 4 52 19208 92 115 435 12 39 4
4 28 136 52 12 103 199 48 7 99 51 7 8 8 7 7 28 35 4 1060 8
7 236 88 8 27 4 11 11 1083 4 4 23 11 20 27 120 2148 84 4 44
3359 24 24 4 4 28 4 24 27 56 16 4 359 4 104 59 8 7 12 1972
427 120 23 4 35 40 24 200 7 11 76 4 7 164 16 59 8 4 19 4
14276 4 4 4 44 4 55 4 11092 108 4 6200 15 19 135 12 7 48
40039 896 116 4 11 12 12 4 4 27 15 7 7 8 15 15 35 4 4 4 12
4 272 4 19 4 8 227 4 8 179 8 416 59 4 1611 4 19 12 8 4 31
11 335 4 8 8 260 11 8 4 8 16 4 12 4 4 4 4 8 8 23400 4 119
19 8 4 171 576 19 4 147 15 16 51 100 4 15 43 1792 35 4 4 35
28 72 31 28 195 304 20 4 83 8 11 652 16 12 55 40 19 28 31283
8 8 24 8 4 4 4 391 12551 261264 12 28 8 4 251 31 4 100 44
27 9804 8 112 79 4 52 8 191 12 32 7 4 52 7 4 1248 96 23 4
67 339 4 24 67 19 4 4 4 407 11 16 132 1831 1243 3071 12 4 43
4 4 75 4 4 175 8 11 4 11 7 1403 4 4 44 36 988 1207 29015 4
219 24 36 368 7 4 3403 8 4832 12 15 11 4 15 7 4 19 24 852
63 7 55 68 12 12 24 4 4 8 4 8 47 16 447 4 31 8 35 72 16 8
4 11 64 72 4 68 83 4 13239 11 395 4 68 2907 8 107 4 44 31 4
35 119 20 56 668 16 191 12 16 8 4 44 51 127 10599 4 12 4 164
31 43 11 4 11 92 39 31 231 36 4 4 12 4 4 84 15 8 12 32 136
20 8 15 256 7 4 4 55 179 4 12 24 4 43 27 4 4 48 127 55 79
12 4 128 4 275 4 16 4 435 120 235 4 1028 16 4 15 83 44 4 71
16 96 56 4 4 2304 4 43 4 44 4 24 7 4 7 23 943 60 99 8 7 8
4 20911 4 4 31 1027 28 4 7 51 4 251 11 11 12 7 119 8 4 4 4
35 76 283 7 4 4 60 736 8 4 2071 16 1496 12 139 8 3663 28 11
11 7 52 8 31 6228 328 7 44 8 147 4 4 4 87 11 7 4 19 4
40799 11 7 43 11 4 67 4 664 31 12 104 15 4 5791 4 267 31 32
216 7 4 11 4 4 4 80 4 7 27 4 7 4 16455 11 12 28 4 4 4 4
35 27 4 64540 4 908 52 1172 348 4 52 20 100 4 2576 4 9367 4
7 84 76
The categorization is by the number if digits in the number of steps to return to the origin:
digits: 1 2 3 4 5 6
count 340 372 118 47 19 4 0 0 0 0
15912 4 19 12 12 320 36 8 59 4 4 367 159 35 131 44 232 4 24
4 592 40 47 4 515 4 19 124 4 4 4 15 23 4 88 192 4 44 8 7
4 12 4 4 4 4 39 8 35 28 187 4 4 19 15 60 60 4 4 16 3728 4
15 32 452 16 4 15 4241072 4 4 4 204 4 68 8904 52 59 11 4 4
4 52 32 7 4 40 4 4 36720 4 15 211 39 4 11 27 8 28 4 51 16
7 476 68 24 7 4 12 4 7 91 4 16 35 104 3567 16 19 4 4 232 4
4 4 4 36 32 11 4 88 8 315 8 4 159 4 3383 11 124 20 236 152
4 23 7 31 12 35 68 276 84 7 4 100 267 7 4 11 19 172 23 8 4
236 4 20 739 11 4 332 4223 96 4 199 4 12 11 16 4 7 28 20 4
11 131 4 23 80 4 11 4 8 91 4 47 4 119 51 4 25663 35 31 4
44 183 4 28 4 248 23 291 128 68 8 6447 4112 11 12 4 4 4 4 8
8 4 23 8 36 4 72 35 12 35 16 27 8 48 4 4 8 164 11 15 43 4
4 691 3960 19 155 4 4 235 23 24 16 16 55 24 4 12 11 359 1355
163 2392 255 59 4 4 4 24 112 68 19 51823 4 28 19 79 36 6220
27 4 8 60 4 11 4 4078459 8 2891 56 4 7 16 7 40 15 4 8 7 4
4 28 4 4 712 4 8 8 172 4 16 4 248 271 747 119 2148 360 8 4
12 4 15 12 4 68 56 4 7 71 1804 35 656 192 19 19 20 763 23
32055 8 31 32 4 4 44 4 1315 707 351 463 303 8 36 404 107
21695 380 8 12 23 4 39 56 7 19 11 8 4 4 2452 4 103 4 4 15
12 4 4 11 276 19 155 1467 12 40 4 1512 16 4 4 8 60 23 208 4
4 592 23 4 4 7 4 64 4 44 36 7 16 11 5864 27 8 4 4 4 4
287635 276 855 40 4 55 4 171 972 11 7 4 151 12 21948 64 7 28
228 4 27 20 4 51 16 4 56 1208 4 316 15 16 23 20 100 36 3148
8 8 4 7 19 24 7 12 24 4 268 4 7 67 4 23 16 15 96 15 8 39
4 4 20 15 4 75 4 44 23 448 28 11 11 8291 20 4 300 92 8 956
12 6216 12 463 127 5972 11 20 95 7 24 4288 4 2079 27319 4 11
4 8516 4 647 32 20 20 71 7 8 8 148 24 4 56 8 151 4 12 10300
808644 160 56 4 4 8 280 15 8527 175 4 39 656 4 12 48 3387 43
4 56 27 7 779 183 928 95 100 12 11 99 4 8 4 4 4 4 4 4 4
40 12 28 311 148 4 7 435 19663 19 135 8 19 8 55 11 8 27 248
4 7 344 51 4 15 23804 24 43 4 4 12 4 7 131 96 12 411 4 27
15 8 4 19 4 275148 4 140 19 4 83 48 16 28 19 4 55 4 4 1620
19 9971 12 4 12 12 4 15 43 4 4 52 15 4 4 24 39 24 8 24 4
23 48 4 11 64 4 44 4 4 4 4 15 887 424 20 44 16 8 7 56
58460 180 931 8 159 8 4 4 44 4 47 108 208 88 12 16 67 72 19
4 11 20 4 7 68 4 23 4 4 8 4 115 11 28 44 11 36 4 7 23 4
19 4 27 4 216 15 48 2115 56 164 11 15 583 16 4 135 248 4 96
75 4 368 16 27 40 8 4 4 303 40 131 8 4 44 71 16 4 23 8 16
63 39 17175 11 88 35 20 104 240 11 187 8 20 284 8 16 4 20 4
4 4 4 36 32 564 8 4 8 7279 4 7 4 59 16 16 24 19 75 4832 12
4 4 35 2248412 8 4 19 4 140 47 100 4335 76 47 39 1856 16 4
17756 35 32 432504 7 4 4 4 4 4 227 6159 39 1424 15 87 7 240
4 664 7 108 4 7 2912 168 4 12 36 4 12 228 4 111 20 35 16 64
8 4 24 15 104 8 84 4992 1427 60 171 1228 4 7 87 4 4155 12
360 727 11251 19 12 4 4 11 80 16 38843 4 740 499 27 47 15
6235 4 8 99 11 91 4903 291228 20 603 291 458420
1 2 3 4 5 6 7
327 366 137 45 16 6 3 0 0 0
4 4 160 4 7 32 16 252 47 92 8172 180 7 4 28 15 4 212 71 64
32 8 64 96 20 95 120 39 16 4 2587 12 4 4 6219 27 72 11 4
148 16 4 107 56 40 36 15 56 4 11 55 144 8 4 1288 4 28 7 4
15 15 72 3644 4 8 264 4 63 116 4 12 4 7 76 47 7 12 8 23 88
4 104 15 8 24 7 79116 7 3367 64 35 131 12 12 244 384 4 39
444 1264 12 4 36 32 15 724 35 10147 684 196 52 27 8 48 4 4 4
76 127 4 15 4 8 4 4 15 12 20 355 4 20 40 27 31 4 16 4 8
24 92 15 984 7 4 8 4 120 36 83 2499 120 27 4 19 4 77159 84
23 48 72 7 4 147 4 788 4 52 95 24 132 16 948 4 407 4 11 8
1664 88 20 12 43 8 11 35 4 68 8 852 64 51 411 32 12 4 20 8
187 12 1487 11 7 299 4 1372 448 8 75 4 4 23 8 8 279 4 63 4
8 4 20 4 7 47 20 52 7 71 19 12 8 4 4 4 19 24 151 67 16
3431 44 15 8 168 11 4 4 11 32 12 8 583 11 4 4 4 132 511 11
20 4 17084 115 4 8 16 4 7 8 115 148 12 96 196 136 40 32 255
19700 23 344 7 12 68 1295416 8 315 864 44 4 43 52 4 4 79 384
8 12 8 4 7 367 2015 43 4 144 8 40 19 4 8 4 104 7 375 12 19
8 148 123 16 4 107 7 4 40 32 4 11 4 4 31 4 127 3688 343 11
59 7 4 31 16 4 15 20 27 4 7 8 3472 7 8 420 19 8 28 4 20
19 92 4 39 40 8 24 4 64 91 4 2624 4 43 4 17727 31 27 19 31
543 4 20 24 119 215 4 51163 20 4 8 19 75 224 7 4 172 4 4
284 60 8 4 11 4 55 8 4 4 4 279 464 167 4 12 503 15 4 8435
8 12 251 79 8 4 4 196 100 24 4 19 7 23 4 11 475 4 8 4 15
4 4 7 4 4 4 7 100 1264 1776 40 4 11 4 51 608 4 8 119 4 7
23 115 95 12 7 7 135 4 4 943 604315 351 4 4 12 4 152 12 568
8 7 12 12 20 48 7 35 12 336 4 16 72 8 4 35 20 4 104 4 4
40 4 8 75 11 1140 4 4932 19 4 4 60 4 47 427 20 32 11 8 4
223 32 27 8 44 348 4 92 1124 208 60 4 840 1863 8 52 155 27
15 12 959 83 12 23 172 39 4 4 4 108492 4 208 15 4 3043 4 4
75 4 15 12 4059 4 1375 376 8 27 72 4 15 24 4 12 12 19 4 4
64 4 32 4 24 4 11099 4 19 28 20 359 8 348 464 219 7 48 15
15 136 4 4 176 3064 83 107 27 4 8 11 4 4 12 15 56 8 8 4 4
4 19 59 32 4 96 11 12 312 12627 7 4 12 12 459 11 51 123 36
4 4 47 4 32 59 2207 40 232 16 15 1468 27 64 16 4 4 191 19 4
1000 7 7 36 23 540 24 12 4 52 124 11 4 15 23 4 27 4 35 11
15 723 135 11 996 15 4 4 8 16 4 92 168 39 4 12 4 7348 4 11
16 36 4 47 48 36 139 4 16975 36 7 2696 8 4 63 56 28 4 11
104 20 7 35 4226768 4 4 436 100 20 4 123 7 48 4 4 132 52 7
4 11 15 20 1335 35 8 43 236 4 359 16 4 4 71 39 4 4 4 4 7
12 180 4 8 4 4 4 15 16 75 4 15 47 80 11 4 4 4956 139 108 4
51 4 47 203 55 71 20 412 4 8 4 7 44 283 4 35 9171 20 200
2684 1167 148 28359 195 4 8 124 7 147 27 139 36 8 139 4 23 8
4 8 323 23 4 12 348 4 39 12 15 31 4 4 4 4 4 12 31 35 43
19 47 215 4 7 8 16 4 23 4 272 28 20 123 16 4 4 8108 20 652
15 7 4 23 8 12 7 36 7 4 12 16 7 4 239 16 4 4 383 84 31 7
44 4 11 699 5432 47 48 956 7 4 120 23 16 27 8 11 195 11 12
43 67 4 7 12 16 8
1 2 3 4 5 6 7
334 367 145 39 11 2 2 0 0 0
Edited on January 18, 2009, 1:07 pm
|
|
Posted by Charlie
on 2009-01-17 16:39:01 |
solution and exploration
