FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > DSP

DSP comp.dsp newsgroup, mailing list

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 05-11-2006, 03:50 AM
chaselweng
Guest
 
Posts: n/a
Default A Stirling Approximation question....

I read a paper and see below inequality

1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )

where C(n,l) means the combination with n!/( l! * (n-l)! )...
I tried to use stirling approximation, but i can't get the same
result....

Can anyone help me for any kinds of comment......

Reply With Quote
  #2 (permalink)  
Old 05-11-2006, 06:38 AM
robert bristow-johnson
Guest
 
Posts: n/a
Default Re: A Stirling Approximation question....


chaselweng wrote:
> I read a paper and see below inequality
>
> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )
>
> where C(n,l) means the combination with n!/( l! * (n-l)! )...
> I tried to use stirling approximation, but i can't get the same
> result....
>
> Can anyone help me for any kinds of comment......


there are slightly different formulae for Stirling's approximation,
some are a little more accurate than others, but they all have the same
asymtotic behavior when n gets large. i recommend looking at

http://en.wikipedia.org/wiki/Stirling%27s_approximation

anyway it says that

n! = sqrt(2*pi*n) exp(n*log(n)-n) * exp(lambda)

where 12*n < 1/lambda < 12*n + 1

that's the best approximation and shows the error constraint. i have
also seen

n! approx= exp(n*log(n)-n)

which will also work in most cases when n is super large.

r b-j

Reply With Quote
  #3 (permalink)  
Old 05-11-2006, 08:27 AM
chaselweng
Guest
 
Posts: n/a
Default Re: A Stirling Approximation question....

I have refered to the website you provide...
But i still can get the same inequality...

I think a lot of terms are be ignore in the above inequality..
I have no sense what's kinds of term i can ignore with n is large...

Can anyone tell me what's happen in the inequality...thx a lot!!

Reply With Quote
  #4 (permalink)  
Old 05-11-2006, 09:26 PM
robert bristow-johnson
Guest
 
Posts: n/a
Default Re: A Stirling Approximation question....


chaselweng wrote:
> I have refered to the website you provide...
> But i still can get the same inequality...
>
> I think a lot of terms are be ignore in the above inequality..
> I have no sense what's kinds of term i can ignore with n is large...


>>> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/(12*n) - 1/(360*n^3) ) <= C(n, l) <=
>>> 1/sqrt(2*pi*n) * n^n * exp( -n + 1/ (12*n) )
>>>
>>> where C(n,l) means the combination with n!/( l! * (n-l)! )...


well, one problem with it is that there is no function of "l" on either
left or right expression. there is no "l" in

1/sqrt(2*pi*n) * n^n * exp(-n + 1/(12*n))

or in

1/sqrt(2*pi*n) * n^n * exp(-n + 1/(12*n) - 1/(360*n^3))

where the 1/(360*n^3) term comes from, i do not know.

again, what Stirling's approximation says most concisely is:

1/(12*n+1) < log(n!) - (1/2)*log(2*pi) - (n+1/2)*log(n) + n < 1/(12*n)

note that the expression gets squeezed between 1/(12*n+1) and 1/(12*n)
as n gets large making the approximation really good for large n.

r b-j

Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Stirling Approximation question.... chaselweng DSP 0 05-11-2006 03:45 AM
A Stirling Approximation question.... chaselweng DSP 0 05-11-2006 03:43 AM
approximation of log(x+y) ?? Lars Hansen DSP 9 10-06-2005 09:37 PM
about approximation of a signal kiki DSP 4 11-25-2004 04:57 PM
Padé's Approximation MadJock DSP 9 12-16-2003 04:49 PM


All times are GMT +1. The time now is 06:38 AM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved