Intereting Posts

Reference request: Vector bundles and line bundles etc.
lacunary sum of binomial coefficients
Can a fractal be a manifold? if so: will its boundary (if exists) be strictly one dimension lower?
How did we know to invent homological algebra?
Complete induction proof that every $n > 1$ can be written as a product of primes
Real Analysis, Folland Problem 6.1.2 $L^p$ spaces
$f: \mathbb{R}^2 \to \mathbb{R}$ a continuous open map, show that for each $x \in \text{range}(f)$, $f^{-1}(x)$ is always uncountable.
Learning Model Theory
Prove or find a counter example to the claim that for all sets A,B,C if A ∩ B = B ∩ C = A ∩ C = Ø then A∩B∩C ≠ Ø
distribution of days in a week on Christmas
Determine if the following subsets are subspaces of $\mathbb R^3$
Why does finding the $x$ that maximizes $\ln(f(x))$ is the same as finding the $x$ that maximizes $f(x)$?
If $b_n$ is a bounded sequence and $\lim a_n = 0$, show that $\lim(a_nb_n) = 0$
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
Roots of $y=x^3+x^2-6x-7$

For example, consider a 6 sided die rolled 10 times. Based on the following monte-carlo simulation, I get that the side that appears most will appear 3.44 times on average.

```
n = 6
k = 10
samples = 10000
results = []
for _ in range(samples):
counts = {s:0 for s in range(n)}
for _ in range(k):
s = randint(0, n-1)
counts[s] += 1
results.append(max(counts.values()))
print sum(results)/float(len(results))
```

But I can’t figure out how to get this in a closed form for any particular N and K.

- Analysis of “Tiny Dice Dungeon” (I)
- Finding $X_t$ of an Itô Diffusion
- Is $E\left$ = $\frac{1}{\sum_{i=1}^{n} E\left}$?
- Can you make money on coin tosses when the odds are against you?
- Expectation of an Absolute Value that is the Standard Normal?
- Would you ever stop rolling the die?

- Convergence in distribution to derive the expectation convergence
- Result and proof on the conditional expectation of the product of two random variables
- Expected number of unpecked chicks - NYT article
- Should you ever stop rolling, THE SEQUEL
- Prove that if expectations agree on a Pi-System, then they agree on the Sigma-Algebra generated by the Pi-System.
- Expected value: Random sequence
- Can you make money on coin tosses when the odds are against you?
- How much area in a unit square is not covered by $k$ disks of area $1/k$ centered at random points within the square?
- Computing expectation of: $\small E\left $
- If U1, U2, U3 are iid Uniform, then what is the probability of U1+U2>U3?

Not an answer, but it’s worth trying some example with small $N$.

Let $M$ be your number.

For $n=2$, and any $k/2 < m \leq k$ you have $P(M=m)=\frac{\binom{k}{m}}{2^{k-1}}$. If $k$ even, then $P(M=k/2)=\frac{\binom{k}{k/2}}{2^k}$.

So, for $k=2j+1$ odd, you have:

$$\begin{align}E(M)&=\frac{1}{2^{2j}}\sum_{m=j+1}^{2j+1} m\binom{2j+1}{m}\\

&=\frac{2j+1}{2^{2j}}\sum_{m=j+1}^{2j+1}\binom{2j}{m-1}\\

&=\frac{2j+1}{2^{2j}}\sum_{m=j}^{2j}\binom{2j}{m}\\

&=\frac{2j+1}{2^{2j}}\left(\frac{1}{2}2^{2j}+\frac{1}{2}\binom{2j}{j}\right)\\

&=\frac{k}{2}\left(1+\frac{\binom{k-1}{(k-1)/2}}{2^{k-1}}\right)

\end{align}$$

For $N=2$ and $k=2j$, you get: $$

\begin{align}E(M)&=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{1}{2^{2j-1}}\sum_{m=j+1}^{2j}m\binom{2j}{m}\\

&=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{2j}{2^{2j-1}}\sum_{m=j+1}^{2j}\binom{2j-1}{m-1}\\

&=j\frac{\binom{2j}{j}}{2^{2j}}+\frac{j}{2^{2j-2}}\cdot\frac{2^{2j-1}}{2}\\

&=\frac{k}{2}\left(1+\frac{\binom{k}{k/2}}{2^k}\right)

\end{align}$$

It’s gonna get messier when trying it for $N=3$.

Here is a closed form, we will need more sophisticated methods for the

asymptotics.

Following the notation introduced at this MSE

link we suppose

that the die has $m$ faces and is rolled $n$ times. Rolling the die

with the most occured value being $q$ and instances of this size being

marked yields the species

$$\mathfrak{S}_{=m}

(\mathfrak{P}_{=0}(\mathcal{Z})

+ \mathfrak{P}_{=1}(\mathcal{Z})

+ \cdots

+ \mathcal{V}\mathfrak{P}_{=q}(\mathcal{Z})).$$

This has generating function

$$G(z,v) =

\left(\sum_{r=0}^{q-1} \frac{z^r}{r!} + v\frac{z^q}{q!}\right)^m.$$

Subtracting the values where sets of size $q$ did not occur we obtain

the generating function

$$H_{q}(z) =

\left(\sum_{r=0}^{q} \frac{z^r}{r!}\right)^m

– \left(\sum_{r=0}^{q-1} \frac{z^r}{r!}\right)^m.$$

This also follows more or less by inspection.

We then obtain for the desired quantity the closed form

$$\bbox[5px,border:2px solid #00A000]{

\frac{n!}{m^n}

[z^n] \sum_{q=1}^n q H_q(z).}$$

Introducing

$$L_{q}(z) =

\left(\sum_{r=0}^{q} \frac{z^r}{r!}\right)^m$$

we thus have

$$\frac{n!}{m^n} [z^n] \sum_{q=1}^n q (L_{q}(z) – L_{q-1}(z)).$$

This is

$$\frac{n!}{m^n} [z^n]

\left(n L_n(z) – \sum_{q=0}^{n-1} L_q(z)\right).$$

We also have for

$$[z^n] L_q(z) =

\sum_{k=0}^{\min(q, n)} \frac{1}{k!} [z^{n-k}]

\left(\sum_{r=0}^{q} \frac{z^r}{r!}\right)^{m-1}$$

Furthermore we obtain for $m=1$

$$[z^n] L_q(z) =

[[n \le q]] \times \frac{1}{n!}.$$

With these we can implement a recursion, which in fact on being coded

proved inferior to Maple’s fast polynomial multiplication routines. It

is included here because it memoizes coefficients of $L_q(z)$, thereby

providing a dramatic speed-up of the plots at the cost of allocating

more memory.

All of this yields the following graph where we have scaled the plot

by a factor of $n/m.$ This is it for a six-sided die:

3+ H + | H + H | + H + HH | HH 2+ HH | HHH + HHHH + HHHHHHH | HHHHHHHHHHH + HHHHHHHHHHHHHHHHHHHHHHHHH | HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH -+--+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- 0 20 40 60 80 100 120

And here is the plot for a twelve-sided die. (I consider it worth

observing that we have the **exact** value for the expectation in the

case of $120$ rolls of this die, a case count that has $130$ digits,

similar to what appeared in the companion post.)

8+ | + + | + + H | 6+ | + + | H + + H | 4+ HH + H | H + HH + HH | HHHH + HHHHHH 2+ HHHHHHHHHHH | HHHHHHHHHHHHHHHHHHHHHHHHH + HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH -+--+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- 0 20 40 60 80 100 120

This was the Maple code.

with(plots); with(combinat); ENUM := proc(n, m) option remember; local rolls, res, ind, counts, least, most; res := 0; for ind from m^n to 2*m^n-1 do rolls := convert(ind, base, m); counts := map(mel->op(2, mel), convert(rolls[1..n], `multiset`)); res := res + max(counts); od; res/m^n; end; L := (m, rmax) -> add(z^r/r!, r=0..rmax)^m; X := proc(n, m) option remember; local H; H := q -> expand(L(m,q)-L(m,q-1)); n!/m^n* coeff(add(q*H(q), q=1..n), z, n); end; LCF := proc(n,m,q) option remember; if n < 0 then return 0 fi; if m = 1 then if n <= q then return 1/n! fi; return 0; fi; add(1/k!*LCF(n-k,m-1,q),k=0..min(q,n)); end; LVERIF := (m, q) -> add(LCF(n, m, q)*z^n, n=0..q*m); XX := proc(n, m) option remember; local res; res := n*LCF(n,m,n) - add(LCF(n,m,q), q=0..n-1); res*n!/m^n; end; DICEPLOT := proc(nmx, m) local pts; pts := [seq([n, XX(n,m)/(n/m)], n=1..nmx)]; pointplot(pts); end;

- Cosine Similarity between two sets of vectors?
- Prove that the center of a group is a normal subgroup
- Integral $\int_0^\infty \log(1+x^2)\frac{\cosh \pi x +\pi x\sinh \pi x}{\cosh^2 \pi x}\frac{dx}{x^2}=4-\pi$?
- Geodesic distance from point to manifold
- Every preorder is a topological space
- Prove these two segments are equal
- Determinant of a adjoint
- Conditional expectation in the case of $\mathcal{A}=\{\emptyset,\Omega,A,A^c\}$
- On the graph of $f(x)=i^x$ being sinusoidal: reasons, related ideas, and relevant literature
- Transforming from one spherical coordinate system to another
- Does $x_{n+2} = (x_{n+1} + x_{n})/2$ converge?
- Logical puzzles and arguments
- Existence of isomorphism between tensor products.
- Linear independence of the numbers $\{1,e,e^2,e^3\}$
- $p$ prime, $1 \le k \le p-2$ there exists $x \in \mathbb{Z} \ : \ x^k \neq 0,1 $ (mod p)