Intereting Posts

Morphism from a line bundle to a vector bundle
Why Do Structured Sets Often Get Referred to Only by the Set?
Wanted: example of an increasing sequence of $\sigma$-fields whose union is not a $\sigma$-field
CW complex structure on standard sphere identifying the south pole and north pole
How to construct polynomial ring $K$ over commutative ring $K$ by making use of universal arrows.
Derivative at x=0 of piecewise funtion
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression?
Prove that $\gcd(x, y)=\gcd(x,ax+y)$, would this be the correct reasoning?
If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$
What is $(-1)^{\frac{2}{3}}$?
Let $A=\{\sum_{i=1}^{\infty} \frac{a_i}{5^{i}}:a_i=0,1,2,3$ or $4 \} \subset \mathbb{R}$. Then which of the following are true??
Probability of getting k different coupons in a set of S coupons, from an infinite set of N different types of coupons.
Number of generators of the maximal ideals in polynomial rings over a field
Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.
Is the following set a manifold?

Given a set $S$ such that $|S|=n$,

A random item is chosen randomly from $S$, and being appended to a new set $T$.

This process is being repeated $n$ times (with repetition), what is the expected value of $|T|$ ?

- Number of ways of distributing balls into boxes
- Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?
- Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$
- How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?
- Probability of number of unique numbers in $37$ Roulette Wheel spins.
- If n balls are thrown into k bins, what is the probability that every bin gets at least one ball?

- A disease spreading through a triangular population
- Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?
- Combinatorics problem: $n$ people line up to $m$ clubs
- Expected Value of Maximum of Two Lognormal Random Variables with One Source of Randomness
- Proving $E=3σ^4$
- How do you prove that if $ X_t \sim^{iid} (0,1) $, then $ E(X_t^{2}X_{t-j}^{2}) = E(X_t^{2})E(X_{t-j}^{2})$?
- Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?
- How much area in a unit square is not covered by $k$ disks of area $1/k$ centered at random points within the square?
- Expectation of norm of a random variable
- Question on the 'Hat check' problem

Let $T_k$ be the number of elements in $T$ after $k$ rounds. We also set $T_0 = 0$.

Assuming that $T_k = l$, you have a probability of $\frac{l}{n}$ that the $k + 1$-th element is already in $T$ and a probability of $\frac{n – l}{n}$ that it isn’t. This means:

$$E[T_{k + 1} \mid T_k = l] = \frac{l}{n} l + \frac{n – l}{n}(l+1) = l\left(1 – \frac{1}{n}\right) + 1$$

Now we can apply the law of total expectation:

$$E[T_{k + 1}] = E[E[T_{k + 1} \mid T_k]] = E\left[T_k \left(1 – \frac{1}{n}\right) + 1\right] = E[T_k] \left(1 – \frac{1}{n}\right) + 1$$

This is a geometric progession and we can explicitly calculate:

$$E[T_k] = \sum \limits_{i = 0}^{k – 1} \left(1 – \frac{1}{n}\right)^i = n\left(1 – \left(1 – \frac{1}{n}\right)^k\right)$$

Specifically for $k = n$ this yields

$$E[T_n] = n\left(1 – \left(1 – \frac{1}{n}\right)^n\right) \approx n(1 – e^{-1}) \approx \frac{2}{3} n.$$

For $x\in S$ define $A_x$ to be the event that $x\in T$.

Then $|T|=\sum_{x\in S} 1_{A_x}$ which has expected value

$$\mathbb{E}(X)=\sum_{x\in S} \mathbb{P}(A_x)=n\left[1-\left(1-{1\over n}\right)^n\right].$$

This question can also be answered by total enumeration using Stirling

numbers of the second kind. Observe that the expectation is given by

$$\mathrm{E}[X] = n^{-n} \sum_{k=0}^n k \times {n\choose k}

k! {n\brace k}.$$

Here we multiply the value of the random variable by the probability,

which is obtained from the fact that a sample with $k$ different

entries needs a choice of these entries from the $n$ possibles and a

partition of the $n$ slots into $k$ sets whose elements receive the

same value. All $k!$ permutations of the $k$ chosen values result in

a valid unique assignment.

We have

$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}$$

by the species equation for set partititions

$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

which yields for the expectation

$$n^{-n} n! [z^n]

\sum_{k=0}^n k \times {n\choose k}

(\exp(z)-1)^k

\\ = n^{-n} n! [z^n] n

\sum_{k=1}^n {n-1\choose k-1}

(\exp(z)-1)^k

\\ = n^{-n} n! [z^n] n (\exp(z)-1)

\sum_{k=0}^{n-1} {n-1\choose k}

(\exp(z)-1)^k

\\ = n^{-n} n! [z^n] n (\exp(z)-1) \exp((n-1)z)

= n n^{-n} n! [z^n] (\exp(nz)-\exp((n-1)z))

\\ = n n^{-n} (n^n – (n-1)^n)

\\ = n \left(1 – \left(1-\frac{1}{n}\right)^n\right)

\sim n \left(1 – \frac{1}{e}\right).$$

Now we can also compute higher moments with this,

the variance for example.

We first compute the expectation of $X(X-1)$, getting

$$\mathrm{E}[X(X-1)] =

n^{-n} \sum_{k=0}^n k (k-1) \times {n\choose k}

k! {n\brace k}

\\ = n^{-n} n! [z^n] n (n-1)

\sum_{k=2}^n {n-2\choose k-2}

(\exp(z)-1)^k

\\ = n^{-n} n! [z^n] n (n-1) (\exp(z)-1)^2

\sum_{k=0}^{n-2} {n-2\choose k}

(\exp(z)-1)^k

\\ = n^{-n} n! [z^n] n (n-1) (\exp(z)-1)^2 \exp((n-2)z).$$

Extracting coefficients we obtain

$$n (n-1) n^{-n} (n^n – 2(n-1)^n + (n-2)^n)

= n(n-1) \left(1-2\left(1-\frac{1}{n}\right)^n

+\left(1-\frac{2}{n}\right)^n\right)

\\ \sim

n(n-1) \left(1-\frac{2}{e}+\frac{1}{e^2}\right).$$

We thus get for the variance

$$\mathrm{Var}[X] = \mathrm{E}[X^2] – \mathrm{E}[X]^2

\\ = n(n-1) \left(1-2\left(1-\frac{1}{n}\right)^n

+\left(1-\frac{2}{n}\right)^n\right)

\\ + n\left(1-\left(1-\frac{1}{n}\right)^n\right)

– n^2\left(1-\left(1-\frac{1}{n}\right)^n\right)^2

\\ = n^2 \left(\left(1-\frac{2}{n}\right)^n

– \left(1-\frac{1}{n}\right)^{2n}\right)

\\ + n \left(\left(1-\frac{1}{n}\right)^n

– \left(1-\frac{2}{n}\right)^n \right).$$

The asymptotic expansion then yields

$$\mathrm{Var}[X] \sim n \left(\frac{1}{e}-\frac{2}{e^2}\right).$$

**Addendum.** We need the second term rather than the constant term in

the asymptotic expansion of the factor on $n^2.$

We get for the first term in the difference

$$\exp\left(n\log\left(1-\frac{2}{n}\right)\right)

= \exp\left(-\sum_{q\ge 1} \frac{2^q}{n^{q-1} q}\right)

\\ = \sum_{k\ge 0} \frac{(-1)^k}{k!}

\left(\sum_{q\ge 1} \frac{2^q}{n^{q-1} q}\right)^k.$$

This yields for the constant term

$$\sum_{k\ge 0} \frac{(-1)^k}{k!} 2^k = \frac{1}{e^2}.$$

We get for the next term

$$\frac{1}{n}

\sum_{k\ge 0} \frac{(-1)^k}{k!}

{k\choose 1} 2\times 2^{k-1}

= -\frac{2}{n}

\sum_{k\ge 1} \frac{(-1)^{k-1}}{(k-1)!} 2^{k-1}

= -\frac{2}{n} \frac{1}{e^2}.$$

For the second term in the difference we have

$$\exp\left(2n\log\left(1-\frac{1}{n}\right)\right)

= \exp\left(-2\sum_{q\ge 1} \frac{1}{n^{q-1} q}\right)

\\ = \sum_{k\ge 0} \frac{(-2)^k}{k!}

\left(\sum_{q\ge 1} \frac{1}{n^{q-1} q}\right)^k.$$

This time we get for the constant term

$$\sum_{k\ge 0} \frac{(-2)^k}{k!} = \frac{1}{e^2}$$

and for the next term

$$\frac{1}{n}

\sum_{k\ge 0} \frac{(-2)^k}{k!}

{k\choose 1} \frac{1}{2} \times 1^{k-1}

= -\frac{1}{n}

\sum_{k\ge 1} \frac{(-2)^{k-1}}{(k-1)!}

= -\frac{1}{n} \frac{1}{e^2}.$$

The difference then yields for the variance

$$n^2 \left(-\frac{1}{n} \frac{1}{e^2}\right)

+ n\left(\frac{1}{e}-\frac{1}{e^2}\right)$$

which is the desired result.

We can count the number of arrangements of $n$ items picked from a pool of $n$ items that have $d$ distinct items.

Let $S(i)$ be the collection of arrangements missing item $i$. Let $N(j)$ be the sum of the sizes of all intersections of $j$ of the $S(i)$.

Since we can choose $\binom{n}{j}$ items to leave out and for each of those choices there are $(n-j)^n$ arrangements of those items, we have

$$

N(j)=\binom{n}{j}(n-j)^n\tag{1}

$$

Since the number of arrangements with $d$ distinct items is the number of arrangements missing exactly $n-d$ items, according to the Generalized Inclusion-Exclusion Principle, the number of arrangements with exactly $d$ distinct items is

$$

\sum_{j=n-d}^n(-1)^{j-n+d}\binom{j}{n-d}N(j)

=\sum_{j=n-d}^n(-1)^{j-n+d}\binom{j}{n-d}\binom{n}{j}(n-j)^n\tag{2}

$$

To get the total number of arrangements, sum $(2)$ in $d$:

$$

\begin{align}

\sum_{d=0}^n\sum_{j=n-d}^n(-1)^{j-n+d}\binom{j}{n-d}\binom{n}{j}(n-j)^n

&=\sum_{j=0}^n\sum_{d=n-j}^n(-1)^{j-n+d}\binom{j}{n-d}\binom{n}{j}(n-j)^n\\

&=\sum_{j=0}^n[j=0]\binom{n}{j}(n-j)^n\\[9pt]

&=n^n\tag{3}

\end{align}

$$

as expected.

To get the total number of arrangements times their size, multiply by $d$ and sum in $d$:

$$

\begin{align}

\sum_{d=0}^n\sum_{j=n-d}^n(-1)^{j-n+d}\binom{j}{n-d}\binom{n}{j}(n-j)^nd

&=\sum_{j=0}^n\sum_{d=n-j}^n(-1)^{j-n+d}\color{#00A000}{\binom{j}{n-d}}\binom{n}{j}(n-j)^n(\color{#C00000}{n}-\color{#00A000}{(n-d)})\\

&=\color{#C00000}{n\,n^n}-\sum_{j=0}^n\sum_{d=n-j}^n(-1)^{j-n+d}\color{#00A000}{\binom{j-1}{n-d-1}}\binom{n}{j}(n-j)^n\color{#00A000}{j}\\

&=n\,n^n-\sum_{j=0}^n[j=1]\binom{n}{j}(n-j)^nj\\[9pt]

&=n\,n^n-n(n-1)^n\tag{4}

\end{align}

$$

Therefore, the expected number of distinct items picked would be

$$

n\left[1-\left(1-\frac1n\right)^n\right]\sim n\left(1-\frac1e\right)\tag{5}

$$

- Increase by one, Shortest path, changes the edges or not?
- Coordinates of a point which we know distance from another …
- Is my proof that the product of covering spaces is a covering space correct?
- Find a change in variable that will reduce the quadratic form to a sum of squares
- Indicator function for a vertex-induced random subgraph of $G$?
- Can any finite group be realized as the automorphism group of a directed acyclic graph?
- Proof of the least upper bound or completeness axiom corollary (greatest lower bound)
- Distribution of Functions of Random Variables
- Are $\pi$ and $e$ algebraically independent?
- Is a sphere a closed set?
- Why must polynomial division be done prior to taking the limit?
- Ten soldiers puzzle
- Can a finitely generated group have infinitely many torsion elements?
- Distance traveled by a bouncing ball with exponentially diminishing rebounds
- Prove that $\sin x \cdot \sin (2x) \cdot \sin(3x) < \tfrac{9}{16}$ for all $x$