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](https://wildonblog.wordpress.com/2015/02/23/how-much-do-hash-collisions-help-an-attacker/). 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.



A balls and urns model for a hashing problem
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}$$


