7
$\begingroup$

Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c \in \{1,\ldots, N\}$ uniformly at random. Then choose further $b_1, \ldots, b_r \in \{1,\ldots, N\}$, so that $b_i$ is chosen uniformly at random from $\{1,\ldots,N\} \backslash \{b_1,\ldots,b_{i-1}\}$, stopping as soon as ball $b_r$ and ball $c$ are in the same urn.

What is the expected value of $r$?

I can get some fairly crude upper and lower bounds. I would like an asymptotically correct answer.

One possible approach to the problem is to approximate the number of balls in urn $j$ by a Poisson random variable with mean $1$. So I would also be interested in the answer to the following question.

Let $B_1,\ldots, B_N$ be independent Poisson random variables with mean $1$. What is the expected value of $r$ if we start with $B_j$ balls in urn $j$, for each $j$?

Motivation. Suppose $\{1,\ldots, N\}$ are permitted passwords, and that passwords are hashed using an idealized hash function $h : \{1,\ldots, N\}\rightarrow \{1,\ldots, N\}$, constructed so that each $h(b)$ is chosen uniformly at random from $\{1,\ldots, N\}$. Then $r$ is the expected number of hashes we must compute to obtain a password $b \in \{1,\ldots,N\}$ with the same hash as a randomly chosen $c \in \{1,\ldots, N\}$.

Very possibly the answer to my question is out there in the cryptography literature, but if so, I'm finding it hard to find among all the papers dealing with the birthday paradox or other types of hash collision.

Improve this question
$\endgroup$
6
  • $\begingroup$ Why does your hash function have the same domain and range? You can ask the same thing without this restriction. $\endgroup$
    – Douglas Zare
    Commented Mar 2, 2015 at 21:58
  • $\begingroup$ I think your model and your motivation do not match very well. The motivation suggests a simpler model where $c$ is in an arbitrary bin $\{1,\dots,N\}$ and we throw balls uniformly at random into the $N$ bins until we hit the bin containing $c$. $\endgroup$
    – usul
    Commented Mar 3, 2015 at 1:20
  • $\begingroup$ @usul: There are two ways to stop. You can stop because you encounter the index of the special ball (and you would wait an average of $(N+1)/2$ before that happens) or you can stop because a different ball is sent to the same location as the special ball. Conditional on the first not happening, the second happens with probability $1/N$ each time, so in some sense you would expect to check $N$ balls before that happens. $\endgroup$
    – Douglas Zare
    Commented Mar 3, 2015 at 2:58
  • $\begingroup$ @DouglasZare, yes, in the model I propose, I think that the expected wait time is exactly $\sum_{r=1}^{\infty} r \frac{1}{N}\left(1-\frac{1}{N}\right)^{r-1} = N$. $\endgroup$
    – usul
    Commented Mar 3, 2015 at 4:13
  • $\begingroup$ @usul: I don't think your model fits the motivation. $\endgroup$
    – Douglas Zare
    Commented Mar 3, 2015 at 4:16

3 Answers 3

Reset to default
3
$\begingroup$

Let $X$ be the number of balls other than the special ball sent to the same urn as the special ball. The distribution of $X$ is close to a Poisson distribution with mean $1$. Condition on $X=x$. There are $x+1$ balls including the special ball sent to the same urn as the special ball. The expected first among $x+1$ objects out of $N$ is about $N/(x+2)$. So (glossing over some details in the double limit) to get the asymptotics, you want to calculate $NE[1/(Y+2)]$ where $Y$ has a Poisson distribution with mean $1$. $E[1/(Y+2)] = 1/e$ so the expected number of balls it takes to get a ball in the special ball's urn is asymptotically $N/e$.

$$\begin{eqnarray}E\left[ \frac{1}{Y+2}\right] &=& \frac{1}{e} \sum_{n=0}^\infty \frac{1}{n+2} \frac{1}{n!}\newline &=& \frac{1}{e} \sum_{n=0}^\infty \frac{n+1}{(n+2)!} \newline &=&\frac{1}{e}\sum_{n=0}^\infty \left[\frac{n+2}{(n+2)!} - \frac{1}{(n+2)!}\right] \newline &=& \frac{1}{e} \left[ \sum_{m=1}^\infty \frac{1}{m!} - \sum_{k=2}^\infty \frac{1}{k!} \right] \newline &=& \frac {1}{e}.\end{eqnarray}$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is similar to the analysis of the expected value of buying $2$ lottery tickets with the same combination. You can extend this to the case that you don't have an equal number of tickets purchased by other people as combinations, or where your hash function has a range that is not the same size as the domain. $\endgroup$
    – Douglas Zare
    Commented Mar 2, 2015 at 22:52
  • $\begingroup$ (+1) I agree with this answer on the assumption that $X$ is close to Poisson with mean $1$. But my intuition (which may well be wrong) is that the special ball is disproportionately likely to be in an urn containing many other balls. Yes, of course the problem makes sense with different domain and range, and I'd be interested to have a general answer. $\endgroup$
    – Mark Wildon
    Commented Mar 3, 2015 at 11:02
  • 3
    $\begingroup$ @Mark Wildon: That urns with $k$ balls are $k$ more times as likely to have the special ball is the difference between the distribution of balls in the special ball's urn, about $\textrm{Pois}(1)+1$, and the distribution of balls in a general urn, roughly $\textrm{Pois}(1).$ $P(Y+1=10) = 10 P(Y=10).$ $\endgroup$
    – Douglas Zare
    Commented Mar 3, 2015 at 12:58
3
$\begingroup$

General solution: assume there are $n$ passwords, $k$ hashes and $x_i$ passwords hashing to $i$. The expected time (drawing without replacement) for the drawing of the first password with hash $i$ is ${n+1 \over x_i +1}$. the probability that a randomly chosen $c$ hashes to $i$ is ${x_i \over n}$. Thus $$\mathbb{E}(r)={n+1 \over n}\sum_{i=1}^k {x_i \over 1+x_i}$$ If the hash function is a random mapping from $[n]$ to $[k]$ each $X_i$ is $Bin(n,{1 \over k})$, and $$\mathbb{E}(R)={k \over n}\big(n+1-k+k(1-{1 \over k})^{n+1}\big)$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ But if each $X_i$ is independent $\mathrm{Bin}(n,1/k)$ then we need not have $\sum_{i=1}^k X_i = n$. So I don't think this agrees with the intended model for a randomly chosen hash function. Of course it may still be a good approximation. $\endgroup$
    – Mark Wildon
    Commented Mar 5, 2015 at 10:26
  • 1
    $\begingroup$ @Mark Wildon: Independence isn't required. We can write the stopping time as a sum of random variables that are $r$ when the special ball goes into the $i$th bin, and $0$ otherwise, and use linearity of expectation, so only the distributions of balls in each bin matters. $\endgroup$
    – Douglas Zare
    Commented Mar 5, 2015 at 12:33
  • $\begingroup$ Of course. Linearity of expectation strikes again. Thank you for the explanation. $\endgroup$
    – Mark Wildon
    Commented Mar 5, 2015 at 14:55
  • $\begingroup$ I should have stated that the $X_i$ are jointly Multinomial (with $n$ and $p_1=...=p_k=1/k$), which makes clear that (1) it agrees with the model of a randomly chosen hash function and (2) that each $X_i$ is $Bin(n,1/k)$. A proof along the elegant lines of the first solution can also be given, by showing that the no. $X_c$ of pwds which hash to the same value as a randomly chosen pwd has distribution $1+Bin(n-1,1/k)$, and computing $\mathbb{E}(R)=\mathbb{E}{n+1 \over 1+X_c}$. But I found the approach above simpler. $\endgroup$
    – esg
    Commented Mar 5, 2015 at 19:49
0
$\begingroup$

I think I missed something in the model. It seems to me that $r$ is uniform in $\{1,\dots,N\}$.

$$ \mathbb{P}(r=x)=\frac{N-1}{N}\times \frac{N-2}{N-1} \times \dots \frac{N-(x-1)}{N-x+2}\times \frac{1}{N-(x-1)} $$ which simplifies in $1/N$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This would be correct if we choose urns at random until we choose an urn containing ball $c$ (discarding urns found not to contain this ball). But we're choosing balls, not urns. $\endgroup$
    – Mark Wildon
    Commented Mar 3, 2015 at 10:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .