How many times do I roll an unfair die to determine its bias? This question comes from computer security, but I'll distill it into a probability question:
I have a biased die with 96 sides.  95 sides are equiprobable, each having a 1% chance of landing up.  The remaining side, side X, has a 5% chance.
All sides look identical; I want to identify side X.  My best strategy is obviously to roll it a bunch of times and take the majority, but my question is this: how many rolls are needed until Pr{X is majority result} > p for any given p > 1/2?
 A: As the other answer shows, the answer is not simple. This is because it depends on the exact sequence of rolls. You can see this using Bayesian reasoning. Let $X$ be a r.v. that indicates the biased side. Denote the value of the $i^\mathrm{th}$ role by $Y_i$. Then, 
$$p(Y_1, \cdots, Y_n|X=x) =  \left(\frac{1}{20}\right)^{m_x} \left(\frac{1}{100}\right)^{n-m_x}$$
where 
$$m_x = \sum_{i=1}^n \mathbf{1}\left(Y_i = x\right)$$
and $\mathbf{1}$ is the indicator function. Then, we can use Bayes rule to calculate the probability of $X=x$ given a sequence of rolls.
$$p(X=x|Y_1, \cdots, Y_n) = \frac{p(Y_1, \cdots, Y_n|X=x)p(X=x)}{P(Y_1, \cdots, Y_n)} = \frac{p(Y_1, \cdots, Y_n|X=x)p(X=x)}{\sum_{x'} P(Y_1, \cdots, Y_n | X=x')p(X=x')}$$
Substituting from above and assuming all sides are uniformly equal 
$$=\frac{\left(\frac{1}{20}\right)^{m_x} \left(\frac{1}{100}\right)^{n-m_x} \frac{1}{96}}{\sum_{x'=1}^{96}\left[ \left(\frac{1}{20}\right)^{m_{x'}} \left(\frac{1}{100}\right)^{n-m_{x'}}\right] \frac{1}{96}}$$
So, basically, its hard to know a priori how many rolls because it depends on how many "repeats" on all sides comes up. But, you can easily compute the probability that $X=x$ where $x$ is any side you want and stop after enough rolls.
A: Let's agree that the first side has $5\%$ chance, and remaining $95$ sides each have $1\%$ of occurrence. After $n$ rolls, let $N_k$ denote the random variable for the number of occurrences of $k$-th side. Then the random vector $(N_1,\ldots, N_{96})$, subject to $\sum_{k=1}^{96} N_k = n$, follows multi-nomial distribution. 
I would interpret your question as a quest to determine, for $p > \frac{1}{2}$:
$$
  n_\mathrm{min} = \operatorname{arg min}_n \mathbb{P}(N_1 > N_2 \land N_1 > N_3 \land \ldots \land N_1 > N_{96} ) > p
$$
This probability equals:
$$ \begin{eqnarray}
  \mathbb{P}\left( \land_{k=2}^{96} N_1 > N_k \right) &=& \sum_{n_1=1}^n \mathbb{P}\left( \land_{k=2}^{96}  N_k \le n_1 -1 ; N_1 = n_1 \right) \mathbb{P}\left( N_1 = n_1 \right) \\
   &=& \sum_{k=0}^{n-1} \left( F\left( k+1,k,\ldots,k \right) - F\left( k,k,\ldots,k \right) \right)
  \end{eqnarray}
$$
where $F(n_1,\ldots,n_k,\ldots,n_{96}) = \mathbb{P}\left( N_1 \le n_1, \ldots, N_k \le n_k,\ldots, N_{96} \le n_{96} \right)$.
Even when normal or Poisson approximation to multinomial cumulative distribution function is applicable, it does not simplify matter very much.
As an approximation $F$ can be replaced with product of marginal cumulative distribution functions, since correlation coefficients are on the order of $0.01$, i.e. small:
$$
   \mathbb{P}\left( \land_{k=2}^{96} N_1 > N_k \right) = 
      \sum_{k=0}^{n-1} f_{\mathrm{Bi}\left(n, \frac{1}{20}\right)}(k+1) \left( F_{\mathrm{Bi}\left(n, \frac{1}{95}\right)}(k) \right)^{95}
$$
I ran simulation, and plotted the probability $\mathbb{P}(\land_{k=2}^{96} N_k < N_1)$ as a function of $n$, and compared to this approximation, the agreement is rather good:

