Spaghetti Problem

[LetYouDown]

Over/under at 3 hours on this one.

At a dinner party, there are N people seated around a table. A plate of spaghetti starts at the head of the table. The person sitting there takes some spaghetti and then passes the plate at random to his/her right or left. Henceforth each person receiving the palte takes some spaghetti and then passes the plate at random to his/her right or left. (Diners who have already received the plate can simply pass it on, without taking any more.) When all the diners have finally received their spaghetti, the plate stops being passed.

What are the chances of being the last to be served, as a function of position (relative to the head) at the table of N people?

If this is repeated over the course of many dinners, what is the average number of times the plate is passed.

[pzhon]

Answer in white:

<font color="white">If n&gt;1, then anyone other than the head is last with probability 1/(n-1).

Proof: Consider the first time one of your neighbors gets the plate. Label that neighbor 1, then the next person in that direction 2, etc., so your other neighbor is n-1. Call your own seat 0. You get the plate last precisely when an unbiased random walk starting at 1 reaches n-1 before it reaches 0. </font>

[LetYouDown]

Correct for part 1. Thoughts on part 2?

[pzhon]

Oops, I hadn't noticed the second question.

Answer in white:
<font color="white">
N(N-1)/2

The expected amount of time between the k-1st and the kth people gets the plate for the first time is the amount of time it takes for a random walk starting at 1 to hit 0 or k.

If the random walk is expected to take x steps starting at 1, it takes mx-2(m choose 2) steps at m (each term is 1 more then the average of its neighbors), which must be 0 at k, so kx - k(k-1)=0. x=k-1.

Therefore, the expected number of passes before the last person is served is the sum of k-1 from k=2 to k=N, N(N-1)/2.
</font>

[LetYouDown]

My over/unders are unimaginably good. 2 hours, 59 minutes for my 3 hour over/under =).