How to reasonably (numerically) estimate $n\int_0^\infty\left(1-\left(1-e^{-t}\left(1+t+\ldots+{{t^{m-1}}\over{(m-1)!}}\right)\right)^n\right)dt$? Recently in doing some expected value calculations, I've derived the following two integrals:
$$6\int_0^\infty\left(1-\left(1-e^{-t}\left(1+t\right)\right)^6\right)dt$$
$$6\int_0^\infty\left(1-\left(1-e^{-t}\left(1+t + {{t^2}\over2}\right)\right)^6\right)dt$$
Plugging these into Wolfram Alpha can get us numerical answers. For instance, the first integral comes out to about $24.1$, and the second integral comes out to about $32.7$.
However, I'm wondering if anyone can give a reasonable numerical estimate for these $2$ integrals from first principles (pencil and paper) without using a calculator, Wolfram Alpha, or a computer.
I've tried but made little to no progress, and I consulted some nearby PhD students and they didn't know either, so asking here.
 A: I think the sigmoid approximation is a little more workable by hand than leonbloy suggests. Following his answer, we will approximate the integral as $6t_0$ where $g(t_0) = \frac{1}{2}$. For the first integral this means estimating the solution to
$$\frac{1 + t}{e^t} = 1 - 2^{-\frac{1}{6}} \approx \frac{\log 2}{6}$$
or
$$\frac{e^t}{1 + t} \approx \frac{6}{\log 2} \approx 9$$
(using $\log 2 \approx 0.69 \dots $). The LHS can be shown to be an increasing function of $t$ so we can try to estimate the root using the intermediate value theorem. Substituting $t = 3$ gives $\frac{e^3}{4} < \frac{3^3}{4} < 7$ while substituting $t = 4$ gives $\frac{e^4}{5}$. We can estimate this by just computing $e^4$ to two significant digits, which gives
$$e^2 \approx 2.7^2 \approx 7.3, e^4 \approx 7.3^2 \approx 53$$
so $\frac{e^4}{5} \approx 10.6$. So $t_0$ in this case is between $3$ and $4$ and likely closer to $4$. If we just estimate $t_0 \approx 3.5$ as the midpoint we get an estimate of $6 \times 3.5 = \boxed{ 21 }$ for the first integral, sadly with no error bound.
For the second integral similarly we want to estimate the solution to
$$\frac{e^t}{1 + t + \frac{t^2}{2}} \approx 9.$$
Substituting $t = 4$ gives $\frac{e^4}{13} < \frac{81}{13} \approx 6$ while substituting $t = 5$ gives $\frac{e^6}{18.5}$. We again compute to two significant digits that $e^6 \approx 140$, so $\frac{e^6}{18.5} \approx \frac{140}{18.5} = 10 - \frac{45}{18.5} \approx 7.5$. So $t_0$ in this case is a bit larger than $5$ (we could substitute $t = 6$ to confirm this but I won't). If we just estimate $t_0 \approx 5$ we get an estimate of $6 \times 5 = \boxed{ 30 }$ for the second integral, again sadly with no error bound.
For the general integral we now want to estimate the solution to
$$e^{-t} \left( \sum_{i=0}^{m-1} \frac{t^i}{i!} \right) = 1 - 2^{-\frac{1}{n}} \approx \frac{\log 2}{n}.$$
We can think of the LHS as $\mathbb{P}(X \le m-1)$ where $X \sim \text{Pois}(t)$. Since we want this probability to be small we want $t \ge m-1$, so using the Chernoff bound adapted to this case we get
$$\mathbb{P}(\text{Pois}(t) \le a) \le \exp \left( a - t + a \log \frac{t}{a} \right)$$
where $a = m-1$. Setting $t = a + x$, which simplifies things a bit, we get
$$\mathbb{P}(\text{Pois}(a + x) \le a) \le \exp \left( - x + a \log \left( 1 + \frac{x}{a} \right) \right).$$
Taking the Chernoff bound as our approximation and setting it equal to $\frac{\log 2}{n}$ gives
$$x \approx \log n - \log \log 2 + (m-1) \log \left( 1 + \frac{x}{m-1} \right)$$
which has dominant growth $x \approx \log n$; substituting this into the logarithm term gives
$$x_0 \approx \log n - \log \log 2 + (m-1) \log \left( 1 + \frac{\log n}{m-1} \right)$$
which gives $t_0 \approx m-1 + x_0$, so we get a final approximation for the quantity in the title of your question:
$$\boxed{ n \left( \log n + (m-1) \left( 1 + \log \left( 1 + \frac{\log n}{m-1} \right) \right) - \log \log 2 \right) }.$$
The dominant growth here looks like $n \log n + (m-1)n \log \log n$ which seems roughly reasonable as an answer to the coupon collector problem you describe in the comment. For $m = 2, n = 6$ we get an approximation of
$$6 \left( \log 6 + \left( 1 + \log \left( 1 + \log 6 \right) \right) - \log \log 2\right) \approx \boxed{ 25.1 }$$
whereas for $m = 3, n = 6$ we get an approximation of
$$6 \left( \log 6 + 2 \left( 1 + \log \left( 1 + \frac{\log 6}{2} \right) \right) - \log \log 2\right) \approx \boxed{ 32.7 }.$$
The Chernoff bound itself can be used to estimate the integrand (we should split into two integrals, one from $0$ to something like $m$ and another from something like $m$ to $\infty$) which can maybe do better; the integrand itself can be written $1 - \mathbb{P}(\text{Pois}(t) \ge m)^n$, which means for fixed $t$ it gives the probability that the minimum of $n$ iid Poisson random variables with intensity $t$ is $\le m-1$. This seems closely related to the coupon collector problem you describe but I have to admit I don't actually see the relationship at the moment.
Edit: The asymptotics for the generalized coupon collector problem are actually described on Wikipedia and given by $n \log n + (m-1) n \log \log n + O(n)$, due to Newman and Shepp. So the above estimate is not too bad!
A: I doubt that you can get a reasonable estimate with pencil and paper.
For a quick and rough approximation (still requires calculator):
Let $E_1 = 6 I_1 = 6 \int_{0}^\infty g_1(t) dt$ with $g_1(t)=1-h_1(t)^6$ and $h_1(t)=1-e^{-t}(1+t)$.
Same for $E_2$, with $h_2(t)=1-e^{-t}(1+t+\frac12 t^2)$
In both cases, we can see that $h(t)$ increase monotonously from $0$ to $1$ (can be checked computing the derivative). Hence we can expect that, after the composition with $1-(\cdot)^6$, $g(t)$ has a sigmoid shape, starting at $g(0) =1$ with some quite steep transition to $g(+\infty)=0$. If we assume this, we can try to approximate this sigmoid by a piecewise linear activation function. And in this case, the integral is $I=t_{0}$, where $g(t_0)=1/2$.
Under this assumption, we are left with computing $t_0$ as the solution of
$$  1-(1-e^{-t}(1+t))^6=1/2 \tag 1$$
or $$ t = \log(1+t) - \log \left(1- \sqrt[6]{1/2}\right) \tag 2$$
Again, this cannot be computed with paper and pencil, but the numerical solution can be found iteratively, eg with a spreadsheet.
(The attempt to use the Taylor series for the logarithm leads nowhere).
We get the values $I_1=3.78$ ($E_1=22.68$) for the first one
and $I_2=5.196$ ($E_2=31.17$) for the second one.
The relative error wrt the exact values (from Yuri Negometyanov's answer) is around $5\%$.
See also  Qiaochu Yuan's comment for a probabilistic bound.
For general $m,n$, the method used in the answer of this similar (but not quite) question might be of interest.
A: Let $f(t)=1-(1-e^{-t}(1+t))^6$.

*

*Binomial Theorem: $f(t)=1-\sum_k\binom{6}{k}e^{-kt}(1+t)^{6-k}$.

*Binomial Theorem: $f(t)=1-\sum_{j+k\le 6}\binom{6}{j,k,6-j-k}e^{-kt}t^j$.

*Cheat by looking up the moments of the exponential distribution or integrate yourself (using induction).
\begin{aligned}
\int_0^\infty e^{-kt}t^j\mathrm{d}t
&=-\int_0^\infty\frac{j}{k}e^{-kt}t^{j-1}-e^{-kt}t^j\mathrm{d}t+\int_0^\infty\frac{j}{k}e^{-kt}t^{j-1}\mathrm{d}t\\
&=-\left[\frac{1}{k}e^{-kt}t^j\right]_{t=0}^\infty+\frac{j}{k}\cdot\frac{(j-1)!}{k^j}
=\frac{j!}{k^{j+1}}.
\end{aligned}
Evaluating the multinomial coefficients and aggregating is straightforward (don't forget to multiply with $6$ in the end). Solving the second integral is completely analogous.

