# Average Neighbouring Impurity Separation in a Random 1D chain (Cross-post from Physics.SE)

Someone recommended asking in here instead of Physics.SE since it is more of a probability question than anything purely physical:

I have a finite and discrete 1D chain (edit: linear chain, i.e. a straight line) of atoms, with unit separation, with a set number of impurities randomly distributed in the place of these atoms in the system. What I would like to do is describe the separation between neighbouring impurities (call it "D" which will always be an integer) statistically, and also to work out the average separation .

For example, the plot below was calculated from several thousand simulations of a chain of length 200 atoms and 10 impurities where the y-axis is the probability $P(D)$ of finding an impurity at distance D, and the x-axis is nearest impurity distance $D$. It kind of looks like a Poisson distributon, which one would expect since the system is discrete and random and a kind of counting exercise, but it doesn't work to well as a fit to the data points. It has been a long time since I did any statistics so I'm not sure how to start expressing what I found mathematically. Since I know the system length ($L = 200$) and the number of impurities ($N_i$) is a fair starting point the impurity density $\rho = N_i/L$ ?

EDIT: The chain isn't allowed to self-intersect, it's a straight line in each case. The system I'm using above is a straight line of 200 evenly spaced atoms, and I'm distributing 10 impurities in the place of random atoms (e.g. at sites 4, 11, 54,...so there are still discrete steps between sites). The graph above is the result of finding the spacings between these impurity sites.

EDIT 2: Attached a picture at the top

EDIT 3: A poster in Physics.SE suggested it might be a geometrical distribution when the system size becomes very big. Is there any way to describe my distribution for this smaller system however?

-
How do you distribute the N impurities among the L sites? – Did Jul 25 '12 at 14:22
I wrote a FORTRAN program that uses a random number generator to randomly pick sites in the chain to assign to being an impurity, and then worked out the distance between them. Repeated it about 10,000 times and then used that data to make the graph above. – Josh Jul 25 '12 at 14:40
This does not say how one picks the impurities. If one chooses the set of impurities uniformly at random amongst the ${L\choose N}$ subsets of size $N$, then @Ilmari Karonen's conjecture on the Physics.SE page can be made rigorous in the limit $L\to\infty$, $N\to\infty$, $N/L\to\varrho$, that is, $D$ converges in distribution to the geometric distribution with mean $1/\varrho$. – Did Jul 25 '12 at 14:48
I'm still not sure what you mean about how one picks the impurities, is choosing the subset at random not the same as what I am doing? I'll try and explain my program in more depth for a system of size 200 with 10 impurities 1) Build an array of size 200 with all elements set to zero 2) Random number generator spits out a number between 1 and 200 and check it against that element in the array, if it is Zero then change it to One (corresponds to an impurity) 3) Keep repeating this process until the array has the required number of impurities (used SUM(Array) = 10 in this case). – Josh Jul 25 '12 at 15:48
This is indeed choosing the set of impurities uniformly at random hence Ilmari's conjecture applies. – Did Jul 25 '12 at 16:05

If you count the number of pure atoms in the gaps (so one less than the distance between the impure atoms) then you can also consider the gaps before the first impure atom and after the last impure atom. So you have $L-N$ pure atoms in $N+1$ gaps and so the average number of pure atoms in a gap is $\frac{L-N}{N+1}$. Add one to this to get $\frac{L+1}{N+1}$ if you must.
The gaps are identically (but not independently) distributed. The easiest way to see this is to consider a circular chain of $L+1$ atoms of which $N+1$ are impure at random. Choose one of the impure atoms at random to break the circle and you are back at your original question, but there is clearly symmetry in the randomness.
The probability that there are at least $g$ [i.e. $D-1$ in your terms] pure atoms in the first gap (and so in any particular gap) is $\frac{L-g \choose N}{L \choose N}$ if $0 \le g \le L-N$ and so the probability there are exactly $g$ pure atoms in any particular gap is $\frac{1}{L \choose N}$ if $g=L-N$ and $\frac{{L-g \choose N}-{L-g-1 \choose N}}{L \choose N} =\frac{{L-g-1 \choose N-1}}{L \choose N}$ if $0 \le g \lt L-N$. Adjust $g$ by one if you must.