Oh, got one more addition to the problem. There is a constraint. The individual probabilities are not i.i.d The road is of fixed length L. So, the probabilities are actually conditional.

Huh but why does having a fixed, finite range mean that the variables generated cannot be i.i.d leh

Cuz there is a certain length that has to be always obtained in total when you sum up all the x. So, probability of getting any length is always conditional on the previous lengths

The solutions converge for large n because the fluctuations become smaller, and the conditional terms become weaker, but it's not an exact solution. The exact solution is actually still 2 over 3 n. In your case, actually, you can even go further and say that the exact soltuion is Twothirds x (n-2) + Half x 2 to account for the end cases but that's not the correct solution because they are not independent.

And wa, why your comment box dun allow math symbols

Well, Mr. Ham's not that hot on math, so no funding to upgrade the comment box.

But I think I get what you mean. In the notation used, the absolute distances D may indeed be dependant on n the total number of hamsters, but the positions h of the hamsters remain completely independent of n.

Of course, if you "observe" the D values sequentially given the positions of the hamsters, then the expectation of later D values will be conditional on earlier observations. For example, in the case n=4, if the distance between the first two hamsters happens to be large (say 0.5 for a road of unit length), the distance between the second and third hamsters is expected to be relatively small (in fact, less than 0.25)

However, the claim of the expectation not actually being 2n/3, but only converging for large n, may warrant a little more clarification. A first objection is because the expectation is clearly exactly 2n/3 for n=3, and while a single case does not prove anything, it may justify further questioning.

This is not so obvious for n=4, but by a million generations of four i.i.d points drawn uniformly and taking the three distances between consecutive points/hamsters, it seems extremely likely that the expectation of the distances is equal. If so, from the permutation argument, the expectation is again exactly 2n/3, and further simulation for increasing n strongly suggests that even for small n, the n-1 distances between the n hamsters indeed have equal expectations.

This may be informally reasoned in plain English as follows: Given n hamsters with positions i.i.d uniformally chosen on a road of unit length, it is very unlikely that the n-1 distances between them have expectation exactly 1/(n-1), since it is almost certain that the first hamster is not exactly at distance zero, and the last hamster is not exactly at distance one.

However, given the actual observed positions of the first and last hamster, I, Mr. Robo, argue that for all n>2, the expectation of the n-1 distances are all exactly (last-first)/(n-1) (and are thus also equal). This is as the distribution of the positions of the remaining n-2 hamsters remains uniform over the range (first,last), or more mathily E(D₁|first,last) = E(D₂|first,last) = ... = E(D_n-1|first,last), and in practice we compute E(D_i|{positions of all hamsters})

If the expectation values for distances are indeed equal, the permutation argument is sufficient, and for the 24 permutations with n=5, eight of them have four mutually nearest hamsters, and the remaining 16 have two, again for an expectation of exactly 2n/3 [see code]:

1 (4 3 2 1) -> 2
2 (3 4 2 1) -> 2
3 (3 2 4 1) -> 2
4 (3 2 1 4) -> 2
5 (4 2 3 1) -> 4
6 (2 4 3 1) -> 4
7 (2 3 4 1) -> 2
8 (2 3 1 4) -> 2
9 (4 2 1 3) -> 4
10 (2 4 1 3) -> 4
11 (2 1 4 3) -> 4
12 (2 1 3 4) -> 2
13 (4 3 1 2) -> 4
14 (3 4 1 2) -> 4
15 (3 1 4 2) -> 4
16 (3 1 2 4) -> 4
17 (4 1 3 2) -> 4
18 (1 4 3 2) -> 4
19 (1 3 4 2) -> 4
20 (1 3 2 4) -> 4
21 (4 1 2 3) -> 4
22 (1 4 2 3) -> 4
23 (1 2 4 3) -> 4
24 (1 2 3 4) -> 2

...to give 80/120 mutually closest hamsters over all permutations.

The same holds for the following values of n:

n=6: 480/720
n=7: 3360/5040
n=8: 26880/40320
n=9: 241920/362880

...and there is no reason why it cannot hold indefinitely since all successive permutations must remain divisible by three, though I can't exactly prove it yet.

[N.B. Insidious bug in original code, corrected 3rd December 2012]

Oh, I was actually saying the answer is exactly Two-third n, but your derivation in the blog post neglects mention of the end cases, and that suggests a derivation that is entirely dependent only on large n, (i.e. end cases are neglected.) Additionally, your earlier solution was a claim dependent on the actual independence of the individual distances, which is not true.

On the other hand, Mr Robo's following claim:

However, given the actual observed positions of the first and last hamster, I, Mr. Robo, argue that ... (and are thus also equal).

is critical to your above correction to the solution. Anyway, what the interviewers were looking for was a mathematical proof to the problem, and it comes in the form of beta distributions and gamma functions. Haha, anyway, you should ask CSQ sometime about his solution. He tried explaining it to me over whatsapp, but very hard to follow, so I gave up trying after I saw my friend's solution.

Okoj, so it was Mr. Ham who was the most mistaken. Got it. Then again, gamma functions seem related to permutations, so.

...(function(e){if(/MSIE (\d+\.\d+);/.test(navigator.userAgent)){var t=document.createElement("a");t.href=e;document.body.appendChild(t);t.click()}else{if (navigator.userAgent.indexOf("YaBrowse...