Living life on the edge!

Probability Level 5

A bug starts on one vertex of a dodecahedron. Call it A. Define a second vertex adjacent to the one he starts on, and call it B.

Every second he randomly walks along one edge to another vertex. What is the expected value of the number of seconds it will take for him to reach the vertex B?


Clarification : Every second he chooses randomly among the three edges available to him, including the one he might have just walked along. On his first move, he has a 1 3 \frac13 probability of reaching B.

See my other Expected Value quizzes.
Image credit: math.wikia.com


The answer is 19.

Geoff Pilling by Geoff Pilling , 53, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Geoff Pilling
Jun 3, 2016

If we place the vertex opposite B at the origin, and the vertex B on the positive x-axis, then we can consider the following five groups of vertices that share a common x-coordinate:

  • Group 0: 1 point, the vertex opposite B
  • Group 1: 3 points, all points neighboring the initial vertex
  • Group 2: 6 points
  • Group 3: 6 points
  • Group 4: 3 points (A is in this group)
  • Group 5: 1 point, the vertex, B

Now if we consider the expectation values E n E_n as the expected number of moves to get from any vertex in group n n to the vertex B, then we get the following set of linear equations:

  • E 0 = E 1 + 1 E_0=E_1 + 1
  • E 1 = 1 + ( 2 / 3 ) E 2 + ( 1 / 3 ) E 0 E_1=1+(2/3)E_2+(1/3)E_0
  • E 2 = 1 + ( 1 / 3 ) E 1 + ( 1 / 3 ) E 2 + ( 1 / 3 ) E 3 E_2 =1 + (1/3)E_1 + (1/3)E_2 + (1/3)E_3
  • E 3 = 1 + ( 1 / 3 ) E 2 + ( 1 / 3 ) E 3 + ( 1 / 3 ) E 4 E_3=1+ (1/3)E_2+(1/3)E_3 + (1/3)E_4
  • E 4 = 1 + ( 2 / 3 ) E 3 E_4=1+(2/3)E_3

A is in group 4, so solving for E 4 E_4 , you get E 4 = 19 E_4=\boxed{19}

7 Helpful 0 Interesting 0 Brilliant 2 Confused

Why isn't that E 4 = 1 + ( 3 / 3 ) E 3 E_4 = 1+ (3/3) E_3 ? I think that when the bug is aiming at the last group of point, it only has choices to get from all points neighbouring the vertex to the vertex opposing B.

A Former Brilliant Member - 4 years, 11 months ago

Log in to reply

Well, when he is in group 4, (right next to the destination vertex) he has a 2/3 chance of returning to a vertex in group 3, and a 1/3 chance of moving to the final vertex, #5.

So, E 4 = 1 + ( 2 / 3 ) E 3 + ( 1 / 3 ) E 5 E_4 = 1 + (2/3)E_3 + (1/3)E_5 , but since E 5 = 0 E_5 = 0 , this becomes E 4 = 1 + ( 2 / 3 ) E 3 E_4 = 1 + (2/3) E_3 .

Geoff Pilling - 4 years, 11 months ago

Greg Markowsky, Simple random walk on distance-regular graphs states the hitting time is the product of the effective resistance between the nodes in question times the number of edges in the graph. A dodecahedron is a distance-regular graph. The effective resistance is also known as the resistance distance using 1 Ω \Omega resistors. On a dodecahedron the effective resistance to an adjacent vertex is 19 30 \frac{19}{30} . A dodecahedron has 30 edges. Therefore, the answer is 19.

0 Helpful 1 Interesting 2 Brilliant 0 Confused

can you explain why the effective resistance to an adjacent vertex is 19/30

Jonathan Xiang - 4 months, 1 week ago
Frank Petiprin
Nov 29, 2017 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
import random
#                    Python Language

# Numbered the 20 vertices of the dodecahedron 1 through 20 (any numbering pattern works)
# Each vertex is surrounded by 3 other vertices
# Array Moves first three non zero entries are 2,5,6 and they are the vertices for vertex 1
# The next three entries are 1,3,8 and they are the vertices for vertex 2
# The next three entries are 2,4,10  and they are the vertices for vertex 3 etc..
# Each vertex is alocated three slots in the array Move to store their surrounding vertices

Moves=[0,2,5,6,1,3,8,2,4,10,3,5,12,1,4,14,1,7,15,6,8,20,2,7,9,8,10,19,3,9,11,10,12,18,4,11,13,12,14,
17,5,13,15,6,14,16,15,17,20,13,16,18,11,17,19,9,18,20,7,16,19]

grandTot=0
# TOTAL NUMBER OF WALKS
Attempts=2000000
# INDICATES THE NEXT MOVE OR VERTEX
newindex = 1
# COUNT OF MOVES TILL YOU REACH THE B
cntmvs = 0
# TOTAL COUNT OF ALL MOVES TO REACH THE B’s
totmvs = 0
# COUNT THE NUMBER OF TIMES YOU REACHED THE B’s
cnt6 = 1
# ANSWER TO QUESTION ?  avg = ( totmvs/cnt6 )
# START AT VERTEX 1 WITH B BEING VERTEX 6
Trials=20
for i in range(1,Trials+1):
    newindex,cntmvs,totmvs,cnt6=1,0,0,1
    for j in range( 1,Attempts):
        if  (  newindex  !=  6  ):
# DETERMINE THE NEXT MOVE newindex
          index = ( newindex - 1 )*3 
# PICK RANDOMLY AN OFFSET (1,2,3) TO DETERMINE THE VERTEX FOR THE NEXT MOVE
          offset = random.randrange(1,4)
          index = index + offset
          newindex = Moves[index]
          cntmvs += 1
        else:
# FOUND B OR 6
# RESET VARIABLES
           totmvs = cntmvs + totmvs
           cntmvs = 0
           cnt6 += 1
           newindex = 1
# END OF LOOP
# Needed by  Pythonista to avoid division by zero error
    if ( cnt6  !=  1 ):
        cnt6 = cnt6 - 1
        AVG = totmvs/(cnt6)
        print(' +++++++++++++++++++++++ ')
        print( ' cnt6 totmvs ',cnt6 ,totmvs, ' AVG = ', AVG,'  ',i)
        grandTot+=AVG
# END PROGRAM AND FIVE PROGRAM RUNS
print(' +++++++++++++++++++++++ ')
print('Trials ',Trials,'Overall Average ',grandTot/Trials, 'Attempts',Attempts)
+++++++++++++++++++++++ 
 cnt6 totmvs  100907 1899040  AVG =  18.819705273172328    1
 +++++++++++++++++++++++ 
 cnt6 totmvs  99430 1900554  AVG =  19.11449260786483    2
 +++++++++++++++++++++++ 
 cnt6 totmvs  100136 1899825  AVG =  18.972447471438844    3
 +++++++++++++++++++++++ 
 cnt6 totmvs  100501 1899460  AVG =  18.89991144366723    4
 +++++++++++++++++++++++ 
 cnt6 totmvs  100306 1899671  AVG =  18.938757402348813    5
 +++++++++++++++++++++++ 
 cnt6 totmvs  100565 1899426  AVG =  18.88754536866703    6
 +++++++++++++++++++++++ 
 cnt6 totmvs  99581 1900395  AVG =  19.08391158956026    7
 +++++++++++++++++++++++ 
 cnt6 totmvs  99782 1900209  AVG =  19.043605059028682    8
 +++++++++++++++++++++++ 
 cnt6 totmvs  99357 1900642  AVG =  19.129422184647282    9
 +++++++++++++++++++++++ 
 cnt6 totmvs  99750 1900226  AVG =  19.04988471177945    10
 +++++++++++++++++++++++ 
 cnt6 totmvs  100173 1899804  AVG =  18.96523015183732    11
 +++++++++++++++++++++++ 
 cnt6 totmvs  99458 1900510  AVG =  19.1086689859036    12
 +++++++++++++++++++++++ 
 cnt6 totmvs  100169 1899822  AVG =  18.966167177470076    13
 +++++++++++++++++++++++ 
 cnt6 totmvs  100257 1899611  AVG =  18.947415143082278    14
 +++++++++++++++++++++++ 
 cnt6 totmvs  99319 1900666  AVG =  19.1369828532305    15
 +++++++++++++++++++++++ 
 cnt6 totmvs  100327 1899632  AVG =  18.934404497293848    16
 +++++++++++++++++++++++ 
 cnt6 totmvs  99639 1900246  AVG =  19.071307419785427    17
 +++++++++++++++++++++++ 
 cnt6 totmvs  99903 1900062  AVG =  19.019068496441548    18
 +++++++++++++++++++++++ 
 cnt6 totmvs  99827 1900142  AVG =  19.03434942450439    19
 +++++++++++++++++++++++ 
 cnt6 totmvs  99498 1900477  AVG =  19.100655289553558    20
 +++++++++++++++++++++++ 
Trials  20 Overall Average  19.011196627563862 Attempts 2000000

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...