tag:blogger.com,1999:blog-4115025577315673827.post7564355630292697795..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Mean minimum distance for N random points on a one-dimensional lineUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-4115025577315673827.post-79513653636212832462009-10-27T11:17:49.780+05:302009-10-27T11:17:49.780+05:30It can be related to the following: Imagine you ha...It can be related to the following: Imagine you have n marked cards in a pack of m cards and shuffle them randomly. What is the probability that they are all at least distance d apart?<br /><br />Consider dealing the cards out, one by one, from the top of the pack. Every time you deal a marked card from the top of the deck, you then deal d cards from the bottom (or just deal out the remainder if there's less than d of them). Once all the cards are dealt out, they are still completely random. The dealt out cards will have distance at least d between all the marked cards if (and only if) none of the marked cards were originally in the bottom (n-1)d. The probability that the marked cards are all distance d apart is the same as the probability that none are in the bottom (n-1)d.<br /><br />The points uniformly distributed on a line segment is just the same (considering the limit as m →∞). The probability that they are all at least a distance d apart is the same as the probability that none are in the left section of length (n-1)d. This has probability (1-(N-1)d/L)^N.<br /><br />Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N^2-1).<br /><br />:) I am happy!!! :DPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.com