Suppose there are $(N +1)$ identical urns marked $0,1,2, . . . ,N$ which contains $N$ balls. The $k^{th}$ urn contains $ k $ black and $N−k$ white balls, $k =0,1,2, . . . ,N.$ An urn is chosen at random, and $n$ random drawings are made from it, the ball drawn being always replaced. If all the $n$ draws result in black balls, find the probability that the $(n+1)^{th}$ draw will also produce a black ball. How does this probability behave as $N\to \infty$?

What I attempted:- Since all the $n$ balls drawn are found black, we can consider only those urns which contain at least $n$ black balls. There are $N-n+1$ urns which contain at least $n$ balls. The probability of choosing any one of them is $\frac{1}{N-n+1}$

Suppose, $A$ =The event of getting black balls in $n$ consecutive draws of a randomly chosen urn
$A_i$ = The $i^{th}$ urn is chosen. Here $n\le i \le N$

Now,\begin{equation} \begin{aligned} P(A)&=P(AA_n)+P(AA_{n+1})+......+P(AA_{N}) \\ &=\sum_{i=n}^{N} P(A_i) P(A|A_i)\\ &=\frac{1}{N-n+1} \sum_{i=n}^{N} \left(\frac{i}{N}\right)^n \end{aligned} \end{equation}

Similarly, we define
$B$= The event of getting $n+1$ black balls in $n+1$ consecutive draws of a randomly chosen urn. We obtain that $P(B)=\frac{1}{N-n} \sum_{i=n+1}^{N} \left(\frac{i}{N}\right)^{n+1}$

We are required to find, $P(B|A)$ which is given as \begin{equation} \begin{aligned} P(B|A)=&\frac{P(AB)}{P(A)}\\ &=\frac{\frac{1}{N-n} \sum_{i=n+1}^{N} \left(\frac{i}{N}\right)^{n+1}}{\frac{1}{N-n+1} \sum_{i=n}^{N} \left(\frac{i}{N}\right)^n}\\ \end{aligned} \end{equation}

Am I correct?

  • 2
    $\begingroup$ If the balls are replaced why does the urn need to have at least n balls? $\endgroup$
    – dsaxton
    Commented Jul 28, 2018 at 12:11
  • $\begingroup$ @dsaxton you are correct. I made a mistake. The correct answer should be Thanks for pointing the mistake. Probably, the correct answer should be $\frac{\frac{1}{N+1} \sum_{i=1}^{N} \left(\frac{i}{N}\right)^{n+1}}{\frac{1}{N+1} \sum_{i=1}^{N} \left(\frac{i}{N}\right)^n}=\frac{ \sum_{i=1}^{N} \left(\frac{i}{N}\right)^{n+1}}{\sum_{i=1}^{N} \left(\frac{i}{N}\right)^n}$ \\ [@ Jim - The problem is from the book "An Introduction to Probability and Statistics" by V.K. Rohatgi and Saleh $\endgroup$
    – user159457
    Commented Jul 28, 2018 at 12:45
  • $\begingroup$ If I am not wrong, the limit of this probability as $N \to \infty$ can be evaluated as follows:- \begin{equation} \lim_{N \to \infty} \frac{ \sum_{i=1}^{N} \left(\frac{i}{N}\right)^{n+1}}{\sum_{i=1}^{N} \left(\frac{i}{N}\right)^n}=\lim_{N \to \infty} N \lim_{N \to \infty} \frac{1^{n+1}+2^{n+1}+.....+N^{n+1}}{1^n+2^n+......+N^n}=\lim_{N \to \infty}N \frac{\int_{0}^{N} t^{n+1} dt}{\int_{0}^{N} t^{n+1} dt}=\frac{n+1}{n+2} \end{equation} I am using Euler-Maclaurin's Summation formula. $\endgroup$
    – user159457
    Commented Jul 28, 2018 at 13:09

1 Answer 1


In this problem you effectively select a random value $K \sim \text{U} \{ 0,...,N \}$ and you observe a count value $X \sim \text{Bin}(n,\tfrac{K}{N})$ from sampling-with-replacement from an urn with $K$ black balls of $N$ balls. In your problem you have $X=n$ and you now want to find $\mathbb{E}(\tfrac{K}{N} | X=n)$, which is the posterior probability of drawing a black ball on the next draw.

Solving the problem: Applying the law of total probability you have:

$$\begin{equation} \begin{aligned} \mathbb{P}(X=n) &= \sum_{k=0}^N \mathbb{P}(X=n|K=k) \mathbb{P}(K=k) \\[6pt] &= \sum_{k=1}^N (\tfrac{k}{N})^n \tfrac{1}{N+1} \\[6pt] &= \frac{1}{N+1} \sum_{k=1}^N (\tfrac{k}{N})^n \\[6pt] &= \frac{1}{N+1} S_n(N), \\[6pt] \end{aligned} \end{equation}$$

where $S_n(N) \equiv\sum_{k=1}^N (\tfrac{k}{N})^n$ is related to Faulhaber's sum, which has various useful expressions. Now we can apply Bayes' rule to obtain:

$$\begin{equation} \begin{aligned} \mathbb{P}(K=k | X=n) &= \frac{\mathbb{P}(X=n|K=k) \mathbb{P}(K=k)}{\mathbb{P}(X=n)} \\[6pt] &= \frac{ (\tfrac{k}{N})^n \tfrac{1}{N+1}}{\tfrac{1}{N+1} S_n(N)} \cdot \mathbb{I}(k>0) \\[6pt] &= \frac{(\tfrac{k}{N})^n}{S_n(N)} \cdot \mathbb{I}(k>0). \\[6pt] \end{aligned} \end{equation}$$

Hence, you have posterior expectation:

$$\begin{equation} \begin{aligned} \mathbb{E}(K|X=n) &= \sum_{k=1}^N k \cdot \frac{(\tfrac{k}{N})^n}{S_n(N)} \\[6pt] &= N \sum_{k=1}^N \frac{ (\tfrac{k}{N})^{n+1}}{S_n(N)} \\[6pt] &= N \cdot \frac{S_{n+1}(N)}{S_n(N)}. \\[6pt] \end{aligned} \end{equation}$$

From this result you have:

$$\mathbb{P}(\text{Next ball is black} | X=n) = \mathbb{E} ( \tfrac{K}{N} | X=n ) = \frac{S_{n+1}(N)}{S_n(N)}.$$

This gives you the probability that the next ball is black, in terms of a ratio of two different instances of Faulhaber's sum. It can be calculated through various known formulae for any given values of $N$ and $n$. It is simple to take the limit $N \rightarrow \infty$ by recognising that this gives a Riemann integral:

$$\lim_{N \rightarrow \infty} \frac{S_n(N)}{N} = \lim_{N \rightarrow \infty} \sum_{k=1}^N (\tfrac{k}{N})^n \cdot \tfrac{1}{N} = \int \limits_0^1 x^n dx = \Big[ \frac{x^{n+1}}{n+1} \Big]_{x=0}^{x=1} = \frac{1}{n+1}.$$

This gives us the limiting result:

$$\lim_{N \rightarrow \infty} \mathbb{P}(\text{Next ball is black} | X=n) = \lim_{N \rightarrow \infty} \frac{S_{n+1}(N) / N}{S_n(N) / N} = \frac{n+1}{n+2}.$$


Your Answer

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