An Upper Bound on Stirling Number of the Second Kind

We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman.

Definition A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of \(n\) objects into \(k\) non-empty subsets and is denoted by \(S(n,k)\).

Proposition For all \(n, k\), we have $$S(n,k) \leq \frac{k^n}{k!}\left(1-(1-1/m)^k\right)^m.$$

Proof Consider a random bipartite graph with partite sets \(U:=[n], V:=[k]\). For each vertex \(u\in U\), it (independently) connects to exactly one of the vertices in \(V\) uniformly at random. Suppose \(X\) is the set of non-isolated vertices in \(V\). It is easy to see that $$\operatorname{Pr}\left(X=V\right) = \frac{\text{number of surjections from }U\text{ to }V}{k^n} = \frac{k!S(n,k)}{k^n}.$$

On the other hand,  we claim that for any \(\emptyset \neq A \subset [k]\) and \(i \in [k]\setminus A\), $$\operatorname{Pr}\left(i\in X \mid A\subset X\right) \leq \operatorname{Pr}\left(i\in X\right).$$ Note that the claim is equivalent to $$\operatorname{Pr}\left(A\subset X \mid i\notin X\right) \geq \operatorname{Pr}\left(A\subset X\right).$$ Consider the same random bipartite graph with \(V\) replaced by \(V’:=[k]\setminus \{i\}\) and let \(X’\) be the set of non-isolated vertices in \(V’\). The claim is justified since $$\operatorname{Pr}\left(A\subset X\mid i\notin X\right) = \operatorname{Pr}\left(A\subset X’\right) \geq \operatorname{Pr}\left(A\subset X\right).$$

Set \(A:=[i-1]\) in above for \(i = 2, \ldots, k\). Using the multiplication rule with telescoping the conditional probability, we obtain $$\begin{eqnarray}\operatorname{Pr}\left(X=V\right) &=& \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X \mid [1]\subset X\right)\ldots \operatorname{Pr}\left(k\in X\mid [k-1]\subset X\right)\\ & \leq & \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X\right)\ldots\operatorname{Pr}\left(k\in X\right) \\ & = & \left(1-(1-1/m)^k\right)^m.\end{eqnarray}$$ QED.

4 (this post is made with love)

A Probabilistic Proof of Isoperimetric Inequality

This note is based on Nicolas Garcia Trillos’ talk, Some Problems and Techniques in Geometric Probability, at Carnegie Mellon University on January 29, 2015.

In particular, we demonstrate a probabilistic proof of the isoperimetric inequality. The proof can also be found in Integral Geometry and Geometric Probability by Luis A. Santaló.

Theorem For a convex set with perimeter \(L\) and area \(A\), the isoperimetric inequality states that \(4\pi A\leq L^2\), and that equality holds if and only if the convex set is a disk. (Assume that the boundary is a closed convex curve of class \(C^1\).)

Proof Let \(P(s)\) parametrize the boundary by its arc length \(s\). Given \(s\) and \(\theta\). Suppose the line through \(P(s)\) whose angle to the tangent line equals \(\theta\) intersects the boundary at another point \(Q(s)\). Let \(\sigma(s, \theta)\) be the length of the chord between the two intersections \(P(s), Q(s)\). Consider the integral $$\int (\sigma_1\sin\theta_2 – \sigma_2\sin\theta_1)^2 \mathrm{d}s_1\mathrm{d}\theta_1\mathrm{d}s_2\mathrm{d}\theta_2,$$ where the integration extends over \(0 \leq s_1, s_2 \leq L\) and \(0 \leq \theta_1, \theta_2 \leq \pi\).

Random variables
Random variables

Expanding the square in the integrand, we obtain that the integral is equal to $$\pi L \int \sigma^2\mathrm{d}s\mathrm{d}\theta – 2\left(\int \sigma\sin\theta\mathrm{d}s\mathrm{d}\theta\right)^2.$$

On one hand, we have $$\int \sigma^2\mathrm{d}s\mathrm{d}\theta = \int_0^L\int_0^\pi \sigma^2\mathrm{d}\theta\mathrm{d}s = \int_0^L 2A\mathrm{d}s = 2LA.$$

Change variables
Change variables

On the other hand, let \(p\) be the distance from the chord to the origin and \(\phi\) the angle from the \(x\)-axis to the chord. Suppose the angle from the \(x\)-axis to the tangent line is \(\tau\). We have $$p = \langle x, y\rangle\cdot\langle \sin\phi, -\cos\phi \rangle = x\sin\phi – y\cos\phi.$$ Differentiating the latter, we get $$\mathrm{d}p = \sin\phi\mathrm{d}x – \cos\phi\mathrm{d}y + (x\cos\phi + y\sin\phi)\mathrm{d}\phi.$$ Moreover, we know that $$\mathrm{d}x = \cos\tau\mathrm{d}s, \mathrm{d}y = \sin\tau\mathrm{d}s.$$ Therefore $$\mathrm{d}p = \sin\phi\cos\tau\mathrm{d}s – \cos\phi\sin\tau\mathrm{d}s + + (x\cos\phi + y\sin\phi)\mathrm{d}\phi,$$ and so $$\mathrm{d}p\mathrm{d}\phi = \sin(\phi – \tau)\mathrm{d}s\mathrm{d}\phi.$$ Since \(\theta + \phi = \tau\) and \(\mathrm{d}\theta + \mathrm{d}\phi = \tau’\mathrm{d}s\), we have $$\mathrm{d}p\mathrm{d}\phi = -\sin\theta\mathrm{d}s\mathrm{d}\theta,$$ and so $$\int\sigma\sin\theta\mathrm{d}s\mathrm{d}\theta = \int_0^{2\pi}\int_{-\infty}^\infty \sigma\mathrm{d}p\mathrm{d}\theta = 2\pi A.$$

Since the integral is non-negative, we have that \(2\pi A(L^2 – 4\pi A)\geq 0\), and so \(4\pi A \leq L^2\). The equality is achieved if and only if \(\sigma / \sin\theta\) is a constant, in which case the boundary is a circle. QED.

Remark The proof is considered a probabilistic proof because the differential form \(\mathrm{d}p\mathrm{d}\theta\) is the measure (invariant under rigid motion) of a random line.

0 (be the first to like this)