Tagged Questions
1
vote
1answer
43 views
Weighted sum of ratio of partial sum of binomial coefficients
I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$,
$$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
0
votes
0answers
45 views
How can weakly/strongly decreasing or increasing approximate sums be explained?
I'm reading around big O to get some concept about performance for data structures. The mathematics book recommended by the open book ~ maths for computer science
In the book (pg 456) part of the ...
1
vote
2answers
47 views
Roots of the equation $I_1(b x) - x I_0(b x) = 0$
I'm interested in the roots of the equation:
$I_1(bx) - x I_0(bx) = 0$
Where $I_n(x)$ is the modified Bessel function of the first kind and $b$ is real positive constant.
More specifically, I'm ...
5
votes
3answers
184 views
“$O$” notation in Stirling approximation
In the Stirling approximation the formula as typically used in applications is
$$\ln n! = n\ln n - n +O(\ln(n))$$
I'm confused about the last term "$O$" . What does it mean actually, and when do we ...
1
vote
1answer
169 views
Method of dominant balance
Find the leading asymptotic behaviour as $x \rightarrow \infty$ of
$$x^2y'' + (1 + 3x)y' + y = 0 $$
Can someone kindly explain me how to solve this problem? Im learning asymptotic analysis, and I ...
0
votes
1answer
106 views
Techniques for bounding a sum
I have a very messy function. It consists sums four levels deep, and the inner-most term is itself quite messy.
$$ \sum \sum \sum \sum (\mbox{stuff})$$
I can't find a closed form for this function. ...
0
votes
0answers
72 views
When does distribution bootstrap mean converge to distribution sample mean?
Let $\bar{X}_n$ denote the sample mean of n iid random variables. Let $\bar{X}^*_n$ be the bootstrap sample mean. Does $\left|\mathbb{P}\left(n^{1/2}\bar{X}_n\leq ...
3
votes
1answer
143 views
Laplace's method with unknown exponent.
Given the integral:
$$I = \int_0^a{e^{-\lambda g(x)}f(x)dx}$$
Where $g(x)$ and $f(x$) are both low order positive polynomials, and $\lambda \gg 1$, Laplace's method is commonly used to approximate ...
2
votes
1answer
66 views
Finding the asymptotic limit of an integral.
I'm having trouble finding the asymptotic of the integral
$$ \int^{1}_{0} \ln^\lambda \frac{1}{x} dx$$
as $\lambda \rightarrow + \infty$.
Can anyone help?
Thank you!
1
vote
0answers
73 views
Describe growth of $\epsilon n$
For all $\epsilon$ we have that $f(n)\le \epsilon n$ where n is a natural number. What can we say about the growth of $f(n)$? Clearly $f(n)=O(n)$, can we say anything sharper?
0
votes
1answer
99 views
asymptotic limit of $\int_0^{\infty}\left(1-\frac{t^2}{2(2k+3)}+\frac{t^4}{2\cdot 4\cdot(2k+3)\cdot(2k+5)}\right)^qdt$
Help me please with the following integral. I've asked this question before Asymptotic limit of the integral with polynomial, but it turns out that it was incorrect question. I should get an ...
2
votes
1answer
72 views
asymptotic limit at the integral
I would like to get an asymptotic limit at the following integral: for $p\ge 2, n \in N$, $t \ge 0$
$$
\int_{0}^{\frac 12 \sqrt{(n+1)!}}\left(1-\frac{t^2}{2^2(n+1)!}\right)^p \mathrm{d} t
$$
I think ...
2
votes
0answers
41 views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = ...
20
votes
9answers
2k views
What is the purpose of Stirling's approximation to a factorial?
Stirling approximation to a factorial is
$$
n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n.
$$
I wonder what benefit can be got from it?
From computational perspective (I admit I don't ...
