A bug is placed at one corner of a wire frame in the shape of a cube. At the diagonally opposite corner is a piece of sugar.
The bug crawls along the 12 wires of the frame searching for the sugar. At each of the 8 corners the bug randomly chooses one of the 3 wires to follow next (including the one it just traveled).
What is the expected number of edges the bug will traverse until it reaches the sugar? What if the bug never doubles back on the wire it just crossed?
Call the expected number of edges crawled from its initial point A. From each of that point's adjacent vertices, call the expected value B. From the vertices adjacent to the sugar, call that expected value C.
Part 1:
A = B + 1
B = (A + 1) / 3 + 2*(C + 1)/3
C = 2*(B + 1) / 3 + 1/3
Wolfram Alpha solves this as:
A = 10, B = 9, C = 7
The expected number starting at the beginning is 10.
Part 2:
A = B + 1
B = C + 1
C = (B + 1) / 2 + 1/2
This leads to
A = 5, B = 4, C = 3
and the expected number from the beginning is 5.
The above argument for part 2 is flawed. It assumes that when the bug is at a B point, it got there from A, and therefore must go to one of the C points. But it may have come from one of the C points and has the choice to go to A or the other C to which it's connected, and we have made no provision for taking into consideration the probabilities of how a given point was reached.
So the above is just a beginning outline for an analytic solution of part 2, and I'll do a simulation.
totCt=0;
for trial=1:10000000
bug='a';
while bug(end)~='d'
switch bug(end)
case 'a'
bug(end+1)='b';
case 'b'
if bug(end-1)=='a'
bug(end+1)='c';
else
if randi(2)==1
bug(end+1)='c';
else
bug(end+1)='a';
end
end
case 'c'
if randi(2)==1
bug(end+1)='b';
else
bug(end+1)='d';
end
end
end
totCt=totCt+length(bug)-1;
end
totCt
totCt/trial
does ten million trials.
Run three times, it produces:
>> bugOnACubePart2
totCt =
60002898
ans =
6.0002898
>> bugOnACubePart2
totCt =
60007242
ans =
6.0007242
>> bugOnACubePart2
totCt =
59997092
ans =
5.9997092
>>
each time suspiciously close to an integer, 6.
|
|
Posted by Charlie
on 2023-11-19 13:08:53 |
some analytic, some computer
