# Generalizing the German Tank Problem

Anthony Lee<EMAIL_ADDRESS>Milton Academy, Milton, MA 02186  and
Steven J. Miller<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Mathematics and Statistics, Williams College, Williamstown, MA
01267

###### Abstract.

The German Tank Problem dates back to World War II when the Allies used a
statistical approach to estimate the number of enemy tanks produced or on the
field from observed serial numbers after battles. Assuming that the tanks are
labeled consecutively starting from 1, if we observe $k$ tanks from a total of
$N$ tanks with the maximum observed tank being $m$, then the best estimate for
$N$ is $m(1+1/k)-1$. We explore many generalizations. First, we looked at the
discrete and continuous one dimensional case. We attempted to improve the
original formula by using different estimators such as the second largest and
$L\textsuperscript{{\rm th}}$ largest tank, and applied motivation from
portfolio theory by seeing if a weighted average of different estimators would
produce less variance; however, the original formula, using the largest tank
proved to be the best; the continuous case was similar. Then, we attempted to
generalize the problem into two dimensions, where we pick pairs instead of
points. We looked at the discrete and continuous square and circle variants.
There were more complications, as we dealt with problems in geometry and
number theory, such as dealing with curvature issues in the circle, and the
problem that not every number is representable as a sum of two squares. In
some cases, we concentrated on the large $N$ limit (with fixed $k$) by
deriving approximate formulas. For the discrete and continuous square, we
tested various statistics, but found that the largest observed component of
our pairs is the best statistic to look at; the scaling factor for both cases
is $(2k+1)/2k$. For the circle we used motivation from the equation of a
circle; for the continuous case, we looked at $\sqrt{X^{2}+Y^{2}}$ and for the
discrete case, we looked at $X^{2}+Y^{2}$ and took a square root at the end to
estimate for $r$. The discrete case was especially involved because we had to
use approximation formulas that gave us the number of lattice points inside
the circle. Interestingly, the scaling factors were different for the cases.
Lastly, we generalized the problem into $L$ dimensional squares and circles.
The discrete and continuous square proved similar to the two dimensional
square problem. However, for the $L\textsuperscript{{\rm th}}$ dimensional
circle, we had to use formulas for the volume of the $L$-ball, and had to
approximate the number of lattice points inside it. The formulas for the
discrete circle were particularly interesting, as there was no $L$ dependence
in the formula.

###### Key words and phrases:

German Tank Problem, Uniform Distribution, Discrete setting, Continuous
setting

###### 2010 Mathematics Subject Classification:

60B10, 11B39, 11B05 (primary) 65Q30 (secondary)

###### 2010 Mathematics Subject Classification:

62J05, 60C05 (primary), 05A10 (secondary)

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Probability Review
    2. 2.2 Analysis Review
    3. 2.3 Combinatorial Results
  3. 3 Derivation of Original German Tank Problem
    1. 3.0.1 The PDF of the Largest Observed Tank
    2. 3.0.2 Derivation
  4. 4 Estimating with more tanks
    1. 4.1 Estimation from Various Tanks
      1. 4.1.1 Variance of $M_{k}$
    2. 4.2 Weighted Statistic
      1. 4.2.1 Covariance term
      2. 4.2.2 Finding optimal alpha
  5. 5 Continuous One Dimensional Problem
    1. 5.1 Formulas Using Largest and Second Largest Observations.
      1. 5.1.1 Formula from Largest
      2. 5.1.2 Formula using Second Largest
    2. 5.2 Continuous weighted formula
  6. 6 Two Dimensional Discrete Generalizations
    1. 6.1 Square Problem
      1. 6.1.1 Maximum from Lists:
      2. 6.1.2 Comparing Formulas
      3. 6.1.3 Recursive Argument:
      4. 6.1.4 Continuous Square Problem
    2. 6.2 Circle Problem
      1. 6.2.1 Discrete Circle Problem
      2. 6.2.2 Continuous Circle Problem
  7. 7 Higher Dimension Version
    1. 7.1 Generalized Square Problem
      1. 7.1.1 Discrete Square Problem:
      2. 7.1.2 Continuous Square Problem:
    2. 7.2 Generalized Circle Problem
      1. 7.2.1 Discrete Circle Problem
      2. 7.2.2 Continuous $L$-dimensional circle problem
  8. 8 Acknowledgements
  9. A Basic Probability Review
    1. A.1 Variance and Covariance
    2. A.2 Identities from Pascal’s Triangle
  10. B Portfolio Theory
  11. C Proof of Identities
  12. D Calculations
    1. D.1 Formula for $L\textsuperscript{th}$ largest tank
    2. D.2 Variance calculation for $m_{k-1}$ in discrete one dimensional case
    3. D.3 Continuous Weighted Problem
      1. D.3.1 Formulas using $m_{k}$ and $m_{k-1}$
      2. D.3.2 Variance of $m_{k}$ and $m_{k-1}$
      3. D.3.3 Covariance term
      4. D.3.4 Finding optimal alpha
  13. E Mathematica Code

##  1\. Introduction

We study a problem where we are given some information about observations, and
we have to estimate the number of objects. The motivation comes from the
German Tank problem, a classic problem in probability. During World War II,
Germans used powerful tanks to their advantage. To develop appropriate
military strategies against the Germans, the Allies had to estimate the number
of tanks produced on various battlefields. Initially, spies were used to
figure out the number of tanks. However, using statistics to estimate the
number of tanks proved to be much more accurate; see [Ka] for a history of the
problem. During battles, the Allies realized that the destroyed or captured
tanks had serial numbers and that they could reverse engineer and use these to
their advantage. Assuming that the serial numbers are consecutive111It is
convenient to have the numbers in order; by looking at the serial number one
can often quickly tell when it was made and thus when it may need certain
types of repairs. However, as the previous work shows, this opens one up to
disclosing more information than one would like, and in many applications now
companies use formulas to determine the serial numbers, masking information.
and started from 1, the statisticians came up with a formula using the largest
observed tank $m_{k}$ and the number of tanks observed $k$ to make a estimate
for $N$, which we denote $\mathaccent 866{N}$:

$\displaystyle\mathaccent 866{N}\ =\ m_{k}\bigg{(}1+\frac{1}{k}\bigg{)}\ -\
1.$ (1.1)

This formula proved to be very effective. A comparison between the actual and
estimated production rate of tanks from [Al] shows how accurate this formula
was: while the intelligence estimated that Germans were producing 1,400 tanks
per month, using the formula, the statisticians estimated that Germans were
producing 256 tanks per month, and indeed, 255 tanks were made! The chart
below compares the estimation from the statistical method and intelligence to
the actual number of German Tanks [Ru].

Figure 1. Statistics vs Intelligence.

We see that the statistical estimate is reasonably similar to the German
records. However, the intelligence estimate is very off from the actual number
of tanks. Had the Allies used the intelligence estimate, their strategy would
have mislead them as they would have overly prepared defense to minimize
damage from tanks, which could have left them vulnerable to other attacks.
However, the statistical estimate provided them with reasonable estimates.

The German Tank problem is an excellent example of how statistical inference
can be applied to real world problems. We attempt to generalize the well known
German Tank Problem. Previously, Clark, Gonye, and Miller [CGM] derived a more
general formula where the smallest serial number isn’t 1, but the tanks are
still numbered consecutively. If the spread between the smallest and largest
serial number is $s$, then their formula to estimate the number of tanks is

$\displaystyle\mathaccent 866{N}\ =\ s\bigg{(}1+\frac{2}{k-1}\bigg{)}\ -\ 1.$
(1.2)

We start by recalling the derivation of the original German tank problem, as
we will be extending those calculations. We then see if we can improve the one
dimensional formula by looking at different estimators and using motivation
from portfolio theory in financial mathematics, specifically looking at
weighted sums of estimators to see if we can find a new statistic that has the
same mean of its predictions but smaller variance; see Appendix B for a review
of portfolio theory and the construction of such statistics. However, we find
that the original German tank formula does better than formulas from these two
approaches. We use code to check, and it is attached in Appendix E.

Generalizing further, we looked at what would happen if we modified some of
the assumptions of the problem. First, we modified the condition that all
serial numbers are consecutive integers and we looked at the standard German
Tank Problem in the continuous setting. The problem changed slightly as we
sample $k$ tanks from the range of $0$ to $N$, but the tanks can be real
numbers. To find the answer of the question of finding the best estimator for
$N$, we tried various statistics, starting with some obvious choices such as
the largest observed tank, the second largest observed tank, and the weighted
sum. Interestingly, the continuous case turned out to be very similar to the
discrete case, as the best statistic to look at in the continuous case was the
largest observed tank, as it produced a formula with the least variance.
Furthermore, the scaling factor for the discrete and continuous case were both
$(k+1)/k$, which shows the similarity between the two cases. The main
conclusion here was that even in the continuous case, the largest observed
tank is the best statistic to study.

Moving on from the one dimensional case, we generalized the German Tank
problem further into two dimensions. In the two dimensional case, we select
pairs instead of points, and the main condition is that we select $k$ pairs
without replacement. Specifically, we looked at the square and circle, as we
have explicit closed form and asymptotic expressions for the area and number
of lattice points inside. The main strategy of deriving formulas was using the
CDF method for the discrete and continuous case. (See Lemma 2.7 for details)
Starting from the two dimensional case, we see geometry being involved in the
calculations. For the discrete square, we looked at the square with bottom
left vertex at $(1,1)$ and upper right vertex at $(N,N)$ and looked at the
number of lattice points inside the square. From inspiration from the one
dimensional problem, we looked at the largest observed component.
Unfortunately, because the closed form expressions that we get are very
complex, which makes it difficult to invert, we approximate by focusing on the
main term and sometimes second order, as that’s enough to get a pretty good
approximation of what’s going on. Thus, for the discrete square, we provide a
approximate formula that still does a very good job estimating. The continuous
square problem was much easier as calculating integrals was easier than
calculating sums. We set the bottom left vertex as $(0,0)$ and the upper right
vertex as $(N,N)$. We also looked at the largest observed component for this
case too. However, instead of looking at the number of lattice points as we
did in the discrete case, we looked at the area, which was much easier.
Interestingly, the scaling factor for both the discrete and continuous square
was the same, and we state both formulas.

$\displaystyle{\rm\textbf{Discrete Square}:}\ \mathaccent 866{N}\ =\
\frac{2k+1}{2k}(m-1)\ \ \ \ {\rm\textbf{Continuous Square}:}\ \mathaccent
866{N}\ =\ \frac{2k+1}{2k}\cdot m.$ (1.3)

After looking at the square problem in the discrete and continuous case, we
looked at the circle problem. For both the discrete and continuous cases, we
set the circle so that it’s center was at $(0,0)$ and that it had radius $r$.
The statistics we looked at the for the discrete and continuous cases were
different. For the continuous case, we looked at the largest observed value of
$m_{2}=\sqrt{X^{2}+Y^{2}}$. The motivation comes from the standard form
equation of the circle, which is $(x-x_{1})^{2}+(y-y_{1})^{2}=r^{2}$ where
$(x,y)$ are the arbitrary coordinates on the circumference of the circle, $r$
is the radius of the circle, and $(x_{1},y_{1})$ are the coordinates of the
center of the circle. We used the CDF method with areas to calculate the
formula.

Before we look at the discrete case, we see that we need to know the number of
lattice points inside a circle with center $(0,0)$ and radius $r$. We visit
the classic Gauss Circle problem and use the approximations and denote the
error term using Big O notation to denote the number of lattice points inside
the circle. To solve the discrete case, we looked at various statistics.
First, we looked at the largest observed component, as we were able to obtain
nice formulas in the square problem using the largest observed component.
However, we faced problem of curvature because we had to split the ranges of
the side of the square to see if the square completely fit in a circle or not.
Thus, we decided that this isn’t the best statistic to look at. We wanted to
look at a statistic similar to $\sqrt{X^{2}+Y^{2}}$, the formula for the
radius of the circle, but we had to make sure that the statistic that we were
studying gave only discrete values as outcomes. Therefore, we chose to look at
$m_{1}=X^{2}+Y^{2}$ as all values of $m$ are integers. At the end, we have to
take the square root of $m$ because now, we are essentially estimating for
$m^{2}$. Another complication that arises in this problem is that
$X^{2}+Y^{2}\equiv 0,1,2$ (mod 4). We explain more about the number theory
complication when we derive the formula. Also, because we used a asymptotic
formula for the number of lattice points inside the circle, we weren’t able to
produce a exact formula, but we produce one that still gives accurate
estimations. We see that the discrete and continuous formula is different, and
we explain more details in Remark 6.4.

$\displaystyle{\rm\textbf{Discrete Circle}:}\ \mathaccent 866{r}\ =\
\sqrt{\frac{k+1}{k}(m_{1}-1)}.\ \ \ \ \ {\rm\textbf{Continuous Circle}:}\
\mathaccent 866{r}\ =\ \frac{2k+1}{2k}\cdot m_{2}.$ (1.4)

Finally, we generalized the problem into higher dimensions, $L$ dimensions. We
looked at the $L^{\rm th}$ dimensional square and the $L^{\rm th}$ dimensional
sphere, also known as the $L$-ball in the continuous and discrete setting. The
problem changes slightly as we are selecting $k$ tuples of length $L$ without
replacement. For the discrete and continuous $L^{\rm th}$ dimensional square
cases, we looked at the largest observed component value from the tuples and
derived the formulas. For the continuous $L^{\rm th}$ dimensional square, we
obtained a exact formula, but for the discrete $L^{\rm th}$ dimensional
square, we approximated the result using the main term. We see that the
scaling factors for the discrete and continuous setting are the the same.

$\displaystyle{\rm\textbf{Discrete L-dim Square}:}\ \mathaccent 866{N}\ =\
\frac{Lk+1}{Lk}(m-1).\ {\rm\textbf{Continuous L-dim Square}:}\ \mathaccent
866{N}\ =\ \frac{Lk+1}{Lk}\cdot m.$ (1.5)

The difficulty is calculating the number of lattice points inside the
$L$-ball. We use the known formula about the volume of the $L$-ball, and use
this formula to estimate how many lattice points are contained inside using
Big-O notation. Now, we look at various statistics. For our statistic in the
discrete case, we looked at $m_{1}=X_{1}^{2}+X_{2}^{2}+\dots+X_{L}^{2}$, as
this statistic guarantees that all $m$ values are discrete. Then after
estimating, we took the square root of $m$ to find the estimate for $r$. For
the continuous case, we looked at
$m_{2}=\sqrt{X_{1}^{2}+X_{2}^{2}+\cdots+X_{L}^{2}}$ as we are allowed to get
real numbers for $m$ values. The continuous $L$-ball problem was easier, as we
could plug in the equation for the $L$-ball to get the volume instead of
having to estimate the number of lattice points. We state the formulas we
derived:

$\displaystyle{\rm\textbf{Discrete L-ball}:}\ \mathaccent 866{r}\ =\
\sqrt{\frac{k+1}{k}\cdot(m_{1}-1)}.\ {\rm\textbf{Continuous L-ball}:}\
\mathaccent 866{r}\ =\ \frac{Lk+1}{Lk}\cdot m_{2}.$ (1.6)

##  2\. Preliminaries

We quickly review some needed results from probability, combinatorics, and
integration.

###  2.1. Probability Review

We list a few standard results from probability; for proofs see for example
[Mi, Sh].

######  Definition 2.1.

The variance for a random variable $X$ is the average of the squared
difference from the mean, $\mathbb{E}[X]$:

$\displaystyle{\rm Var}(X)\ :=\ \mathbb{E}[(X-\mathbb{E}[X])^{2}].$ (2.1)

######  Lemma 2.2.

The variance can be computed by

$\displaystyle{\rm Var}(X)\ =\ \mathbb{E}[X^{2}]\ -\ \mathbb{E}[X]^{2}.$ (2.2)

See Lemma A.1 in Appendix A for a proof.

######  Definition 2.3.

For two jointly distributed real valued random variables $X$ and $Y$, the
covariance is defined as the expected value of the product of their deviations
from their individual expected values:

$\displaystyle{\rm Cov}(X,Y)\ :=\
\mathbb{E}\left[\left(X-\mathbb{E}[X]\right)\cdot\left(Y-\mathbb{E}[Y]\right)\right].$
(2.3)

######  Lemma 2.4.

The covariance can be computed by

$\displaystyle{\rm Cov}(X,Y)\ =\ \mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y].$
(2.4)

See Lemma A.2 in Appendix A for a proof.

######  Theorem 2.5.

(Linearity of expectation) Let $X_{1},\dots,X_{n}$ be random variables, and
let $g_{1},\dots,g_{n}$ be functions such that $\mathbb{E}[|g_{i}(X_{i})|]$
exists and is finite, and let $a_{1},\dots,a_{n}$ be any real numbers; note
the random variables do not have to be independent. Then

$\displaystyle\mathbb{E}\left[a_{1}g_{1}(X_{1})+\dots+a_{n}g_{n}(X_{n})\right]\
=\ a_{1}\mathbb{E}[g_{1}(X_{1})]+\cdots+a_{n}\mathbb{E}[g_{n}(X_{n})].$ (2.5)

######  Theorem 2.6.

(Joint Probability Density Function) Let $X_{1},X_{2},\dots,X_{n}$ be
continuous random variables with densities
$f_{X_{1}},f_{X_{2}},\dots,f_{X_{n}}$ defined on $\mathbb{R}$. The joint
density function of the tuple $(X_{1},\dots,X_{n})$ is a non-negative
integrable function $f_{X_{1},X_{2},\dots,X_{n}}$ such that for every nice set
$S\subset\mathbb{R}^{n}$ we have

$\displaystyle{\rm Prob}((X_{1},\dots,X_{n})\in S)\ =\
\idotsint_{S}f_{X_{1},X_{2},\dots,X_{n}}(x_{1},\dots,x_{n})\,dx_{1}\cdots
dx_{n},$ (2.6)

and

$\displaystyle f_{X_{i}}(x_{i})\ =\
\int_{x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n}=-\infty}^{\infty}f_{X_{1},X_{2},\dots,X_{n}}(x_{1},\dots,x_{n})dx_{1}\cdots
dx_{i-1}dx_{i+1}\cdots dx_{n}.$ (2.7)

For discrete random variables, we can just replace integrals with sums.

######  Definition 2.7.

The cumulative distribution function (CDF) of a random variable $X$ with
density $f$, denoted $F$, is given by

$\displaystyle F(x)\ :=\ {\rm Prob}(X\leq x)\ =\ \int_{-\infty}^{x}f(t)\,dt,\
{\rm for\ any}\ x\in\mathbb{R}.$ (2.8)

In many situations it is easy to compute the CDF, and thus by using the
Fundamental Theorem of Calculus we can determine the probability density
function. In the continuous case it is the derivative of the CDF, in the
discrete case when the values of our random variable are non-negative
integers, then the probability of $m$ is $F(m)-F(m-1)$.

###  2.2. Analysis Review

Unfortunately many of the sums we encounter are very complex and difficult to
invert when expressed in a closed form, and thus we estimate using the main
term and the second order. The following frequently provides a good, easily
computed bound; see for example [YK].

######  Theorem 2.8.

(Euler-Maclaurin formula) For $p$ a positive integer and a function $f(x)$
that is $p$ times continuously differentiable on the interval $[a,b]$, we have

$\displaystyle\sum_{i=a}^{b}f(i)$ $\displaystyle\ =\ $
$\displaystyle\int_{a}^{b}f(x)\,dx+\frac{f(a)+f(b)}{2}\ +\
\sum_{q=1}^{\lfloor\frac{p}{2}\rfloor}\frac{B_{2q}}{(2q)!}(f^{2q-1}(b)-f^{2q-1}(a))+R_{p},$
(2.9)

and

$\displaystyle|R_{p}|\ \leq\
\frac{2\zeta(p)}{(2\pi)^{p}}\int_{m}^{n}|f^{(p)}(x)|\,dx.$ (2.10)

The estimation below is needed in computing upper and lower bounds in
applications of the Euler-Maclaurin formula later.

######  Lemma 2.9.

For $m,L\geq 0$ and $k\geq 1$,

$\displaystyle\bigg{(}m^{Lk}-m^{Lk-L}\bigg{(}\frac{k(k-1)}{2}\bigg{)}\bigg{)}\
\leq\ m^{L}(m^{L}-1)\cdots(m^{L}-(k-1)\leq m^{Lk}.$ (2.11)

###### Proof.

The upper bound follow trivially as

$\displaystyle m^{L}(m^{L}-1)\cdots(m^{L}-(k-1))\ \leq\
(m^{L})(m^{L})\cdots(m^{L}).$ (2.12)

To justify the lower bound, we want to prove the inequality

$\displaystyle m^{L}(m^{L}-1)\cdots(m^{L}-(r-1))\ \geq\
m^{Lr}-\frac{r(r-1)}{2}m^{Lr-L}.$ (2.13)

The base case is satisfied when $r=1$ as $m^{2}\ \geq\ m^{2}$. We assume that
the case when $r=k$ is true:

$\displaystyle m^{L}(m^{L}-1)\cdots(m^{L}-(k-1))\ \geq\
m^{Lk}-\frac{k(k-1)}{2}m^{Lk-L}.$ (2.14)

We must show it holds when $r=k+1$; namely we must show

$\displaystyle m^{L}(m^{L}-1)\cdots(m^{L}-k)\ \geq\ m^{Lk+L}\ -\
\frac{(k+1)k}{2}m^{Lk}.$ (2.15)

This follows immediately by substitution and expansion:

$\displaystyle m^{L}(m^{L}-1)\cdots(m^{L}-(k-1))(m^{L}-k)$ $\displaystyle\
\geq\ $
$\displaystyle\bigg{(}m^{Lk}-\frac{k(k-1)}{2}m^{Lk-L}\bigg{)}(m^{L}-k)$ (2.16)
$\displaystyle\geq$ $\displaystyle m^{Lk+L}\ -\ \frac{k(k+1)}{2}m^{Lk}\ +\
\frac{k^{2}(k-2)}{2}m^{Lk-L}$ $\displaystyle\geq$ $\displaystyle m^{Lk+L}\ -\
\frac{k(k+1)}{2}m^{Lk}.$

∎

Finally, in many of our generalizations it is impossible to obtain simple
closed form expressions such as those in the original problem. We thus
investigate the large $N$ limit, and big-Oh notation is useful in isolating
the main term from lower order terms which have negligible effect.

######  Definition 2.10.

(Big-Oh Notation) Suppose $f(x)$ and $g(x)$ are two functions defined on the
real numbers. We write $f(x)=O(g(x))$ (read “$f$ is Big-Oh of $g$”) if there
exists a positive constant $C$ such that $|f(x)|\leq Cg(x)$ is satisfied for
all sufficiently large $x$.

###  2.3. Combinatorial Results

We list four useful identities that are needed in later calculations. These
are generalizations of the famous hockey stick identity from Pascal’s
triangle; that identity is responsible for the closed form expression in the
original problem, and these identities play a similar role in our
generalizations. The proofs for these identities can be found in the Appendix
C.

Identity I: For all $N\geq k$,

$\displaystyle\sum_{m=k}^{N}\binom{m-b}{k-c}$ $\displaystyle\ =\ $
$\displaystyle\binom{N-b+1}{k-c+1}\ -\ \binom{k-b}{k-c+1}.$ (2.17)

Identity II: For all $N\geq k$,

$\displaystyle\sum_{m=k-a+1}^{N-a+1}m\frac{\binom{m-1}{k-a}\binom{N-m}{a-1}}{\binom{N}{k}}$
$\displaystyle\ =\ $ $\displaystyle\frac{(N+1)(k-a+1)}{k+1}.$ (2.18)

Identity III: For all $N\geq k$,

$\displaystyle\sum_{m=k-a+1}^{N-a+1}m^{2}\frac{\binom{m-1}{k-a}\binom{N-m}{a-1}}{\binom{N}{k}}$
$\displaystyle\ =\ $
$\displaystyle\frac{(k-a+1)(k-a+2)(N+2)(N+1)}{(k+2)(k+1)}$ (2.19)
$\displaystyle\ \ \ \ -\ \frac{(N+1)(k-a+1)}{k+1}.$

Identity IV: For all $k\geq 0$,

$\displaystyle\sum_{i=0}^{k}\binom{a+i}{a}\binom{b+k-i}{b}\ =\
\binom{a+b+k+1}{a+b+1}.$ (2.20)

##  3\. Derivation of Original German Tank Problem

We derive below the formula for the original German tank problem where $m$
represents the largest tank observed, $k$ the number of tanks observed, and
$N$ the number of tanks (which are numbered consecutively from 1 to $N$). We
use $\mathaccent 866{N}$ to represent our estimate for the total number of
tanks, $N$. It is useful to run through this argument before we generalize the
inference problem, and we follow the exposition in [CGM]. We prove

$\displaystyle\mathaccent 866{N}\ =\ m_{k}\bigg{(}1+\frac{1}{k}\bigg{)}\ -\
1.$ (3.1)

We quickly check some extreme cases to see if this formula is reasonable. When
we observe just one tank, the estimation formula is $2m-1$. We expect the
observation to be $N/2$, so multiplying by 2 is reasonable. When we observe
all $N$ tanks (so $k=N$), the estimation is just $m$, which is also reasonable
because we know the number all the tanks. We use Pascal’s identity and the
hockey stick identity frequently in calculations; see Appendix A for proofs.

####  3.0.1. The PDF of the Largest Observed Tank

Let $M_{k}$ be the random variable for the largest tank observed, and let
$m_{k}$ be its observed value. Thus $m_{k}$ is the largest tank serial number
that we observe. Our goal is to find a formula to estimate $N$ from $m_{k}$
and $k$. We first compute the PDF for $M_{k}$.

######  Lemma 3.1.

For $k\leq m_{k}\leq n$,

$\displaystyle{\rm Prob}(M=m_{k})\ =\
\frac{\binom{m_{k}-1}{k-1}}{\binom{N}{k}}.$ (3.2)

###### Proof.

We know that the total number of ways to select $k$ tanks from $N$ possible
tanks is $\binom{N}{k}$. If the largest tank we observe is $m$, then we have
to choose $k-1$ tanks from $m_{k}-1$ possibilities. Therefore, the probability
that the largest tank we observe is $m$ is
$\binom{m_{k}-1}{k-1}/\binom{N}{k}$, thus proving the claim. ∎

######  Remark 3.2.

It is worth remarking that the process of deriving the formula is different
from the application. In the application, we use tanks we observe,
$m_{1},m_{2},\dots,m_{k}$ and estimate for $N$ by applying the formula.
However, when we are deriving the formula, we use $N$ and $k$ to compute the
expected value of $M_{k}$, and then we invert the equation to find the formula
for $N$.

####  3.0.2. Derivation

Now we calculate the expected value of $M_{K}$ in order to find a equation
with $N$ and $k$. To calculate the expected value, we multiply each value of
the random variable by its probability and add the products. We expand the
binomials, and regroup so that we can use the hockey stick identity. We find

$\displaystyle\mathbb{E}[M_{k}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{k}=k}^{N}m_{k}{\rm Prob}(M_{k}=m_{k})$ (3.3)
$\displaystyle=$
$\displaystyle\sum_{m_{k}=k}^{N}m_{k}\frac{\binom{m_{k}-1}{k-1}}{\binom{N}{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m_{k}=k}^{N}\frac{m_{k}!}{(k-1)!(m_{k}-k)!}\frac{k}{k}$
$\displaystyle=$
$\displaystyle\frac{k}{\binom{N}{k}}\sum_{m_{k}=k}^{N}\frac{m_{k}!}{(k)!(m_{k}-k)!}$
$\displaystyle=$
$\displaystyle\frac{k}{\binom{N}{k}}\sum_{m_{k}=k}^{N}\binom{m_{k}}{k}$
$\displaystyle{\rm We\ use\ the\ hockey\ stick\ identity,\ recall\ Lemma\
\ref{lem:fourhockeystickidentity},\ to\ evaluate\ the\ sum}$ $\displaystyle=$
$\displaystyle\frac{k}{\binom{N}{k}}\binom{N+1}{k+1}$ $\displaystyle=$
$\displaystyle k\Bigg{(}\frac{N+1}{k+1}\Bigg{)}.$

Using our formula for $M_{k}$ as a function of $N$ and $k$, we can invert and
obtain the formula for $N$ in terms of $M_{k}$ and $k$:

$\displaystyle\mathaccent 866{N}\ =\
\mathbb{E}[M_{k}]\Bigg{(}\frac{k+1}{k}\Bigg{)}\ -\ 1.$ (3.4)

To obtain our estimate $\mathaccent 866{N}$ we substitute the observed $m_{k}$
for $\mathbb{E}[M_{k}]$:

$\displaystyle\mathaccent 866{N}\ =\ m_{k}\Bigg{(}\frac{k+1}{k}\Bigg{)}\ -\
1.$ (3.5)

To see how well this formula does, we paste results of code. We see the mean
and variance when we plug in values of $N$ and $k$.

Figure 2. Results for formula using largest tank.

##  4\. Estimating with more tanks

There are two natural approaches to try to improve the our prediction for the
original problem. One is to find another estimator; perhaps the mean or median
might do better. We pursue this and investigate statistics derived from the
$L\textsuperscript{{\rm th}}$ largest tank, value does better.

Another approach is to use some motivation from portfolio theory; see for
example [H]. Imagine we have two independent stocks with the same expected
return. By looking at a linear combination, the combined portfolio will still
have the same expected return, but if the weights are chosen properly a
smaller variance; we provide details in Appendix B. The idea of weighing two
random variables to create a combined one with less variance is a common
method, and we apply that to our problem to see if we can improve the quality
of the estimator for the German tank problem by looking at a combination of
two tanks. The computation is a bit more involved than the two stock example,
as the values of the two tanks are not independent; if we know the largest
tank value is $m_{k}$ then clearly $m_{k-1}<m_{k}$. We provide complete
details of the analysis of exploring statistics involving the two largest
observed serial numbers, and find that the quality of the estimator is _not_
improved by incorporating both values.

###  4.1. Estimation from Various Tanks

Let $M_{k-1}$ be the random variable for the value of the second largest tank
observed and let $m_{k-1}$ be the value we observe. We find the probability
that the second largest tank is $m_{k-1}.$ We claim that for $k-1\leq
m_{k-1}\leq n-1$, the probability that $M_{k-1}=m_{k-1}$ is

$\displaystyle{\rm Prob}(M_{k-1}=m_{k-1})\ =\
\frac{\binom{m_{k-1}-1}{k-2}\binom{N-m_{k-1}}{1}}{\binom{N}{k}}.$ (4.1)

Clearly the probability is zero for tanks outside this range. There are
$\binom{N}{k}$ ways to choose $k$ tanks from $N$. We need $k-2$ tanks to be
smaller than $m_{k-1}-1$; there are $\binom{m_{k-1}-1}{k-2}$ ways for that to
happen. We then have to choose tank $m_{k}$, which has to be larger than tank
$m_{k-1}$. Thus, the range from $m_{k}$ goes from $m_{k-1}+1$ to $N$, and
there are $\binom{N-m_{k-1}}{1}$ ways to do this. $\Box$

We can now calculate the expected value of $M_{k-1}$:

$\displaystyle\mathbb{E}[M_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}{\rm Prob}(M_{k-1}\ =\ m_{k-1})$
(4.2) $\displaystyle=$
$\displaystyle\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}\frac{\binom{m_{k-1}-1}{k-2}(N-m_{k-1})}{\binom{N}{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{k-1}{k-1}\frac{m_{k-1}!}{(k-2)!(m_{k-1}-k+1)!}(N-m_{k-1})$
$\displaystyle=$
$\displaystyle\frac{k-1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{m_{k-1}!}{(k-1)!(m_{k-1}-k+1)!}(N-m_{k-1})$
$\displaystyle=$
$\displaystyle\frac{k-1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\binom{m_{k-1}}{k-1}\binom{N-m_{k-1}}{1}$
$\displaystyle{\rm We\ use\ Identity\ IV}$ $\displaystyle=$
$\displaystyle\frac{k-1}{\binom{N}{k}}\binom{N+1}{k+1}$ $\displaystyle=$
$\displaystyle(N+1)\frac{k-1}{k+1}.$

Therefore, the formula for our estimator of $N$, in terms of $m$ and $k$,
coming from $M_{k-1}$ is

$\displaystyle\mathaccent 866{N}\ =\ m_{k-1}\frac{k+1}{k-1}\ -\ 1.$ (4.3)

We attach some code to see the mean and variances of the formula using the
second largest tank.

Figure 3. Results for formula using second largest tank.

######  Remark 4.1.

Comparing this result to the variance of the formula using the largest tank,
we see that the formula using the second largest tank has higher variance.
Later, we confirm this finding by theory, and not just by code.

Calculating similarly, we obtain the formula for the $L\textsuperscript{th}$
largest tank (see Appendix D for details):

$\displaystyle\mathaccent 866{N}\ =\ m_{k-L+1}\frac{k+1}{k-L+1}\ -\ 1.$ (4.4)

We calculate the variances for statistics arising from the different tank
(from largest observed to smallest); we scale each of these so that the mean
is $N$, and see which has the least variance. We let $X_{k}$ be the estimation
from using the largest tank, $X_{k-1}$ from using the second largest tank, and
so on. To calculate the variances of these formulas, we calculate the
variances of $M_{k}$, the largest tank, $M_{k-1}$, the second largest tank,
and so on; we then scale by a multiplicative factor to get the variances we
want.

####  4.1.1. Variance of $M_{k}$

: We use Lemma 2.2, to compute the variance. We find

$\displaystyle{\rm Var}(M_{k})$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[M_{k}^{2}]\ -\ \mathbb{E}[M_{k}]^{2}$ (4.5)
$\displaystyle=$ $\displaystyle\sum_{m_{k}=k}^{N}m_{k}^{2}{\rm Prob(M_{k}\ =\
m_{k})}\ -\ \bigg{[}\sum_{m_{k}=k}^{N}m_{k}{\rm Prob(M_{k}\ =\
m_{k})}\bigg{]}^{2}$ $\displaystyle{\rm We\ know\ the\ second\ term,\ as\ we\
calculated\ it\ earlier.}$ $\displaystyle{\rm We\ just\ have\ to\ calculate\
the\ first\ term.}$ $\displaystyle=$
$\displaystyle\sum_{m_{k}=k}^{N}m_{k}^{2}\frac{\binom{m_{k}-1}{k-1}}{\binom{N}{k}}\
-\ \bigg{[}\frac{k(N+1)}{k+1}\bigg{]}^{2}$ $\displaystyle{\rm We\ use\
Identity\ III\ to\ calculate\ the\ first\ term.}$ $\displaystyle{\rm After\
substituting\ in\ and\ simplifying,\ we\ get}$ $\displaystyle=$
$\displaystyle=\ N^{2}\ -\ (2N-1)\frac{N-k}{k+1}\ $ $\displaystyle\ \ \ \ \ +\
2\frac{(N-k)(N-k-1)}{(k+1)(k+2)}\ -\ \frac{k^{2}(N+1)^{2}}{(k+1)^{2}}$
$\displaystyle=$ $\displaystyle\frac{(k)(N-k)(N+1)}{(k+1)^{2}(k+2)}.$

Now that we have the variance for $M_{k}$, we easily scale the formula and
obtain the variance of $X_{k}=m_{k}(k+1)/k$, as the variance of $a$ times $X$
is $a^{2}$ times the variance of $X$:

$\displaystyle{\rm Var}(X_{k})$ $\displaystyle\ =\ $ $\displaystyle{\rm
Var}(M_{k})\cdot\frac{(k+1)^{2}}{k^{2}}$ (4.6) $\displaystyle=$
$\displaystyle\frac{(k)(N-k)(N+1)}{(k+1)^{2}(k+2)}\cdot\frac{(k+1)^{2}}{k^{2}}$
$\displaystyle=$ $\displaystyle\frac{(N-k)(N+1)}{(k)(k+2)}.$

Through similar calculations, we obtain the variance of $X_{k-1}$ (see
Appendix D for details):

$\displaystyle{\rm Var}(X_{k-1})$ $\displaystyle\ =\ $
$\displaystyle\frac{2(N-k)(N+1)}{(k+2)(k-1)}.$ (4.7)

We see that the estimator using $m_{k-1}$, and more generally using
$m_{k-L+1}$, is worse than using $m_{k}$, as the variance is larger. We can
simply plug in some values of $N$ and $k$ and compare the variances. Also, we
see that the variance for $X_{k-1}$ is roughly two times the variance of
$X_{k}$, which shows that $X_{k}$ is a better statistic. We can also compare
variances easily by writing some code and numerically exploring. We made a
simulation where we sample the $k$ tanks from 1 to $N$ when all tanks are
equally likely to be seen. This simulation is attached in the Appendix E.
Thus, we conclude that if we are only going to use one observed value, it is
best to use the largest.

This leads to our second question: can we do better if we create a statistic
combining two or more observed values?

###  4.2. Weighted Statistic

Previously, we’ve only considered using one tank to estimate for $N$. In this
section, we create a statistic using the largest and second largest tank
values, and show that this weighted statistic isn’t better.

Before we state the weighted formula, we set our notation.

  * •

$N$ = Total number of tanks

  * •

$k$ = Numbers of tanks observed

  * •

$M_{k}$ = Largest Observed Tank

  * •

$M_{k-1}$ = Second largest Observed Tank

  * •

$X_{k}$ = Statistic to estimate $N$ using $M_{k}$: $M_{k}(\frac{k+1}{k})$ \- 1

  * •

$X_{k-1}$ = Statistics to estimate $N$ using $M_{k-1}$:
$M_{k-1}(\frac{k+1}{k-1})$ \- 1

We state the weighted statistic. Let $\alpha\in[0,1]$ and define the weighted
statistic $X_{\alpha}$ by

$\displaystyle X_{\alpha}\ :=\ \alpha X_{k}\ +\ (1-\alpha)X_{k-1}.$ (4.8)

From the formula, we see that when $\alpha$ is 1, this collapses to the
formula for $N$ using $m_{k}$, and similarly when $\alpha$ is 0, we get the
$m_{k-1}$ formula. In order to see if there is a better estimation, we find
the optimal $\alpha$ value, the value that minimizes the variance of
$X_{\alpha}$. If the optimal $\alpha$ value is 1, then we can conclude that
the $m_{k}$ formula is the best we can do to estimate for $N$. We compute the
variance of $X$:

$\displaystyle{\rm Var\ X}_{\alpha}\ =\ \alpha^{2}{\rm Var\ X_{k}}\ +\
(1-\alpha)^{2}{\rm Var\ X_{k-1}}\ +\ 2\ \alpha(1-\alpha){\rm
Cov}(X_{k},X_{k-1}).$ (4.9)

As We have already calculated the variances of $X_{k}$ and $X_{k-1}$, we just
have to calculate the covariance term.

####  4.2.1. Covariance term

We calculate the term, ${\rm Cov}[X_{k},X_{k-1}]$ separately first. By Lemma
2.4, we have

$\displaystyle{\rm Cov}[X_{k},X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]\ -\
\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}].$ (4.10)

Recall that

$\displaystyle X_{k}\ =\ m_{k}\bigg{(}\frac{k+1}{k}\bigg{)}-1\ ,\ \ \ \
X_{k-1}\ =\ m_{k-1}\bigg{(}\frac{k+1}{k-1}\bigg{)}-1.$ (4.11)

We know that the second term of the covariance,
$\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}]$ is $N^{2}$ because they are both
estimation formulas. Thus, we only have to calculate the first term.

We use linearity of expectation to expand. Recall Theorem 2.5, linearity of
expectation.

$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}\bigg{[}\bigg{(}m_{k}\bigg{(}\frac{k+1}{k}\bigg{)}-1\bigg{)}\cdot\bigg{(}m_{k-1}\bigg{(}\frac{k+1}{k-1}\bigg{)}-1\bigg{)}\bigg{]}$
(4.12) $\displaystyle=$
$\displaystyle\frac{(k+1)^{2}}{k(k-1)}\mathbb{E}[m_{k}\cdot m_{k-1}]\ -\
\frac{k+1}{k}\mathbb{E}[m_{k}]\ -\ \frac{k+1}{k-1}\mathbb{E}[m_{k-1}]\ +\
\mathbb{E}[1].$

We calculate term by term. We use the joint PDF, recall Theorem 2.6, to
calculate $\mathbb{E}[m_{k}\cdot m_{k-1}]$.

$\displaystyle\mathbb{E}[M_{k}\cdot M_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{k}=k}^{N}\sum_{m_{k-1}=k-1}^{m_{k}-1}m_{k}m_{k-1}{\rm
Prob}(M_{k-1}=m_{k-1},M_{k}=m_{k})$ (4.13) $\displaystyle{\rm This\ is\ the\
joint\ probability\ density\ function\ of\ m_{k}\ and\ m_{k-1}}$
$\displaystyle=$
$\displaystyle\sum_{m_{k}=k}^{N}\sum_{m_{k-1}=k-1}^{m_{k}-1}m_{k}m_{k-1}\frac{\binom{m_{k-1}-1}{k-2}}{\binom{N}{k}}$
$\displaystyle{\rm The\ probability\ is\ the\ following\ because\ after\
selecting\ m_{k}\ and\ m_{k-1},\ we}$ $\displaystyle\ \ \ \ {\rm have\ to\
select\ (k-2)\ more\ tanks\ from\ the\ possible\ (m_{k-1}-1)\ tanks.}$
$\displaystyle\ \ \ \ \ {\rm The\ range\ of\ m_{k-1}\ is\ dependent\ on\ the\
value\ of\ m_{k}\ because}$ $\displaystyle\ \ \ \ \ {\rm m_{k-1}\ \leq\ m_{k}\
is\ always\ satisfied.}$ $\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m_{k}=k}^{N}m_{k}\sum_{m_{k-1}=k-1}^{m_{k}-1}m_{k-1}\binom{m_{k-1}-1}{k-2}$
$\displaystyle=$
$\displaystyle\frac{k-1}{\binom{N}{k}}\sum_{m_{k}=k}^{N}m_{k}\sum_{m_{k-1}=k-1}^{m_{k}-1}\binom{m_{k-1}}{k-1}$
$\displaystyle=$
$\displaystyle\frac{k-1}{\binom{N}{k}}\sum_{m_{k}=k}^{N}m_{k}\binom{m_{k}}{k}$
$\displaystyle{\rm We\ use\ Identity\ II\ to\ calculate}$ $\displaystyle=$
$\displaystyle\frac{(k-1)(N+2)(N+1)}{(k+2)}\ -\ \frac{(k-1)(N+1)}{k+1}.$

Now that we’ve calculated the joint PDF, we know all the terms and find

$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\frac{(k+1)^{2}}{k(k-1)}\bigg{[}\frac{(k-1)(N+2)(N+1)}{(k+2)}-\frac{(k-1)(N+1)}{k+1}\bigg{]}$
(4.14) $\displaystyle\ \ \ \ \ -\ \frac{k+1}{k}\frac{(N+1)k}{k+1}\ -\
\frac{k+1}{k-1}\frac{(N+1)(k-1)}{k+1}\ +\ 1,$

and of course from our normalizations we have

$\displaystyle\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle N^{2}.$ (4.15) $\displaystyle\mathbb{E}[X_{k}\cdot
X_{k-1}]-\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\frac{(k+1)^{2}}{k}\frac{(N+2)(N+1)}{(k+2)}\ -\
\frac{(k+1)}{k}{(N+1)}\ -(N+1)^{2}$ (4.16) $\displaystyle=$
$\displaystyle\frac{(n+1)(n-k)}{k(k+2)}.$

####  4.2.2. Finding optimal alpha

Now that we’ve calculated ${\rm Var}(X_{k})$, ${\rm Var}(X_{k-1})$, and ${\rm
Cov}(X_{k},X_{k-1})$, we find the optimal $\alpha$ value (that minimizes the
variance of $X_{\alpha}$). To find the optimal alpha value, we optimize by
taking the derivative and finding the unique value that gives the least
variance. Let $\alpha_{k,{k-1}}$ denote the specific value of $\alpha$ that
minimizes the variance. We have

$\displaystyle{\rm Var}(X_{\alpha})$ $\displaystyle\ =\ $
$\displaystyle\alpha^{2}{\rm Var}(X_{k})\ +\ (1-\alpha)^{2}{\rm
Var}(X_{k-1})+2\alpha(1-\alpha){\rm Cov}(X_{k},X_{k-1})$ (4.17)
$\displaystyle=$ $\displaystyle\alpha^{2}({\rm Var}(X_{k})+{\rm
Var}(X_{k-1})-2\ {\rm Cov}(X_{k},X_{k-1}))$ $\displaystyle\ \ \ \ \ \ \ \ \ +\
2\alpha({\rm Cov}(X_{k},X_{k-1})\ -\ {\rm Var}(X_{k-1}))\ +\ {\rm
Var}(X_{k-1}).$

Taking the derivative with respect to $\alpha$ yields

$\displaystyle{\rm Var}(X_{\alpha})^{\prime}$ $\displaystyle\ =\ $
$\displaystyle 2\alpha_{k,{k-1}}({\rm Var}(X_{k})+{\rm Var}(X_{k-1})-2\ {\rm
Cov}(X_{k},X_{k-1})$ (4.18) $\displaystyle\ \ \ \ \ \ +\ 2\ ({\rm
Cov}(X_{k},X_{k-1})\ -\ {\rm Var}(X_{k-1})).$

Because we want to find the optimal $\alpha$ value, we solve for ${\rm
Var}(X)^{\prime}=0$ (and of course also check the endpoints of $\alpha=0$ or
$1$). After substituting in the formulas and doing some algebra, we see that
the optimal alpha value is 1, which is in fact one of our endpoints and
corresponds to only using the largest tank. Thus if we use both the largest
and second largest values observed we do worse than just using the largest:

$\displaystyle\alpha_{k,{k-1}}\ =\ \frac{{\rm Var}(X_{k-1})\ -\ {\rm
Cov}(X_{k},X_{k-1})}{{\rm Var}(X_{k})+{\rm Var}(X_{k-1})-2\ {\rm
Cov}(X_{k},X_{k-1})}\ =\ 1.$ (4.19)

Similar calculations hold for other weighted combinations. Therefore, in the
discrete one dimensional German Tank problem where we sample without
replacement, we conclude that the formula using the largest tank does the best
job.

##  5\. Continuous One Dimensional Problem

We now explore our first generalization of the German Tank Problem and
consider a continuous one dimensional analogue. In the original formulation,
the serial numbers of the tanks were all integers drawn from 1 to $N$. We now
consider a continuous version, where we select $k$ tanks from the interval
$[0,N]$ with $N$ unknown. Thus our goal is to find a statistic to estimate
$N$. We discuss the effectiveness of various statistics and compare the
continuous formulas to the discrete ones; the scaling factor is the same in
the continuous and discrete one dimensional problems.

###  5.1. Formulas Using Largest and Second Largest Observations.

We begin by estimating using the largest and second largest tanks by using the
CDF method to find the PDF. In the continuous case, to find the PDF, we take
the derivative of the CDF.

####  5.1.1. Formula from Largest

: We first find the CDF by computing the probability that all the tanks are at
most $m_{k}$:

$\displaystyle{\rm Prob}(M_{k}\leq m_{k})\ =\
\bigg{(}\frac{m_{k}}{N}\bigg{)}^{k};$ (5.1)

this is because in the continuous case we can view all $k$ observations as
independent, and the probability any is at most $m_{k}$ is just $m_{k}/N$.

Taking the derivative gives the PDF:

$\displaystyle f(m_{k})\ =\ PDF_{M_{k}}(m_{k})\ =\
CDF_{M_{k}}(m_{k})^{\prime}\ =\ \frac{km_{k}^{k-1}}{N^{k}}.$ (5.2)

Now that we have the PDF, we calculate the expected value of $m_{k}$:

$\displaystyle\mathbb{E}[M_{k}]$ $\displaystyle\ =\ $
$\displaystyle\int_{0}^{N}m_{k}f(m_{k})\,dm_{k}$ (5.3) $\displaystyle=$
$\displaystyle\int_{0}^{N}m_{k}\frac{km_{k}^{k-1}}{N^{k}}\,dm_{k}$
$\displaystyle=$ $\displaystyle\frac{k}{N^{k}}\int_{0}^{N}m_{k}^{k}\,dm_{k}$
$\displaystyle=$ $\displaystyle\frac{k}{k+1}\cdot N.$

Thus we obtain

$\displaystyle\mathaccent 866{N}\ =\ m\cdot\bigg{(}1+\frac{1}{k}\bigg{)}.$
(5.4)

######  Remark 5.1.

Comparing the continuous formula to the discrete, the only difference is that
there is a $-1$ in the discrete formula. This difference is due to in the
discrete case we sample from tanks numbered from 1 to $N$ while in the
continuous case wehave chosen to have the interval to be $[0,N]$.

####  5.1.2. Formula using Second Largest

: We first find the CDF by computing the probability that the second largest
tank is at most $m_{k-1}$. There are two possibilities – all the tanks are
less than $m_{k-1}$, or one tank (and there is $\binom{N}{1}$ ways to choose
which of the $k$ tanks that is) is larger than $m_{k-1}$ and the rest are
$m_{k-1}$ or smaller. Thus

$\displaystyle CDF_{M}(m_{k-1})$ $\displaystyle\ =\ $ $\displaystyle{\rm
Prob}(M_{k-1}\leq X)$ (5.5) $\displaystyle=$
$\displaystyle\bigg{(}\frac{X}{N}\bigg{)}^{k}\ +\
\binom{k}{1}\bigg{(}\frac{X}{N}\bigg{)}^{k-1}\frac{N-X}{N}.$

We take the derivative of the CDF in order to find the PDF. After standard
integration, we find

$\displaystyle\mathaccent 866{N}\ =\ m_{k-1}\cdot\frac{k+1}{k-1}.$ (5.6)

######  Remark 5.2.

For the continuous formula using $m_{k-1}$, we see that there is a difference
arising from a factor of $-1$ from the discrete case. The same explanation of
the difference applies here too. Also, as we saw in the discrete case, because
the continuous and discrete formula are essentially the same formulas, the
variance for the formula using $m_{k-1}$ is larger.

###  5.2. Continuous weighted formula

:

As we did in the discrete one dimensional case, we see if constructing a
statistic that is a linear combination of $m_{k}$ and $m_{k-1}$ does a better
job estimating $N$. Similar to before, the best value is again when
$\alpha=1$, meaning that the formula using only $m_{k}$ gives the least
variance and there is no benefit to including $m_{k-1}$. The calculation is
similar to the discrete weighted problem; see Appendix D.

##  6\. Two Dimensional Discrete Generalizations

We now generalize the German Tank Problem to two dimensions, after which it
will be easy to extend to higher dimensions. We look at the discrete and
continuous versions of the square and the circle. We find for each problem
which statistic gives the best estimate for $N$, and compare the formulas of
the discrete two dimensional square to that of the one dimensional discrete
square. Note that if we use all the terms in the calculation, we would not get
a clean closed form, as we have many different powers of $m$, making the
equation uninvertible. In order to avoid this, we approximate using the main
term and get formulas for fixed $k$ and $N$ tending to infinity.

###  6.1. Square Problem

We first consider the case of the square from $(1,1)$ to $(N,N)$ as the
natural generalization of the one-dimensional set $\\{1,\dots,N\\}$. Thus
there are $N^{2}$ pairs, we select $k$ of them without replacement. We call
the two components the $X$ and the $Y$ list and use the pairs to find the best
estimate for $N$. We investigated two statistics: the largest number from the
two lists, and a recursive method where we start with a estimate of $N$ and
use the largest $L$ to estimate for $N$ again until the value of our estimate
for $N$ stabilizes.

####  6.1.1. Maximum from Lists:

The motivation of looking at the largest observed component in the two
dimensional square comes from the one dimensional German tank problem, where
looking at the largest tank gave the most accurate estimation. To calculate
the formula, we use the CDF method. The CDF method in the discrete case is
slightly different from the one in the continuous case. The statistic we look
at is the largest observed component of the $X$ list and $Y$ list, which we
denote by $M$. To calculate the probability that the largest observed
component is at most $m$, instead of taking the derivative to find the PDF as
we did in the continuous case, in the discrete case we calculate

${\rm Prob}(M\leq m)\ -\ {\rm Prob}(M\leq m-1)$ (6.1)

to get the ${\rm Prob}({\rm Max}=m)$. The PDF is computed similarly as in
previous arguments, giving

$\displaystyle{\rm PDF}_{M}(m)$ $\displaystyle\ =\ $ $\displaystyle{\rm
Prob}(M\leq m)\ -\ {\rm Prob}(M\leq m-1)$ (6.2) $\displaystyle=$
$\displaystyle\frac{\binom{m^{2}}{k}}{\binom{N^{2}}{k}}\ -\
\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}.$

Thus the expected value of $M$ is

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N}m\cdot{\rm PDF}_{M}(M=m)$ (6.3)
$\displaystyle=$
$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{m\binom{m^{2}}{k}\ -\
m\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}$ $\displaystyle=$
$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{m\binom{m^{2}}{k}\ -\
(m-1)\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}\ -\
\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}$
$\displaystyle{\rm We\ telescope\ the\ first\ term.}$ $\displaystyle=$
$\displaystyle\frac{N\binom{N^{2}}{k}\ -\
(\lceil\sqrt{k}\rceil-1)\binom{(\lceil\sqrt{k}\rceil-1)^{2}}{k}}{\binom{N^{2}}{k}}\
-\
\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}.$

We now determine the second term above; it is

$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}$
$\displaystyle\ =\ $
$\displaystyle\frac{1}{\binom{N^{2}}{k}}\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}\binom{m^{2}}{k}$
(6.4) $\displaystyle{\rm Range\ for\ m\ starts\ at\ \lceil\sqrt{k}\rceil\
because\ if\ m\ is\ \lceil\sqrt{k}\rceil-1,\ we\ get\ 0.}$ $\displaystyle=$
$\displaystyle\frac{1}{k!\binom{N^{2}}{k}}\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}m^{2}(m^{2}-1)\cdots(m^{2}-(k-1)).$

We use Lemma 2.9 to provide upper and lower bounds for the sum

$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}\bigg{(}m^{2k}-m^{2k-2}\bigg{(}\frac{k(k-1)}{2}\bigg{)}\bigg{)}\leq\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}m^{2}(m^{2}-1)\cdots(m^{2}-(k-1)\leq\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}m^{2k},$
(6.5)

and we now use the Euler-Maclaurin formula, Lemma 2.8, to approximate the sums
with integrals, and bound the error of the approximation in terms of the
derivative of the function at the boundary points. We take $p\ =\ 2$, as for
the range we are studying this gives an excellent bound and an expression that
is easy to work with.

######  Remark 6.1.

When we calculate the upper and lower bounds, we see that the first order of
the upper and lower are the same, which is why we can set these bounds.

We state a result for a general sum using Euler-Maclaurin, and then will
choose appropriate values of the constants. We can just plug in values of $w$
and $y$, which are the powers of $m$, and we also plug in $a$ and $b$ in order
to make the calculation easier.

$\displaystyle\sum_{i=a}^{b}\bigg{[}m^{w}-c\cdot m^{y}\bigg{]}$
$\displaystyle\ =\ $ $\displaystyle\int_{a}^{b}(x^{w}-c\cdot x^{y})\,dx\ +\
\frac{a^{w}+b^{w}-c\cdot a^{y}-c\cdot b^{y}}{2}$ (6.6) $\displaystyle\ \ \ \ \
+\ \frac{B_{2}}{2}(f^{\prime}(b)-f^{\prime}(a))\ +\ R_{2}$ $\displaystyle=$
$\displaystyle\frac{b^{w+1}-a^{w+1}}{w+1}\ -\ \frac{c\cdot b^{y+1}-c\cdot
a^{y+1}}{y+1}$ $\displaystyle\ \ +\ \frac{a^{w}+b^{w}-c\cdot a^{y}-c\cdot
b^{y}}{2}\ +\ \frac{1}{12}\bigg{(}w\cdot b^{w-1}$ $\displaystyle\ \ \ \ \ -\
c\cdot y\cdot b^{y-1}\ -\ w\cdot a^{w-1}+c\cdot y\cdot a^{w-1}\bigg{)}\ +\
R_{2}.$

We calculate the remainder term for the general equation:

$\displaystyle|R_{2}|$ $\displaystyle\ \leq\ $
$\displaystyle\frac{2\zeta(2)}{(2\pi)^{2}}\int_{a}^{b}|f^{2}(x)|\,dx$ (6.7)
$\displaystyle\leq$
$\displaystyle\frac{1}{12}\cdot\bigg{[}\int_{a}^{b}\bigg{(}w(w-1)m^{w-2}-c\cdot
y\cdot(y-1)m^{y-2}\bigg{)}\,dm\bigg{)}$ $\displaystyle\leq$
$\displaystyle\frac{1}{12}\bigg{[}w\cdot b^{w-1}-c\cdot y\cdot b^{y-1}-w\cdot
a^{w-1}+c\cdot y\cdot a^{y-1}\bigg{]}.$

Now that we’ve calculated the main term and remainder of the general equation,
we calculate the lower and upper bounds using the general Euler-Maclaurin
formula.

We first do the lower bound:

$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}\bigg{(}m^{2k}-m^{2k-2}\bigg{(}\frac{k(k-1)}{2}\bigg{)}\bigg{)}$
(6.8) $\displaystyle=$
$\displaystyle\frac{(N-1)^{2k+1}-(\lceil\sqrt{k}\rceil)^{2k+1}}{2k+1}\ -\
\bigg{(}\frac{k(k-1)}{2}\bigg{)}\cdot\frac{(N-1)^{2k-1}-(\lceil\sqrt{k}\rceil)^{2k-1}}{2k-1}$
$\displaystyle\ \ \ +\ \frac{\lceil\sqrt{k}\rceil^{2k}+(N-1)^{2k}}{2}\ -\
\frac{k(k-1)}{2}\cdot\frac{\lceil\sqrt{k}\rceil^{2k-2}+(N-1)^{2k-2}}{2}$
$\displaystyle\ \ +\ \frac{1}{12}\bigg{[}2k(N-1)^{2k-1}-2k\cdot\
(\lceil\sqrt{k}\rceil)^{2k-1}-k(k-1)^{2}(N-1)^{2k-3}$ $\displaystyle\ \
+k(k-1)^{2}(\lceil\sqrt{k}\rceil)^{2k-3}\bigg{]}\ +\ R_{2},$

where we have the following bound for the remainder term:

$\displaystyle|R_{2}|$ $\displaystyle\ \leq\ $
$\displaystyle\frac{1}{12}\bigg{[}2k\cdot(N-1)^{2k-1}-\frac{k(k-1)}{2}(2k-2)(N-1)^{2k-3}\
-\ 2k\cdot(\lceil\sqrt{k}\rceil)^{2k-1}$ (6.9) $\displaystyle\ \ +\
\frac{k(k-1)}{2}\cdot(2k-2)\cdot(\lceil\sqrt{k}\rceil)^{2k-3}\bigg{]}$
$\displaystyle\leq$
$\displaystyle\frac{1}{12}\bigg{[}2k\cdot(N-1)^{2k-1}-2k(\lceil\sqrt{k}\rceil)^{2k-1}-k(k-1)^{2}(N-1)^{2k-3}$
$\displaystyle\ +k(k-1)^{2}(\lceil\sqrt{k}\rceil)^{2k-3}\bigg{]}.$

We now calculate the main and remainder term of the upper bound:

$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}m^{2k}$ $\displaystyle\ =\ $
$\displaystyle\frac{(N-1)^{2k+1}-(\lceil\sqrt{k}\rceil)^{2k+1}}{2k+1}\ +\
\frac{(\lceil\sqrt{k}\rceil)^{2k}+(N-1)^{2k}}{2}$ (6.10) $\displaystyle\ \ +\
\frac{1}{12}\bigg{(}2k\cdot(N-1)^{2k-1}-2k\cdot(\lceil\sqrt{k}\rceil)^{2k-1}\bigg{)}\
+\ R_{2}$ $\displaystyle=$
$\displaystyle\frac{(N-1)^{2k+1}-(\lceil\sqrt{k}\rceil)^{2k+1}}{2k+1}\ +\
\frac{(\lceil\sqrt{k}\rceil)^{2k}+(N-1)^{2k}}{2}$ $\displaystyle\ \ +\
\frac{k}{6}\bigg{[}(N-1)^{2k-1}-(\lceil\sqrt{k}\rceil)^{2k-1}\bigg{]}\ +\
R_{2},$

with the remainder term bounded by

$\displaystyle|R_{2}|$ $\displaystyle\ \leq\ $
$\displaystyle\frac{1}{12}\bigg{[}2k\cdot(N-1)^{2k-1}-2k\cdot(\lceil\sqrt{k}\rceil)^{2k-1}\bigg{]}$
(6.11) $\displaystyle\leq$
$\displaystyle\frac{k}{6}\bigg{[}(N-1)^{2k-1}-(\lceil\sqrt{k}\rceil)^{2k-1}\bigg{]}.$

Now that we have the upper and lower bounds, we use the main term (which as
$N\to\infty$ dominates the error terms) to find an equation of $m$ in terms of
$N$ and $k$:

$\displaystyle\sum_{m=\lceil\sqrt{k}\rceil}^{N-1}m^{2k}$ $\displaystyle\
\approx\ $
$\displaystyle\frac{(N-1)^{2k+1}-(\lceil\sqrt{k}\rceil)^{2k+1}}{2k+1}$ (6.12)
$\displaystyle{\rm Because\ we\ assumed\ that\ k\ is\ fixed,\ if\ N\ is\ very\
large}$ $\displaystyle{\rm the\ other\ terms\ are\ negligible.}$
$\displaystyle\approx$ $\displaystyle\frac{(N-1)^{2k+1}}{2k+1}.$

We plug this estimation back into the formula for $\mathbb{E}[M]$:

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\frac{N\binom{N^{2}}{k}\ -\
(\lceil\sqrt{k}\rceil-1)\binom{(\lceil\sqrt{k}\rceil-1)^{2}}{k}}{\binom{N^{2}}{k}}\
-\
\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}$
(6.13) $\displaystyle{\rm We\ use\ the\ same\ argument\ as\ above}$
$\displaystyle{\rm to\ say\ that\ the\ term\ with\ k\ is\ negligible.}$
$\displaystyle\approx$ $\displaystyle N\ -\
\sum_{m=\lceil\sqrt{k}\rceil}^{N}\frac{\binom{(m-1)^{2}}{k}}{\binom{N^{2}}{k}}$
$\displaystyle{\rm We\ plug\ in\ the\ estimate\ of\ the\ second\ term}$
$\displaystyle\approx$ $\displaystyle N\ -\
\frac{\frac{(N-1)^{2k+1}}{2k+1}}{\binom{N^{2}}{k}\cdot k!}$
$\displaystyle\approx$ $\displaystyle N\bigg{[}1\ -\
\frac{1}{2k+1}\bigg{(}1-\frac{1}{N}\bigg{)}^{2k+1}\bigg{]}$ $\displaystyle{\rm
We\ expand\ out\ the\ first\ two\ terms\ to\ estimate\ for\ (1-1/N)^{2k+1}.}$
$\displaystyle{\rm If\ we\ use\ more\ terms,\ the\ accuracy\ slightly\
increases,\ but\ the\ equation}$ $\displaystyle{\rm will\ not\ be\
invertible.\ Thus,\ we\ only\ write\ the\ first\ two\ terms.}$
$\displaystyle\approx$ $\displaystyle
N\bigg{[}1-\frac{1}{2k+1}\bigg{(}1-\frac{2k+1}{N}\bigg{)}\bigg{]}$
$\displaystyle=$ $\displaystyle N\bigg{[}\frac{2k}{2k+1}\bigg{]}\ +\ 1$

We obtain a good estimate of $(1-1/N)^{2k+1}$ by using two terms. Inverting
the equation, we get

$\displaystyle\mathaccent 866{N}\ =\ \frac{2k+1}{2k}(m-1)$ (6.14)

Now that we have a estimation formula for $\mathaccent 866{N}$, we run some
simulations to see how accurate this estimation formula is. See Appendix E for
the simulation. We see that the two dimensional formula does well as the
variance is small. In the next subsubsection, we compare the one dimensional
formula to the two dimensional formula and see which one does better.

####  6.1.2. Comparing Formulas

We compare the one dimensional formula and the discrete square formula to see
which one does better. We have to make sure that we are making correct
comparisons (apples to apples), because a pair gives two data points whereas a
point gives one. Also, we want to make sure that both formulas estimate for
$N$. For the $N$ by $N$ square, we pick $k$ pairs, which gives us $2k$
components of $N^{2}$ pairs. For the one dimensional case, we pick $2k$ tanks
from $N^{2}$ possible tanks. This will give us a estimate for $N^{2}$, and we
take the square root to find the estimate for $N$. By comparing these two
quantities, we make sure that we observe $2k$ data points. We run code (see
Appendix E) to compare the two formulas.

Figure 4. Comparing results from square formula to one dimensional formula

######  Remark 6.2.

From the code, we see that the 1-dimensional case does a better job than the
two dimensional case, as the one dimensional case has lower variance. The
difference is clearly visible when $k$ is a very small value such as 2. We’ve
seen from code that the 1-dimensional formula does better, and we confirm this
by theory. We paste some results from the code.

####  6.1.3. Recursive Argument:

For another approach, we start with an initial estimate for $N$, which we call
$N_{0}$. We construct a formula to recursively generate new estimates of $N$
from previous; thus let $N_{1}$ be our next guess. We investigate if the
values of $N$ converge, and if so if they converges to a more accurate
estimate.

We first transform the $N^{2}$ pairs into a list of numbers from 1 to $N^{2}$.
For each pair ($X$,$Y$), we write the tanks as $(X-1)\ +\ N(Y-1)\ +\ 1$. This
way, we can represent all tanks from 1 to $N^{2}$, as this maps the $N^{2}$
pairs uniquely to the integers from 1 to $N^{2}$. Unfortunately, when we use
observed tank values to estimate, we do not know the value of $N$ so we cannot
immediately use this formula. Instead we replace $N$ with our estimate. With
that estimate, we express a new $N$ with the largest observed component. As
before, let $M$ denote the maximum of the two lists. Then

$\displaystyle{\rm Prob}(M=L)\ =\ \frac{\binom{L-1}{k-1}}{\binom{N^{2}}{k}}.$
(6.15)

Thus

$\displaystyle\mathbb{E}[L]$ $\displaystyle\ =\ $
$\displaystyle\sum_{L=k}^{N^{2}}L\cdot\frac{\binom{L-1}{k-1}}{\binom{N^{2}}{k}}$
(6.16) $\displaystyle{\rm We\ calculate\ and\ get}$ $\displaystyle=$
$\displaystyle k\cdot\frac{N^{2}+1}{k+1}.$

Thus

$\displaystyle\mathaccent 866{N}\ =\
\sqrt{\mathbb{E}[L]\cdot\frac{k+1}{k}-1}.$ (6.17)

In order to create a iterative process, we plug in $\mathbb{E}[L]\ =\ {\rm
Max}X+({\rm current\ estimation\ for\ N})({\rm Max}Y-1)$. We rewrite our
estimation for $\mathaccent 866{N}$

$\displaystyle\mathaccent 866{N}\ =\ \sqrt{\bigg{[}{\rm Max}X+({\rm current\
estimation\ for\ N})({\rm Max}Y-1)\bigg{]}\cdot\frac{k+1}{k}-1}.$ (6.18)

Now, we’ve got a recursive function of $N$. We can use the preliminary
estimation of $N$ to get another estimate for $N$. Therefore, by starting with
a value of $N$, we can continue to produce estimates of $N$. The hope is that
by producing more values of $N$, the values converge to the actual number $N$.
To see how well this process does, we attached the code for simulation in the
Appendix E. Using the simulation, we plugged in different values of Max($X$)
and Max($Y$). However, though the results converge, they do not do a better
job as often the value it converges to is off from the actual $N$.

####  6.1.4. Continuous Square Problem

The continuous square problem is slightly different from the discrete square
as we can pick points from $(0,0)$ to $(N,N)$. To calculate the PDF, we use
the CDF method by calculating the CDF and taking the derivative. Let $m$
denote the largest component observed:

$\displaystyle CDF_{M}(m)\ =\ {\rm Prob}(M\leq m)\ =\
\left(\frac{m^{2}}{N^{2}}\right)^{k}\ =\ \frac{m^{2k}}{N^{2k}},$ (6.19)

and thus

$\displaystyle{\rm PDF}_{M}(m)\ =\ {\rm CDF_{M}}^{\prime}(m)\ =\ \frac{2k\cdot
m^{2k-1}}{N^{2m}}.$ (6.20)

Therefore

$\displaystyle\mathbb{E}[m]$ $\displaystyle\ =\ $
$\displaystyle\int_{0}^{N}m\cdot\frac{2k\cdot m^{2k-1}}{N^{2k}}\,dm$ (6.21)
$\displaystyle{\rm We\ calculate\ and\ get:}$ $\displaystyle=$
$\displaystyle\frac{2k}{2k+1}\cdot N.$

Solving yields

$\displaystyle\mathaccent 866{N}\ =\ m\cdot\frac{2k+1}{2k}.$ (6.22)

######  Remark 6.3.

We see that the scaling factor for the continuous case is the same as the
scaling factor for the discrete case. The scaling factor of $(2k+1)/(2k)$ is
reasonable, and we see this by comparing this formula to the one dimensional
formula. In the one dimensional case, the scaling factor was $(k+1)/(k)$,
which is larger than $(2k+1)/(2k)$. However, because in the two dimensional
case we are looking at the largest of both components, we have more data
points and therefore we will likely get a larger $M$ value. Therefore, in the
two dimensional case, we would have to scale by a value smaller than
$(k+1)/k$, and scaling by $(2k+1)/(2k)$ makes sense.

###  6.2. Circle Problem

####  6.2.1. Discrete Circle Problem

The goal of the discrete circle problem is to find a formula that estimates
the radius. We assume the circle is centered at $(0,0)$ with radius $r$ and we
select $k$ different lattice points contained in the circle without
replacement. We look at $X^{2}+Y^{2}$ as our statistic, because the resulting
values are integers, and of course we can then take a square-root at the end.

We let $m_{1}=X^{2}+Y^{2}$. However, some elementary number theory enters in
two dimensions and not all values of $m_{1}$ are attainable. Notice that
$X^{2}$ and $Y^{2}$ are each 0 or 1 modulo 4, so any attainable $m_{1}$ is
either 0, 1 or 2 modulo 4.

The number of lattice points inside a circle with radius $r$ and center
$(0,0)$ is the well studied Gauss Circle problem [Co]. Let $P(r)$ be the
number of lattice points inside a circle in plane of radius $r$ and center at
the origin, i.e.,

$\displaystyle P(r)\ =\ {\rm Number\ of}\
({(q,n)\in\mathbb{Z}^{2}|q^{2}+n^{2}\leq r^{2}}).$ (6.23)

The number of lattice points inside the circle is well estimated by the area
of the circle, $\pi r^{2}$; the challenge is determining the size of the
error.

We have

$\displaystyle P(r)\ =\ \pi r^{2}\ +\ E(r).$ (6.24)

We do not need the best known results, so we write $E(r)$ as $O(r^{\delta})$
where $(0\leq\delta\leq 1)$, using Big-Oh notation (see Definition 2.10); the
current world record has $.5<\delta<.63$. Note $P(m)\ =\ CDF_{M_{m_{1}}}(M\leq
m_{1})$, where $M$ is the random variable that is the value of $X^{2}+Y^{2}$.
We see that the $PDF_{M}(m)$ is $P(m_{1})-P(m_{1}-1)$. Therefore, if we have
$m_{1}\equiv 3\ ({\rm mod\ 4})$ , then the $PDF_{M}(m_{1})=0$, and thus we
don’t have to worry about this case, though for ease we do include it below.

We calculate the expected value of $M$:

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{1}=0}^{r^{2}}m_{1}\cdot{\rm Prob}(M=m_{1})$ (6.25)
$\displaystyle=$
$\displaystyle[P(1)-P(0)]+[2P(2)-2P(1)]+\dots+r^{2}[P(r^{2})-r^{2}P(r^{2}-1)]$
$\displaystyle=$ $\displaystyle r^{2}P(r^{2})-[P(1)+P(2)+\dots+P(r^{2}-1)$
$\displaystyle=$ $\displaystyle r^{2}\ -\ \frac{1}{\binom{\pi
r^{2}+O(r^{\delta})}{k}}\sum_{m_{1}=0}^{r^{2}}\binom{\pi(m-1)+O((m-1)^{\delta})}{k}.$

We estimate the summation part of $\mathbb{E}[M]$ by using Lemma 2.9:

$\displaystyle\sum_{m_{1}=0}^{r^{2}}\binom{\pi(m_{1}-1)+O(m_{1}^{\delta})}{k}$
(6.26) $\displaystyle=$
$\displaystyle\frac{1}{k!}\sum_{m_{1}=0}^{r^{2}}(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))\dots(\pi(m_{1}-1)+O((m_{1}-1)^{\delta})-(k-1)).$

Note we have

$\displaystyle(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))^{k}-\frac{k(k-1)}{2}(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))^{k-1}$
(6.27) $\displaystyle\ \ \leq\
(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))\dots(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}-(k-1))$
$\displaystyle\leq$ $\displaystyle(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))^{k}.$

We use Euler-Maclaurin to obtain upper and lower bounds. As the analysis is
similar to what we have done earlier, we omit the bounding of the error terms
and concentrate on the main term:

$\displaystyle\sum_{m_{1}=0}^{r^{2}}(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))^{k}$
$\displaystyle\ \approx\ $
$\displaystyle\int_{0}^{r^{2}}(\pi(m_{1}-1)+O((m_{1}-1)^{\delta}))^{k}\,dm$
(6.28) $\displaystyle{\rm We\ neglect\ the\ Big\ O\ term,\ as\ it\
doesn^{\prime}t}$ $\displaystyle{\rm affect\ the\ final\ calculation\ by\
much}$ $\displaystyle\approx$
$\displaystyle\pi^{k}\int_{0}^{r^{2}}(m_{1}-1)^{k}$ $\displaystyle{\rm After\
evaluating\ the\ integrals,\ we\ get}$ $\displaystyle\approx$
$\displaystyle\pi^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1}.$

Now that we’ve estimated the main term, we calculate $\mathbb{E}[M]$.

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ \approx\ $ $\displaystyle
r^{2}-\frac{1}{\binom{\pi r^{2}+O(r^{\delta})}{k}\cdot
k!}\cdot(\pi^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1})$ (6.29)
$\displaystyle\approx$ $\displaystyle r^{2}\ -\
\frac{\pi^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1}}{\pi^{k}\cdot(r^{2})^{k}}$
$\displaystyle\approx$ $\displaystyle
r^{2}\bigg{[}1-\frac{1}{k+1}\cdot(1-\frac{k+1}{r^{2}})\bigg{]}$
$\displaystyle\approx$ $\displaystyle r^{2}\cdot\frac{k}{k+1}+1,$

and thus

$\displaystyle\mathaccent 866{r}\ =\ \sqrt{\frac{k+1}{k}(m_{1}-1)}.$ (6.30)

######  Remark 6.4.

We analyze the formula from the discrete circle problem. The formula is quite
interesting, because we have a square root involved, and unlike other cases,
the continuous and discrete setting have different scaling factors. First, we
have the square root of $\mathbb{E}[M]$ which is a value similar to
$\sqrt{X^{2}+Y^{2}}$, and is similar to $r$. Also, the scaling factor for the
discrete case is $\sqrt{(k+1)/k}$, which is similar to $(2k+1)/(2k)$ as we
take the square root because taking the square root decreases the value by a
little bit. Though the formula doesn’t completely align with the continuous
circle, this formula makes a lot of sense, and the difference likely results
from the different statistics that we looked at for the discrete and
continuous circle.

####  6.2.2. Continuous Circle Problem

The continuous circle problem has similar conditions as the discrete circle
problem, but we can select any points contained in the circle; the points
don’t necessarily have to be lattice points. We approach the continuous circle
problem similarly as the continuous square problem. We look at
$m_{2}=\sqrt{X^{2}+Y^{2}}$ because that is the formula for the radius. Let
$m_{2}$ be the largest observed statistic, and $M$ the corresponding random
variable. Then

$\displaystyle{\rm Prob(\sqrt{X^{2}+Y^{2}}\leq m_{2})}\ =\
\frac{(m_{2}^{2}\pi)^{k}}{(r^{2}\pi)^{k}}\ =\ \frac{m_{2}^{2k}}{r^{2k}}.$
(6.31)

Thus

$\displaystyle{\rm PDF}_{M}(m_{2})\ =\ {\rm CDF}_{M}^{\prime}(m_{2})\ =\
\frac{2k\cdot m_{2}^{2k-1}}{r^{2k}}.$ (6.32)

The calculation for the expected value is the same as the continuous square,
so we omit it, and we find

$\displaystyle\mathaccent 866{r}\ =\ m_{2}\cdot\frac{2k+1}{2k}.$ (6.33)

######  Remark 6.5.

We compare the continuous circle formula to the discrete circle formula. They
don’t look similar, as the discrete formula has a square root. Note that
$m_{1}=m_{2}^{2}$, by the values of statistics we look at. Also, if we taylor
expand $\sqrt{1+1/k}$, we get $\sqrt{1+1/k}\ =\ 1+1/2k+\dots$. In the discrete
circle, as the value of $k$ gets very very large, the $\sqrt{1+1/k}$ looks
like $1+1/2k$, which is the formula for the continuous circle. Thus, though
the formulas look different, if we take the limit as $k$ gets large, we see
how similar these are.

We run some code to check the formula and see how well it does.

Figure 5. Code for discrete circle.

##  7\. Higher Dimension Version

###  7.1. Generalized Square Problem

####  7.1.1. Discrete Square Problem:

To calculate the formula for the discrete $L$-dimensional square, we use
similar strategies as the two dimensional square. We let $M$ be the the
largest observed coordinate. Thus

$\displaystyle{\rm Prob}(M=m)$ $\displaystyle\ =\ $ $\displaystyle
F(m)-F(m-1)$ (7.1) $\displaystyle=$
$\displaystyle\frac{\binom{m^{L}}{k}}{\binom{N^{L}}{k}}\ -\
\frac{\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}$ $\displaystyle=$
$\displaystyle\frac{\binom{m^{L}}{k}-\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}.$

The mean is thus

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}m\cdot{\rm PDF}_{M}(m)$
(7.2) $\displaystyle=$
$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}\frac{m\binom{m^{L}}{k}-m\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}$
$\displaystyle=$
$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}\frac{m\binom{m^{L}}{k}-(m-1)\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}\
-\
\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}\frac{\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N^{L}}{k}}\bigg{[}N\binom{N^{L}}{k}-(\lceil\sqrt[L]{k}\rceil)\binom{\lceil\sqrt[L]{k}\rceil)^{L}}{k}\bigg{]}\
-\
\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}\frac{\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}.$

We use Lemma 2.9 to bound the sums:

$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N}\binom{(m-1)^{L}}{k}$
$\displaystyle\ =\ $
$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N-1}\binom{m^{L}}{k}$ (7.3)
$\displaystyle=$
$\displaystyle\frac{1}{k!}\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N-1}(m^{L})(m^{L}-1)\cdots(m^{L}-(k-1)).$

We have

$\displaystyle m^{Lk}-\frac{k(k-1)}{2}m^{Lk-L}\ \leq\
(m^{L})(m^{L}-1)\cdots(m^{L}-(k-1)\ \leq\ m^{Lk}.$ (7.4)

We apply Euler-Maclaurin to the lower bound:

$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N-1}\bigg{[}m^{Lk}-\frac{k(k-1)}{2}m^{Lk-L}\bigg{]}$
(7.5) $\displaystyle=$
$\displaystyle\frac{(N-1)^{Lk+1}-(\lceil\sqrt[L]{k}\rceil)^{Lk+1}}{Lk+1}\ -\
\frac{k(k-1)}{2}\frac{(N-1)^{Lk-L+1}-(\lceil\sqrt[L]{k}\rceil)^{Lk-L+1}}{Lk-L+1}$
$\displaystyle+\ \frac{(N-1)^{Lk}+(\lceil\sqrt[L]{k}\rceil)^{Lk}}{2}\ -\
\frac{k(k-1)}{2}\frac{(N-1)^{Lk-L}+(\lceil\sqrt[L]{k}\rceil)^{Lk-L}}{2}$
$\displaystyle\ +\
\frac{1}{12}\bigg{[}Lk\cdot(N-1)^{Lk-1}-\frac{k(k-1)}{2}(Lk-L)(N-1)^{Lk-L-1}$
$\displaystyle\ -\ Lk\cdot(\lceil\sqrt[L]{k}\rceil)^{Lk-1}\ +\
\frac{k(k-1)}{2}\cdot(Lk-L)\cdot(\lceil\sqrt[L]{k}\rceil)^{Lk-1}\bigg{]}\ +\
R_{2}.$

We bound the remainder term:

$\displaystyle|R_{2}|$ $\displaystyle\ \leq\ $
$\displaystyle\frac{1}{12}\bigg{[}Lk\cdot(N-1)^{Lk-1}\ -\
\frac{k(k-1)}{2}\cdot(Lk-L)\cdot(N-1)^{Lk-L-1}$ (7.6) $\displaystyle\ -\
(Lk)(\lceil\sqrt[L]{k}\rceil)^{Lk-1}+\frac{k(k-1)}{2}(Lk-L)(\lceil\sqrt[L]{k}\rceil)^{Lk-L-1}\bigg{]}.$

Similarly we calculate the main term for the upper bound:

$\displaystyle\sum_{n=\lceil\sqrt[L]{k}\rceil}^{N-1}m^{Lk}$ (7.7)
$\displaystyle=$
$\displaystyle\frac{(N-1)^{Lk+1}-(\lceil\sqrt[L]{k}\rceil)^{Lk+1}}{Lk+1}\ +\
\frac{(N-1)^{Lk}+(\lceil\sqrt[L]{k}\rceil)^{Lk}}{2}$ $\displaystyle+\
\frac{1}{12}\bigg{[}Lk\cdot(N-1)^{Lk-1}-Lk\cdot(\lceil\sqrt[L]{k}\rceil)^{Lk-1}\bigg{]}\
+\ R_{2}.$

We bound the remainder term by

$\displaystyle|R_{2}|\ \leq\
\frac{1}{12}\bigg{[}Lk\cdot(N-1)^{Lk-1}-Lk\cdot(\lceil\sqrt[L]{k}\rceil)^{Lk-1}\bigg{]}.$
(7.8)

Now that we have fairly tight upper and lower bounds, we use the main term to
find an equation of $m$ in terms of $N$ and $k$. As we are only interested in
the case of $k$ fixed and $N$ tending to infinity, we can just keep the main
term in the analysis below. We find

$\displaystyle\sum_{m=\lceil\sqrt[L]{k}\rceil}^{N-1}m^{Lk}$ $\displaystyle\
\approx\ $
$\displaystyle\frac{(N-1)^{Lk+1}-(\lceil\sqrt[L]{k}\rceil)^{Lk+1}}{Lk+1}$
(7.9) $\displaystyle{\rm Because\ we\ assumed\ that\ k\ is\ fixed,\ if\ N\ is\
very\ large}$ $\displaystyle{\rm the\ term\ with\ k\ is\ negligible.}$
$\displaystyle\approx$ $\displaystyle\frac{(N-1)^{Lk+1}}{Lk+1}$

We plug this estimation back into the formula for $\mathbb{E}[M]$:

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\frac{N\binom{N^{L}}{k}\ -\
(\lceil\sqrt[L]{k}\rceil-1)\binom{(\lceil\sqrt[L]{k}\rceil-1)^{L}}{k}}{\binom{N^{L}}{k}}\
-\
\sum_{m=\lceil\sqrt[L]{k}\rceil}^{N}\frac{\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}$
(7.10) $\displaystyle{\rm We\ use\ the\ same\ argument\ as\ above}$
$\displaystyle{\rm to\ say\ that\ the\ term\ with\ k\ is\ negligible.}$
$\displaystyle\approx$ $\displaystyle N\ -\
\sum_{m=\lceil\sqrt[L]{k}\rceil}^{N}\frac{\binom{(m-1)^{L}}{k}}{\binom{N^{L}}{k}}$
$\displaystyle{\rm We\ plug\ in\ the\ estimate\ of\ the\ second\ term}$
$\displaystyle\approx$ $\displaystyle N\ -\
\frac{\frac{(N-1)^{Lk+1}}{Lk+1}}{\binom{N^{L}}{k}\cdot k!}$
$\displaystyle\approx$ $\displaystyle N\bigg{[}1\ -\
\frac{1}{Lk+1}\bigg{(}1-\frac{1}{N}\bigg{)}^{Lk+1}\bigg{]}$ $\displaystyle{\rm
We\ expand\ out\ the\ first\ two\ terms\ to\ estimate\ for\ (1-1/N)^{Lk+1}.}$
$\displaystyle{\rm If\ we\ use\ more\ terms,\ the\ accuracy\ slightly\
increases,\ but\ the\ equation}$ $\displaystyle{\rm will\ not\ be\
invertible.\ Thus,\ we\ only\ write\ the\ first\ two\ terms.}$
$\displaystyle\approx$ $\displaystyle
N\bigg{[}1-\frac{1}{Lk+1}\bigg{(}1-\frac{Lk+1}{N}\bigg{)}\bigg{]}$
$\displaystyle=$ $\displaystyle N\bigg{[}\frac{Lk}{Lk+1}\bigg{]}\ +\ 1$

Inverting the equation, we get

$\displaystyle\mathaccent 866{N}\ =\ \frac{Lk+1}{Lk}(m-1).$ (7.11)

####  7.1.2. Continuous Square Problem:

The continuous problem is easily generalized to $L$ dimensions. We select $k$
tuples of length $L$ and let $M$ be the largest observed component:

$\displaystyle{\rm Prob}(M\leq m)\ =\ \left(\frac{m^{L}}{N^{L}}\right)^{k}\ =\
\frac{m^{Lk}}{N^{Lk}}.$ (7.12) $\displaystyle{\rm PDF}_{M}(m)\ =\ {\rm
CDF}_{M}^{\prime}(m)\ =\ \frac{Lk\cdot m^{Lk-1}}{N^{Lk}}.$ (7.13)

Thus

$\displaystyle\mathbb{E}[M]\ =\ \int_{0}^{N}m\cdot\frac{Lk\cdot
m^{Lk-1}}{N^{Lk}}\,dm.$ (7.14)

We solve the integral and we get:

$\displaystyle\mathaccent 866{N}\ =\ m\cdot\frac{Lk+1}{Lk}.$ (7.15)

######  Remark 7.1.

We see that the scaling factors for the discrete $L$ dimensional square
continuous $L$ dimensional square are the same. This scaling factor makes
sense because if we have $L$ dimensions, we have many more components to
choose from. Thus by scaling by $(Lk+1)/(Lk)$, which is a value smaller than
$(2k+1)/(2k)$, and is close to 1, we get a good estimate for $N$.

###  7.2. Generalized Circle Problem

####  7.2.1. Discrete Circle Problem

: We look at the generalized $L$ dimensional circle problem. We study a
statistic similar to the two dimensional circle:

$\displaystyle X_{1}^{2}+X_{2}^{2}+\cdots+X_{L}^{2}\ =\ m_{1}$ (7.16)

We see that all values of $m_{1}$ are integers. Using this statistic, we end
up estimating for $r^{2}$, so after getting the formula, we have to take the
square root of $m_{1}$ to get a estimation for $r$. Let $P(r)$ be the number
of lattice points inside an $L$-ball, a $L$-dimensional sphere with radius
$r$. We use the volume of the $L$-ball to find a approximate value for the
number of lattice points inside the $L$-ball. The formula for the volume of a
$L$\- ball is [Gi]

$\displaystyle V(n)\ =\ \frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}.$
(7.17)

We use this formula to find $P(r)$. We denote the bounds with big O notation.

$\displaystyle P(r)\ =\ \frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\
+\ O(r^{\delta}).$ (7.18)

We now calculate the density using the CDF method.

$\displaystyle{\rm PDF}_{M_{m_{1}}}\ =\ P(m_{1})-P(m_{1}-1).$ (7.19)

We calculate the expected value

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{1}=0}^{r^{2}}m_{1}\cdot{\rm Prob}(M=m_{1})$ (7.20)
$\displaystyle=$
$\displaystyle\frac{\sum_{m_{1}=0}^{r^{2}}m_{1}\cdot\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}m_{1}\
+\
O(m_{1}^{\delta})}{k}-\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\
O((m_{1}-1)^{\delta})}{k}}{{\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\
+\ O(r^{\delta})}{k}}}$ $\displaystyle=$
$\displaystyle\frac{1}{{\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\
+\
O(r^{\delta})}{k}}}\sum_{m_{1}=0}^{r^{2}}\bigg{[}m_{1}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}m_{1}\
+\ O(m_{1}^{\delta})}{k}$ $\displaystyle\ \ -\
(m_{1}-1)\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\ +\
O((m_{1}-1)^{\delta})}{k}\bigg{]}$ $\displaystyle\ -\
\frac{1}{{\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\ +\
O(r^{\delta})}{k}}}\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}$ $\displaystyle{\rm We\ telescope\ and\ get}$
$\displaystyle=$ $\displaystyle r^{2}\ -\
\frac{1}{{\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\ +\
O(r^{\delta})}{k}}}\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}.$

We calculate the summation part.

$\displaystyle\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}$ (7.21) $\displaystyle=$
$\displaystyle\frac{1}{k!}\sum_{m_{1}=0}^{r^{2}}\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})\bigg{)}\dots$ $\displaystyle\
\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\ +\
O((m_{1}-1)^{\delta})-(k-1)\bigg{)}.$

We use Lemma 2.9 to set bounds.

$\displaystyle\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}^{k}$ (7.22) $\displaystyle\
-\frac{k(k-1)}{2}\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}^{k-1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{k!}\sum_{m_{1}=0}^{r^{2}}\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})\bigg{)}$ $\displaystyle\
\dots\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\ +\
O((m_{1}-1)^{\delta})-(k-1)\bigg{)}$ $\displaystyle\leq$
$\displaystyle\sum_{m_{1}=0}^{r^{2}}\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})}{k}^{k}.$

We apply Euler-Maclaurin to both bounds. We omit the calculation here, and
just show the approximation using the main term.

$\displaystyle\sum_{m_{1}=0}^{r^{2}}\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})\bigg{)}^{k}$ $\displaystyle\ \approx\ $
$\displaystyle\int_{0}^{r^{2}}\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\
+\ O((m_{1}-1)^{\delta})\bigg{)}^{k}\,dm_{1}$ (7.23) $\displaystyle{\rm We\
neglect\ the\ Big\ O\ term}$ $\displaystyle\approx$
$\displaystyle\int_{0}^{r^{2}}\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}(m_{1}-1)\bigg{)}^{k}\,dm_{1}$
$\displaystyle\approx\ $
$\displaystyle\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}\bigg{)}^{k}\cdot\frac{(r^{2}-1)^{k+1}-(-1)^{k+1}}{k+1}$
$\displaystyle\approx$
$\displaystyle\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}\bigg{)}^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1}.$

We calculate the expected value.

$\displaystyle\mathbb{E}[M]$ $\displaystyle\ =\ $ $\displaystyle r^{2}\ -\
\frac{1}{k!\binom{\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}\ +\
O(r^{\delta})}{k}}\cdot\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}\bigg{)}^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1}$
(7.24) $\displaystyle\approx$ $\displaystyle r^{2}\ -\
\frac{1}{\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}\bigg{)}^{k}\cdot
r^{2k}}\cdot\bigg{(}\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}\bigg{)}^{k}\cdot\frac{(r^{2}-1)^{k+1}}{k+1}$
$\displaystyle\approx$ $\displaystyle r^{2}\ -\
\frac{1}{k+1}\cdot\frac{(r^{2}-1)^{k+1}}{r^{2k}}$ $\displaystyle\approx$
$\displaystyle
r^{2}\bigg{[}1-\frac{1}{k+1}\bigg{(}1-\frac{1}{r^{2}}\bigg{)}^{k+1}\bigg{]}$
$\displaystyle{\rm We\ use\ the\ first\ two\ terms\ of\ the\ binomial\
expansion}$ $\displaystyle\approx$ $\displaystyle
r^{2}\bigg{[}1-\frac{1}{k+1}\bigg{(}1-\frac{k+1}{r^{2}}\bigg{)}\bigg{]}$
$\displaystyle\approx$ $\displaystyle r^{2}\cdot\frac{k}{k+1}+1.$

We invert the relationship to get

$\displaystyle\mathaccent 866{r}\ =\ \sqrt{(m_{1}-1)\cdot\frac{k+1}{k}}.$
(7.25)

######  Remark 7.2.

Notice that the formula for discrete $L$-dimensional circle problem isn’t
dependent on $N$.

####  7.2.2. Continuous $L$-dimensional circle problem

We select $k$ tuples of length $L$ where each component is contained in the
$L$-dimensional circle. Let $m$ be the largest observed component. We look at
$m_{2}=\sqrt{X_{1}^{2}\ +\ X_{2}^{2}\ +\cdots+X_{L}^{2}}$ as out statistic. We
use the volume of the $L^{th}$ dimensional circle to calculate the PDF. Recall
the formula of the $L$-ball. We see that

$\displaystyle V(n)\ =\ \frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L}.$
(7.26)

We calculate the CDF:

$\displaystyle{\rm Prob}(\sqrt{X_{1}^{2}\ +\ X_{2}^{2}\ +\cdots+X_{L}^{2}}\leq
m_{2})\ =\
\frac{(\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}m_{2}^{L})^{k}}{(\frac{\pi^{\frac{L}{2}}}{\Gamma(\frac{L}{2}+1)}r^{L})^{k}}\
=\ \frac{m_{2}^{Lk}}{r^{Lk}}.$ (7.27)

The rest of the calculation is identical as the $L$-dimensional square
problem. Thus, we omit the calculation. After calculating, we get:

$\displaystyle\hat{r}\ =\ m_{2}\cdot\frac{Lk+1}{Lk}.$ (7.28)

######  Remark 7.3.

Notice that the L dependence in the formula is very small as the formula is
$1+1/Lk$ and if L and k are reasonably large, then the scaling factor is very
very close to 1.

##  8\. Acknowledgements

I, Anthony Lee, was the student and this research was mentored by Professor
Steven J Miller. I truly thank Professor Miller for this research opportunity,
the research topic, and his continued hard work in making the research process
very intriguing and smooth. I also thank my parents and teachers who have been
very supportive and encouraging about my studies.

##  Appendix A Basic Probability Review

###  A.1. Variance and Covariance

######  Lemma A.1.

The variance of a random variable satisfies

$\displaystyle{\rm Var}(X)\ :=\ \mathbb{E}[(X-\mathbb{E}[X])^{2}]\ =\
\mathbb{E}[X^{2}]\ -\ \mathbb{E}[X]^{2}.$ (A.1)

###### Proof.

$\displaystyle{\rm Var}(X)$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[(X-\mathbb{E}[X])^{2}]$ (A.2) $\displaystyle=$
$\displaystyle\mathbb{E}[X^{2}\ -\ 2X\ \mathbb{E}[X]\ +\ \mathbb{E}[X]^{2}]$
$\displaystyle=$ $\displaystyle\mathbb{E}[X^{2}]\ -\ 2\
\mathbb{E}[X]\mathbb{E}[X]\ +\ \mathbb{E}[X]^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}[X^{2}]\ -\ \mathbb{E}[X]^{2}.$

∎

######  Lemma A.2.

The covariance of two random variables satisfies

$\displaystyle{\rm Cov}(X,Y)\ =\
\mathbb{E}[X-\mathbb{E}[X]]\cdot\mathbb{E}[Y-\mathbb{E}[Y]]\ =\
\mathbb{E}[XY]\ -\ \mathbb{E}[X]\mathbb{E}[Y].$ (A.3)

###### Proof.

We use the linearity properties of the expected values. We have

$\displaystyle{\rm Cov}(X,Y)$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[X-\mathbb{E}[X]]\cdot\mathbb{E}[Y-\mathbb{E}[Y]]$
(A.4) $\displaystyle=$ $\displaystyle\mathbb{E}[XY\ -\ X\cdot\mathbb{E}[Y]\ -\
Y\cdot\mathbb{E}[X]\ +\ \mathbb{E}[X]\mathbb{E}[Y]]$ $\displaystyle=$
$\displaystyle\mathbb{E}[XY]\ -\ \mathbb{E}[X]\cdot\mathbb{E}[Y]\ -\
\mathbb{E}[X]\cdot\mathbb{E}[Y]\ +\ \mathbb{E}[X]\mathbb{E}[Y]$
$\displaystyle=$ $\displaystyle\mathbb{E}[XY]\ -\
\mathbb{E}[X]\cdot\mathbb{E}[Y].$

∎

###  A.2. Identities from Pascal’s Triangle

######  Lemma A.3.

(Pascal’s Identity) We have

$\displaystyle\binom{n+1}{r}\ =\ \binom{n}{r}\ +\ \binom{n}{r-1}.$ (A.5)

###### Proof.

Pascal’s identity can be proved directly by expanding out the factorials, but
it can also be proved by story. Say we have $n+1$ people and we want to select
$k$ of them. Designate one person as special and the other $n$ as ordinary.
There are two cases: we select the special person, in which case we need $k-1$
additional people all drawn from the $n$ ordinary people, or we do not select
the special person and now need $k$ ordinary people. As these are mutually
exclusive the number of ways, $\binom{n+1}{k}$, is equal to the sum:
${1\choose 1}{n\choose k-1}+{1\choose 0}{n\choose k}$. ∎

######  Lemma A.4.

(Hockey Stick Identity) We have

$\displaystyle\sum_{i=r}^{n}\binom{i}{r}\ =\ \binom{n+1}{r+1}.$ (A.6)

We can prove the hockey stick identity using induction and Pascal’s identity.

###### Proof.

Base case: $n=r$

$\displaystyle\binom{r}{r}\ =\ \binom{r+1}{r+1}\ =\ 1.$ (A.7)

Inductive step: Assume it is true for $n=k$:

$\displaystyle\sum_{i=r}^{n}\binom{i}{r}\ =\ \binom{n+1}{r+1}.$ (A.8)

Using our assumption, we prove the case where $n=k+1$:

$\displaystyle\sum_{i=r}^{n+1}\binom{i}{r}\ =\ \binom{n+2}{r+1}.$ (A.9)

We rewrite the left hand side to facilitate using the inductive hypothesis:

$\displaystyle\sum_{i=r}^{n+1}\binom{i}{r}$ $\displaystyle\ =\ $
$\displaystyle\sum_{i=r}^{n}\binom{i}{r}\ +\ \binom{n+1}{r}$ (A.10)
$\displaystyle{\rm We\ use\ our\ inductive\ hypothesis}$ $\displaystyle=$
$\displaystyle\binom{n+1}{r+1}\ +\ \binom{n+1}{r}$ $\displaystyle=$
$\displaystyle\binom{n+2}{r+1}$ $\displaystyle{\rm We\ use\ Pascal^{\prime}s\
identity,\ and\ thus}$ $\displaystyle{\rm we^{\prime}ve\ proved\ the\ hockey\
stick\ identity}.$

∎

##  Appendix B Portfolio Theory

Consider the case of two stock $X_{1},X_{2}$ with the same mean return and
variances $\sigma_{1}$ and $\sigma_{2}$; the variances are not necessarily the
same. For simplicity we assume the two stocks’ performances are independent of
each other, though in general we need to consider covariances. We construct a
weighted portfolio $X_{\alpha}:=\alpha X_{1}+(1-\alpha)X_{2}$, with
$\alpha\in[0,1]$. It is easy to see that the expected value of $X_{\alpha}$ is
that of the two stocks; our goal is to find $\alpha$ that minimizes the
variance of $X_{\alpha}$ and thus gives us the most certainty in knowing our
future performance. Of course, such a strategy decreases the possibility of
getting a much larger than expected return, but it also minimizing the
possibility of having a significantly smaller return.

Let’s say we have two options. The first is we are guaranteed $500,000. The
second is we have a 50% chance of getting $1,000,000, and a 50% chance of
getting $0 dollars. The expected value for both is $500,000 dollars. Though it
may depend on each person’s financial situation, we see that taking the
$500,000 dollars has no risk. For some, this may be life changing (and the
marginal utility of the second $500,000 is almost surely less than the first).

The hypothetical situation above is a simple example of modern portfolio
theory, a practical method for selecting investments where we maximize the
overall return with an acceptable level of risk. This theory was pioneered by
American economist Harry Markowitz; see [In]. A key idea of this theory is
diversification. Because most investments are either high risk and high return
or low risk and low return, Markowitz argued that perhaps investors could
achieve best profit with acceptable risk by choosing an optimal mix of the
investments.

The expected return of the portfolio is calculated as a weighted sum of the
return of individual assets. Let’s say that we have four assets with different
values of expected return. To calculate the risk of the portfolio, an investor
needs to know the variances of each assets and also the correlation of any two
assets, so six correlation values in total. Because of the asset correlations,
the total portfolio risk is lower than what would be calculated by a weighted
sum.

We return to the simple case of two stocks both with mean $\mu$, variances
$\sigma_{i}$ (we may assume $0\leq\sigma_{2}\leq\sigma_{1}$) and we assume the
two stocks are independent. Then if $X_{\alpha}=\alpha X_{1}+(1-\alpha)X_{2}$
we have

$\displaystyle{\rm Var}(X_{\alpha})\ =\
\alpha^{2}\sigma_{1}^{2}+(1-\alpha)^{2}\sigma_{2}^{2}.$ (B.1)

To find the minimum variance we check the endpoints ($\alpha=0$ or 1) and the
critical points from the derivative of the variance is zero: that happens when

$2\alpha\sigma_{1}^{2}-2(1-\alpha)\sigma_{2}^{2}\ =\ 0,$ (B.2)

which gives a critical value of

$\alpha_{\ast}\ =\ \frac{\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}$ (B.3)

We now see which value of alpha gives the minimum variance.

  * •

When $\alpha=0$ , ${\rm Var}(X_{\alpha})\ =\ \sigma_{2}^{2}$

  * •

When $\alpha=1$ , ${\rm Var}(X_{\alpha})\ =\ \sigma_{1}^{2}$

  * •

When $\alpha=\frac{\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}$ ,

$\displaystyle{\rm Var}(X_{\alpha})$ $\displaystyle\ =\ $
$\displaystyle\bigg{(}\frac{\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}\bigg{)}^{2}\sigma_{1}^{2}\
+\
\bigg{(}1-\frac{\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}\bigg{)}^{2}\sigma_{2}^{2}$
(B.4) $\displaystyle=$
$\displaystyle\bigg{(}\frac{\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}\bigg{)}^{2}\sigma_{1}^{2}\
+\
\bigg{(}\frac{\sigma_{1}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}\bigg{)}^{2}\sigma_{2}^{2}$
$\displaystyle=$
$\displaystyle\frac{\sigma_{1}^{2}\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{2}^{2})}{(\sigma_{1}^{2}+\sigma_{2}^{2})^{2}}$
$\displaystyle=$
$\displaystyle\frac{\sigma_{1}^{2}\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}$

From our assumption that $0<\sigma_{2}\leq\sigma_{1}$, we see that
$\sigma_{2}^{2}\leq\sigma_{1}^{2}$. Now, we compare
$\frac{\sigma_{1}^{2}\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}$ and
$\sigma_{2}^{2}$.

Straightforward algebra shows

$\displaystyle\frac{\sigma_{1}^{2}\sigma_{2}^{2}}{\sigma_{1}^{2}+\sigma_{2}^{2}}$
$\displaystyle\ <\ $ $\displaystyle\sigma_{2}^{2};$ (B.5)

to see this multiply both sides by $\sigma_{1}^{2}+\sigma_{2}^{2}$, and
subtract $\sigma_{1}^{2}\sigma_{2}^{2}$ and obtain $0<\sigma_{2}^{4}$. Thus
the variance of the weighted quantity is always less than the variance of the
smaller one! If the two variances are equal, the new variance is half of that.

Our German Tank problem is slightly different, as the probability we choose
certain tanks is dependent on each other. For example, one condition that we
have is that the largest has to be a larger value than the second largest
tank, which makes them dependent. We see if we can apply this motivation of
using weights to see if we can reduce variance of the outcome even in two
dependent random variables.

##  Appendix C Proof of Identities

###### Proof.

Identity I.

$\displaystyle\sum_{m_{k}=k}^{N}\binom{m-b}{k-c}$ $\displaystyle\ =\ $
$\displaystyle\binom{k-b}{k-b}\ +\ \binom{k-b+1}{k-b}\ +\ \cdots\ +\
\binom{N-b}{k-c}$ (C.1) $\displaystyle=$ $\displaystyle\binom{k-c}{k-c}\ +\
\binom{k-c+1}{k-c}\ +\ \cdots\ +\ \binom{N-b}{k-c}$ $\displaystyle\ \ \
-\left[\binom{k-c}{k-c}\ +\ \binom{k-c+1}{k-c}\ +\ \cdots\ +\
\binom{k-b-1}{k-c}\right]$ $\displaystyle=$
$\displaystyle\binom{N-b+1}{k-c+1}\ -\ \binom{k-b}{k-c+1}.$

∎

###### Proof.

Identity II.

$\displaystyle\sum_{m=k-a+1}^{N-a+1}m\frac{\binom{m-1}{k-a}\binom{N-m}{a-1}}{\binom{N}{k}}$
$\displaystyle\ =\ $
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m=k-a+1}^{N-a+1}m\cdot\binom{m-1}{k-a}\binom{N-m}{a-1}$
(C.2) $\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m=k-a+1}^{N-a+1}\frac{m!}{(k-a)!(m-k+a-1)!}\cdot\frac{(N-m)!}{(a-1)!(N-m-a+1)!}$
$\displaystyle=$
$\displaystyle\frac{k-a+1}{\binom{N}{k}}\cdot\sum_{m=k-a+1}^{N-a+1}\binom{m}{k-a+1}\cdot\binom{N-m}{a-1}$
$\displaystyle{\rm We\ use\ Identity\ IV}$ $\displaystyle=$
$\displaystyle\frac{(N+1)(k-a+1)}{k+1}$

∎

###### Proof.

Identity III.

$\displaystyle\sum_{m=k-a+1}^{N-a+1}m^{2}\frac{\binom{m-1}{k-a}\binom{N-m}{a-1}}{\binom{N}{k}}$
$\displaystyle\ =\ $
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m=k-a+1}^{N-a+1}(m+1)m\binom{m-1}{k-a}\binom{N-m}{a-1}$
(C.3) $\displaystyle\ \ \ \ -\
\frac{1}{\binom{N}{k}}\sum_{m=k-a+1}^{N-a+1}m\binom{m-1}{k-a}\binom{N-m}{a-1}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m=k-a+1}^{N-a+1}\frac{(m+1)!}{(k-a)!(m-k+a-1)!}\binom{N-m}{a-1}$
$\displaystyle\ \ \ \ \ -\ \frac{(N+1)(k-a+1)}{k+1}$ $\displaystyle=$
$\displaystyle\frac{(k-a+1)(k-a+2)(N+2)(N+1)}{(k+2)(k+1)}$ $\displaystyle\ \ \
\ -\ \frac{(N+1)(k-a+1)}{k+1}$

∎

###### Proof.

Identity IV.

$\displaystyle\binom{a+b+k+1}{a+b+1}\ $ $\displaystyle=$ $\displaystyle\
\sum_{i=0}^{k}\binom{a+i}{a}\binom{b+k-i}{b}.$ (C.4)

We use proof by strong induction to prove the identity. Case where $k=0$:

$\displaystyle\binom{a+b+1}{a+b+1}\ =\ \binom{a}{a}\binom{b}{b}\ =\ 1$ (C.5)

Case where k=1:

$\displaystyle\binom{a+b+2}{a+b+1}\ =\ \binom{a}{a}\binom{b+1}{b}\ +\
\binom{a+1}{a}\binom{b}{b}\ =\ a+b+2.$ (C.6)

We continue through all k until $k=k$ and we assume that the case where $k=k$
is true. We use this assumption to prove that the case works for $(k+1)$. We
add all the equations when $k=k$ to when $k=1$. We write the sum of equations
as the following.

$\displaystyle\binom{a}{a}\binom{b+k}{b}\ +\ \binom{a+1}{a}\binom{b+k-1}{b}\
+\ \cdots+\ \binom{a+k}{a}\binom{b}{b}\ =\ \binom{a+b+k+1}{a+b+1}.$ (C.7)
$\displaystyle\binom{a}{a}\binom{b+k-1}{b}\ +\ \binom{a+1}{a}\binom{b+k-2}{b}\
+\ \cdots+\ \binom{a+k-1}{a}\binom{b}{b}\ =\ \binom{a+b+k}{a+b+1}.$ (C.8)
$\displaystyle\binom{a}{a}\binom{b+k-2}{b}\ +\ \binom{a+1}{a}\binom{b+k-3}{b}\
+\ \cdots+\ \binom{a+k-2}{a}\binom{b}{b}\ =\ \binom{a+b+k-1}{a+b+1}.$ (C.9)
$\displaystyle\binom{a}{a}\binom{b+1}{b}\ +\ \binom{a+1}{a}\binom{b}{b}\ =\
\binom{a+b+2}{a+b+1}.$ (C.10) $\displaystyle\binom{a}{a}\binom{b}{b}\ =\
\binom{a+b+1}{a+b+1}.$ (C.11)

We add all the columns.

$\displaystyle\binom{a}{a}\binom{b+k}{b}\ +\ \binom{a+1}{a}\binom{b+k-1}{b}$
(C.12) $\displaystyle\ +\ \cdots\ +\ \binom{a+k}{a}\binom{b}{b}$
$\displaystyle=$ $\displaystyle\ \binom{a+b+k+2}{a+b+2}.$

The resulting equation is the equation in the $(k+1)$ case. Since we assumed
by strong induction that cases when $k=1$ to $k=k$ is all true, we are able to
prove that the $(k+1)$ case is true. Therefore, the identity is proved. ∎

##  Appendix D Calculations

###  D.1. Formula for $L\textsuperscript{th}$ largest tank

We state the calculation for the estimation formula using the
$L\textsuperscript{th}$ largest tank.

$\displaystyle{\rm Prob}(M_{k-L+1}=m_{k-L+1})\ =\
\frac{\binom{m_{k-L+1}-1}{k-L}\binom{N-m_{k-1}}{L-1}}{\binom{N}{k}}.$ (D.1)

We calculate the expected value of $M_{k-L+1}$.

$\displaystyle\mathbb{E}[M_{k-L+1}]$ $\displaystyle\ =\ $
$\displaystyle\sum_{m_{k-L+1}=k-L+1}^{N-L+1}m_{k-L+1}{\rm Prob}(M_{k-L+1}\ =\
m_{k-L+1})$ (D.2) $\displaystyle=$
$\displaystyle\sum_{m_{k-L+1}=k-L+1}^{N-L+1}m_{k-L+1}\frac{\binom{m_{k-L+1}-1}{k-L}\binom{N-m_{k-L+1}}{L-1}}{\binom{N}{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m_{k-L+1}=k-1}^{N-L+1}\frac{k-L+1}{k-L+1}\frac{m_{k-L+1}!}{(k-L)!(m_{k-L+1}-k+L-1)!}\binom{N-m_{k-1}}{L-1}$
$\displaystyle=$
$\displaystyle\frac{k-L+1}{\binom{N}{k}}\sum_{m_{k-L+1}=k-L+1}^{N-L+1}\frac{m_{k-L+1}!}{(k-L+1)!(m_{k-L+1}-k+L-1)!}\binom{N-m_{k-1}}{L-1}$
$\displaystyle=$
$\displaystyle\frac{k-L+1}{\binom{N}{k}}\sum_{m_{k-L+1}=k-L+1}^{N-L+1}\binom{m_{k-L+1}}{k-L+1}\binom{N-m_{k-L+1}}{L-1}$
$\displaystyle{\rm We\ use\ Identity\ IV}$ $\displaystyle=$
$\displaystyle\frac{k-L+1}{\binom{N}{k}}\binom{N+1}{k+1}$ $\displaystyle=$
$\displaystyle(N+1)\frac{k-L+1}{k+1}.$

Therefore, the formula for $N$ in terms of $m$ and $k$ is

$\displaystyle N\ =\ m_{k-L+1}\frac{k+1}{k-L+1}\ -\ 1.$ (D.3)

######  Remark D.1.

We see that when $L=1$, the case where we observe the largest tank, we get the
original German Tank problem formula. Also, notice that as we observe smaller
and smaller tanks, the scaling factor increases.

###  D.2. Variance calculation for $m_{k-1}$ in discrete one dimensional case

We start by calculating the variance of $m_{k-1}$

$\displaystyle{\rm Var}(M_{k-1})$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[M_{k-1}^{2}]\ -\ \mathbb{E}[M_{k-1}]^{2}$ (D.4)
$\displaystyle=$ $\displaystyle\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}^{2}{\rm
Prob(M_{k-1}=m_{k-1})}\ -\ \bigg{[}\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}{\rm
Prob(M_{k-1}=m_{k-1})}\bigg{]}^{2}$ $\displaystyle{\rm We\ know\ the\ second\
term\ so\ we\ just\ calculate\ the\ first\ term.}$ $\displaystyle=$
$\displaystyle\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}^{2}\frac{\binom{m_{k-1}-1}{k-2}(N-m_{k-1})}{\binom{N}{k}}\
-\ \frac{(N+1)^{2}(k-1)^{2}}{{k+1}^{2}}.$

We take out the first term and calculate it separately. We expand the binomial
coefficients, and regroup terms, so that we can use our identities.

$\displaystyle\sum_{m_{k-1}=k-1}^{N-1}m_{k-1}^{2}\frac{\binom{m_{k-1}-1}{k-2}(N-m_{k-1})}{\binom{N}{k}}$
(D.5) $\displaystyle=$
$\displaystyle\sum_{m_{k-1}=k-1}^{N-1}(m_{k-1})(m_{k-1}+1)\frac{\binom{m_{k-1}-1}{k-2}\binom{N-m_{k-1}}{1}}{\binom{N}{k}}$
$\displaystyle\
-\sum_{m_{k-1}=k-1}^{N-1}(m_{k-1})\frac{\binom{m_{k-1}-1}{k-2}\binom{N-m_{k-1}}{1}}{\binom{N}{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{k(k-1)}{k(k-1)}\frac{(m_{k-1}+1)!}{(k-2)!(m_{k-1}-k+1)!}\binom{N-m_{k-1}}{1}\
$ $\displaystyle\ \ \ -\
\frac{1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{k-1}{k-1}\frac{m_{k-1}!}{(k-2)!(m_{k-1}-k+1)!}\binom{N-m_{k-1}}{1}$
$\displaystyle=$
$\displaystyle\frac{k(k-1)}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{(m_{k-1}+1)!}{k!(m_{k-1}-k+1)!}\binom{N-m_{k-1}}{1}\
$ $\displaystyle\ \ \ -\
\frac{k-1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\frac{m_{k-1}!}{(k-1)!(m_{k-1}-k+1)!}\binom{N-m_{k-1}}{1}$
$\displaystyle=$
$\displaystyle\frac{k(k-1)}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\binom{m_{k-1}+1}{k}\binom{N-m_{k-1}}{1}\
$ $\displaystyle\ \ \ -\
\frac{k-1}{\binom{N}{k}}\sum_{m_{k-1}=k-1}^{N-1}\binom{m_{k-1}}{k-1}\binom{N-m_{k-1}}{1}$
$\displaystyle{\rm We\ use\ Identity\ IV\ to\ simplify}$ $\displaystyle=$
$\displaystyle\frac{k(k-1)}{\binom{N}{k}}\cdot\binom{N+2}{k+2}\ -\
\frac{k-1}{\binom{N}{k}}\binom{N+1}{k+1}$

We calculate all terms now.

$\displaystyle{\rm Var}(M_{k-1})$ $\displaystyle\ =\ $
$\displaystyle\frac{(k)(k-1)(N+1)(N+2)}{(k+1)(k+2)}\ -\
\frac{(N+1)(k-1)}{k+1}\ -\ \frac{(N+1)^{2}(k-1)^{2}}{(k+1)^{2}}$ (D.6)
$\displaystyle=$ $\displaystyle\frac{2(k-1)(N-k)(N+1)}{(k+1)^{2}(k+2)}.$

We scale the variance of $X_{k-1}\ =\ m_{k-1}(k+1)/(k-1):$

$\displaystyle{\rm Var}(X_{k-1})$ $\displaystyle\ =\ $ $\displaystyle{\rm
Var}(M_{k-1})\cdot\frac{(k+1)^{2}}{(k-1)^{2}}$ (D.7) $\displaystyle=$
$\displaystyle\frac{2(k-1)(N-k)(N+1)}{(k+1)^{2}(k+2)}\cdot\frac{(k+1)^{2}}{(k-1)^{2}}$
$\displaystyle=$ $\displaystyle\frac{2(N-k)(N+1)}{(k+2)(k-1)}.$

###  D.3. Continuous Weighted Problem

: In this subsection, we include the calculation of the weighted problem in
the continuous case. Let $X$ be the value between 0 and $N$. We use the same
motivation from portfolio theory and see if we can apply the idea here of
seeing if we can decrease variance by optimizing the two weights.

####  D.3.1. Formulas using $m_{k}$ and $m_{k-1}$

Because we are in the continuous case, we use the CDF method where we take the
derivative of the CDF. We use integrals instead of sums.

$\displaystyle{\rm CDF}_{M}(X)\ =\ {\rm Prob}(M_{k-1}\leq X)\ =\
(\frac{X}{N})^{k}$ (D.8) $\displaystyle f_{X}(x)\ =\ {\rm PDF}_{M}(X)\ =\ {\rm
CDF}_{M}(X)^{\prime}\ =\ \frac{kX^{k-1}}{N^{k}}$ (D.9)
$\displaystyle\mathbb{E}[X]\ =\ \int_{0}^{N}Xf(X)\,dX\ =\
\int_{0}^{N}\frac{kX^{k}}{N^{k}}\,dX\ =\ \frac{kN^{k+1}}{(k+1)N^{k}}.$ (D.10)
$\displaystyle m_{k}\ =\ \frac{k}{k+1}N$ (D.11) $\displaystyle N\ =\
m_{k}(\frac{k+1}{k}).$ (D.12)

Through similar calculations, we can get the formula of estimation using
$m_{k-1}$.

$\displaystyle N\ =\ m_{k-1}(\frac{k+1}{k-1}).$ (D.13)

####  D.3.2. Variance of $m_{k}$ and $m_{k-1}$

:

$\displaystyle{\rm Var}(m_{k})$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[X_{k}^{2}]\ -\ \mathbb{E}[X_{k}]^{2}$ (D.14)
$\displaystyle=$ $\displaystyle\int_{0}^{N}X^{2}f(X)\,dX\ -\
\Bigg{[}\int_{0}^{N}Xf(X)\,dX\Bigg{]}^{2}$ $\displaystyle=$
$\displaystyle\int_{0}^{N}\frac{kX^{k+1}}{N^{k}}\,dX\ -\ (\frac{kN}{k+1})^{2}$
$\displaystyle=$ $\displaystyle\frac{kN^{2}}{(k+1)^{2}(k+2)}.$

We scale the variance of $m_{k}$ to get the variance of $X_{k}$ by multiplying
$(k+1)^{2}/k^{2}$.

$\displaystyle{\rm Var}(X_{k})\ =\ \frac{N^{2}}{(k+2)k}.$ (D.15)

After going through very similar calculations, we get the variance of
$X_{k-1}$. We won’t write the full calculation.

$\displaystyle{\rm Var}(X_{k-1})\ =\ \frac{2N^{2}}{(k+2)(k-1)}.$ (D.16)

####  D.3.3. Covariance term

We calculate the covariance term using Lemma 2.4. Again, we use integrals
instead of sums, as we are in the continuous setting.

$\displaystyle{\rm Cov}(X_{k},X_{k-1})$ $\displaystyle\ =\ $
$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]\ -\
\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}]$ $\displaystyle=$
$\displaystyle\frac{(k+1)^{2}}{k(k-1)}\mathbb{E}[m_{k}\cdot m_{k-1}]\ -\
\frac{(k+1)^{2}}{k(k-1)}\mathbb{E}[m_{k}]\cdot\mathbb{E}[m_{k-1}].$

We calculate term by term.

$\displaystyle\mathbb{E}[m_{k}\cdot m_{k-1}]\ =\
\int_{0}^{N}\int_{0}^{m_{k}}m_{k}m_{k-1}({\rm Prob\ M_{k}\ =\ m_{k},\
M_{k-1}=m_{k-1}})\,dm_{k-1}\,dm_{k}.$ (D.17)

To calculate this term, we have to use the joint probability density function.
After choosing $m_{k}$ and $m_{k-1}$, the rest of $(k-2)$ tanks have to be
smaller than $m_{k-1}$, the probability is ${m_{k-1}^{k-2}}/{N^{k}}$. Also,
note that we multiply the probability by $\binom{k}{2}$ and also by 2 because
the tanks aren’t ordered. But, we know that $m_{k}$ must be larger than
$m_{k-1}$. Therefore, we multiply by 2.

$\displaystyle\mathbb{E}[m_{k}\cdot m_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle
2\binom{k}{2}\int_{0}^{N}\int_{0}^{m_{k}}m_{k}m_{k-1}\frac{m_{k-1}^{k-2}}{N^{k}}\,dm_{k-1}\,dm_{k}$
(D.18) $\displaystyle\ {\rm After\ calculating\ this\ integral,\ we\ get:}$
$\displaystyle=$ $\displaystyle\frac{N^{2}(k)(k-1)}{k(k+2)}.$

We scale $\mathbb{E}[m_{k}\cdot m_{k-1}]$ to get $\mathbb{E}[X_{k}\cdot
X_{k-1}]$

$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]\ =\
\frac{N^{2}(k+1)^{2}}{k(k+2)}.$ (D.19)

We know that

$\displaystyle\mathbb{E}[X_{k}]\cdot\mathbb{E}[X_{k-1}]\ =\ N^{2}.$ (D.20)

Therefore, we calculate the full covariance term.

$\displaystyle\mathbb{E}[X_{k}\cdot X_{k-1}]$ $\displaystyle\ =\ $
$\displaystyle\Bigg{[}\frac{N^{2}(k+1)^{2}}{k(k+2)}-1\Bigg{]}$ (D.21)
$\displaystyle=$ $\displaystyle\frac{N^{2}}{k(k+2)}.$

Now that we have the variances of $X_{k}$ and $X_{k-1}$ and covariance of
$X_{k}$ and $X_{k-1}$, we plug them into the formula we used for the discrete
weighted sum case.

####  D.3.4. Finding optimal alpha

: Recall the weighted statistic. We state the weighted statistic. Let
$\alpha\in[0,1]$ and define the weighted statistic $X_{\alpha}$ by

$\displaystyle X_{\alpha}\ :=\ \alpha X_{k}\ +\ (1-\alpha)X_{k-1}.$ (D.22)

We take the derivative on both sides and find the alpha value that minimizes
the total variance of the weighted statistic. We compute the variance of
$X_{\alpha}$:

$\displaystyle{\rm Var\ X}_{\alpha}\ =\ \alpha^{2}{\rm Var\ X_{k}}\ +\
(1-\alpha)^{2}{\rm Var\ X_{k-1}}\ +\ 2\ {\rm Cov}(X_{k},X_{k-1}).$ (D.23)

Let $\alpha_{k,k-1}$ denote the optimal alpha value. Taking the derivative
with respect to $\alpha_{k,k-1}$ yields

$\displaystyle{\rm Var}(X)^{\prime}$ $\displaystyle\ =\ $ $\displaystyle
2\alpha_{k,{k-1}}({\rm Var}(X_{k})+{\rm Var}(X_{k-1})-2\ {\rm
Cov}(X_{k},X_{k-1})$ (D.24) $\displaystyle\ \ \ \ \ \ +\ 2\ ({\rm
Cov}(X_{k},X_{k-1})\ -\ {\rm Var}(X_{k-1})).$

After doing some basic algebra, we see that the optimal value of alpha is
equal to 1.

$\displaystyle\alpha_{k,k-1}\ =\ \frac{{\rm Var}(X_{k-1})\ -\ {\rm
Cov}(X_{k},X_{k-1})}{{\rm Var}(X_{k})+{\rm Var}(X_{k-1})-2\ {\rm
Cov}(X_{k},X_{k-1})}\ =\ 1.$ (D.25)

We plug in the formulas that we’ve calculated. Then, we see that the optimal
alpha value is also 1 for the continuous case.

##  Appendix E Mathematica Code

One Dimensional German Tank Problem code

Figure 6. Simulation for one dimensional discrete case.

Two Dimensional Circle Code

Figure 7. Simulation for two dimensional discrete circle.

Two Dimensional Discrete Square Simulation

Figure 8. Simulation for Two Dimensional Discrete Square.

Recursive Method

Figure 9. Simulation for recursion method for square. Figure 10. Simulation
for two dimensional discrete circle.

Code for Comparing Formulas for one and two dimensions

Figure 11. Code for Comparing Formulas for one and two dimensions.

Results of comparison

Figure 12. Results of comparison.

## References

  * [Al] The Albert Team. (2022, March 1). The German Tank Problem Explained: AP® Statistics Review. Albert Resources. Retrieved September 2, 2022, from https://www.albert.io/blog/german-tank-problem-explained-ap-statistics-review/

  * [CGM] G. Clark, A. Gonye, and S. J. Miller, _Lessons From the German Tank Problem_. https://arxiv.org/pdf/2101.08162.pdf.
  * [Co] Constantinescu, P. (n.d.). The Gauss Circle problem - github pages. The Gauss circle problem. Retrieved September 4, 2022, from https://petruconstantinescu.github.io/The_Gauss_circle_problem.pdf
  * [Gi] Gipple, Jake (2014) "The Volume of n-balls," Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 1 , Article 14.
  * [H] A. Hayes, _Portfolio variance_ , Investopedia (2022, February 8), retrieved September 2, 2022 from https://www.investopedia.com/terms/p/portfolio-variance.asp.
  * [In] The Investment Team, _Modern portfolio theory (MPT)_ , Investopedia (2022, June 14), retrieved September 4, 2022 from https://www.investopedia.com/terms/m/modernportfoliotheory.asp.
  * [Ka] M. C. Kalu, _How the allies guessed the number of German tanks using serial numbers_ , warhistoryonline (2019, September 18), retrieved September 2, 2022 from https://www.warhistoryonline.com/instant-articles/the-german-tank-problem.html.
  * [Ku] K. Kuter, K. _Chapter 4.1: Probability density functions (pdfs) and cumulative distribution functions (cdfs) for continuous random variables_ , Statistics LibreTexts (2021, March 9), retrieved September 4, 2022 from https://tinyurl.com/2dchr2v8.
  * [Mi] S. J. MILLER, _The Probability Lifesaver: All the Tools You Need to Understand Chance_ , Princeton University Press (2017), https://doi.org/10.2307/j.ctvc7767n.
  * [Sh] https://www.overleaf.com/project/62ff9ab376ab6c2040cd9279 S. Sheffield, S. _18.600: Lecture 24 .1in covariance and some conditional expectation …_ , retrieved September 2, 2022 from https://math.mit.edu/~sheffield/2017600/Lecture24.pdf.
  * [Ru] Ruggles, R., & Brodie, H. (1947). An Empirical Approach to Economic Intelligence in World War II. Journal of the American Statistical Association, 42(237), 72–91. https://doi.org/10.2307/2280189
  * [YK] V. Kac and K. Yessenov, _18.704 Seminar in Algebra and Number Theory: Euler-Maclaurin Formula_ (Fall 2015), retrieved September 1, 2022 from https://people.csail.mit.edu/kuat/courses/euler-maclaurin.pdf.