5
$\begingroup$

What will be the value of the following summation?

$$\sum_{i=1}^{m}{ \frac{i(n-i)!}{ n!} }$$

Is it $\frac{m}{2}$ ? Can anybody show the derivation?

$\endgroup$
4
  • 2
    $\begingroup$ $\frac m2$ is not correct for $n=1$ and I would expect the result to be dependent on $n$, too. Are you sure you typed your question correctly? Did you want to write $n$ instead of $m$? $\endgroup$ Jul 17 '12 at 8:27
  • $\begingroup$ The series becomes: $$\dfrac{1}{n} + \dfrac{2}{n(n - 1)} + \cdots + \dfrac{k}{n(n - 1)\cdots(n - k + 1)} + \cdots + \dfrac{m}{n(n - 1)\cdots(n - m + 1)}$$ $\endgroup$
    – hjpotter92
    Jul 17 '12 at 8:59
  • $\begingroup$ Yes, the problem given is as follows: There is a string of length m chosen randomly from n characters. Before a character is added to the string, it is checked if the character is already present in a set S. If found, it declares the string non-unique, else it adds the character to the set S. What will be the length of the string that should be scanned on average? While trying to find the expected length, I came up with this expression and it has been mentioned that on average half the string length i.e. m/2 will be scanned. $\endgroup$ Jul 17 '12 at 15:35
  • 1
    $\begingroup$ WolframAlpha gives a closed form, and it is not very pretty: wolframalpha.com/input/… (be sure to click "exact form") $\endgroup$
    – Argon
    Jul 18 '12 at 0:57
1
$\begingroup$

I've voted to delete my original (non-) answer. Here's a real one. You're given a string $x=x_1x_2\dots x_m$ where each character $x_i$ is in a set of size $n$. Throughout, we assume $n\ge m$. (We can analyze the case where $n<m$ but it's messier.) The task is to determine whether $x$ has any duplicate characters. You've agreed that the algorithm to do this will use a set $S$, initially empty, and will test each character in turn, like this

for i = 1 to n
   if x[i] is in S
      quit: we've found a duplicate character
   else
      add x[i] to S
quit: no duplicates found

The question is, what is the expected value of the number of characters that have been inspected when the algorithm terminates? I'll give an example with $m=4$ before I give the general (and quite messy) value. Denote the expectation by $E(n,m)$.

($i=1$) The first iteration will simply result in $S=\{x_1\}.$

($i=2$) On the second iteration of the loop, $x_2$ will be in $S$ with probability $1/n$ and we'll quit, having inspected two characters, so we add the term $(2)(1/n)$ to our expectation. On the other hand, $x_2$ will not be in $S$ with probability $1-1/n = (n-1)/n$ so we add $x_2$ to $S$ and continue searching.

($i=3$) We get to the third iteration with probability $(n-1)/n$. We see that $x_3$ will be in $S$ with probability $2/n$ upon which we'll quit, having added the term $(3)(2/n)((n-1)/n)$ to our expectation. If $x_3$ is not in $S$, we'll continue with probability $((n-1)/n)((n-2)/n$.

($i=4$) In the last step, we have inspected all the characters in $x$ and will quit. This will add the final term, $(4)((n-1)/n)((n-2)/n)$ to our expectation.

Thus, we'll have $$ E(n, 4)=(2)\frac{1}{n}+(3)\frac{2}{n}\cdot\frac{n-1}{n}+(4)\frac{n-1}{n}\cdot\frac{n-2}{n} = 4-\frac{4n-2}{n^2} $$ With a lot more tedious work, we can show that in general, with $n\ge m$ we'll have $$ E(n, m) = \frac{1}{n^{m-3}}\sum_{k=1}^{m-3}\left(k(k+1)\prod_{j=1}^{k-1}(n-j)\right) +\frac{nm-m+2}{n^{m-2}}(n-1)\cdots (n-m+3) $$ As far as I can tell, there's no nice closed form for this. However, we do have a nice asymptotic estimate. I'm pretty sure that for fixed $m$, as $n$ gets large, $$ E(n, m) \sim m - \binom{m}{3}\frac{1}{n} $$ This agrees with our intuition: for large $n$ almost all length-$m$ strings won't have duplicate characters, meaning that most strings will require inspecting all $m$ characters before we know whether or not there are any duplicates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.