1
$\begingroup$

The following is a very dummy probability problem. I just want an elegant solution to get the result.

The problem: In a book of $500$ pages, the total number of typos is $500$. Find the probability that a certain page contains at most $3$ typos.

If one assigns the variable name $x_k$ to the number of typos in the $k^{th}$ page, then the total number of ways, there can be $500$ typos in those $500$ pages is the number of non negative integer tuple solutions to $$\sum_{k=1}^{500}x_k=500$$ Which can be easily seen to be $$\binom{999}{499}$$ Now the number of ways a particular page, say $i^{th}$ page contains $x_i=m$ typos is the number of non negative integer tuple solutions to $$\sum_{k=1}^{499}y_k=500-m$$ Which can be easily seen to be $$\binom{998-m}{498}$$ So the required probability is $$\frac{\sum_{m=0}^3\binom{998-m}{498}}{\binom{999}{499}}$$ Now finding the exact value is also quite tedious doing by hand.

I want a very elegant method to find the answer, that doesn't involve such calculations.

$\endgroup$
  • 2
    $\begingroup$ Number of misprints/typos in a page can be said to have a Poisson distribution when number of pages is large. $\endgroup$ – StubbornAtom Jan 7 '18 at 7:31
1
$\begingroup$

Unfortunately, as with many `real world' examples, before we can start to actually do any probabilistic calculations we have to determine what model we would like to use.

In this instance, before we pick a distribution for the problem, we would want to know more about how the typos occur. Consider the two following descriptions:

  1. The author of the book has told you that they deliberately put exactly 500 typos in, but not where they are.
  2. The author accidentally makes typos as they are writing the book, and at the end sees that the spell checker says that there are a total of 500.

I claim that you would want very different probability distributions to handle these two interpretations: even though they both represent the simpler question in the original post. One argument for this is: consider the scenario where every typo occurs on the first page.

If we were in scenario 1 (the author has deliberately planted typos) then we might say that this should have equal probability to any other distribution of the typos in the book.

In the second scenario, we would say that this is a highly unlikely scenario, as the typos are occurring by accident, and if there were so many typos on the first page, you'd expect a large number throughout (violating the maximum of 500).

In the below I will discuss three methods, and their limitations. Firstly I address the original posters approach, then a second similar method, and finally a very different method which addresses the second problem description above.

The model proposed in the original post

I generalize the set up and suppose that there are $n$ typos ($n=500$ in the original post), over $m$ pages ($m=500$ in the original).

In the original post, the model suggested is to consider each possible assignment $(x_1,\ldots,x_m)$ such that $\sum_{k=1}^m x_m =n$ as equally likely; therefore this is in line with the first proposed scenario.

In the form given in the post, it also assumes that the typos are indistinguishable from each other, which gives rise to the enumeration of exactly $\binom{n+m-1}{m-1}$ such vectors $\underline x$, see `stars and bars'. From which the assumed model is for all valid $\underline x$

\begin{align*} P(\underline x) &= \frac{1}{\# \left\{ (x_1,\ldots, x_m) \, \colon \, \sum_{k=1}^m x_k =n , \, x_k \in \mathbb{N}\right\}} \\ & = \frac1{\binom{n+m-1}{m-1}} \end{align*} The original poster then correctly identifies the probability that a given page (we'll consider page $1$ without loss of generality) contains exactly $j$ typos is:

\begin{align*} P(x_1 = j) & = P\left( \textstyle \sum_{k=2}^m x_k = n-j \right) \\ & = \frac{\# \left\{ (x_1,\ldots, x_{m-1}) \, \colon \, \sum_{k=1}^{m-1} x_k =n-j , \, x_k \in \mathbb{N}\right\}}{\# \left\{ (x_1,\ldots, x_m) \, \colon \, \sum_{k=1}^m x_k =n , \, x_k \in \mathbb{N}\right\}} \\ & = \frac{\binom{n-j + m-2}{m-2}}{\binom{n+m-1}{m-1}} \end{align*}

Unfortunately this binomial expression does not have a simple closed form, and does not describe a commonly used `stock' probability distribution. Therefore the chances of getting a nice closed form expression for $P(x_1 \leq t)$ for some $t \geq 0$ ($t = 3$ in the original post), is unlikely.

A second model for the same scenario

One question that arises from this approach is: why treat the typos as indistinguishable?

By this, I am referring to the fact that in enumerating the number of vectors $\underline x$ above, using stars and bars, we were answering the combinatorial question of: how many ways are there to put $n$ indistinguishable balls in $m$ boxes.

One could instead consider that each typo is distinguishable: i.e. in the scenario that the author had told us the typos are "nathematics", "qrobability", "slackexchange", etc.

This is another case of choosing how to interpret the question, and has to be decided by the user ahead of doing any calculations.

Since the typos are now distinguishable, the number of ways to distribute $n$ typos across $m$ pages is given by $m^n$. Moreover the equivalent probability distribution for $\underline x$ (with $x_k$ still the number of typos on page $k$) is now given a special case of the multinomial distribution:

$$P( x_1,\ldots, x_m) = m^{-n} \binom{n}{x_1,\ldots, x_m}. $$ This is a special case, as generally the distribution has additional paramters $p_1, \ldots, p_m$ which allow you to say that some pages are more likely to have typos than others.

Under this model, to find the probability that the first page has exactly $j$ errors: we first note that there are $\binom{n}{j}$ ways to pick the errors (since they are distinguishable), and that then the remaining $(n-j)$ are distributed across the remaining pages according to a multinomial distribution with $m-1$ pages. So we have

$$P(x_1 = j) = \binom{n}{j} \frac{(m-1)^{n-j}}{m^n}$$

Note that we can do a quick check to see that:

\begin{align*} \sum_{j=0}^n P(x_1 = j) & = \sum_{j=0}^n \binom{n}{j} \frac{(m-1)^{n-j}}{m^n} \\ & = m^{-n} \sum_{j=0}^n\binom{n}{j} (m-1)^{n-j}1^j \\ & = m^{-n} \big( (m-1) + 1 \big)^n \\ & = 1, \end{align*} as expected. Again, to get a closed form expression for the statement $P(x_1 \leq t)$, seems out of reach because (at least to my immediate knowledge) there is no way to take the partial sum of binomial coefficients in the above.

A model for the second scenario

Both models above have considered the case of the first scenario I described, where we assume that any distribution of errors is equally as likely.

A more realistic distribution might be to assume that each page should roughly have the same number of errors. This is in line with comment by @stubbornAtom, who mentions a Poisson distribution.

In this case we would say that each page has an independent number of errors, for us we'll assume this is Poisson distributed with some rate $\lambda$, so independently:

$$P(x_i = j) = e^{-\lambda} \frac{\lambda^j}{j!}$$

Now the information we have about the total number of errors should be used to form a conditional distribution. That is, we are interested in the probability

$$P(x_1 = j \, | \, \textstyle \sum_{k=1}^m x_k = n)$$

To compute this we need two things: Bayes rule, and the fact that sums of independent poisson variables are poisson, in particular if $x_1,\ldots, x_m \sim \text{Poi}(\lambda)$ then $\sum_{k=1}^m x_i \sim \text{Poi}(m \lambda)$.

So now:

\begin{align*} P(x_1 = j \, | \, \textstyle \sum_{k=1}^m x_k = n) & = \frac{P( \sum_{j=1}^m x_j = n\, | \, x_1 = j ) P(x_1 = j) }{ P(\sum_{j=1}^m x_j = n)} \\ & = \frac{P( \sum_{j=2}^m x_j = n-j ) P(x_1 = j)}{ P(\sum_{j=1}^m x_j = n)} \\ & = \frac{P_{(m-1)\lambda}(n-j) P_{\lambda}(j)}{P_{m\lambda}(n)} \end{align*} where in the last line I introduced the notation $P_\mu(k)$ to denote the probability that a Poisson $\mu$ variable is equal to $k$. Writing this in terms of the Poisson distribution function we have:

\begin{align*} P(x_1 = j \, | \, \textstyle \sum_{k=1}^m x_k = n) & = \frac{ e^{-(m-1)\lambda} \frac{((m-1)\lambda)^{n-j}}{(n-j)!} \times e^{-\lambda} \frac{\lambda^j}{j!}}{e^{-m\lambda} \frac{(m\lambda)^n}{n!}} \\ & = \binom{n}{j} \frac{(m-1)^{(n-j)}}{m^n}, \end{align*} which follows after some cancellations and rearranging.

Noteably, in the end we observe two things: the solution is independent of the Poisson parameter $\lambda$, and secondly that the solution returns the same value as the second method!

This in fact reflects a more general property that the individual summands of a sum of Poisson variables conditioned to equal $n$ is given by a multinomial distribution, see for instance here.

As such, in this model we still cannot expect to derive a closed form expression for $P(x_1 \leq t)$.

$\endgroup$
2
$\begingroup$

If we make the assumption that the 500 typos are independently and identically uniformly distributed over the 500 pages, then we have a "balls in boxes" style problem.

The count of typos on a particular page would therefore be binomially distributed, with parameters: $n=500$, $p=1/500$ .

$\endgroup$
  • $\begingroup$ But if you know the total number of typos in the first $499$ pages to be $x$, then the number of typos in the last page is automatically fixed to be $500-x$, so I don't think we can just assume they are independent. $\endgroup$ – Abishanka Saha Jan 7 '18 at 7:50
  • $\begingroup$ Also this approximation doesn't make the calculation any easier. $\endgroup$ – Abishanka Saha Jan 7 '18 at 7:51
  • $\begingroup$ The problem does not state there are $x$ typos in the first 499 pages; only that there are 500 typos somewhere in 500 pages. Also the calculation is quite simple. $\endgroup$ – Graham Kemp Jan 8 '18 at 2:28
1
$\begingroup$

As mentioned by others the simplest model is to assume a Poisson distribution for the number of typos on individual pages. The Poisson distribution is an approximation to the binomial distribution at the left end of the Gauss curve, valid for "rare events". Note that one typo per page means one typo per ca. 2000 keystrokes.

Since there is on average one typo per page the Poisson parameter $\lambda$ has value $1$ in our case. According to the "Poisson philosophy" the probability for exactly $r\geq0$ typos on a page is given by $\>{1\over r!}e^{-1}$. It follows that the probability for $\leq3$ typos on a given page comes to $$\left({1\over1}+{1\over1}+{1\over2}+{1\over6}\right){1\over e}={8\over3e}=98.1\%\ .$$

$\endgroup$
  • $\begingroup$ In the question it is stated that there are 500 errors. The solution above does not achieve this hard constraint: i.e. that the Poisson variables have to be conditioned to sum to 500.So I don't think this answers the poster's question. The case where the variables are conditioned to sum to 500 is covered in my solution. $\endgroup$ – owen88 Jan 7 '18 at 14:49
  • $\begingroup$ @owen88: What is the numerical value resulting in the exact treatment? $\endgroup$ – Christian Blatter Jan 7 '18 at 15:23
  • $\begingroup$ I'm aware that this gives an approximation (in this case, correct to the third significant figure): my point is simply that I don't think it is clear from your answer that this is an approximation only, and not an exact solution (in particular since you use the wording "it follows that the probability for $\leq 3$ typos on a given page comes to...". Further, there is no indication of generally how good an approximation this is. $\endgroup$ – owen88 Jan 7 '18 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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