Skip to main content

This can answered without any complicated maths.

It can be related to the following: Imagine you have N$N$ marked cards in a pack of m$m$ cards and shuffle them randomly. What is the probability that they are all at least distance d$d$ apart? 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$d$ cards from the bottom (or just deal out the remainder if there's less than d$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$(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$(N-1)d$.

The points uniformly distributed on a line segment is just the same (considering the limit as m →∞$m$$\rightarrow∞$). The probability that they are all at least a distance d$d$ apart is the same as the probability that none are in the left section of length (N-1)d$(N-1)d$. This has probability (1-(N-1)d/L)N$(1-\frac{(N-1)d}{L})^N$.

Integrating over 0≤d≤L/(N-1)$0$$\le$$d$$\le$$\frac{L}{(N-1)}$ gives the expected minimum distance of L/(N2-1)$\frac{L}{(N^2-1)}$.

This can answered without any complicated maths.

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? 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.

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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

This can answered without any complicated maths.

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? 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$.

The points uniformly distributed on a line segment is just the same (considering the limit as $m$$\rightarrow∞$). 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-\frac{(N-1)d}{L})^N$.

Integrating over $0$$\le$$d$$\le$$\frac{L}{(N-1)}$ gives the expected minimum distance of $\frac{L}{(N^2-1)}$.

Fixed typo, n->N
Source Link
George Lowther
  • 17.1k
  • 1
  • 66
  • 98

This can answered without any complicated maths.

It can be related to the following: Imagine you have nN 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? 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 (nN-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 (nN-1)d.

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 (nN-1)d. This has probability (1-(nN-1)d/L)N.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

This can answered without any complicated maths.

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? 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.

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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

This can answered without any complicated maths.

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? 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.

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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

more typos
Source Link
George Lowther
  • 17.1k
  • 1
  • 66
  • 98

This can answered without any complicated maths.

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? 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 is that the marked cards are all distance d apart is the same as the probability that none are in the bottom (n-1)d.

The points uniformly distributed on a line segment is just the same (considering the limit as nm →∞). 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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

This can answered without any complicated maths.

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? 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 is that the marked cards are all distance d apart is the same as the probability that none are in the bottom (n-1)d.

The points uniformly distributed on a line segment is just the same (considering the limit as n →∞). 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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

This can answered without any complicated maths.

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? 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.

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.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

typo
Source Link
George Lowther
  • 17.1k
  • 1
  • 66
  • 98
Loading
typos
Source Link
George Lowther
  • 17.1k
  • 1
  • 66
  • 98
Loading
Source Link
George Lowther
  • 17.1k
  • 1
  • 66
  • 98
Loading