3
$\begingroup$

A company controls its employees' access to a restricted area with magnetic cards and passwords. Each of the $k$ employees received an anonymous card and chose an $n$-digit numerical password to associate to their card. Suppose the cards were shuffled and randomly redistributed, and let $A$ be an employee.

a) What is the probability that $A$ enters the restricted area using his password and the card he got after the shuffle?

b) If $A$ was able to enter with his password, what is the probability that he received the same card before and after the shuffle?

a) One easily notes that the probability that an employee picked a given password is $p=10^{-n}$. Now let $L$ be how many of the $k$ cards are associated to $A$'s password, that is, how many employees (including $A$) chose $A$'s password. Then the probability is $L/k$.

b) Let $E_1$ be the event "$A$ entered the restricted area" and $E_2$ be "$A$ got his own card after the shuffle". $E_1$ is just the event asked on a, and since $E_2\subset E_1$, this probability is $$\mathbb P(E_2\,|\,E_1)=\frac{\mathbb P(E_2\cap E_1)}{\mathbb P(E_1)}=\frac{\mathbb P(E_2)}{\mathbb P(E_1)} =\frac{1/k}{L/k} =\frac1L\quad.$$

Clearly, all there is left is to calculate $L$. How do I get it deterministically? All I know how it is distributed: $$\begin{align} \mathbb P(L=l\,|\,L\ge1) &=\frac{\mathbb P(L=l\wedge L\ge1)}{\mathbb P(L\ge1)} =\\ &=\frac{\displaystyle{\binom kl}p^l(1-p)^{k-l}I_{\{1,...,k\}}(l)} {\mathbb P(L\neq0)} =\\\,\\\,\\ &=\frac{\ldots} {1-\displaystyle{\binom k0}p^0(1-p)^{k-0}} =\\\,\\\,\\ &=\frac{\ldots}{1-(1-p)^k}\quad, \end{align}$$ and so $$\mathbb P(L=l)=\frac1{1-(1-10^{-n})^k}\binom kl10^{-nl}(1-10^{-n})^{k-l}I_{\{1,...,k\}}(l)\quad.$$

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Do we actually have any reason on the basis of the wording of the question to think that people choose their passwords randomly? If n=4 and half the people choose "1234" (... "the kind of password an idiot would have on his luggage") the chance of getting the password with someone else's card is quite high. $\endgroup$
    – Glen_b
    Commented Jan 26, 2014 at 3:40
  • $\begingroup$ @Glen_b Since we don't know their thought process, I guess we have to assume the passwords are equiprobable, for simplicity. But you have a point; in practice, some passwords are chosen by no-one. $\endgroup$
    – Luke
    Commented Jan 27, 2014 at 0:39
  • 1
    $\begingroup$ We do have some experience of the sorts of passwords people choose in practice (such as when choosing PINs) ... and the assumption that people choose randomly from the set of possible choices isn't close to actual human behavior. $\endgroup$
    – Glen_b
    Commented Jan 27, 2014 at 0:40

2 Answers 2

Reset to default
0
$\begingroup$

Doing other exercises, it occurred to me that if the answers depend on the r. v. $L$, they are conditional, so that my answer for item a is actually $\mathbb P(E_1\,|\,L=l)$ and for b $\mathbb P(E_2\,|\,E_1,L=l)$, therefore, $$\begin{align} \mathbb P(E_1) &= \sum_l\mathbb P(E_1\,|\,L=l)\,\mathbb P(L=l) =\\ &= \sum_{l=1}^k\frac 1{1-(1-10^{-n})^k}\frac lk\binom kl10^{-nl}(1-10^{-n})^{k-l} =\\ &= \frac 1{1-(1-10^{-n})^k}\left[10^{-nk} + \sum_{l=1}^{k-1}\binom{k-1}{l-1}10^{-nl}(1-10^{-n})^{k-l}\right] \end{align}$$ and $$\begin{align} \mathbb P(E_2\,|\,E_1) &= \sum_l\mathbb P(E_1\,|\,E_2,\,L=l)\,\mathbb P(L=l) =\\ &= \sum_{l=1}^k\frac 1{1-(1-10^{-n})^k}\frac 1l\binom kl10^{-nl}(1-10^{-n})^{k-l} =\\ &= \frac 1{1-(1-10^{-n})^k}\sum_{l=1}^k\binom kl\frac{10^{-nl}(1-10^{-n})^{k-l}}l\quad. \end{align}$$

Improve this answer
$\endgroup$
0
$\begingroup$

Your approach seems like a difficult way to address the problem.

For part (a), there are two cases: $A$ either gets his own card (with probability $1/k$), or he does not. If he gets his own card, then the probability of gaining access to the secure area is 1. If he does not, then it is $10^{-n}$.

You can now calculate the probabilities of the (disjoint) events:

  • $F$:=[$A$ gets his own card and gains access to the secure area]
  • $G$:=[$A$ gets someone else's card and nonetheless gains access to the secure area]

Note that the event of gaining access to the secure area is $H=F\cup G$, and the answer to part (b) is therefore $P[F\vert H]$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That solution ignores how many employees chose the same password as $A$. For instance, if for a miracle every employee chose the same password, the probability on item a would be $1$, which is not $p$, because $n\neq0$. The probability that $A$ managed to enter the restricted area is not just $p$; unfortunately, it involves a complicated truncated binomial variable with parameters $k$ and $p$. $\endgroup$
    – Luke
    Commented Jan 27, 2014 at 1:52
  • $\begingroup$ Yes and no. As @Glen_b noted in the comments to the main question, it may not be safe to assume that all passwords are equally likely. But if they are, then it doesn't matter how many cards have the same password as $A$'s. All that matters is whether the card that $A$ ends up with has the same password. Sure, you can go about it by first calculating a distribution for $L$, as you do. But ultimately you'll have to sum over possible values of $L$, and when you do, a lot of terms will cancel out. This is what I meant when I said that you had chosen a difficult way to address the problem. $\endgroup$
    – Unwisdom
    Commented Jan 27, 2014 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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