All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Weird Walk (Posted on 2009-01-17)
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.

 No Solution Yet Submitted by K Sengupta Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution and exploration | Comment 1 of 4

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

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  6432  8  64  96  20  95  120  39  16  4  2587  12  4  4  6219  27  72  11  4148  16  4  107  56  40  36  15  56  4  11  55  144  8  4  1288  4  28  7  415  15  72  3644  4  8  264  4  63  116  4  12  4  7  76  47  7  12  8  23  884  104  15  8  24  7  79116  7  3367  64  35  131  12  12  244  384  4  39444  1264  12  4  36  32  15  724  35  10147  684  196  52  27  8  48  4  4  476  127  4  15  4  8  4  4  15  12  20  355  4  20  40  27  31  4  16  4  824  92  15  984  7  4  8  4  120  36  83  2499  120  27  4  19  4  77159  8423  48  72  7  4  147  4  788  4  52  95  24  132  16  948  4  407  4  11  81664  88  20  12  43  8  11  35  4  68  8  852  64  51  411  32  12  4  20  8187  12  1487  11  7  299  4  1372  448  8  75  4  4  23  8  8  279  4  63  48  4  20  4  7  47  20  52  7  71  19  12  8  4  4  4  19  24  151  67  163431  44  15  8  168  11  4  4  11  32  12  8  583  11  4  4  4  132  511  1120  4  17084  115  4  8  16  4  7  8  115  148  12  96  196  136  40  32  25519700  23  344  7  12  68  1295416  8  315  864  44  4  43  52  4  4  79  3848  12  8  4  7  367  2015  43  4  144  8  40  19  4  8  4  104  7  375  12  198  148  123  16  4  107  7  4  40  32  4  11  4  4  31  4  127  3688  343  1159  7  4  31  16  4  15  20  27  4  7  8  3472  7  8  420  19  8  28  4  2019  92  4  39  40  8  24  4  64  91  4  2624  4  43  4  17727  31  27  19  31543  4  20  24  119  215  4  51163  20  4  8  19  75  224  7  4  172  4  4284  60  8  4  11  4  55  8  4  4  4  279  464  167  4  12  503  15  4  84358  12  251  79  8  4  4  196  100  24  4  19  7  23  4  11  475  4  8  4  154  4  7  4  4  4  7  100  1264  1776  40  4  11  4  51  608  4  8  119  4  723  115  95  12  7  7  135  4  4  943  604315  351  4  4  12  4  152  12  5688  7  12  12  20  48  7  35  12  336  4  16  72  8  4  35  20  4  104  4  440  4  8  75  11  1140  4  4932  19  4  4  60  4  47  427  20  32  11  8  4223  32  27  8  44  348  4  92  1124  208  60  4  840  1863  8  52  155  2715  12  959  83  12  23  172  39  4  4  4  108492  4  208  15  4  3043  4  475  4  15  12  4059  4  1375  376  8  27  72  4  15  24  4  12  12  19  4  464  4  32  4  24  4  11099  4  19  28  20  359  8  348  464  219  7  48  1515  136  4  4  176  3064  83  107  27  4  8  11  4  4  12  15  56  8  8  4  44  19  59  32  4  96  11  12  312  12627  7  4  12  12  459  11  51  123  364  4  47  4  32  59  2207  40  232  16  15  1468  27  64  16  4  4  191  19  41000  7  7  36  23  540  24  12  4  52  124  11  4  15  23  4  27  4  35  1115  723  135  11  996  15  4  4  8  16  4  92  168  39  4  12  4  7348  4  1116  36  4  47  48  36  139  4  16975  36  7  2696  8  4  63  56  28  4  11104  20  7  35  4226768  4  4  436  100  20  4  123  7  48  4  4  132  52  74  11  15  20  1335  35  8  43  236  4  359  16  4  4  71  39  4  4  4  4  712  180  4  8  4  4  4  15  16  75  4  15  47  80  11  4  4  4956  139  108  451  4  47  203  55  71  20  412  4  8  4  7  44  283  4  35  9171  20  2002684  1167  148  28359  195  4  8  124  7  147  27  139  36  8  139  4  23  84  8  323  23  4  12  348  4  39  12  15  31  4  4  4  4  4  12  31  35  4319  47  215  4  7  8  16  4  23  4  272  28  20  123  16  4  4  8108  20  65215  7  4  23  8  12  7  36  7  4  12  16  7  4  239  16  4  4  383  84  31  744  4  11  699  5432  47  48  956  7  4  120  23  16  27  8  11  195  11  1243  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

 Search: Search body:
Forums (0)