text:
# Evaluating Double Integrals

## Evaluating Iterated Integrals

Evaluating a multiple integral involves expressing it as an iterated integral, which can then be evaluated either symbolically or numerically. We begin by discussing the evaluation of iterated integrals.

## Example 1

We evaluate the iterated integral

To evaluate the integral symbolically, we can proceed in two stages.
syms x y
firstint=int(x*y,y,1-x,1-x^2)

firstint =

(x^2*(x - 1)^2*(x + 2))/2

1/24

We can even perform the two integrations in a single step:

int(int(x*y,y,1-x,1-x^2),x,0,1)

ans =

1/24

There is, of course, no need to evaluate such a simple integral numerically. However, if we change the integrand to, say, exp(x^2 - y^2), then MATLAB will be unable to evaluate the integral symbolically, although it can express the result of the first integration in terms of erf(x), which is the (renormalized) antiderivative of exp(-x^2).

int(int(exp(x^2-y^2),y,1-x,1-x^2),x,0,1)

Warning: Explicit integral could not be found.

ans =

int((pi^(1/2)*exp(x^2)*(erf(x - 1) - erf(x^2 - 1)))/2, x = 0..1)

However, we can evaluate the integral numerically, using double.

double(int(int(exp(x^2-y^2),y,1-x,1-x^2),x,0,1))

Warning: Explicit integral could not be found.

ans =

0.167491678970600

## Problem 1

Evaluate the iterated integrals

and

## Finding the Limits

We will now address the problem of determining limits for a double integral from a geometric description of the region of integration. While MATLAB cannot do that for us, it can provide some guidance through its graphics and can also confirm that the limits we have chosen define the region we intended. For a first example, we will consider the bounded region between the curves y = 2x+2 and y = exp(x). We begin by plotting the two curves on the same axes. You may need to experiment with the interval to get a useful plot; it should be large enough to show the region of interest, but small enough so that the region of interest occupies most of the plot.

y1=exp(x);y2=2*x+2;
ezplot(y1,[-1,2]); hold on;
ezplot(y2,[-1,2]); hold off;
title('region bounded by y = 2x+2 and y = e^x')

We can see from the plot that, to define the bounded region between the two graphs, exp(x) should be the lower limit for y, and 2x+2 should be the upper limit. In order to find the limits for x, we need the values for which the two functions coincide. We can try to use solve to find them.

solve(y1-y2)

ans =

- lambertw(0, -1/2*exp(-1)) - 1

Hmm..., not clear what this means, but we can convert to numerical values:

lims=double(ans)

lims =

-0.768039047013466

That seems to be the lower limit, but there should have been an upper limit around 1.7. We can search for its numerical value using fzero:

lims(2) = fzero (@(t) subs(y1-y2, x, t), 1.7)

lims =

-0.768039047013466   1.678346990016661

Now that we have found the limits, we can use the following M-file verticalRegion to visualize the region they define so that we can check that it is the same as the region we had in mind. This program plots the two curves in two different colors: red for the function entered first, and blue for the function entered second, and shades the region in between in cyan.

type verticalRegion

function out = verticalRegion(a, b, f, g)
%VERTICALREGION is a version for Matlab of the routine on page 157
%  of "Multivariable Calculus and Mathematica" for viewing the region
%  bounded by two curves. f and g must be names of functions;
%  a and b are the limits.  The function f is plotted in red and the
%  function g in blue, and lines are drawn connecting the two curves
%  to illustrate the region they bound. The function g must have a variable
%  in it, so if it's supposed to be a constant, try a fudge like
%  '0 + eps*x'.
var=findsym(g);
a=double(a);b=double(b);
%This guarantees these are floating point
% numbers and not just symbolic expressions like sqrt(2)
xx=a:(b-a)/40:b;
fin=inline([vectorize(f+var-var),'+zeros(size(',char(var),'))'],char(var));
gin=inline(vectorize(g+var-var),char(var));
plot(xx,fin(xx),'r');
hold on
plot(xx,gin(xx),'b');
for xxx=a:(b-a)/20:b,
Y=[fin(xxx), gin(xxx)];
plot([xxx, xxx], Y, 'c');
end
title(['region between ',char(f),' and ',char(g)])
hold off

verticalRegion(lims(1),lims(2),y1,y2)

Evidently our limits define the right region. We can now use them to integrate any function we like over the region in question. To find the area of the region, for example, we integrate the function 1. Since our limits for x are numerical, a symbolic calculation is not of much use directly, so we use double to convert to a numerical answer.

area=double(int(int(1,y1,y2),lims(1),lims(2)))

area =

2.226964641160632

Of course, the area between two curves could just as easily have been evaluated as the integral of the difference between the two functions of x whose graphs define the region; that is to say the first integration in this case is so simple that one can write down the result as easily as the integral. However, we can also integrate any function we like over the same region, changing only the integrand. For instance:

newint=double(int(int(x^2+y^2,y,y1,y2),x,lims(1),lims(2)))

newint =

18.576868823773250

The numerical evaluation in this case was performed using numerical routines borrowed from MuPAD, which takes care of symbolic calculations. MATLAB has its own double integrator, called dblquad. There is a complication in using dblquad; it does not accept variable limits. Thus there are two ways to use dblquad:

1. expand the region of integration to a rectangle, and make the integrand = 0 outside of the region where one wants to integrate, or
2. make a change of variables in the inner integral. Fortunately, it is always the same one. We set y=y1+u(y2-y1) so that as u varies from 0 to 1, y varies from y1 to y2, and then integrate over x and u instead of over x and y. Note that dy=(y2-y1)du. This gives the identity

dblquad demands a vectorized function (not symbolic expression) as an input, depending on vector-valued x and scalar-valued y. We implement both methods, and use format long to compare the results.

format long
newint

newint =

18.576868823773250

Next, the method using integration over a rectangle bigger than the true region of integration. We have to multiply the original integrand g by something that is 0 outside the region of integration. But y<=y2 is 0 (false) if y>y2 and 1 (true) otherwise. Similarly, y>=y1 is 0 (false) if y<y1 and 1 (true) otherwise.

g = @(x,y) x.^2+y^2;
h = @(x,y) g(x, y).*(y<=2*x+2).*(y>=exp(x));

newint1 =

18.078690871319640

Finally the method using a change of variables:

g = @(x,y) x.^2+y.^2;
h1 = @(x,u) g(x, exp(x)+u*(2*x+2-exp(x))).*(2*x+2-exp(x));

newint2 =

18.576868790136942

The answers provided by all three methods are clearly in the same ballpark, and those produced by int and the change of variables method agree to eight significant digits. The method using "truncation" is less accurate, because it results in integrating a discontinuous function, whereas the usual algorithms for numerical integration work best with an integrand that is smooth.

Because of the syntactical complications of using dblquad on a region that is not rectangular, we have created M-files symint2 and numint2, which have identical calling syntax and implement, respectively, symbolic double integration using int, and numerical double integration using dblquad. The advantage of the identical syntax is that if symint2 fails, one can try numint2 instead with a minimum of editing. We illustrate them by repeating the two previous computations.

type symint2

function out=symint2(integrand,var1,varlim1,varlim2,var2,lim1,lim2)
%SYMINT2 Symbolically evaluate double integral.
%   NUMINT2 is basically a "wrapper" for iterated application of INT.
%   The INNER integral should be written first.
%   Example:
%       syms x y
%       symint2(x,y,0,x,x,1,2) integrates
%       the function x over the trapezoid 1<x<2, 0<y<x,
%       and gives the symbolic output 7/3.
out=int(int(integrand,char(var1),varlim1,varlim2),char(var2),lim1,lim2);

type numint2

function out=numint2(integrand,var1,varlim1,varlim2,var2,lim1,lim2)
%NUMINT2 Numerically evaluate double integral.
%   NUMINT2 is basically a "wrapper" for DBLQUAD, to
%   get around the fact that the latter is only designed for integration
%   over a rectangle, and requires inline vectorized input.  The
%   INNER integral should be written first.
%   Example:
%       syms x y
%       numint2(x,y,0,x,x,1,2) integrates
%       the function x over the trapezoid 1<x<2, 0<y<x,
%       and gives the numerical output 2.3333.
syms uU
newvar1=varlim1+uU*(varlim2-varlim1);
integrand2=subs(integrand,var1,newvar1)*(varlim2-varlim1);
integrand3=inline([char(vectorize(integrand2)),'.*ones(size(uU))'],'uU',char(var2));

double(symint2(sin(x^2+y^2),y,y1,y2,x,lims(1),lims(2)))
numint2(sin(x^2+y^2),y,y1,y2,x,lims(1),lims(2))

Warning: Explicit integral could not be found.

ans =

0.289216044183966

ans =

0.289216393390081

Note: As this example illustrates, in some problems, dblquad and numint2 do not work that well, and spit out long lists of warning messages. In next week's lesson, we will discuss another package called nit, or "numerical integration toolbox", that usually corrects the problem.

## Problem 2

Let R be the region bounded by the curves y=3*x^2 and y=|2*x+3|.

a) Determine the limits of integration for a double integral over R; confirm your limits by using verticalRegion.

b) Evaluate

both using double and int (or double and symint2, and using dblquad (or numint2).

## Integrating over Implicitly Defined Regions

Let us now turn to the process of integrating over a region bounded by a level curve of a function of two variables. Once again, the real issue is the determination of the limits of integration. We will consider the region bounded by the ellipse 3*x^2+4*y^2=37. Although it is not strictly necessary in this case, we will begin by plotting the ellipse.

ezplot(3*x^2+4*y^2-37, [-4, 4, -4, 4]), axis equal

We can see from the plot that this region is vertically simple. We obtain our y limits by solving the equation of the ellipse for y in terms of x.

ylims=solve(3*x^2+4*y^2-37,y)

ylims =

-(37 - 3*x^2)^(1/2)/2
(37 - 3*x^2)^(1/2)/2

The two solutions give the upper and lower limits for y; we can find the limits for x by setting their difference to 0 and solving for x.

y1=ylims(2)
y2=ylims(1)
xlims=solve(y1-y2,x)
x1=xlims(2)
x2=xlims(1)

y1 =

(37 - 3*x^2)^(1/2)/2

y2 =

-(37 - 3*x^2)^(1/2)/2

xlims =

(3^(1/2)*37^(1/2))/3
-(3^(1/2)*37^(1/2))/3

x1 =

-(3^(1/2)*37^(1/2))/3

x2 =

(3^(1/2)*37^(1/2))/3

We can confirm our limits, using verticalRegion. The first two arguments to verticalRegion must be numerical, rather than symbolic. Therefore, we must apply double to x1 and x2. verticalRegion(double(x1),double(x2),y1,y2)

We can now integrate any function we desire over the region bounded by the ellipse.

## Problem 3

Integrate

a) Over the region bounded by the ellipse 3*x^2+4*y^2=36.

b) Over the region bounded by the curve x^4+y^4=20.

## Polar Coordinates

We conclude this lesson with a discussion of integration in polar coordinates. We consider integrating the function exp(-x^2-y^2) over the disk bounded by the circle (x-1)^2 + y^2 = 1. We begin by expressing the function whose vanishing defines the boundary curve in polar coordinates.

syms r th
polarfun=simplify(subs((x-1)^2+y^2-1, [x,y],[r*cos(th),r*sin(th)]))

polarfun =

r^2 - 2*r*cos(th)

Next we solve the equation of the boundary curve for r in terms of theta, to obtain the limits for r.

rlims=solve(polarfun,r)

rlims =

0
2*cos(th)

Since the disk in which we are interested lies entirely to the right of the x-axis, the appropriate limits for theta are -pi/2 and pi/2. Bearing in mind that we must include a factor of |r |when integrating in polar coordinates, we can now set up and evaluate an iterated integral in any of the usual ways. For example:

double(int(int(r*exp(-r^2),0,2*cos(th)),-pi,pi))

Warning: Explicit integral could not be found.

ans =

2.172385173883870

## Problem 4

Reevaluate the integral above using numint2.

1) Evaluate

where R is the triangle with vertices at (0,0), (0,2) and (3,0). Hint: begin by determining the equation of the oblique side of the triangle. Use verticalRegion to confirm your limits.

2) Evaluate

where R is the region bounded by the closed curve

3) Evaluate

where R is the region bounded by the cardioid

4) Compute the area of the region bounded by the two curves x^2 - y^2 = 1 and y = x^2 - 3*x + 1.


text:
# Meaning of having a rational $m$-torsion point

Suppose I have an elliptic curve $E/\mathbb{Q}$. What does it mean when one says $E$ has a rational $m$-torsion point over $\mathbb{Q}$? What does this mean for the torsion subgroup, $E_{\mathrm{tor}}(\mathbb{Q})$ and $E[m]$?

-
It means that there is a point $P$ on $E$ such that $m\cdot P = O$, and the coordinates of $P$ are in $\mathbb{Q}$. –  Álvaro Lozano-Robledo Sep 15 '12 at 2:57

format: plain


text:
# What is the net ionic equation for the formation of Fe(OH)_3 from "ferric nitrate" and "sodium hydroxide"?

Oct 3, 2015

"Fe"_text((aq])^(3+) + 3"OH"_text((aq])^(-) -> "Fe"("OH")_text(3(s]) darr

#### Explanation:

You're dealing with a double replacement reaction that results in the formation of an insoluble solid that precipitates out of solution.

More specifically, a solution of iron(III) nitrate, "Fe"("NO"_3)_3, will react with a solution of sodium hydroxide, $\text{NaOH}$, to form iron(III) hydroxide, "Fe"("OH")_3, which precipitates out of solution.

So, the molecular equation that describes this reaction is

${\text{Fe"("NO"_3)_text(3(aq]) + 3"NaOH"_text((aq]) -> "Fe"("OH")_text(3(s]) darr + 3"NaNO}}_{\textrm{3 \left(a q\right]}}$

The complete ionic equation will include the solid and all the ions that are present in solution

${\text{Fe"_text((aq])^(3+) + 3"NO"_text(3(aq])^(-) + 3"Na"_text((aq])^(+) + 3"OH"_text((aq])^(-) -> "Fe"("OH")_text(3(s]) darr + 3"Na"_text((aq])^(+) + 3"NO}}_{\textrm{3 \left(a q\right]}}^{-}$

Notice tha the insoluble solid is not represented as ions!

The net ionic equation will only show the ions that actually take part in the reaction.

The reaction between the two solutions will result in the formation of the solid, which means that the ions that are not a part of the solid will not take part in the reaction.

More specifically, they will act as spectator ions. You can tell which ions are spectator ions by their presence on both sides of the equation.

So, the net ionic equation is

"Fe"_text((aq])^(3+) + 3"OH"_text((aq])^(-) -> "Fe"("OH")_text(3(s]) darr

Here's how this reaction would look like

Here the iron(III) nitrate solution is added to the colorless sodium hydroxide solution


text:
# Reversing Diffie Hellman from the secret

This is a homework assignment that's been giving me some trouble:

By eavesdropping on a Diffie-Hellman key exchange, we observe

modulus $$p$$

the base $$3$$

$$A\ =\ 3^a \bmod p\quad$$ and

$$B\ =\ 3^b \bmod p$$

If we somehow had access to the secret $$=\ 3^{ab} \bmod p$$, how could you retrieve the secret exponents $$a$$ and $$b$$?

$$p$$ is 996-bit. $$A$$, $$B$$ also are very large numbers. I think I am missing something about exponential arithmetic. I've tried working on the actual numbers using PARI/GP, but the numbers are too big to use the built-in discrete logarithm functionality.

• Common wisdom is that with $p$ , $3^a\bmod p$ and $3^b\bmod p$ known, additional knowledge of $3^{ab}\bmod p$ does not help decisively towards finding $a$ and $b$, for random choice of these. Also, in unauthenticated DH key exchange, the attacker only wants $a$ and $b$ in order to find $3^{ab}\bmod p$, thus it seems strange to assume that the later is known. Did you test if $p$ is prime? If it (or its factors if it is composite) is of the special form $\dfrac{r^e\pm s}t$ making SNFS possible? – fgrieu Mar 5 at 8:17
• If $p$ is prime, do you know the factorization of $p-1$? Even if you can get its partial factorization, if the order of 3 consists solely of small factors, solving the discrete log problem to obtain $a$ or $b$ is easy... – poncho Mar 5 at 14:12


text:
# Hast Thou Slain the Jabberwock?

Your task is to output the exact string

The Jabberwocky

without taking input. Normal rules for input and output apply, so both functions and programs are allowed.

Of course there is a catch, it wouldn't be fun without a catch. Your program, when stripped of non-alphabetic characters, must start the poem The Jabberwocky (case insensitive). To start the poem it must be a continuous substring of the poem starting at the beginning. The empty string is fine (although you probably won't score very well).

Here is the text for reference:

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyesofflamecamewhifflingthroughthetulgeywoodandburbledasitcameonetwoonetwoandthroughandthroughthevorpalbladewentsnickersnackheleftitdeadandwithitsheadhewentgalumphingbackandhastthouslainthejabberwockcometomyarmsmybeamishboyofrabjousdaycalloohcallayhechortledinhisjoytwasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabe

Here is a program you can use to test this property.

If you run out of poem to use you may not use any additional alphabetic characters.

Alphabetic characters are characters a-z and A-Z here is the complete list:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

## Scoring

Your program will be scored in the number of non-alphabetic bytes used with fewer being better.

Here is a Haskell program that scores answers. (This assumes inputs are valid)

## Example program

The following program would be valid:

twas&*brilliga77812nd Thesli thyt Oves didgy reand Gim bleinth ewab eal lmims ywe""""""""
ret h eb or o g o ve sa n dthemomerAthsoutgrabebewaretheJABBERWOCKmysonthe)(*)()((*98980908(()*(jawsthatbit

When stripped down to alphabetic characters it is:

twasbrilligandTheslithytOvesdidgyreandGimbleinthewabeallmimsyweretheb orogovesandthemomerAthsoutgrabebewaretheJABBERWOCKmysonthejawsthatbit

Which matches the first bit of the poem (case insensitive).

This program would score 59 because it contains these non-alphabetic characters:

&*77812           """"""""
)(*)()((*98980908(()*(

• What do you mean by "Start the poem"? – Pavel Mar 2 '18 at 20:53
• This is trivial to do in languages without letters. – NoOneIsHere Mar 2 '18 at 21:02
• The pedant in me feels obligated to remind you that the name of the poem is Jabberwocky (with no article), while the name of the beast is the Jabberwock (with no -y). Of course you can't change the required output now, but... – DLosc Mar 3 '18 at 4:55
• Why so many votes to close as unclear? The "Here is a program you can use to test this property." part completely and unambiguously determines the valid criteria. – user202729 Mar 3 '18 at 8:44
• @JonathanAllan Their being unable to understand the question doesn't necessary mean that the question is unclear... – user202729 Mar 3 '18 at 13:24

## oOo CODE, score 0

Thanks to Dennis for golfing the Brainfuck code.

TwASbRIlLIgAnDthEsliTHyTOvEsdiDgyreaNdgImbleinthEwaBeaLlmimSywEreThEBoroGoveSAndTheMOmERaTHSoutGRabEbeWArEthEjaBbeRWockMYsONtHEJawsTHaTBiTEThecLawSthATcaTChBeWAReTHeJuBJuBBiRDAndsHUNtHeFRuMIoUSbANdERSnatchheTooKHisvORpaLswORdinhAndLonGtiMetHEmanXomEFoEHeSOUg

Try it online!

I've got bad news for this challenge... :(

oOo CODE is just a binary encoding of brainfuck which uses the case of a letter for each bit. So yeah, since the poem is long enough (or the output short enough) to cover a Brainfuck program that prints The Jabberwocky (without actually trying hard to golf it), this becomes a trivial optimal answer.

• Golfed. – Dennis Mar 3 '18 at 0:44
• @JoKing Try it online! (generated with BF-Crunch) – Dennis Mar 3 '18 at 1:30
• "bad news" ... yes, that's bad. I predicted Unary will get 0 bytes, the rule changed, and there are still score 0 submissions. – user202729 Mar 3 '18 at 8:47
• I don't think it's bad news at all. This has zero implications on how fun it is to golf in other languages. – Lynn Mar 6 '18 at 0:34

# C, score  104  79  74

Thanks to @gastropner for lowering the score to 79 and thanks to @wizzwizz4 for lowering it further to 74!

*t,w;a(s,b,rilligand){*(t//he
=s++)="lithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewareThe Jabberwock\0mysonthejawsthat"[b++]?//i
:121;*t>12e1?*++t//hecl
=0:a//wsthatcatchbewarethejubjubbirdandshunthefrumiou
(s,b);}an;der(s,n){a(//tchhetookhi
s,88);}

Try it online!

• Score 79 – gastropner Mar 3 '18 at 15:43
• Wouldn't //abcdefgh\n be 1 fewer characters than /*abcdefgh*/? – wizzwizz4 Mar 4 '18 at 12:15
• @wizzwizz4 Yes, it would. Thanks! – Steadybox Mar 4 '18 at 14:26

## Fission 2, score 3

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewaRe"The Jabberwock"mysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyesofflamecamewhifflingthroughthetulgeywoodandburbledasitcameonetwoonetwoandthroughandthroughthevorpalbladewentsnickersnackheleftitdeadandwithitsheadhewentgalumphingbackandhastthouslainthejabberwockcometomyarmsmybeamishboyO

Try it online!

### Explanation

We can ignore most of the lowercase letters, they just set an atom's energy to their code point.

...Re"The Jabberwock"my...oyO

The uppercase R is the program's entry point, as it creates an atom going right. As I said, we can ignore the e. Then " toggles string mode, which just prints all characters it encounters to STDOUT, which gives us The Jabberwock. That only leaves the y. We could use the y that's coming up immediately in y, but then we'd have to waste at least one non-letter byte on printing it (!) and possibly another on terminating the program.

Instead, we patiently wait for y to show up immediately before o in the poem. Because that lets us use O which prints the character and destroys the atom, terminating the program. This way, the only non-letter characters we need are the space and the two quotes.

• Very very impressive. – Weijun Zhou Mar 2 '18 at 23:18

# Alice, score 7

"T/was"bri@lligandtheslithytovesdidgyreandgimbleinthewabeallmimsywe
rethe borogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyesofflamecamewhifflingthroughthetulgeywoodandburbledasitcameonetwoonetwoandthroughandthroughthevorpalbl

Try it online!

The / makes the IP move diagonally and bounce off the edges, so the instructions actually executed are "The "ono@. The n command (in ordinal mode) pushes the string "Jabberwocky" if the top of the stack is empty, and o outputs the top of the stack.

• Very nice answer! – Jonathan Allan Mar 3 '18 at 19:30
• Right tool for the job. – Robert Fraser Mar 4 '18 at 2:45
• Nice, I tried several things but didn't find any layout that scored nearly as well as this. – Martin Ender Mar 4 '18 at 9:58

# Jelly, score  6  4

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathSOUTGRABEBEWARE“The Jabberwock”m”y

A full program printing the result
(as a monadic link it prints The Jabberwock as a side-effect and returns the character y)

Inserts the characters “ ”” into a case-changed prefix of the poem.

This works because:

1. The last h before SOUTGRABEBEWARE“The Jabberwock”m”y is (at least at the time of writing!) an undefined atom, which makes that all become a new link which takes the default input of 0 and performs some monadic functions, SOUTGRABEBEWARE, which yield 1 (see below).

2. 1“The Jabberwock”m then performs m, modulo slicing, on "The Jabberwock" with a slice size of 1, yielding "The Jabberwock".

3. The trailing ”y is a new leading constant chain so Jelly prints that list of characters and then yields the character y, and since it's now the end of the program this then gets printed.

 implicit input = 0
S sum             0
O cast to ordinal 0
U upend           [0]
T truthy indices  []
G group           []
R range           []
A absolute value  []
B to-binary       []
E all-equal?      1
B to-binary       [1]
E all-equal?      1
W wrap            [1]
A absolute value  [1]
R range           [[1]]
E all-equal?      1

Previous 6 byter:

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware
“The Jabberwock”m1“y

Try it online!

The six non-poem characters are a newline plus “ ”1“.

Alternative 6s:

“T“wasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewaret“he Jabberwock”m2“y

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewaret
“The Jabberwockmy”ṪṭṖ

• Is the first program not valid without m1“y? It still prints The Jabberwock and begins with a subset of the poem – dylnan Mar 3 '18 at 18:00
• No, the m1“y (or it could be m1”y) is needed because we must print The Jabberwocky, not The Jabberwock. – Jonathan Allan Mar 3 '18 at 19:25

# Charcoal, score 3

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware⎚The Jabberwock⌈my

Try it online!

Inserted the three characters: ⎚ ⌈

...it also works with the whole poem.

### How?

twas ... ware⎚The Jabberwock⌈my - no input
twas ... ware                    - print this text     >  twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware
⎚                  - clear the screen    >
The Jabberwock    - print this text     > The Jabberwock
⌈   - (print) maximum of:
my -   this text         > The Jabberwocky

# Ruby (-p), Score 12

$_=#twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware 'The Jabberwock'+#m ?y  Try it online! Abuse all the comments! With the -p flag, ruby will print whatever stored in $_. Requires a single line of any input.

• I don't think you can use -p here, because of the required line of input. "Your task is to output the exact string The Jabberwocky without taking input." – benj2240 Mar 2 '18 at 21:41
• @benj2240 -p is a command line flag, not an input. – Mr. Xcoder Mar 2 '18 at 21:42
• @benj2240 Taking unused empty input when no input is required is allowed, by meta concencus. This takes an empty line. – Pavel Mar 2 '18 at 21:43
• @Pavel I see, thank you – benj2240 Mar 2 '18 at 22:15

# Charcoal, score: 5 4

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware⎚The Jabberwock¿m¦y

Try it online! Edit: Saved 1 byte thanks to @ASCII-only. Explanation: Translates to the following verbose code:

Print("twas...beware");
Clear();
Print("The Jabberwock");
if ("m") Print("y");

• whole poem :P – ASCII-only Mar 3 '18 at 12:20
• @JonathanAllan Fixed! – Neil Mar 3 '18 at 20:37

# Foo, score 5

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware"The Jabberwock"m"y"

Try it online!

# ><>, Score: 13 12

\twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware
\"The Jabberwockmy"$~\sonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyeso fflamecamewhifflingth>ro<  Try it online! Immediately redirects to the second line, which pushes "The Jabberwockmy" in reverse to the stack. $~ pops the excess m and >ro< prints the whole stack, reversing it beforehand.

# Retina 0.8.2, score: 21201816138 6

|twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware
The Jabberwock0$*my  Try it online! Edit: Score reduced by 2 thanks to @MartinEnder. • You can score 6 like this: tio.run/… and then 5 by switching to Retina 1.0 (and using * instead of $*). – Martin Ender Mar 3 '18 at 1:00

# C, score 23

twasbrilligandtheslithytovesdidgyreandgimble(int**h){//ewabeallmimsyweretheborogovesandthemomerat
*h//soutgrabebeware
="The Jabberwock"//m
"y";}

Try it online!

# PowerShell, Score: 19 10

#twasbrilligandTheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethe
'The Jabberwock'+#m
'y'

Try it online!

Port of Pavel's Ruby answer. Thanks to Jo King for -9 points.

The strings are + concatenated together. Once the comments are removed and the code parsed, PowerShell sees this as 'The Jabberwock'+'y'. That string is left on the pipeline and output is implicit.

• I was just about to post this exact answer :P – Pavel Mar 2 '18 at 21:31
• Can’t you combine The and Jabberwock into one string? Try it online! – Jo King Mar 5 '18 at 22:29
• @JoKing Indeed, thanks. Funny how you're getting by without the line continuation character. I wonder when that parsing rule changed... – AdmBorkBork Mar 6 '18 at 13:26

# 05AB1E, score 14

"twasbrilligand""The ""slithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethe"Š"Jabberwock"+"my"Š

Try it online!

# Yabasic, 13

Thanks for @Pavel's Ruby answer!

#twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware
?"The Jabberwock";//m
?"y"

Try it online!

• I count a score of 20, I think you forgot to count newlines. – Pavel Mar 2 '18 at 21:51
• Yes, there are problems with scores of other answers as well. – Weijun Zhou Mar 2 '18 at 21:53
• Just a note: Yabasic is available for use at Try It Online, you should consider adding a link to your solution at TIO such as this one – Taylor Scott Mar 2 '18 at 22:12
• @TaylorScott How can I fail to notice that! Fixed. – Weijun Zhou Mar 2 '18 at 22:14
• I think you have an extra "the" at the end of the first line. – 12Me21 Mar 3 '18 at 15:33

## VBA, score 5

Run in the Immediate Window:

?twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware"The Jabberwock"m"y

How it works:

? - This prints out output as a string

-

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware - without Explicit declaration, this is treated as an empty string

-

"The Jabberwock" - String. When you put 2 variables/strings next to each other, VBA will automatically concatenate them. (2 non-variable strings would require a space so as not to add a double-quote)

-

m - Another implicit empty-string, automatically concatenated

-

"y - Another string. Left open, the Immediate Window will automatically close this when it hits the end of the line - again, automatically concatenated

-

1 question-mark, 1 space and 3 double-quotes. VBA sees this as ?"" & "The Jabberwock" & "" & "y" or ?"The Jabberwocky"

# Haskell, score 12

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware="The Jabberwock"++{-m-}"y"

Try it online!

Defines a zero-argument function twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware :: String whose output is "The Jabberwocky".

# Java (OpenJDK 9), score 11

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware->"The Jabberwock"+//m
"y"

Try it online!

### Credits

• -2 score by changing () to t (unused Void null parameter), and removing the leading t from the comment. – Kevin Cruijssen Mar 5 '18 at 8:17
• @KevinCruijssen Thank you for the insights. :-) However, regarding the <s>16</s> 14 I prefer, as always on any StackExchange network to provide a final answer. The changes themselves are listed in the revision page, making it easy for everybody to see the actual changes, and how the answer evolved over time, rather than putting all past and current information in one big unreadable post. – Olivier Grégoire Mar 5 '18 at 9:43
• Ah ok, fine by me. :) The edit was mainly meant to fix 'bytes' to 'score'. – Kevin Cruijssen Mar 5 '18 at 10:06
• @KevinCruijssen Indeed, I saw your change in the credits and they were welcome. In my previous comment, I only meant the title. I even created a meta-post on that topic. ;-) – Olivier Grégoire Mar 5 '18 at 10:08
• Now that you have removed the comment on the first line you don't need the line break any longer. – Wheat Wizard Mar 6 '18 at 3:38

# Jelly, score: 8

“ĠȥṘ®ṖȤ»

Try it online!

Just compresses the string, and is an empty string when all non-alphabet characters are removed. Annoyingly, the shortest compressed form, “81Iȯd» has alphabetical characters, neither of which are t or w

# Stax, 11

£«≡¿«_→Ä:£◘

Run and debug online!

Just a compressed string literal that is in turn packed.

# Canvas, score 5

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware∙The Jabberwockｐm∙yｐ

Try it here!

# SOGL V0.12, score 9

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware”The” Jabberwock”:⁄m+ y+

Try it Here!

# Pip, score 5

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestOOD|"The Jabberwock"witheyesofflamecamewhifflingthroughthetulge'y

Try it online!

Fortunately, lowercase letters in Pip are all variables, which are no-ops in expressions by themselves. The interesting part of the code:

OOD|"The Jabberwock"

The scanner breaks up OOD as O followed by OD. OD is an undefined variable, which evaluates as nil (falsey); we then logical-or this with "The Jabberwock", and O outputs it without a newline.

'y

Single-character string y. Since it is the last expression in the program, it is printed.

# SmileBASIC, score 10

@twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware?"The Jabberwock";
@m?"y

This was pretty much taken directly from the Yabasic answer, and since SB is a better language, we can shorten it by using labels rather than comments, which eliminates the need for some of the line breaks

There is also this alternative solution, for the same size:

@twasbrillig ... ?"The Jabberwock"+@my[2]

A label inside an expression is treated as a string. (@my == "@my"), so taking character 2 gives "y".

# C (gcc), score 58

The useful fact that // style comments + newlines are cheaper than old-style ones comes straight from @wizzwizz4's comment for @Steadybox's answer.

The -m32 flag is required.

Some might be brought to a frumious mood by the lengthy name of the function to call, whereas others might rightly find such objections mimsy; in the end, we must all of us heed the siren song of low scores.

twasbrilligan;d(t,h,e,slithytovesdidgyreandgimble)int*h,*e;//wabeallmimsywere
{t--?*h++=*e++,//borogovesan
d(t,h,e):0;}momerathsoutgrabebewar;*e="The Jabberwock\171";mysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoug(h,tsoreste){d(4,h,e);}

Try it online!

# Batch, score 15 11

:twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbiteth
@ec%lawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffisht%ho%ughthestood% The Jabberwock%withe%y

Basically just echo The Jabberwocky with unused variables and labels.

Old version (score 24):

:twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyesofflamecamewh
:armsmybeamishboyofrabjousdaycalloohcallayh
@echo %*

Requires code to be saved in a file named n.bat and run from the same directory.

Alternate version which can have any name (score 27):

:twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvorpalswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestoodthejabberwockwitheyesofflamecamewh
:armsmybeamishboyofrabjousdaycalloohcallayh
@echo %*

Explanation (with variables removed):

:twas...                         Label (No labels were used, no goto in the poem)
@if %1i==i %~n0 The Jabberwocky  If no command line arguments, run this batch file again
:arms...                          with the arguments 'The Jabberwocky'
@echo %*                         Echo all arguments

# Perl 5, subroutine, score 11

{twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware;'The Jabberwock'.~'X'}

but with the character \x86 (v134) instead of the X.

(perlsub says "The signature is part of a subroutine's body. Normally the body of a subroutine is simply a braced block of code.")

• Does this print the y? – Jo King Mar 4 '18 at 20:22
• @JoKing oops! Now it does; thanks. – msh210 Mar 4 '18 at 20:37

# Ruby, 9 non letter bytes

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewarethejabberwockmysonthejawsthatbitetheclawsthatcatchbewarethejubjubbirdandshunthefrumiousbandersnatchhetookhisvor=p alswordinhandlongtimethemanxomefoehesoughtsorestedhebythetumtumtreeandstoodawhileinthoughtandasinuffishthoughthestood="The Jabberwock"+withe=?y

Try it online!

### Golfed version (for readability):

x=p z="The Jabberwock"+w=?y

Uses a few long and useless variables. In ruby, you can put whatever_you_want= before an expression, and it will still return that expression, just with the side effect of creating an oddly-named variable.

# Self-modifying Brainfuck, score 16

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebeware␀The Jabberwock␀my<[<<]>[.>]>>.

Try it online!

## Explanation

Initially the tape is set up like this:

\begin{aligned} \dots\ \texttt{␀}\ \texttt{T}\ \texttt{h}\ \texttt{e}\ \texttt{␠}\ \texttt{J}\ \texttt{a}\ \texttt{b}\ \texttt{b}\ \texttt{e}\ \texttt{r}\ \texttt{w}\ \texttt{o}\ \texttt{c}\ \texttt{k}\ \texttt{␀}\ \texttt{m}\ \texttt{y}\ \texttt{<}\ \texttt{[}\ \texttt{<}\ \texttt{<}\ \texttt{]}\ \texttt{>}\ \texttt{[}\ \texttt{.}\ \texttt{>}\ \texttt{]}\ \texttt{>}\ \texttt{>}\ \texttt{.}\ & \texttt{␀}\ \texttt{␀}\ \dots \\ & \uparrow \end{aligned}

Since we want to move to the beginning of the string we use <[<<] such that we jump over the first $\texttt{␀}$ character.

Now we can just move to the $\texttt{T}$ with > and print the whole string with [.>] and since we picked the substring where the next $\texttt{y}$ is not far, we can just jump to it directely and print it with >>..

# Fission, score 6

twasbrilligandtheslithytovesdidgyreandgimbleinthewabeallmimsyweretheborogovesandthemomerathsoutgrabebewaRe"The Jabberwock"m"y";

Try it online!


text:
Optimal construction of k-nearest neighbor graphs for identifying noisy clusters

We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest neighbor or symmetric k-nearest neighbor? What is the optimal parameter k? In our setting, clusters are defined as connected components of the t-level set of the underlying probability distribution. Clusters are said to be identified in the neighborhood graph if connected components in the graph correspond to the true underlying clusters. Using techniques from random geometric graph theory, we prove bounds on the probability that clusters are identified successfully, both in a noise-free and in a noisy setting. Those bounds lead to several conclusions. First, k has to be chosen surprisingly high (rather of the order n than of the order log n) to maximize the probability of cluster identification. Secondly, the major difference between the mutual and the symmetric k-nearest neighbor graph occurs when one attempts to detect the most significant cluster only.

Authors

• 2 publications
• 65 publications
• 26 publications
• Learning to Index for Nearest Neighbor Search

In this study, we present a novel ranking model based on learning the ne...
07/09/2018 ∙ by Chih-Yi Chiu, et al. ∙ 0

• Speculate-Correct Error Bounds for k-Nearest Neighbor Classifiers

We introduce the speculate-correct method to derive error bounds for loc...
10/09/2014 ∙ by Eric Bax, et al. ∙ 0

• Pruning nearest neighbor cluster trees

Nearest neighbor (k-NN) graphs are widely used in machine learning and d...
05/03/2011 ∙ by Samory Kpotufe, et al. ∙ 0

• Clustering by Hierarchical Nearest Neighbor Descent (H-NND)

Previously in 2014, we proposed the Nearest Descent (ND) method, capable...
09/09/2015 ∙ by Teng Qiu, et al. ∙ 0

• A Novel and Efficient Data Point Neighborhood Construction Algorithm based on Apollonius Circle

Neighborhood construction models are important in finding connection amo...
09/27/2018 ∙ by Shahin Pourbahrami, et al. ∙ 0

• Nonparametric Nearest Neighbor Random Process Clustering

We consider the problem of clustering noisy finite-length observations o...
04/20/2015 ∙ by Michael Tschannen, et al. ∙ 0

• Faster DBSCAN via subsampled similarity queries

DBSCAN is a popular density-based clustering algorithm. It computes the ...
06/11/2020 ∙ by Heinrich Jiang, et al. ∙ 0

This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

1 Introduction

Using graphs to model real world problems is one of the most widely used techniques in computer science. This approach usually involves two major steps: constructing an appropriate graph which represents the problem in a convenient way, and then constructing an algorithm which solves the problem on the given type of graph. While in some cases there exists an obvious natural graph structure to model the problem, in other cases one has much more choice when constructing the graph. In the latter cases it is an important question how the actual construction of the graph influences the overall result of the graph algorithm.

The kind of graphs we want to study in the current paper are neighborhood graphs. The vertices of those graphs represent certain “objects”, and vertices are connected if the corresponding objects are “close” or “similar”. The best-known families of neighborhood graphs are -neighborhood graphs and -nearest neighbor graphs. Given a number of objects and their mutual distances to each other, in the first case each object will be connected to all other objects which have distance smaller than , whereas in the second case, each object will be connected to its

nearest neighbors (exact definitions see below). Neighborhood graphs are used for modeling purposes in many areas of computer science: sensor networks and wireless ad-hoc networks, machine learning, data mining, percolation theory, clustering, computational geometry, modeling the spread of diseases, modeling connections in the brain, etc.

In all those applications one has some freedom in constructing the neighborhood graph, and a fundamental question arises: how exactly should we construct the neighborhood graph in order to obtain the best overall result in the end? Which type of neighborhood graph should we choose? How should we choose its connectivity parameter, for example the parameter in the -nearest neighbor graph? It is obvious that those choices will influence the results we obtain on the neighborhood graph, but often it is completely unclear how.

In this paper, we want to focus on the problem of clustering. We assume that we are given a finite set of data points and pairwise distances or similarities between them. It is very common to model the data points and their distances by a neighborhood graph. Then clustering can be reduced to standard graph algorithms. In the easiest case, one can simply define clusters as connected components of the graph. Alternatively, one can try to construct minimal graph cuts which separate the clusters from each other. An assumption often made in clustering is that the given data points are a finite sample from some larger underlying space. For example, when a company wants to cluster customers based on their shopping profiles, it is clear that the customers in the company’s data base are just a sample of a much larger set of possible customers. The customers in the data base are then considered to be a random sample.

In this article, we want to make a first step towards such results in a simple setting we call “cluster identification” (see next section for details). Clusters will be represented by connected components of the level set of the underlying probability density. Given a finite sample from this density, we want to construct a neighborhood graph such that we maximize the probability of cluster identification. To this end, we study different kinds of -nearest neighbor graphs (mutual, symmetric) with different choices of and prove bounds on the probability that the correct clusters can be identified in this graph. One of the first results on the consistency of a clustering method has been derived by Hartigan [8], who proved “fractional consistency” for single linkage clustering.

The question we want to tackle in this paper is how to choose the neighborhood graph in order to obtain optimal clustering results. The mathematical model for building neighborhood graphs on randomly sampled points is a geometric random graph, see Penrose [12] for an overview. Such graphs are built by drawing a set of sample points from a probability measure on , and then connecting neighboring points (see below for exact definitions). Note that the random geometric graph model is different from the classical Erdős-Rényi random graph model (cf. Bollobas [3]

for an overview) where vertices do not have a geometric meaning, and edges are chosen independently of the vertices and independently of each other. In the setup outlined above, the choice of parameter is closely related to the question of connectivity of random geometric graphs, which has been extensively studied in the random geometric graph community. Connectivity results are not only important for clustering, but also in many other fields of computer science such as modeling ad-hoc networks (e.g.,

Santi and Blough [14], Bettstetter [1], Kunniyur and Venkatesh [10]) or percolation theory (Bollobas and Riordan [4]). The existing random geometric graph literature mainly focuses on asymptotic statements about connectivity, that is results in the limit for infinitely many data points. Moreover, it is usually assumed that the underlying density is uniform – the exact opposite of the setting we consider in clustering. What we would need in our context are non-asymptotic results on the performance of different kinds of graphs on a finite point set which has been drawn from highly clustered densities.

Our results on the choice of graph type and the parameter for cluster identification can be summarized as follows. Concerning the question of the choice of , we obtain the surprising result that should be chosen surprisingly high, namely in the order of instead of (the latter would be the rate one would “guess” from results in standard random geometric graphs). Concerning the types of graph, it turns out that different graphs have advantages in different situations: if one is only interested in identifying the “most significant” cluster (while some clusters might still not be correctly identified), then the mutual graph should be chosen. If one wants to identify many clusters simultaneously the bounds show no substantial difference between the mutual and the symmetric graph.

2 Main constructions and results

In this section we give a brief overview over the setup and techniques we use in the following. Mathematically exact statements follow in the next sections.

Neighborhood graphs. We always assume that we are given data points which have been drawn i.i.d. from some probability measure which has a density with respect to the Lebesgue measure in . As distance function between points we use the Euclidean distance, which is denoted by . The distance is extended to sets via . The data points are used as vertices in an unweighted and undirected graph. By we denote the set of the nearest neighbors of among . The different neighborhood graphs are defined as follows:

• -neighborhood graph : and connected if ,

• symmetric -nearest-neighbor graph :
and connected if or ,

• mutual -nearest-neighbor graph :
and connected if and .

Note that the literature does not agree on the names for the different graphs. In particular, the graph we call “symmetric” usually does not have a special name.

Most questions we will study in the following are much easier to solve for -neighborhood graphs than for graphs. The reason is that whether two points and are connected in the -graph only depends on , while in the graph the existence of an edge between and also depends on the distances of and to all other data points. However, the graph is the one which is mostly used in practice. Hence we decided to focus on graphs. Most of the proofs can easily be adapted for the -graph.

The cluster model. There exists an overwhelming amount of different definitions of what clustering is, and the clustering community is far from converging on one point of view. In a sample based setting most definitions agree on the fact that clusters should represent high density regions of the data space which are separated by low density regions. Then a straight forward way to define clusters is to use level sets of the density. Given the underlying density of the data space and a parameter , we define the -level set as the closure of the set of all points with . Clusters are then defined as the connected components of the -level set (where the term “connected component” is used in its topological sense and not in its graph-theoretic sense).

Note that a different popular model is to define a clustering as a partition of the whole underlying space such that the boundaries of the partition lie in a low density area. In comparison, looking for connected components of -level sets is a stronger requirement. Even when we are given a complete partition of the underlying space, we do not yet know which part of each of the clusters is just “background noise” and which one really corresponds to “interesting data”. This problem is circumvented by the

-level set definition, which not only distinguishes between the different clusters but also separates “foreground” from “background noise”. Moreover, the level set approach is much less sensitive to outliers, which often heavily influence the results of partitioning approaches.

The cluster identification problem. Given a finite sample from the underlying distribution, our goal is to identify the sets of points which come from different connected components of the -level set. We study this problem in two different settings:

The noise-free case. Here we assume that the support of the density consists of several connected components which have a positive distance to each other. Between those components, there is only “empty space” (density 0). Each of the connected components is called a cluster. Given a finite sample from such a density, we construct a neighborhood graph based on this sample. We say that a cluster is identified in the graph if the connected components in the neighborhood graph correspond to the corresponding connected components of the underlying density, that is all points originating in the same underlying cluster are connected in the graph, and they are not connected to points from any other cluster.

The noisy case. Here we no longer assume that the clusters are separated by “empty space”, but we allow the underlying density to be supported everywhere. Clusters are defined as the connected components of the -level set of the density (for a fixed parameter chosen by the user), and points not contained in this level set are considered as background noise. A point is called a cluster point if and background point otherwise. As in the previous case we will construct a neighborhood graph on the given sample. However, we will remove points from this graph which we consider as noise. The remaining graph will be a subgraph of the graph , containing fewer vertices and fewer edges than . As opposed to the noise-free case, we now define two slightly different cluster identification problems. They differ in the way background points are treated. The reason for this more involved construction is that in the noisy case, one cannot guarantee that no additional background points from the neighborhood of the cluster will belong to the graph.

We say that a cluster is roughly identified in the remaining graph if the following properties hold:

• all sample points from a cluster are contained as vertices in the graph, that is, only background points are dropped,

• the vertices belonging to the same cluster are connected in the graph, that is, there exists a path between each two of them, and

• every connected component of the graph contains only points of exactly one cluster (and maybe some additional noise points, but no points of a different cluster).

We say that a cluster is exactly identified in if

• it is roughly identified, and

• the ratio of the number of background points and the number of cluster points in the graph converges almost surely to zero as the sample size approaches infinity.

If all clusters have been roughly identified, the number of connected components of the graph is equal to the number of connected components of the level set . However, the graph might still contain a significant number of background points. In this sense, exact cluster identification is a much stronger problem, as we require that the fraction of background points in the graph has to approach zero. Exact cluster identification is an asymptotic statement, whereas rough cluster identification can be verified on each finite sample. Finally, note that in the noise-free case, rough and exact cluster identification coincide.

The clustering algorithms. To determine the clusters in the finite sample, we proceed as follows. First, we construct a neighborhood graph on the sample. This graph looks different, depending on whether we allow noise or not:

Noise-free case. Given the data, we simply construct the mutual or symmetric -nearest neighbor graph ( resp. ) on the data points, for a certain parameter , based on the Euclidean distance. Clusters are then the connected components of this graph.

Noisy case. Here we use a more complex procedure:

• As in the noise-free case, construct the mutual (symmetric) graph (resp. ) on the samples.

• Estimate the density at every sample point

(e.g., by kernel density estimation).

• If , remove the point and its adjacent edges from the graph (where is a parameter determined later). The resulting graph is denoted by (resp. ).

• Determine the connected components of (resp. ), for example by a simple depth-first search.

• Remove the connected components of the graph that are “too small”, that is, which contain less than points (where is a small parameter determined later).

• The resulting graph is denoted by (resp. ); its connected components are the clusters of the sample.

Note that by removing the small components in the graph the method becomes very robust against outliers and “fake” clusters (small connected components just arising by random fluctuations).

Main results, intuitively. We would like to outline our results briefly in an intuitive way. Exact statements can be found in the following sections.

Result 1 (Range of k for successful cluster identification).

Under mild assumptions, and for large enough, there exist constants such that for any , all clusters are identified with high probability in both the mutual and symmetric graph. This result holds for cluster identification in the noise-free case as well as for the rough and the exact cluster identification problem (the latter seen as an asymptotic statement) in the noisy case (with different constants ).

For the noise-free case, the lower bound on has already been proven in Brito et al. [5], for the noisy case it is new. Importantly, in the exact statement of the result all constants have been worked out more carefully than in Brito et al. [5], which is very important for proving the following statements.

Result 2.

(Optimal for cluster identification) Under mild assumptions, and for large enough, the parameter which maximizes the probability of successful identification of one cluster in the noise-free case has the form , where are constants which depend on the geometry of the cluster. This result holds for both the mutual and the symmetric graph, but the convergence rates are different (see Result 3). A similar result holds as well for rough cluster identification in the noisy case, with different constants.

This result is completely new, both in the noise-free and in the noisy case. In the light of the existing literature, it is rather surprising. So far it has been well known that in many different settings the lower bound for obtaining connected components in a random graph is of the order . However, we now can see that maximizing the probability of obtaining connected components on a finite sample leads to a dramatic change: has to be chosen much higher than , namely of the order itself. Moreover, we were surprised ourselves that this result does not only hold in the noise-free case, but can also be carried over to rough cluster identification in the noisy setting.

For exact cluster identification we did not manage to determine an optimal choice of due to the very difficult setting. For large values of , small components which can be discarded will no longer exist. This implies that a lot of background points are attached to the real clusters. On the other hand, for small values of there will exist several small components around the cluster which are discarded, so that there are less background points attached to the final cluster. However, this tradeoff is very hard to grasp in technical terms. We therefore leave the determination of an optimal value of for exact cluster identification as an open problem. Moreover, as exact cluster identification concerns the asymptotic case of only, and rough cluster identification is all one can achieve on a finite sample anyway, we are perfectly happy to be able to prove the optimal rate in that case.

Result 3 (Identification of the most significant cluster).

For the optimal as stated in Result 2, the convergence rate (with respect to ) for the identification of one fixed cluster is different for the mutual and the symmetric graph. It depends

• only on the properties of the cluster itself in the mutual graph

• on the properties of the “least significant”, that is the “worst” out of all clusters in the symmetric graph.

This result shows that if one is interested in identifying the “most significant” clusters only, one is better off using the mutual graph. When the goal is to identify all clusters, then there is not much difference between the two graphs, because both of them have to deal with the “worst” cluster anyway. Note that this result is mainly due to the different between-cluster connectivity properties of the graphs, the within-cluster connectivity results are not so different (using our proof techniques at least).

Proof techniques, intuitively. Given a neighborhood graph on the sample, cluster identification always consists of two main steps: ensuring that points of the same cluster are connected and that points of different clusters are not connected to each other. We call those two events “within-cluster connectedness” and “between-cluster disconnectedness” (or “cluster isolation”).

To treat within-cluster connectedness we work with a covering of the true cluster. We cover the whole cluster by balls of a certain radius . Then we want to ensure that, first, each of the balls contains at least one of the sample points, and second, that points in neighboring balls are always connected in the graph. Those are two contradicting goals. The larger is, the easier it is to ensure that each ball contains a sample point. The smaller is, the easier it is to ensure that points in neighboring balls will be connected in the graph for a fixed number of neighbors . So the first part of the proof consists in computing the probability that for a given both events occur at the same time and finding the optimal .

Between-cluster connectivity is easier to treat. Given a lower bound on the distance between two clusters, all we have to do is to make sure that edges in the graph never become longer than , that is we have to prove bounds on the maximal distance in the sample.

In general, those techniques can be applied with small modifications both in the noise-free and in the noisy case, provided we construct our graphs in the way described above. The complication in the noisy case is that if we just used the standard graph as in the noise-free case, then of course the whole space would be considered as one connected component, and this would also show up in the neighborhood graphs. Thus, one has to artificially reduce the neighborhood graph in order to remove the background component. Only then one can hope to obtain a graph with different connected components corresponding to different clusters. The way we construct the graph ensures this. First, under the assumption that the error of the density estimator is bounded by , we consider the -level set instead of the -level set we are interested in. This ensures that we do not remove “true cluster points” in our procedure. A second, large complication in the noisy case is that with a naive approach, the radius of the covering and the accuracy of the density estimator would be coupled to each other. We would need to ensure that the parameter decreases with a certain rate depending on . This would lead to complications in the proof as well as very slow convergence rates. The trick by which we can avoid this is to introduce the parameter and throw away all connected components which are smaller than . Thus, we ensure that no small connected components are left over in the boundary of the -level set of a cluster, and all remaining points which are in this boundary strip will be connected to the main cluster represented by the -level set. Note, that this construction allows us to estimate the number of clusters even without exact estimation of the density.

Building blocks from the literature. To a certain extent, our proofs follow and combine some of the techniques presented in Brito et al. [5] and Biau et al. [2].

In Brito et al. [5] the authors study the connectivity of random mutual -nearest neighbor graphs. However, they are mainly interested in asymptotic results, only consider the noise-free case, and do not attempt to make statements about the optimal choice of . Their main result is that in the noise-free case, choosing at least of the order ensures that in the limit for , connected components of the mutual -nearest neighbor graph correspond to true underlying clusters.

In Biau et al. [2], the authors study the noisy case and define clusters as connected components of the -level set of the density. As in our case, the authors use density estimation to remove background points from the sample, but then work with an -neighborhood graph instead of a -nearest neighbor graph on the remaining sample. Connectivity of this kind of graph is much easier to treat than the one of -nearest neighbor graphs, as the connectivity of two points in the -graph does not depend on any other points in the sample (this is not the case in the -nearest neighbor graph). Then, Biau et al. [2] prove asymptotic results for the estimation of the connected components of the level set , but also do not investigate the optimal choice of their graph parameter . Moreover, due to our additional step where we remove small components of the graph, we can provide much faster rates for the estimation of the components, since we have a much weaker coupling of the density estimator and the clustering algorithm.

Finally, note that a considerably shorter version of the current paper dealing with the noise-free case only has appeared in Maier et al. [11]. In the current paper we have shortened the proofs significantly at the expense of having slightly worse constants in the noise-free case.

3 General assumptions and notation

Density and clusters. Let be a bounded probability density with respect to the Lebesgue measure on . The measure on that is induced by the density is denoted by . Given a fixed level parameter , the -level set of the density is defined as

 L(t)=¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯{x∈Rd|p(x)≥t}.

where the bar denotes the topological closure (note that level sets are closed by assumptions in the noisy case, but this is not necessarily the case in the noise-free setting).

Geometry of the clusters. We define clusters as the connected components of (where the term “connected component” is used in its topological sense). The number of clusters is denoted by , and the clusters themselves by . We set , that means, the probability mass in cluster .

We assume that each cluster () is a disjoint, compact and connected subset of , whose boundary is a smooth -dimensional submanifold in with minimal curvature radius (the inverse of the largest principal curvature of ). For , we define the collar set and the maximal covering radius . These quantities will be needed for the following reasons: It will be necessary to cover the inner part of each cluster by balls of a certain fixed radius , and those balls are not supposed to “stick outside”. Such a construction is only possible under assumptions on the maximal curvature of the boundary of the cluster. This will be particularly important in the noisy case, where all statements about the density estimator only hold in the inner part of the cluster.

For an arbitrary , the connected component of which contains the cluster is denoted by . Points in the set will sometimes be referred to as boundary points. To express distances between the clusters, we assume that there exists some such that for all . The numbers will represent lower bounds on the distances between cluster and the remaining clusters. Note that the existence of the ensures that does not contain any other clusters apart from for . Analogously to the definition of above we set , that is the mass of the enlarged set . These definitions are illustrated in Figure 1.

Furthermore, we introduce a lower bound on the probability mass in balls of radius around points in

 ρ(i)≤infx∈C(i)−(2~ε)μ(B(x,u(i))).

In particular, under our assumptions on the smoothness of the cluster boundary we can set for an overlap constant

 O(i)(u(i))=infx∈C(i)−(2~ε)(vol(B(x,u(i))∩C(i)−(2~ε))/vol(B(x,u(i))))>0.

The way it is constructed, becomes larger the larger the distance of to all the other clusters is and is upper bounded by the probability mass of the extended cluster .

Example in the noisy case. All assumptions on the density and the clusters are satisfied if we assume that the density is twice continuously differentiable on a neighborhood of , for each the gradient of at is non-zero, and .

Example in the noise-free case. Here we assume that the support of the density consists of connected components which satisfy the smoothness assumptions above, and such that the densities on the connected components are lower bounded by a positive constant . Then the noise-free case is a special case of the noisy case.

Sampling. Our sample points will be sampled i.i.d. from the underlying probability distribution.

Density estimation in the noisy case. In the noisy case we will estimate the density at each data point by some estimate . For convenience, we state some of our results using a standard kernel density estimator, see Devroye and Lugosi [6] for background reading. However, our results can easily be rewritten with any other density estimate.

Further notation. The radius of a point is the maximum distance to a point in . denotes the minimal radius of the sample points in cluster , whereas denotes the maximal radius of the sample points in . Note here the difference in the point sets that are considered.

denotes the binomial distribution with parameters

and . Probabilistic events will be denoted with curly capital letters , and their complements with .

4 Exact statements of the main results

In this section we are going to state all our main results in a formal way. In the statement of the theorems we need the following conditions. The first one is necessary for both, the noise-free and the noisy case, whereas the second one is needed for the noisy case only.

• Condition 1: Lower and upper bounds on the number of neighbors ,

 k ≥4d+1p(i)maxtlog(28dp(i)maxvol(C(i))n), k ≤(n−1)min{ρ(i)2−2log(~β(i)n)(n−1),24dηdp(i)maxmin{(u(i))d,(ν(i)max)d}}.
• Condition 2: The density is three times continuously differentiable with uniformly bounded derivatives, , and sufficiently small such that .

Note that in Theorems 1 to 3 is considered small but constant and thus we drop the index there.

In our first theorem, we present the optimal choice of the parameter in the mutual graph for the identification of a cluster. This theorem treats both, the noise-free and the noisy case.

Theorem 1.

(Optimal for identification of one cluster in the mutual graph) The optimal choice of for identification of cluster in (noise-free case) resp. rough identification in (noisy case) is

 k=(n−1)Γ(i)+1, with Γ(i):=ρ(i)2+14dtp(i)max,

provided this choice of fulfills Condition 1.
In the noise-free case we obtain with and for sufficiently large

 P(Cluster C(i) is identified in Gmut(n,k))≥1−3e−(n−1)Ω(i)noisefree.

For the noisy case, assume that additionally Condition 2 holds and let be a kernel density estimator with bandwidth . Then there exist constants such that if we get with

 Ω(i)noisy=min{ρ(i)24d+1p(i)maxt+4,nn−1δ8,nn−1C2hdε2}

and for sufficiently large

 P(Cluster C(i) roughly identified in ~Gmut(n,k,t−ε,δ))≥1−8e−(n−1)Ω(i)noisy.

This theorem has several remarkable features. First of all, we can see that both in the noise-free and in the noisy case, the optimal choice of is roughly linear in . This is pretty surprising, given that the lower bound for cluster connectivity in random geometric graphs is . We will discuss the important consequences of this result in the last section.

Secondly, we can see that for the mutual graph the identification of one cluster only depends on the properties of the cluster , but not on the ones of any other cluster. This is a unique feature of the mutual graph which comes from the fact that if cluster is very “dense”, then the neighborhood relationship of points in never links outside of cluster . In the mutual graph this implies that any connections of to other clusters are prevented. Note that this is not true for the symmetric graph, where another cluster can simply link into , no matter which internal properties has.

For the mutual graph, it thus makes sense to define the most significant cluster as the one with the largest coefficient , since this is the one which can be identified with the fastest rate. In the noise-free case one observes that the coefficient of cluster is large given that

• is large, which effectively means a large distance of to the closest other cluster,

• is small, so that the density is rather uniform inside the cluster ..

Note that those properties are the most simple properties one would think of when imagining an “easily detectable” cluster. For the noisy case, a similar analysis still holds as long as one can choose the constants and small enough.

Formally, the result for identification of clusters in the symmetric graph looks very similar to the one above.

Theorem 2.

(Optimal for identification of one cluster in the symmetric graph) We use the same notation as in Theorem 1 and define . Then all statements about the optimal rates for in Theorem 1 can be carried over to the symmetric graph, provided one replaces with in the definitions of , and . If Condition 1 holds and the condition replaces the corresponding one in Condition 1, we have in the noise-free case for sufficiently large

If additionally Condition 2 holds we have in the noisy case for sufficiently large

 P(C(i) roughly identified in ~Gsym(n,k,t−ε,δ))≥1−(m+7)e−(n−1)Ω(i)noisy.

Observe that the constant has now been replaced by the minimal among all clusters . This means that the rate of convergence for the symmetric graph is governed by the constant of the “worst” cluster, that is the one which is most difficult to identify. Intuitively, this worst cluster is the one which has the smallest distance to its neighboring clusters. In contrast to the results for the mutual graph, the rate for identification of in the symmetric graph is governed by the worst cluster instead of the cluster itself. This is a big disadvantage if the goal is to only identify the “most significant” clusters. For this purpose the mutual graph has a clear advantage.

On the other hand as we will see in the next theorem that the difference in behavior between the mutual and symmetric graph vanishes as soon as we attempt to identify all clusters.

Theorem 3.

(Optimal for identification of all clusters in the mutual graph) We use the same notation as in Theorem 1 and define , . The optimal choice of for the identification of all clusters in the mutual graph in (noise-free case) resp. rough identification of all clusters in (noisy case) is given by

 k=(n−1)Γall+1,withΓall=ρmin2+14dtpmax,

provided this choice of fulfills Condition 1 for all clusters . In the noise-free case we get the rate

 Ωnoisefree=ρmin24d+1pmaxt+4,

such that for sufficiently large

 P(All clusters exactly identified in Gmut(n,k))≥1−3me−(n−1)Ωnoisefree.

For the noisy case, assume that additionally Condition 2 holds for all clusters and let be a kernel density estimator with bandwidth . Then there exist constants such that if we get with

 Ωnoisy=min{ρmin24d+1pmaxt+4,nn−1δ8,nn−1C2hdε2}

and for sufficiently large

 P(All clusters roughly ident. in ~Gmut(n,k,t−ε,δ))≥1−(3m+5)e−(n−1)Ωnoisy.

We can see that as in the previous theorem, the constant which now governs the speed of convergence is the worst case constant among all the . In the setting where we want to identify all clusters this is unavoidable. Of course the identification of “insignificant” clusters will be difficult, and the overall behavior will be determined by the most difficult case. This is what is reflected in the above theorem. The corresponding theorem for identification of all clusters in the symmetric graph looks very similar, and we omit it.

So far for the noisy case we mainly considered the case of rough cluster identification. As we have seen, in this setting the results of the noise-free case are very similar to the ones in the noisy case. Now we would like to conclude with a theorem for exact cluster identification in the noisy case.

Theorem 4 (Exact identification of clusters in the noisy case).

Let be three times continuously differentiable with uniformly bounded derivatives and let be a kernel density estimator with bandwidth for some . For a suitable constant set . Then there exist constants such that for and we obtain

 Cluster C(i) is exactly identified in ~Gmut(n,k,t−εn,δ) almost surely.

Note that as opposed to rough cluster identification, which is a statement about a given finite nearest neighbor graph, exact cluster identification is an inherently asymptotic property. The complication in this asymptotic setting is that one has to balance the speed of convergence of the density estimator with the one of the “convergence of the graph”. The exact form of the density estimation is not important. Every other density estimator with the same convergence rate would yield the same result. One can even lower the assumptions on the density to (note that differentiability is elsewhere required). Finally, note that since it is technically difficult to grasp the graph after the small components have been discarded, we could not prove what the optimal in this setting should be.

5 Proofs

The propositions and lemmas containing the major proof steps are presented in Section 5.1. The proofs of the theorems themselves can be found in Section 5.2. An overview of the proof structure can be seen in Figure 2.

5.1 Main propositions for cluster identification

In Proposition 1 we identify some events whose combination guarantee the connectedness of a cluster in the graph and at the same time that there is not a connected component of the graph that consists of background points only. The probabilities of the events appearing in the proposition are then bounded in Lemma 2-5. In Proposition 6 and Lemma 7 we examine the probability of connections between clusters. The section concludes with Proposition 8 and Lemma 9, which are used in the exact cluster identification in Theorem 4, and some remarks about the differences between the noise-free and the noisy case.

Proposition 1 (Connectedness of one cluster C(i) in the noisy case).

Let denote the event that in (resp. ) it holds that

• all the sample points from are contained in the graph,

• the sample points from are connected in the graph,

• there exists no component of the graph which consists only of sample points from outside .

Then under the conditions

1. ,

2. sufficiently small such that ,

3. ,
,

and for sufficiently large , we obtain

 P((C(i)n)c) ≤P((A(i)n)c)+P((B(i)n)c)+P(Ecn)+P(Dcn) ≤2e−k−14d+1tp(i)max+2e−nδ8+2P(Dcn),

where the events are defined as follows:

• : the subgraph consisting of points from is connected in (resp. ),

• : there are more than sample points from cluster ,

• : there are less than sample points in the set , and

• : for all sample points , .

Proof.

We bound the probability of using the observation that implies

 P((C(i)n)c) ≤P((A(i)n)c)+P((B(i)n)c)+P(Ecn)+P(Dcn). (1)

This follows from the following chain of observations. If the event holds, no point with is removed, since on this event and thus , which is the threshold in the graph .

If the samples in cluster are connected in (), and there are more than samples in cluster (), then the resulting component of the graph is not removed in the algorithm and is thus contained in .

Conditional on all remaining samples are contained in . Thus all non cluster samples lie in . Given that this set contains less than samples, there can exist no connected component only consisting of non cluster points, which implies that all remaining non cluster points are connected to one of the clusters.

The probabilities for the complements of the events , and are bounded in Lemmas 3 to 5 below. Plugging in those bounds into Equation (1) leads to the desired result. ∎

We make frequent use of the following tail bounds for the binomial distribution introduced by Hoeffding.

Theorem 5 (Hoeffding, [9]).

Let and define . Then,

 α≥p, P(M≥k)≤e−nK(α||p), α≤p, P(M≤k)≤e−nK(α||p),

where

is the Kullback-Leibler divergence of

and ,

 K(α||p)=αlog(αp)+(1−α)log(1−α1−p).

In the following lemmas we derive bounds for the probabilities of the events introduced in the proposition above.

Lemma 2 (Within-cluster connectedness (A(i)n)).

As in Proposition 1 let denote the event that the points of cluster are connected in (resp. ). For ,

 P((A(i)n)c) ≤nβ(i)P(M≥k)+N(1−tηdzd4d)n+P(Dcn),

where is a

-distributed random variable and

.

Proof.

Given that holds, all samples lying in cluster are contained in the graph . Suppose that we have a covering of with balls of radius . By construction every ball of the covering lies entirely in , so that is a lower bound for the minimal density in each ball. If every ball of the covering contains at least one sample point and the minimal radius of samples in is larger or equal to , then all samples of are connected in given that . Moreover, one can easily check that all samples lying in the collar set are connected to . In total, then all samples points lying in are connected. Denote by the event that one ball in the covering with balls of radius contains no sample point. Formally, implies connectedness of the samples lying in in the graph .

Define for . Then . We have

 P(R(i)min≤z) ≤n∑s=1P(Ns≥k|Xs∈C(i))P(Xs∈C(i))≤nβ(i)P(U≥k),

where . The final result is obtained using the upper bound .

For the covering a standard construction using a -packing provides us with the covering. Since we know that balls of radius around the packing centers are subsets of and disjoint by construction. Thus, the total volume of the balls is bounded by the volume of and we get . Since we assume that holds, no sample lying in has been discarded. Thus the probability for one ball of the covering being empty can be upper bounded by , where we have used that the balls of the covering are entirely contained in and thus the density is lower bounded by . In total, a union bound over all balls in the covering yields,

 P(F(i)z)≤N(1−tηdzd/4d)n+P(Dcn).

Plugging both results together yields the final result. ∎

In Lemma 2 we provided a bound on the probability which includes two competing terms for the choice of . One favors small whereas the other favors large . The next lemma will provide a trade-off optimal choice of the radius in terms of .

Lemma 3 (Choice of k for within-cluster connectedness (A(i)n)).

If fulfills Condition (3) of Proposition 1, we have for sufficiently large

 P((A(i)n)c)≤2e−k−14d+1tp(i)max+P(Dcn).
Proof.

The upper bound on the probability of given in Lemma 2 has two terms dependent on . The tail bound for the binomial distribution is small if is chosen to be small, whereas the term from the covering is small given that is large. Here, we find a choice for which is close to optimal. Define and . Using Theorem 5 we obtain for and a choice of such that ,

 nβ(i)P(M≥k) ≤nβ(i)e−(n−1)(αlog(αp)+(1−α)log(1−α1−p)) ≤nβ(i)e−(n−1)(αlog(αp)+p−α),

where we have used for . Now, introduce so that , where with we get, . Then,

 nβ(i)P(M≥k) ≤nβ(i)e−k(log(1p(i)maxθ)+θp(i)max−1) ≤e−k2(log(1p(i)maxθ)+θp(i)max−1), (2)

where we used in the last step an upper bound on the term which holds given . On the other hand,

 N(1−tηdzd/4d)n=Nen