perplexus.info :: Probability : Weird Walk

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.

See The Solution Submitted by K Sengupta

Rating: 4.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

re: solution and exploration

Comment 4 of 4 |

(In reply to solution and exploration by Charlie)

As mentioned previously, the probability of an exact hit on each of the infinitely many passes through the origin is greater than the 1/3 originally quoted, and is probably greater than 1/2.

In fact, in addition to correcting the bug in the simulation that caused the jumps to be alternating 1's and 4's rather than 1's and 2's, I've also added a count of how many times the man has passed through the origin before hitting it exactly:

DEFDBL A-Z
RANDOMIZE TIMER
CLS

FOR trial = 1 TO 900
    x = 0: mv = 1: ct = 0: hopCt = 0
    DO
      xSave = x
      x = x + 2 * mv * (INT(RND(1) * 2) - .5)
      IF xSave * x < 0 THEN hopCt = hopCt + 1
      mv = 3 - mv
      ct = ct + 1
    LOOP UNTIL x = 0
    hopTot(hopCt) = hopTot(hopCt) + 1
    PRINT ct;
    s = LEN(LTRIM$(STR$(ct)))
    dCt(s) = dCt(s) + 1
    ' IF trial MOD 40 = 0 THEN PRINT "-": DO: LOOP UNTIL INKEY$ > ""

NEXT trial
PRINT
FOR s = 1 TO 10: PRINT dCt(s); : NEXT: PRINT
PRINT
FOR i = 0 TO 10: PRINT hopTot(i); : NEXT: PRINT
PRINT

8  123  16  3  40  42508  8  7  3  4  3  40  28  4  4  747  40  7  511  11  3
7  3  19  3  4  4  4  3  23  3  3  8  4  4  3  4  4  56  4  3  4  8  2012  3
11  11  3  28  3  8  835  3  4  4  520  3  32  3  12  4  12  3  24  3  3  84
359  15  3  3  19  12  4  11  4  55  51  8  72  11  3  12  4  4  4  4  468  20
4  4  3  52  8  4  3  3  19  3  160  3  79  4  4  3  4  4  7  3  4  4  3  15
8  20  4  3  4  3  3  84  591  36  11  4  55  7  4  4  11  15  8  4  11  4  3
476  8  3  4  8  4  4  3  11  68  12  15  7  3  8  23  812  3  8  3  7  8  3
20  7  7580  59  3  3  3  8  4  12  4  7  11  63  4  47  3  3  3  3  3  15  4
67  11  36  4  31  4  3  4  3  3  20  3  3  8  4  63  20  28  3  8  4  4  3  7
4  15  291  7  3  3  15  28  147  3  3  8  11  3  3  4  128  3  25932  2547  4
12  4  12  4  203  3  15  24  4  4  7  3  7  3  15  4  3  3  336  4  4  263  4
3  19  7  4  4  3  8  3  3  7  4  11  775  14200  19  3  855  56  1223  8  4
7  4  15  108  3  27  3  203  40  11  47  20  11  3  48  3  1680  4  8  4  3
4  4  7  16  4  19  11  3  139583  24  128  8  3  3  4  4  12  7  4  3  3  4
3  4  4  27  4  4  2427  12  3  4  7  7  151  44  4  7  7  4  7  4  4  4  71
8  3  4  11  28  52  19  23  3  16  7  3  3  4  4  11  4  7  1260  3  3  11
39  15  23  16  7  4  3  32  3  3  3  12  4  3  311  4  3  11  44  159  931  4
59  3  3  8  3  3  8  8  12  4  3  4  4  3  4  44  7  3  172  4916  16  1303
7  191  36  4  4  3  755  736  24  4  3  4  147  19  32  3  7  36  24  7  4  7
4  7  11  4  135  3  1172  2059  4  7  39  3  3  4  12  4  4  3  11  3  3  15
168  3  4  8  4  4  11  4  4  12  88  12  24  376  144  27  4  3  143  3092  8
3  7  407  27  16  7  12  3  4  40  19  112  3  8  3  3  8  3  4  4  7  3  16
4  3  4  52  4  3  3  8  4  8  3  3  2111  4  4  3  24  4  44  32  3  2907  3
19  4  8  3  12  8  3  167  4  8  3  16  8  3  3  232  15  11  11  7  4  23  4
4  15  544  3  8  4  3  104  355  36  4  3  19  40  4  139  16  3  4  3  40
15  16  7  20  3  4  3  4  3  4  3  4  4  11  4  3  59  3  3  4  55  4  4  3
11  4  4  3  3  4  39  16  263  19  19  4  11  167  327  27  12  4  3  8  1727
4  12  3  4  7  7  3  4  7  863  8  3  4  731  4  3  23  3  43  3  16  4  295
43  4  31  1703  79  3  11  11  3  3  12  4  20  4  4  4  8  111  32  88  3
367  3  39  4  11  3  3  3  4  12  4  131  24  3  4  111  3  107  55  4  8  3
8  260  4  3  11  232  3  3  7  12  12  23  4  3  3  15  4  3  3  3  4  36  3
12  4  4  179  7  20  3  156  3  4  464  4  3  8  8  16  60  3  131  4  3  3
144  4  52  4  3  4  3  3  3  4  63  8  76  8  27  2031  2240  24  20  3  56
56  3  11  44  3  3  23  4  3  3  4  207  3  47  7  3  8  4  4  63  171  1320
4  4  7  68  3  3  3  7  11  4  28  4  44  7  7  100  47  27  3  16  32  3  11
15  3  131  48  4  11  106668  4  4  8  1536  16  3  51  375  4  15  1975  107
51  4  12  100  584  3  8348  27  19  8  4  4  3  776  3  4  3  15  112  3  20
28  3  4  23  3  3  32  4  7  3  4  8  4  4  4835  28  3  3  408  4  15  4  4
16  7  20  28  16  15  4  4  156  3  7  3  4  3  32  4  12  8  4  4  340  8  3
3  8  79  7  447  3  3  64  32  4  31  52  263  35  7  3  11  32  3  3  47  7
12  3  3  20  3  4  4  4  43  3  3  75

# of digits         
in # of moves:   1    2   3   4  5  6
               545  250  77  23  3  2  0  0  0  0

# of missed passes 
through origin
before hit:     0    1   2  3
              371  505  22  2  0  0  0  0  0  0  0

20  4  3  1000  247  4  7  687  107  2083  319  3  12  8  7  4948  4  131  8
4  4  4  4  8  8  3  19  7  7  1000  3  3  3  52  128  704  35  3  7  3  3
492  20  4  172  24  3  4  4  331  99  19  4  4  4  8  184  4  219  132  3  7
19  4  11  12  12  4  660  3792  3  3  4  3  4  3  4  4  255  12  3  4  332  4
7  7  12  12  12  27  3  4  3  4  4  16  3  151  1060  4  4  15028  8  4  24
48  8  3  3  3  4  4  4  144  3  4  3480  7  4  4  39  139  4  23  3  8  116
3  156  24  4  7  8  4  92  3  4  4  3  7  3  99  19  8  4  4  3  8  3  47  4
39  3  8  4  3  3  3  25459  3  16  3  8  8  4  3  4  277032  8  3  8  4  3
11  15  7  4  3  11  3  136212  128  4  4  8  3  27  3  4  107  4  4  4  12  4
3  3  8  3  3  3  11  7  3  3  7  2815  36  4  15  43  8  3  24  275  28  3  7
4  4  4  12  4  24  3  4  4  4  3  7  395  4  4  4  4  4  108  3  4  4  4  4
7  3  3  3539  8  39  3  11  112  3  12  4  3  120  4  1111  23  897799  4  4
7  3  4  99  12  3  8  428  27  4  3  24  4  16  3  4  11  7  12  4  7  4  3
235  4  3  12  4  7  7  7  4  8  28  3  3  4  68  15  1871  4  4  4  32  4  11
8  208  3  24  3  3  7  152  19  3  3  7  4  4  99  19  960  3  219  68  1796
4  4  3  3  4  4  7  39  4  4  432  11  11  3  3  16  24  23  3  3  8  4  56
3939  4  3  20  7  16  3  44  3  3  4  4  18896  3  40  3  11  3  3  47  79  7
4  7  3  3  3  3  12  4  4  3  3  3  19  4  15  56  12  4  8  31  3  35  4  7
4  24  4  528  4  3  3  3  15  4  4  1524  8  12  3  3  11  7  16  3  3  204
8  15  3  12  3  4  4  4  3  7  116  7  16664  8  3  4  4  48364  4  4  4  24
7  4  3  4  3  4  3  4  8  3  12  4  316  80  3  4  7  4  8  52  3  4  15  8
27  539  3  1419  4  20  51  3859  3  71  12  12  4  4  20  4  4  3  192  4
11  4  3  4  3  3  16  3  4  3  3  3  8  80  8  23  3  3  3  8  3  3  3  3  8
3  3  4  4  3  4  11  4  4  7  3  7  8  32  3  3  3  492  4  3  11  7  4  12
3  4  36  15  3  12  3  60  4  7  3  3  4  15  4  36  11  8  7  8  4  3  27  4
4  4  3  24  15  3  15  4  4  4  8  43  4  4  3  3  7  4  24  7  7  31  4  4
4  12  855  1699  3  4  4  23  4  4  47  7  4  12  31  28  24  80  3  3  15  3
4  3  3  3  3  4  8  4  147  72  19  3  4  16  4  4  104  28855  7  3  3  4  4
3  3  4  159  12  4  3  3  12  4  108  8056  4  4  395  4  3  8  196  3  4  7
171  3  3  3  4  4  119  4  179  8  3  19  4  283  16  119  15  88  3  3  3  3
1215  4  7  1447  4  91  3  8  887  8  3  63  223  4  84  4  3  20  7  4  3  7
7  3  31  4  3  184  3  11  99  15  3  4  63  8  3  91  7  4  112  11  16  3
4  4  1588  4  12  4  4  19  8  3  4  8  8  3307  28  8  16  8  3  3  20  39
7  3  4  3  20  239  3  7  28  116  25443  235  340  472  400  116  4  3  8  3
3  4  23  3  103  3  3  4  7  4  3  31  23  4  3  3  4  15  4  76  3  4  4  8
3  11  207  24  152  47  12  3  3  132  3  7  635  56  3  235  87  7  4  3  7
3  6583  8  11  256  3  4  11  4  3  8  84  4  72  15  4  23  3  3  51  4  667
8  128  4  4  3  15  19  11  8  8  135  3  3  3  3  95  7  3  31  4  4  4  48
4  3  3  443  8  8  8  116  3  4  4  3  120  3  16  204  16  4  4  3  4  8  28
3  4  3  11  4  3  3  3  3  999  3  7  52  3  4  4  27  4  4  140  4  16  8
11  28  3  7  23  16

digits:   1    2   3   4  5  6
        586  200  81  23  7  3  0  0  0  0

inexact passes:   0    1   2
                343  534  23  0  0  0  0  0  0  0  0

20  4  3  1000  247  4  7  687  107  2083  319  3  12  8  7  4948  4  131  8
4  4  4  4  8  8  3  19  7  7  1000  3  3  3  52  128  704  35  3  7  3  3
492  20  4  172  24  3  4  4  331  99  19  4  4  4  8  184  4  219  132  3  7
19  4  11  12  12  4  660  3792  3  3  4  3  4  3  4  4  255  12  3  4  332  4
7  7  12  12  12  27  3  4  3  4  4  16  3  151  1060  4  4  15028  8  4  24
48  8  3  3  3  4  4  4  144  3  4  3480  7  4  4  39  139  4  23  3  8  116
3  156  24  4  7  8  4  92  3  4  4  3  7  3  99  19  8  4  4  3  8  3  47  4
39  3  8  4  3  3  3  25459  3  16  3  8  8  4  3  4  277032  8  3  8  4  3
11  15  7  4  3  11  3  136212  128  4  4  8  3  27  3  4  107  4  4  4  12  4
3  3  8  3  3  3  11  7  3  3  7  2815  36  4  15  43  8  3  24  275  28  3  7
4  4  4  12  4  24  3  4  4  4  3  7  395  4  4  4  4  4  108  3  4  4  4  4
7  3  3  3539  8  39  3  11  112  3  12  4  3  120  4  1111  23  897799  4  4
7  3  4  99  12  3  8  428  27  4  3  24  4  16  3  4  11  7  12  4  7  4  3
235  4  3  12  4  7  7  7  4  8  28  3  3  4  68  15  1871  4  4  4  32  4  11
8  208  3  24  3  3  7  152  19  3  3  7  4  4  99  19  960  3  219  68  1796
4  4  3  3  4  4  7  39  4  4  432  11  11  3  3  16  24  23  3  3  8  4  56
3939  4  3  20  7  16  3  44  3  3  4  4  18896  3  40  3  11  3  3  47  79  7
4  7  3  3  3  3  12  4  4  3  3  3  19  4  15  56  12  4  8  31  3  35  4  7
4  24  4  528  4  3  3  3  15  4  4  1524  8  12  3  3  11  7  16  3  3  204
8  15  3  12  3  4  4  4  3  7  116  7  16664  8  3  4  4  48364  4  4  4  24
7  4  3  4  3  4  3  4  8  3  12  4  316  80  3  4  7  4  8  52  3  4  15  8
27  539  3  1419  4  20  51  3859  3  71  12  12  4  4  20  4  4  3  192  4
11  4  3  4  3  3  16  3  4  3  3  3  8  80  8  23  3  3  3  8  3  3  3  3  8
3  3  4  4  3  4  11  4  4  7  3  7  8  32  3  3  3  492  4  3  11  7  4  12
3  4  36  15  3  12  3  60  4  7  3  3  4  15  4  36  11  8  7  8  4  3  27  4
4  4  3  24  15  3  15  4  4  4  8  43  4  4  3  3  7  4  24  7  7  31  4  4
4  12  855  1699  3  4  4  23  4  4  47  7  4  12  31  28  24  80  3  3  15  3
4  3  3  3  3  4  8  4  147  72  19  3  4  16  4  4  104  28855  7  3  3  4  4
3  3  4  159  12  4  3  3  12  4  108  8056  4  4  395  4  3  8  196  3  4  7
171  3  3  3  4  4  119  4  179  8  3  19  4  283  16  119  15  88  3  3  3  3
1215  4  7  1447  4  91  3  8  887  8  3  63  223  4  84  4  3  20  7  4  3  7
7  3  31  4  3  184  3  11  99  15  3  4  63  8  3  91  7  4  112  11  16  3
4  4  1588  4  12  4  4  19  8  3  4  8  8  3307  28  8  16  8  3  3  20  39
7  3  4  3  20  239  3  7  28  116  25443  235  340  472  400  116  4  3  8  3
3  4  23  3  103  3  3  4  7  4  3  31  23  4  3  3  4  15  4  76  3  4  4  8
3  11  207  24  152  47  12  3  3  132  3  7  635  56  3  235  87  7  4  3  7
3  6583  8  11  256  3  4  11  4  3  8  84  4  72  15  4  23  3  3  51  4  667
8  128  4  4  3  15  19  11  8  8  135  3  3  3  3  95  7  3  31  4  4  4  48
4  3  3  443  8  8  8  116  3  4  4  3  120  3  16  204  16  4  4  3  4  8  28
3  4  3  11  4  3  3  3  3  999  3  7  52  3  4  4  27  4  4  140  4  16  8
11  28  3  7  23  16

move digits:   1    2   3   4  5  6
             586  200  81  23  7  3  0  0  0  0

Inexact passes:   0    1   2
                343  534  23  0  0  0  0  0  0  0  0

Posted by Charlie on 2009-01-18 13:24:31

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info