Kaboobly Cannon

Relevant wiki: Conditional Probability - Problem Solving

If $p_{n,k}$ is the probability that $k$ hits have been obtained after $n+1$ shots, then $p_{1,0} = p_{1,2} = 0$ and $p_{1,1} = 1$ . If $n \ge 1$ then standard conditional probability considerations give $\begin{array}{rcl} p_{n+1,k} & = & p_{n,k} P[(n+2)^{nd} \mbox{ shot a miss}\, \vert \,k \mbox{ hits so far}] + p_{n,k-1} P[(n+2)^{nd} \mbox{ shot a hit}\,\vert\, k-1 \mbox{ hits so far}] \\ & = & \dfrac{n+1 - k}{n+1}p_{n,k} +\dfrac{k-1}{n+1} p_{n,k-1} \end{array}$ for all $1 \le k \le n+1$ , while $p_{n+1,0} = p_{n+1,n+1} = 0$ .

A simple induction on $n$ shows that $p_{n,k} \; = \; \left\{ \begin{array}{lcl} \dfrac{1}{n} & \qquad & 1 \le k \le n \;, \\ 0 & \qquad & k = 0,n+1 \end{array} \right.$ To answer the question, we need $p_{99,50} = \dfrac{1}{99}$ .

This is an alternative representation of a very familiar problem --- that of Polya's Urn . In that model, we start with an urn containing $1$ black ball and $1$ white ball. Every second, a ball is chosen from the urn at random, and then returned, together with a second ball of the same colour. Polya's urn exhibits a number of interesting properties, and therefore so does the Kaboobly cannon.

The probability distribution of the number of hits achieved after $n+1$ shots is (ignoring the impossible $0, n+1$ options) is uniform. However, the proportion $P_n$ of hits after $n$ shots defines a random variable, and this sequence $P_n$ of random variables has a delicate property which makes it what is called a martingale (with respect to itself). This has the consequence that the sequence of random variables $P_n$ converges, with probability $1$ , to a limit. The value of that limit is a continuous random variable which is uniformly distributed over $(0,1)$ .

Thus every Kaboobly cannon will end up hitting the target a fixed proportion of times, but every cannon will have a different success rate, and all success rates are equally likely!

See this solution I wrote for a similar problem.