Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is probability of having a String with random length with random characters ? For example I want to generate 100 Strings with random length k (between 1 to 100) and generate k numbers of characters (between 1-256 ASCII characters). What's the probability to get a duplicate (exact same string with same length and characters) ?

Here's the psuedocode

    for i=0 to 100
          int size = random_int_range(1,100)
          str = ""              

          for j=0 to size
              str += (char) random_int_range(1,256)    

random_int_range is uniformly distributed.

share|improve this question
    
You need to tell us the distributions. Are they each uniform? Or are all strings equally likely? Are the $k$s the same for all 100 strings? –  Henry Oct 3 '12 at 19:04
    
@Henry they are uniformly distributed, and different k for all 100 strings –  user1389813 Oct 3 '12 at 19:05
    
@Henry I dont think he is thinking about pdfs, I would simply guess they are equally likely –  Seyhmus Güngören Oct 3 '12 at 19:05
    
Duplicate means equal length and equal content, right? –  Sasha Oct 3 '12 at 19:11
    
@Sasha that's correct –  user1389813 Oct 3 '12 at 19:17

1 Answer 1

Here goes an approximation.

We have $N=100$ strings of variable lengths, uniformly distributed in $1\cdots N$. Let $k_m$ be the number of strings of length $m$. We have $C^m$ ($C=256$) distinct strings, all equiprobable. And the probability of no collisions inside this set (given $k_m$) is , from the Birthday problem:

$$p_m = \frac{C^m !}{C^{m k_m} (C^m-k_m)!}$$

for $k_m < C^m$.

But $k_m$ is a random variable, and further $k_i, k_j$ are not independent ($\sum k_i = N$). We know, however, that $E(k_m)=1$. Lets introduce the approximation ("poissonization") of considering the $k_m$ as iid Poisson variables, so

$$P(k_m=k) = e^{-1} \frac{1}{k!}$$

Then the probability of no collision in the set $m$ is

$$ p_m \approx \sum_{k=0}^{C^m} e^{-1} \frac{1}{C^{m k}} {C^m \choose k} = e^{-1} \left(1 + \frac{1}{C^m}\right)^{C^m} $$

and the global probability is the product of the above for $m=1\cdots N$. In practice, only the first few terms have influence. One can even approximate further taking the first term only so that

$$p \approx e^{-1} (1 + 1/C)^{C} = 0.998052$$

or take logarithms and approximate even further:

$$\log(p) \approx - \frac{1}{2 C} = -\frac{1}{512} $$

share|improve this answer
    
+1 Well done! $ $ –  Sasha Oct 4 '12 at 3:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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