3
$\begingroup$

For a randomly generated character sequence of length $k$ containing only characters from a fixed set of length $n$ (e.g. alphabet), what is the probability that it contains at least $m$ equal characters?

Original problem: What is the probability that a randomly generated password of length $k = 10$ only consisting of lowercase letters and digits ($n = 26 + 10 = 36$) will contain any character for at least $m = 5$ times? For example, the password aa91abcada contains the character 'a' exactly $5$ times.

I suppose that if we define random variable $X$ as the number of equal characters in a sequence of length n, then the problem boils down to computing: $$P(X\ge m) = P(X=m) + P(X=m+1) + \cdots + P(X=k)$$ Thus we only need to find a formula for computing $P(X=m)$ for $m\in\lbrace1, 2,\ldots,k\rbrace$.

I managed to come up with the following formula: $$P(X=m) = \frac{\text{number of satisfying sequences}}{\text{ number of all possible sequences}} = \frac{n\binom{(m + 1)(k-m)}{(k-m)}(n-1)^{k-m}}{n^k}$$

where the 3 multipliers in the numenator have the following meanings:

  • we choose a fixed character that repeats m times (we do this for all $n$ characters)
  • we can place the remaining $k - m$ characters between any of the fixed characters, at the beginning, or at the end. Thus we want to pick $k - m$ positions out of all possible $(m + 1)(k - m)$ positions (there are $m + 1$ "spaces" between fixed characters and in each one of them there can possibly be $k - m$ characters).
  • each of the remaining $(k - m)$ characters can be any of the remaining $n - 1$ characters in our alphabet

However, I have a strong suspicion that this formula (if correct) works only for for $m > \frac{k}{2}$.

Is the above formula correct? If not, is there a general formula for this kind of problem?

$\endgroup$
5
  • $\begingroup$ Could you clarify whether the character should occur $>m$ times or $\geq m$ times? You specify that the probability you're looking for is $P(X\geq m)$, but the wording of the question suggests that it should be $P(X>m)$. $\endgroup$ – Jason Yuan Oct 21 '20 at 15:04
  • $\begingroup$ You are right, I edited the question $\endgroup$ – brako Oct 21 '20 at 17:56
  • 2
    $\begingroup$ In your algorithm, if a word has both $m$ a's, and $m$ b's, it will be generated twice $\endgroup$ – Sudix Oct 21 '20 at 19:06
  • $\begingroup$ It might be simpler to look at the probability of not satisfying the condition, since you can have a positive match in multiple ways in one sequence, e.g., both $x$ and $y$ occurring $m$ times if $2m\leq k$. $\endgroup$ – Kevin P. Barry Oct 21 '20 at 20:09
  • $\begingroup$ Also, induction over $k$ might be a helpful way to get an intuition of a more general solution, since the probability starts at $0$ and at some point is identically $1$ for all greater $k$. $\endgroup$ – Kevin P. Barry Oct 21 '20 at 20:15
1
$\begingroup$

Okay, here's my attempt. I'm not 100% sure of this either, but maybe it can offer a new perspective. Instead of computing the sums of all $P(X=m)+P(X=m+1)...$, you can directly compute the probability for $X\geq m$.

Using the case provided in the question with $k=10$, $n=36$, and $m=5$, we can create the following string that uses $a$ to represent the fixed character and $b$ to represent all other characters: $$aaaaabbbbb$$ In this scenario, there are $m=5$ $a$'s which have one possible value. On the other hand, the $k-m=10-5=5$ $b$'s can be all 36 different characters. We don't need to exclude the fixed character from $b$ because we're looking for $P(X\geq m)$ and not $P(X=m)$. Hence, the number of outcomes that fulfill the parameters given for that single string is: $$1\times 1\times 1\times 1\times 1\times 36\times 36\times 36\times 36\times 36=36^5=n^{k-m}$$ Next, we multiply by the ${k\choose m}={10\choose5}=252$ different arrangements of strings with 5 $a$'s and 5 $b$'s: $${36^5{10\choose 5}}=n^{k-m} {k\choose m}$$ Finally, there are 36 possible characters that the fixed character can be, hence, we multiply by 36: $$36^{5+1}{10\choose 5}=n^{k-m+1}{k\choose m}$$ Now divide the satisfying outcomes over the total possible outcomes to get the final probability: $$P(X\geq 5)=\frac{36^{5+1}{10\choose 5}}{36^{10}}\approx0.015\%$$ As a general rule: $$P(X\geq m)=\frac{n^{k-m+1}{k\choose m}}{n^k}$$ And then for fun, we can make a general rule for $P(X=m)$ by excluding the fixed character from the $b$ letters: $$P(X=m)=\frac{n(n-1)^{k-m}{k\choose m}}{n^k}$$ Again, I'm not 100% confident in this solution but it seems to make sense to me.

$\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.