Average Neighbouring Impurity Separation in a Random 1D chain [closed]

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: Okay so it seems it could be my PRNG code causing problems. I'm using Fortran 95, here is the code:

CALL RANDOM_SEED(size = n)
ALLOCATE(seed(n))

CALL SYSTEM_CLOCK(COUNT=clock) !!! intentionally slows it down to prevent succesive calls from returning the same number

do i = 1 , 1000000

end do
seed = clock + 37 * (/ (i - 1, i = 1, n) /)
CALL RANDOM_SEED(PUT = seed)

call random_number(x)


EDIT 4!: Repeated this for a system size of 50 with 3 impurities (10,000 iterations), fitted a geometric distribution to it, as one can see immediately there is a huge variation. Is this explained by the fact for small n and L when we go from our first impurity (at site j) the probabilities to find the next impurity change drastically since effectively we are now looking for a system with n=2 and L= 50-j, which would be really sensitive to the location of the first impurity hence the huge variation. When we go to a huge system we can essentially treat the remainder of the chain as still being really long, and n and L are pretty much unchanged so this effect is masked and we see a geometric distribution arise? EDIT 5: Just did a bit of reading around Bernoulli Trials, is what I'm seeing and describing a binomial distribution hence the peak I see with smaller systems? Still that wouldn't explain why my 200 system is different from Ilmari's below...

-

closed as off topic by dmckee♦Jul 30 '12 at 15:49

Questions on Physics Stack Exchange are expected to relate to physics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

The asymptotic expression for long chains with few impurities is given by the statistics of self-avoiding random-walk. –  Ron Maimon Jul 24 '12 at 21:44
What you are asking can't be solved as stated. You need to know what the probability distribution for the location of the impurities along the chain is, and whether the chain is allowed to self-intersect, or whether it is a random walk. I assumed that the impurities were a fixed distance away, but your plot shows the nearest impurity can be occasionally 120 units away! This means that at least in these runs, all 10 impurities are on one side of the chain, and the chain is nearly straight. So I can't answer. But the right fit is like Maxwell's speed distribution in gasses (for RW case). –  Ron Maimon Jul 25 '12 at 4:21
Should have made that more clear, sorry about that - 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. –  Josh Jul 25 '12 at 10:30
You might have better luck asking this on math.SE; there's nothing inherently physical about this question, it's just abstract probability theory. –  Ilmari Karonen Jul 25 '12 at 11:54
Your problem was then very badly stated. Usually when people ask for distances in a chain polymer, they mean it is embedded as a random walk in space. It's fine now, but more math.SE material. You also need to specify what you did if you chose an already occupied point--- could you put two objects at the same point? Also, for peace of mind, say exactly how you chose the points "at random" along the chain, you could have made a mistake in your algorithm. The right way is to pick 10 random integers from 0-199 and reject collisions and pick again if you don't want particles at the same point. –  Ron Maimon Jul 25 '12 at 16:39

I'll conjecture that, at least in the limit as $L \to \infty$ while $\rho = N_i/L$ stays constant, $D$ will be geometrically distributed with parameter $\rho$.

This is because, for large $L$, we may essentially treat the states of each site as if they were i.i.d. Bernoulli random variables with probability $\rho$ of being an impurity. Then the distribution of the distance from one impurity to the next (or, equivalently, from any arbitrary site to the next impurity) is the same as that for the waiting time before the first successful trial in a Bernoulli process with success rate $\rho$, which is what the geometric distribution describes.

To support this conjecture, here's my version of your plot:

The red crosses show the relative frequency of distances between nearest points over 1000 trials with $L=200$ and $N_i=10$, while the green line shows the expected frequencies given by $$P(D) = \rho (1-\rho)^{D-1}.$$

(Ps. From longer simulation runs, it seems evident that the effect of finite $L$ is to slightly increase the frequency of distances around the mean $1/\rho$ while reducing the frequency of longer distances above about $2/\rho$. Intuitively, this seems perfectly reasonable, but even so, the deviation from the geometric distribution appears very slight, at least for these parameter values.)

For what it's worth, here's the Perl code I used to generate my (blipless) simulation data:

#!/usr/bin/perl
use warnings;
use strict;
use 5.010;

my $L = 200; # number of sites my$N = 10;          # number of impurities
my $reps = 1000; # number of repeats my %count; for my$i (1 .. $reps) { # generate$N distinct random integers from 0 to $L-1 and sort them my %a; undef$a{int rand $L} while keys %a <$N;
my @a = sort {$a <=>$b} keys %a;

# count the differences between closest positions
$count{$a[$_] -$a[$_-1] }++ for 1 ..$#a;
}

say $_, "\t",$count{$_} / ($N-1) / $reps for sort {$a <=> $b} keys %count;  - This is Poisson statistics, already mentioned by OP as the model that didn't work for him. He is asking why he didn't get your thing. He didn't take only nearest neighbors in the average, but included every one of the 55 pair distances. – Ron Maimon Jul 25 '12 at 16:37 @Ron: Well, I'd say the answer to that is either bad luck and not enough samples, or a bug in his code. Without seeing the code, it's hard to tell which. – Ilmari Karonen Jul 25 '12 at 16:41 @Ron: Ps. I'm pretty sure the OP did not consider the distances between all pairs of impurities, but only the distances between nearest pairs. If he'd done the former, he would've obtained a plot that looked nothing like what he had. (In fact, the frequency-distance plot would've been approximately linear.) – Ilmari Karonen Jul 25 '12 at 16:45 Ilmari is right, I was only considering the nearest neighbour pairs, not between each in the whole ensemble. I also tried a larger system size (N=2000) and it does fit a geometric distribution so I would say your idea is right. However, is there a reason why I get a 'blip' that looks kind of like a Poisson distribution for smaller size systems? I would have thought that given a smaller system size the impurities are going to be closer together, however the data I got seems to peak around D=10. Thanks for your help guys, really appreciate it. – Josh Jul 25 '12 at 17:21 @Josh: If you're really getting a consistent blip, I'd say it's probably because, as Ron Maimon suggested, there's some bias in the way you're randomly distributing the impurities. The method I used to generate my plot was to place the impurities at uniformly chosen random positions from$0$to$L-1$until I'd successfully placed$N_i\$ of them; I see no blip with that method. –  Ilmari Karonen Jul 25 '12 at 17:24

I suspect you are seeing a flaw in linear congruential random number generators, that they generate successive random numbers restricted to various planes (see this infamous example). When you are generating 20 successive random integers, you are probably using the built in C rand() function, and the 20 points have correlations in their position.

Use the same program, but use a different generator, you can get one online. The problem should go away. You shouldn't use linear congruential generators for this sort of thing anyway.

-
This is an interesting idea, I found my PRNG online but it uses the system clock to generate the numbers. I'll attach the code below, is there any flaw in this that could be causing my strange blip? 'CALL RANDOM_SEED(size = n) ALLOCATE(seed(n)) CALL SYSTEM_CLOCK(COUNT=clock) !!! intentionally slows it down to prevent succesive calls from returning the same number do i = 1 , 1000000 end do seed = clock + 37 * (/ (i - 1, i = 1, n) /) CALL RANDOM_SEED(PUT = seed) call random_number(x)' –  Josh Jul 26 '12 at 15:36
Added the code above in the OP since this is kind of hard to read and SE isn't letting me delete my comment –  Josh Jul 26 '12 at 15:58
@Josh: just use the same code with ranmar. –  Ron Maimon Jul 26 '12 at 18:43