Cube

[Paul Howe]

Here's a puzzle I like, it involves relatively simple maths (you have to know what an expectation is) although if you've done a specific module at uni you'll find it a lot easier.

An ant is standing at a corner of a cube. It picks one of the three edges meeting at the corner with equal probability and walks along the edge until it reaches the next corner. Every time it reaches a corner it picks an edge to walk along according to the same rule. It takes the ant 1 minute to walk along each edge, and it makes the decision about which edge to walk to next instantly.

Let S be the corner where the ant starts and E the corner diagonally opposite S (i.e.the shortest path from S to E is 3 edges). Once the ant reaches E it stops. What is the expected time for the ant to get from S to E?

[Paul Howe]

Oh cock, posted in the wrong forum. Sorry mods.

[Gavin Chipper]

(you have to know what an expectation is)

Or you could just tell us what it means. (The expected time for the ant to get from S to E is just the average time it would take if you ran it loads of times.)

As for the puzzle itself, I think you can only manage it in an odd number of goes, so 3, 5, 7 etc.

The probability of achieving it in 3 goes would be 1 * 2/3 * 1/3 because anything can happen the first time, and then it requires moving in either of 2 of the 3 possible ways and then just one specific way. So that would be 2/9. If we have failed after three goes we will automatically be two moves away from our goal. And the same goes for if we have failed after 5, 7, 9 etc.

When we are two away, the probability of making it in two moves would be 2/3 * 1/3, so 2/9 again.

So I would say that since it can be done in 3, 5, 7, 9, 11 moves etc. and at each point there is a 2 in 9 (1 in 4.5) chance of succeeding, the average would be the 4.5th one along, so 10. My answer is 10 minutes.

[Paul Howe]

(you have to know what an expectation is)

Or you could just tell us what it means. (The expected time for the ant to get from S to E is just the average time it would take if you ran it loads of times.)

As for the puzzle itself, I think you can only manage it in an odd number of goes, so 3, 5, 7 etc.

The probability of achieving it in 3 goes would be 1 * 2/3 * 1/3 because anything can happen the first time, and then it requires moving in either of 2 of the 3 possible ways and then just one specific way. So that would be 2/9. If we have failed after three goes we will automatically be two moves away from our goal. And the same goes for if we have failed after 5, 7, 9 etc.

When we are two away, the probability of making it in two moves would be 2/3 * 1/3, so 2/9 again.

So I would say that since it can be done in 3, 5, 7, 9, 11 moves etc. and at each point there is a 2 in 9 (1 in 4.5) chance of succeeding, the average would be the 4.5th one along, so 10. My answer is 10 minutes.

Oddly enough I had a completely different solution in mind and didn't think of doing it like that, but it all looks right to me, well done

[Dinos Sfyris]

Can the ant double back on itself?

[Gavin Chipper]

Oddly enough I had a completely different solution in mind and didn't think of doing it like that, but it all looks right to me, well done

How did you do it?

Can the ant double back on itself?

I assumed that it could and Paul seemed happy with my answer.

[Michael Wallace]

I'm pretty sure this was on one of my markov chains problem sheets.

[Adam Dexter]

What would happen if he kept toddling around one face, i.e. infinite time?

[Gavin Chipper]

What would happen if he kept toddling around one face, i.e. infinite time?

He'd die of old age.

[Kai Laddiman]

What would happen if he kept toddling around one face, i.e. infinite time?

He'd die of old age.

Stereotypers, not every ant is male.

[Charlie Reams]

What would happen if he kept toddling around one face, i.e. infinite time?

The probability of that is infinitesimally small.

[Michael Wallace]

What would happen if he kept toddling around one face, i.e. infinite time?

The probability of that is infinitesimally small.

Like your penis OH BURN.

[Howard Somerset]

I'd not seen a question like this before, so having opened this thread for the first time yesterday evening and read just the first post, I took it to bed with me, and came up with an answer before finally dropping off to sleep. And having now looked at Gavin's post, which gives the same solution by a much neater method, I think I could've had 30 minutes longer sleep if I'd done it that way.

Anyway, my method:

We've got four essentially different vertices. S, E, A (adjacent to S) and B (adjacent to E).

P (S to A) = 1
P (A to B) = 2/3
P (A to S) = 1/3
P (B to E) = 2/3
P (B to A) = 1/3

That much is the same as Gavin's.

Now-
Expected time S to A: Obviously 1 min.

Expected time A to B:
Prob of doing it in 1 is 2/3
Failing this, we get back to A in 2, so prob of doing it in 3 is 1/3 x 2/3
Failing this, we get back to A in a further 2, so prob of doing it in 5 is (1/3)^2 x 2/3
etc.

Expected time A to B is therefore
1 x 2/3 + 3 x (1/3) x 2/3 + 5 x (1/3)^2 x 2/3 + 7 x (1/3)^3 x 2/3 + ...
A bit of simple algebra turns this into an infinite geometric sequence, giving an expected time of 2 mins.

Expected time B to E:
Prob of doing it in 1 is 1/3
Failing this, we take 1 min to get back to A, and then have already calculated that the expected time to get back from A to B is a further 2 mins, so we're ready to go again after 3 mins. So prob of doing it in 4 is 2/3 x 1/3 [There is clearly a flaw in the wording of my argument at this point, because it's not possible to do it in 4 mins, but we're working on expectations, and an expectation is not always a value that can actually occur, so I felt happy to proceed.]
Similarly, prob of doing it in 7 is (2/3)^2 x 1/3
etc,

Expected time B to E is therefore
1 x 1/3 + 4 x (2/3) x 1/3 + 7 x (2/3)^2 x 1/3 + 10 x (2/3)^3 x 1/3 + ...
which sums to 7.

Expected time S to E is therefore 1 + 2 + 7 = 10 mins.

Is that the same method as yours Paul, or do we now have three methods?

[Dinos Sfyris]

P (B to E) = 2/3
P (B to A) = 1/3

I think you have these the wrong way round. Otherwise good effort.

[Howard Somerset]

P (B to E) = 2/3
P (B to A) = 1/3

I think you have these the wrong way round. Otherwise good effort.

Well spotted. They're the wrong way round. But I used the correct values in what followed.

[Howard Somerset]

I'd not seen a question like this before, so having opened this thread for the first time yesterday evening and read just the first post, I took it to bed with me, and came up with an answer before finally dropping off to sleep. And having now looked at Gavin's post, which gives the same solution by a much neater method, I think I could've had 30 minutes longer sleep if I'd done it that way.

Anyway, my method:

We've got four essentially different vertices. S, E, A (adjacent to S) and B (adjacent to E).

P (S to A) = 1
P (A to B) = 2/3
P (A to S) = 1/3
P (B to E) = 2/3
P (B to A) = 1/3
As Dinos has pointed out, last two lines should read
P (B to A) = 2/3
P (B to E) = 1/3

That much is the same as Gavin's.

Now-
Expected time S to A: Obviously 1 min.

Expected time A to B:
Prob of doing it in 1 is 2/3
Failing this, we get back to A in 2, so prob of doing it in 3 is 1/3 x 2/3
Failing this, we get back to A in a further 2, so prob of doing it in 5 is (1/3)^2 x 2/3
etc.

Expected time A to B is therefore
1 x 2/3 + 3 x (1/3) x 2/3 + 5 x (1/3)^2 x 2/3 + 7 x (1/3)^3 x 2/3 + ...
A bit of simple algebra turns this into an infinite geometric sequence, giving an expected time of 2 mins.

Expected time B to E:
Prob of doing it in 1 is 1/3
Failing this, we take 1 min to get back to A, and then have already calculated that the expected time to get back from A to B is a further 2 mins, so we're ready to go again after 3 mins. So prob of doing it in 4 is 2/3 x 1/3 [There is clearly a flaw in the wording of my argument at this point, because it's not possible to do it in 4 mins, but we're working on expectations, and an expectation is not always a value that can actually occur, so I felt happy to proceed.]
Similarly, prob of doing it in 7 is (2/3)^2 x 1/3
etc,

Expected time B to E is therefore
1 x 1/3 + 4 x (2/3) x 1/3 + 7 x (2/3)^2 x 1/3 + 10 x (2/3)^3 x 1/3 + ...
which sums to 7.

Expected time S to E is therefore 1 + 2 + 7 = 10 mins.

Is that the same method as yours Paul, or do we now have three methods?

[Kai Laddiman]

[Quote]

[Edit]



(Kai's Cryptic Smilies)

[Howard Somerset]

[ Quote ]

[ Edit ]



(Kai's Cryptic Smilies)

[David Williams]

I have to say, Howard, that although your answer is correct I can't quite persuade myself that adding the expected times together is valid. Probably it is, but I don't think it's self-evident.

So much easier to say it takes one minute to reach A, and then every two minutes there's a 2/9 chance of reaching E, and a 7/9 chance of being back at A, as Gavin did. The longer and more complex the solution, the more chance there's a flaw in it.

[Howard Somerset]

I have to say, Howard, that although your answer is correct I can't quite persuade myself that adding the expected times together is valid. Probably it is, but I don't think it's self-evident.

I'm totally with you there, David. Definitely not convinced ... yet.

[Paul Howe]

My solution was to let X denote the expected time to E given the ant is 3 moves away (i.e. X is what we're interested in), Y the expected time given two moves away, and Z the expectation given 1 move away.

Now, p(3->2) = 1, p(2->3) = 1/3, p(2->1) = 2/3, p(1->2) = 2/3, p(1->0) = 1/3, where p(a->b) denotes the probability of being b moves away one second later given that we're a moves away now. From this, we can formulate the following set of equations,

X = Y + 1
Y = 1/3(X+1) + 2/3(Z+1)
Z = 2/3(Y+1) + 1/3

and solving these for X gives X = 10.