Derivation Notes of Subquestion d

Page last edited 1,443 days ago
From Wei-Liang Qian
Jump to navigation Jump to search

We will slightly modify the notation as follows, <math>n</math> will be reserved to denote the occupation number so that it will be replaced by <math>N</math> in our answer.

Let us first try to clarify the strategy. Consider a simple case where <math>N=3, k=3</math>. We will denote a possible occupation distribution <math>\chi_i</math> by <math>(2,1,0)</math> in the sense that for <math>i-</math>th distribution, there are two objects in the first bucket, one object in the second bucket and nothing in the third. Obviously, a given distribution <math>\chi_i</math> corresponds to more than one placement. In other words, there might be a total (degenerate) number of <math>g_i</math> placements. Let us take the above occupation distribution <math>\chi_i=(2,1,0)</math> as an example, it corresponds <math>(k_1k_2,k_3,0),(k_2k_3,k_1,0),(k_3k_1,k_2,0)</math>, and therefore <math>g_i=3</math>. We note that a similar distribution <math>(1,2,0)</math> will be viewed as a different distribution in our treatment. Besides, we will evaluate the probability for a given distribution to take place, namely, <math>p_i</math>. Finally, the number of (pair) collisions associated with a distribution will be denoted by <math>c_i</math>. Therefore, the average collision reads

<math>C=\sum_i c_i g_i p_i</math>.

Also, once one works out the expression for <math>p_i</math> and <math>g_i</math>, the normalization implies

<math>\sum_i g_i p_i =1</math>

Before proceeding to the calculations, let us work out a few simple examples against which we can compare out resultant expression.

For <math>N=1, k=2</math>, <math>C_{1,2}=\frac{2\cdot 1}{2\cdot 1}=1</math>.

For <math>k=1</math>, <math>C_{N,1}=0</math>.

For <math>N=2, k=2</math>, <math>C_{2,2}=\frac{2+0}{4+0}=\frac12</math>

Last but not least, for <math>N=3, k=3</math>, <math>C_{3,3}=\frac{0+6\cdot 3+3\cdot 3}{3\cdot 2+6\cdot 3+3}=1</math>, where the summation have been carried out regarding distributions <math>(1,1,1)</math>, <math>(2,1,0)</math> with its variations, and <math>(3,0,0)</math> with its variations, respectively.

Now, let us try to evalute <math>C_{N,k}</math> for the general case. For the distribution <math>\chi_i\equiv (n_1,n_2,\cdots,n_N)</math>, the probability <math>p_i</math> is simply

<math>p_i=\left(\frac1N\right)^{n_1}\left(\frac1N\right)^{n_2}\cdots \left(\frac1N\right)^{n_N}=\left(\frac1N\right)^{k}</math>

The degeneracy number <math>g_i</math> can be obtained by first carrying out a total permutation among <math>k</math> object, and then compensate the permutation within each bucket, as the latter does not count as different distributions. To be specific,

<math>g_i=\frac{k!}{n_1 !n_2 !\cdots n_N !}</math>.

In order to compute the number of (pair) collisions, we note that if there is <math>n_i</math> object in a bucket, this bucket will contribute a total number of collsions <math>{n_i \choose 2}</math>. Therefore, for the distribution <math>\chi_i</math>, the collision number is the summation

<math>c_i=\sum_j {{n_j} \choose 2} = {{n_1} \choose 2}+{{n_2} \choose 2}+\cdots +{{n_N} \choose 2}</math>

Now, we need to evaluate

<math>C_{N,k}=\sum_i c_i g_i p_i=\sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !} \left(\frac1N\right)^{k}\times \sum_j {{n_j} \choose 2}</math>.

Before continue to work the above ``hard" summation, let us pause for a moment to give two comments. First, as mentioned above, let us verify that the normalization condition indeed is satisfied, namely,

<math>\sum_i g_i p_i = \sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !} \left(\frac1N\right)^{k}=1</math>

This can be readily verified by intentionally ``restoring" the above expression to a previous version. To be more specific

<math>\sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !} \left(\frac1N\right)^{k}=\sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !}\left(\frac1N\right)^{n_1}\left(\frac1N\right)^{n_2}\cdots \left(\frac1N\right)^{n_N}

= \sum_\limits{n_1,n_2,\cdots}{k \choose n_1}{k-n_1 \choose n_2}{k-n_1-n_2 \choose n_3}\cdots{n_N \choose n_N}\left(\frac1N\right)^{n_1}\left(\frac1N\right)^{n_2}\cdots \left(\frac1N\right)^{n_N}</math>

<math>= \sum_\limits{n_1,n_2,\cdots}\left[{k \choose n_1}\left(\frac1N\right)^{n_1}\right]\left[{k-n_1 \choose n_2}\left(\frac1N\right)^{n_2}\right]\cdots\left[{n_N \choose n_N}\left(\frac1N\right)^{n_N}\right]

=\left(\frac1N+\frac1N+\cdots+\frac1N\right)^k=1^k=1</math> where for the first equality, we substitute back how the total probability <math>p_i</math> was evaluate, the latter steps is reminiscent of subquestion (a) of this problem. In fact, the trick one (might have) employed to solve subquestion (b), a slightly sophisticated version of the above lines, will be used shortly. Also, we note that <math>\left[{k \choose n_1}\left(\frac1N\right)^{n_1}\right]</math> is the combination number of choose <math>n_1</math> objects from the total number <math>k</math> and put them in the first bucket, and <math>\left[{k-n_1 \choose n_2}\left(\frac1N\right)^{n_2}\right]</math> is the subsequecial combination number of choosing <math>n_2</math> objects from the remaining <math>k-n_1</math> ones. With this result at hand, we become a little bit more confident that we are indeed on the right track.

The second comment is that instead of using brutal force to work out the above expression for <math>C_{N,k}</math>, we might choose to handle an easy one. In other words, since we have considered all possible combinations and all the buckets are identical, we can simply evaluate the average collision number of the first bucket <math>C_{N,k}^{(1)}</math> and then multiply by a factor of <math>N</math>, the total number of buckets, to get the desired result.

<math>C_{N,k}=N\times C_{N,k}^{(1)}</math>

with

<math>C_{N,k}^{(1)}=\sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !} \left(\frac1N\right)^{k}\times {{n_1} \choose 2}

=\sum_\limits{\chi_i} \frac{k!}{n_1 !n_2 !\cdots n_N !} \left(\frac1N\right)^{k}\frac{n_1(n_1-1)}{2}</math>.

Finally, our task is to calculate <math>C_{N,k}^{(1)}</math>. As mentioned above, one can borrow the trick for subquestion (b). To be more specific, one may introduce an ``artificial" variable <math>x</math> so that

<math>n_1 x^{n_1}=x\frac{d}{dx} x^{n_1}</math>
<math>n_1(n_1-1) x^{n_1}=x^2\frac{d^2}{dx^2} x^{n_1}</math>

Therefore, the calculation of <math>C_{N,k}^{(1)}</math> can be rewritten by

<math>\frac12 x^2\frac{d^2}{dx^2}\left(x+\frac1N+\frac1N+\cdots\frac1N\right)^k=\frac12 x^2\frac{d^2}{dx^2}\left(x+\frac{N-1}{N}\right)^k</math>

Then replace <math>x</math> with <math>\frac1N</math>.

The above trick is also used in treating integrals. For instance, if one has already known how to evaluate <math>C(k)=\int_{-\infty}^{+\infty} dx e^{-kx^2}</math>, then <math>C_x(k)=\int_{-\infty}^{+\infty} dx x^2e^{-kx^2}=-\frac{d}{dk} C(k)</math>. However, if there is no <math>k</math> on the exponential of the original integrant, we can still employ the method by ``artificially" inserting <math>k</math>, carry out the derivative and then assign <math>k=1</math> by the end. This is precisely what we are doing here.

To be completely explicit, for the present case, we have

<math>\sum_\limits{n_1,n_2,\cdots}\frac{n_1(n_1-1)}{2}{k \choose n_1}x^{n_1}{k-n_1\choose n_2}\left(\frac1N\right)^{n_2}\cdots

=\sum_\limits{n_1,n_2,\cdots}\frac12 x^2\frac{d^2}{dx^2}\left({k \choose n_1}x^{n_1}{k-n_1\choose n_2}\left(\frac1N\right)^{n_2}\cdots\right) \to\left.\frac12 x^2\frac{d^2}{dx^2}\left(x+\frac{N-1}{N}\right)^k\right|_{x=\frac1N}</math> where <math>\cdots</math> denotes the remaining terms which does not involve the ``artifical" variable <math>x</math>.

One can easily calculate the derivative and finds it gives rise to

<math>\frac12 k(k-1)x^2 \left(x+\frac{N-1}{N}\right)^{k-2}</math>

By substitution, one arrives at <math>C_{N,k}^{(1)}=\frac12 k(k-1)\left(\frac1N\right)^2</math> which, in turn, gives <math>C_{N,k}=\frac{k(k-1)}{2N}</math>

As a final remark, we can verify that the above expression is indeed consistent with those values of <math>C_{1,2},C_{N,1},C_{2,2},C_{3,3}</math>, obtained forehand.

<math></math>