To leading order?
April 13, 2007 12:53 AM Subscribe
In the context of information theory, what does "to leading order" mean?
(Specifically referencing this book on page 25, in exercise 1.6.)
(Specifically referencing this book on page 25, in exercise 1.6.)
Best answer: Leading order refers to an approximation to a given function, usually under assumptions about the inputs being very small or very large. Lets assume you have a function of x, f(x).
Assuming we have some sort of polynomial representation of f(x), i.e. a + bx + cx^2 + dx^3 + ..., The leading order term usually depends on whether you're looking at very small values of x, or very large values of x. If you're looking at very small values of x, you can see that all the terms drop out except for 'a'. For very large values of x, you'd need the term matching the highest power of x, in the case of a 2nd-order polynomial a + bx + cx^2, it would be the term 'cx^2'. Remember, to leading order means finding the dominant term in an expansion that represents your function when the inputs are usually really close to some point (like zero) or very far (big)!
In the context of this textbook's homework problem, you're considering a polynomial expansion in f (not x), where f is very small because it's a noise term. The (1-f) term is very close to (1) when f is small, and as a result, the biggest term is f^2 (because all the other terms have higher orders of f and therefore will be much smaller when compared to f). Try expanding the series representation of block error for the Hamming code, you'll see a term that looks VERY much like f^2 and a bunch of higher order combinations that look like f^3, f^4, etc..
Mathematicians do this sort of thing all the time, sometimes it can be applied a bit more formally by taking limits, I would hope a good precalculus textbook (or the first chapter on limits in a good calculus textbook) would provide better understanding here.
posted by onalark at 3:33 AM on April 13, 2007 [1 favorite]
Assuming we have some sort of polynomial representation of f(x), i.e. a + bx + cx^2 + dx^3 + ..., The leading order term usually depends on whether you're looking at very small values of x, or very large values of x. If you're looking at very small values of x, you can see that all the terms drop out except for 'a'. For very large values of x, you'd need the term matching the highest power of x, in the case of a 2nd-order polynomial a + bx + cx^2, it would be the term 'cx^2'. Remember, to leading order means finding the dominant term in an expansion that represents your function when the inputs are usually really close to some point (like zero) or very far (big)!
In the context of this textbook's homework problem, you're considering a polynomial expansion in f (not x), where f is very small because it's a noise term. The (1-f) term is very close to (1) when f is small, and as a result, the biggest term is f^2 (because all the other terms have higher orders of f and therefore will be much smaller when compared to f). Try expanding the series representation of block error for the Hamming code, you'll see a term that looks VERY much like f^2 and a bunch of higher order combinations that look like f^3, f^4, etc..
Mathematicians do this sort of thing all the time, sometimes it can be applied a bit more formally by taking limits, I would hope a good precalculus textbook (or the first chapter on limits in a good calculus textbook) would provide better understanding here.
posted by onalark at 3:33 AM on April 13, 2007 [1 favorite]
Best answer: leading order is kind of fuzzy language, which depends highly on the context in which it is used. generally it means something along the lines of "the lowest power term which describes the essence of a problem" or, really, "the easiest thing to calculate that doesn't totally misrepresent the problem."
this isn't really terminology specific to information theory; you see it a LOT in physics books especially. you do it to simplify an otherwise difficult mathematical problem into something less difficult but mostly accurate. the choice of how you do it and the conditions under which this kind of approximation is valid are important.
you usually see it with series expansions, especially (but not always) taylor or maclaurin series. the idea is you have a sum with many terms, and each term in the series is an increasing power of the independent variable. higher powers (that is, higher orders) of the sum contribute less and less, so at some point it makes sense to drop stop adding them more and more.
so given an infinite summation of
foo = a + bx + cx2 + dx3 + ex4 + ...
if you keep terms up to x3 you would then say:
to third order, foo ≅ a + bx + cx2 + dx3 .
as another example, say you have a curve which looks like this one. if you're interested in the behavior in the neighborhood of the minimum (around 3.9 angstroms on that plot) you can do an expansion of the exact equation, which will be a sum of a constant, plus a linear, plus a quadratic, plus a cubic, plus.. etc. the lowest-order term which captures the essential behavior of the curve in the neighborhood of the minimum is x2, so in this case "leading order" is second order. (just keeping the constant is zeroth-order.)
so given your example, the summation in equation 1.46 is a sum over powers of f, where f is a probability (and therefore less than 1). higher powers of numbers less than 1 get smaller and smaller, so in this case, the dominant contribution is the smallest-power non-zero term. (so i guess part of the problem is to show why the r=1 term is irrelevant).
on preview, what these other guys said. (also, as a young physics student it took me a while to get over this notion of approximation -- "but it's not correct!" i'd shout. the thing to realize is that in the context of using math to describe a physical thing (like an information channel) there are usually limits on how well one can make a measurement anyway, so within those limits such an approximation is a valid model, even if it's not strictly-speaking exact mathematics. but then that's what the ≅ symbol is all about.)
posted by sergeant sandwich at 3:54 AM on April 13, 2007 [1 favorite]
this isn't really terminology specific to information theory; you see it a LOT in physics books especially. you do it to simplify an otherwise difficult mathematical problem into something less difficult but mostly accurate. the choice of how you do it and the conditions under which this kind of approximation is valid are important.
you usually see it with series expansions, especially (but not always) taylor or maclaurin series. the idea is you have a sum with many terms, and each term in the series is an increasing power of the independent variable. higher powers (that is, higher orders) of the sum contribute less and less, so at some point it makes sense to drop stop adding them more and more.
so given an infinite summation of
foo = a + bx + cx2 + dx3 + ex4 + ...
if you keep terms up to x3 you would then say:
to third order, foo ≅ a + bx + cx2 + dx3 .
as another example, say you have a curve which looks like this one. if you're interested in the behavior in the neighborhood of the minimum (around 3.9 angstroms on that plot) you can do an expansion of the exact equation, which will be a sum of a constant, plus a linear, plus a quadratic, plus a cubic, plus.. etc. the lowest-order term which captures the essential behavior of the curve in the neighborhood of the minimum is x2, so in this case "leading order" is second order. (just keeping the constant is zeroth-order.)
so given your example, the summation in equation 1.46 is a sum over powers of f, where f is a probability (and therefore less than 1). higher powers of numbers less than 1 get smaller and smaller, so in this case, the dominant contribution is the smallest-power non-zero term. (so i guess part of the problem is to show why the r=1 term is irrelevant).
on preview, what these other guys said. (also, as a young physics student it took me a while to get over this notion of approximation -- "but it's not correct!" i'd shout. the thing to realize is that in the context of using math to describe a physical thing (like an information channel) there are usually limits on how well one can make a measurement anyway, so within those limits such an approximation is a valid model, even if it's not strictly-speaking exact mathematics. but then that's what the ≅ symbol is all about.)
posted by sergeant sandwich at 3:54 AM on April 13, 2007 [1 favorite]
I'm wasn't familiar with that way of expressing the concept. Is it particular to a field of study, or a geographic local?
posted by Chuckles at 11:35 PM on April 13, 2007
posted by Chuckles at 11:35 PM on April 13, 2007
Err, please overlook the bad editing. And, since it might help clarify, "to leading order" isn't commonly used in digital communications classes in Canadian engineering schools, to the best of my knowledge, so..
Actually, I may have 'ever' heard it, although it was probably more like "leading order approximation".
posted by Chuckles at 11:45 PM on April 13, 2007
Actually, I may have 'ever' heard it, although it was probably more like "leading order approximation".
posted by Chuckles at 11:45 PM on April 13, 2007
Hey Chuckles, it's just one of the useful results that pops out of limits in practical applications. I've seen it used in Mechanical Engineering, Aerospace Engineering, Physics, Optics, Computational Chemistry, and Applied Mathematics. I imagine it occurs in other fields as well. There are a variety of ways to get introduced to the concept, but I like using a Taylor expansion if the function isn't already a polynomial and then taking the limit as it provides the clearest demonstration of the principles to me.
posted by onalark at 6:03 PM on April 15, 2007
posted by onalark at 6:03 PM on April 15, 2007
Thanks, but.. I was trying to make it clear that I have a good understanding of the concept. It is the language I'm not familiar with.
posted by Chuckles at 6:20 PM on April 15, 2007
posted by Chuckles at 6:20 PM on April 15, 2007
I don't get it. "To leading order" and "leading order approximation" sound pretty much identical to me. When I see "to leading order" I know they mean a "a first-order approximation asymptotes to" and have just shortened it. "to leading order" is probably short for, "[This approximation is accurate] to leading order"
If I'm answering the question I think I am, I've definitely seen "to leading order" before, but I couldn't tell you in which specific fields, though google has almost a million hits for it as opposed to "leading order approximation" with only 40,000.
posted by onalark at 8:16 PM on April 15, 2007
If I'm answering the question I think I am, I've definitely seen "to leading order" before, but I couldn't tell you in which specific fields, though google has almost a million hits for it as opposed to "leading order approximation" with only 40,000.
posted by onalark at 8:16 PM on April 15, 2007
Ya, I don't know, maybe I'm just forgetting.. :)
I remember that sin(x)~=x. I remember "f(x) = Cx +H.O.T.". I remember how to do Bode plots (which really pushes the notion). Hell, I've even taught linearization.
Half of those million hits go away if you remove "next to" from the search criteria, which is interesting. Also, the first few pages of results seem to be very physics related.. I guess that might be the answer to my question :P
posted by Chuckles at 8:40 PM on April 15, 2007
I remember that sin(x)~=x. I remember "f(x) = Cx +
Half of those million hits go away if you remove "next to" from the search criteria, which is interesting. Also, the first few pages of results seem to be very physics related.. I guess that might be the answer to my question :P
posted by Chuckles at 8:40 PM on April 15, 2007
« Older What is this creepy site advertising? - Round Two | Open source software for design company Newer »
This thread is closed to new comments.
"The leading-order behaviour is found by considering
the outcome in the most probable case where the noise vector has weight two."
Before finding that tidbit, I tried to extrapolate (with my pathetic high school math knowledge) what leading-order actually meant. Bear in mind I have no idea what I'm talking about.
If you look at the solution to the question you're asking about on page 29, the formula provided essentially a series. The possibilities of error are 2/3/4/5/6/7, and the formula itself includes 7-choose-2. "Leading Order" I would thus assume (possibly foolishly) to mean the highest term of that sequence.... 'latest term', if you will.
The first time 'leading order' was mentioned in this book is on page 14, where they're talking about, as far as I can understand, simulating a function with a polynomial. If my guess was correct and 'order' indicates the numerical value of a given variable, then I would think that the 'to' in 'to leading order' is referencing the (possibly asymptotic) relationship between the function and the corresponding polynomial?
This link seems to indicate that leading order behaviour is "the behavior of an nth order ordinary differential equation at a removable singularity"
I should really stick to my biology homework, instead of googling math terms. I have no clue what I'm talking about. But dammit, google is fun.
posted by Phire at 2:47 AM on April 13, 2007