Wikipedia:Reference desk/Archives/Mathematics/2007 April 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 17

Best Approximation

I'm trying to solve a bit of a puzzle. I think I've got it right, but I'm not sure. The question is, given two bounds (for instance .0001 and .0002), can you find the fraction of smallest denominator that falls between those bounds? Faster than exhaustive search, of course. I think it could be done with Farey fractions, keeping track of only three at a time - (a,b,c). Starting out with a=0/1 and c=1/0, in each step you'd calculate b by adding the numerators and denominators. If b was above the range, set c to b, if below, set a to b, and repeat. The first b to be within the range is the answer. Is that right? Black Carrot 00:04, 17 April 2007 (UTC)

I don't think anything so complex is needed. The greater bound (.0002) = 1/5000. That's the smallest possible denominator. --JayHenry 00:22, 17 April 2007 (UTC)

While a unit fraction is that best choice for the particular bounds given, it isn't necessarily always the best choice. For the bounds 0.65-0.70, for example, 2/3 is the fraction with the lowest denominator. I believe he wants a general solution method which applies to all bounds. StuRat 00:38, 17 April 2007 (UTC)

Funny, I was thinking about exactly the same problem a couple of days ago. I tried to make the definitions a bit more rigorous by stating the problem as "Given an open subinterval (a,b) in [0,1], find the rational number p/q in (a,b) that minimises q." Sadly, while I can state the problem in fancy language, I don't know how to solve it either. Confusing Manifestation 01:39, 17 April 2007 (UTC)

And I wanted to find good fractional approximations of pi, but wrote a computer program to do it "the hard way", which, being a computer programmer and not a mathematician, I found to be the easy way. I believe I increased the denominator by 1 in each step, then found the real number that would be needed as a numerator to get exactly pi, then rounded that to the nearest integer, then divided that by the denominator to find how close the result was to pi. Each time I found a fraction that was a closer approximation of pi than the previous result, I printed it out. The whole program was probably only about 20 lines. This program could easily be modified to fit the current problem. StuRat 02:05, 17 April 2007 (UTC)

The simplest (not necessarily the fastest) method might be as follows. 1. Calculate the interval length d=b–a. If it is a closed interval then there is at least one integer q such that q/d belongs to [a, b]. You can find it by dividing a/d and rounding up, or dividing b/d and rounding down. If your interval is open, the guaranteed denominator would be d=b–a+1. 2. Search all natural values from initial d down to 1 and repeat same calculations - for each d^* check if ceiling(a/d^*) ≤ floor(b/d^*), and remember the last (smallest) value that satisfies the equality. That would be your denominator. --CiaPan 05:55, 17 April 2007 (UTC)

See the article on continued fractions, the section on best rational approximations. (StuRat, there is a discussion specifically about π.) For an interval [a,b], write the continued fraction for each end, then compare. To use the [0.65,0.70] example, the continued fractions are [0;1,1,1,6] and [0;1,2,3]. Take [0;1,2], and we automagically get ²⁄₃. To quote Bill Gosper (see here):

• "Write as continued fractions the two endpoints of the interval in question, stopping at least one term beyond the one where they first disagree, except that if one of them terminates before disagreeing, suffix to it a term of ∞. Set aside whatever initial sequence of terms they have in common. These terms will be the initial ones of the simplest included rational, as well as all of the other numbers in the interval. Now we need only find the simplest rational in an interval whose endpoints have continued fractions which start with different terms. (If we have set aside all of the terms of one endpoint, we are left with an explicit ∞.) The only way this new interval can fail to contain ∞ or at least one integer is if the upper endpoint is itself an exact integer, but is excluded by virtue of being the tail of an endpoint which was excluded in the original problem. It must also be the case that the lower endpoint has an initial term 1 less than the upper one. The easiest thing to do in this case is to rewrite the single term which is the upper endpoint as the previous integer followed by a 1, e.g., 3 1 instead of 4. Then we again have two continued fractions which start with the same term, and can proceed with the recipe."

(I have taken the liberty of replacing "oo" with "∞".) Or to quote HAKMEM Item 101C:

• "Express the endpoints as continued fractions. Find the first term where they differ and add 1 to the lesser term, unless it's last. Discard the terms to the right. What's left is the continued fraction for the "smallest" rational in the interval. (If one fraction terminates but matches the other as far as it goes, append an infinity and proceed as above.)"

Apparently the marvelous properties of continued fractions have not been conveyed to a large enough audience. Read enough Gosper and you may become a fan. --KSmrq^T 06:47, 17 April 2007 (UTC)

Nifty. So, I was wrong? Will it not work? Black Carrot 08:11, 17 April 2007 (UTC)

Black Carrot, I think your method is fine. Essentially, you are navigating the Stern-Brocot tree. You will reach the same result as the Gosper method described above. There are close links between the Stern-Brocot tree, Farey sequences and continued fraction expansions. Gandalf61 08:38, 17 April 2007 (UTC)

It is fine for positive numbers; for 0 there is a problem if you are using closed intervals. Also, if the lower bound x of the interval is large, you get many iterations (try x = 1000000). If you set the initial numerator of fraction a to floor(x)−1, you avoid both issues. The value of x should be more than −1, though, and for example the interval [1/1000001, 1/1000000] still requires many iterations. The Gosper method has none of these problems.  --Lambiam^Talk 10:37, 17 April 2007 (UTC)

That's a good point. Thank you very much. Black Carrot 03:55, 18 April 2007 (UTC)

Americans can't count

CNN says "Gunman massacres 32 at two Virginia Tech sites"

Yahoo News says "Gunman kill 32 brings death toll to 33"

BBC News says "Survivors of campus shootings in Virginia that left 33 dead."

CBC says "At least 33 people are dead."

ABC says "Gunman kill 32 before turning the weapon on himself."

So how many people did the gunman kill? Perhaps the gunman is a non-human space alien because how can he kill 32 and yet bring the death toll to 33. 202.168.50.40 05:28, 17 April 2007 (UTC)

He killed himself, so he's the 33rd. So, 32 were murdered, but 33 died, since one was a suicide. StuRat 05:37, 17 April 2007 (UTC)

BBC... America? All those figures say he killed 32 others, btw. --Wirbelwindヴィルヴェルヴィント (talk) 06:32, 17 April 2007 (UTC)

CBC... American? –Pomte 06:42, 17 April 2007 (UTC

ABC... American? 10:55, 17 April 2007 (UTC)

ABC also stands for American Broadcast Corporation, and is one of the major US networks. You are right about the BBC and CBC.-Czmtzc 11:59, 17 April 2007 (UTC)

You can't take a joke, can you? —The preceding unsigned comment was added by 129.78.208.4 (talk) 22:49, 17 April 2007 (UTC).

That was a joke? Black Carrot 03:54, 18 April 2007 (UTC)

Did you follow the link?

Rolling Standard Deviation

I am trying to do a small research on stock market volatility. I would be obliged if someone could help me understand "12 month rolling standard deviation" and how to calculate it. Can anyone suggest me a link where I can learn easily how to calculate rolling standard deviation.--202.52.231.226 06:18, 17 April 2007 (UTC)

I'll assume that by rolling you mean the same as moving in "moving average". The usual estimators m and s for the population standard deviation of a sample X of size N are given by

${\begin{array}{ccl}Nm&=&\sum _{x\in X}\,x\,,\\(N{-}1)s^{2}&=&\sum _{x\in X}\,(x-m)^{2}\,,s\geq 0.\end{array}}$

Omitting the subscripts to the summations, all of which let x range over X, the second sum can be rewritten as:

${\begin{array}{cclcccc}\sum (x-m)^{2}&=&\sum (x^{2}&-&2xm&+&m^{2})\\&=&\sum x^{2}&-&\sum 2xm&+&\sum m^{2}\\&=&\sum x^{2}&-&2m\sum x&+&Nm^{2}\\&=&\sum x^{2}&-&2Nm^{2}&+&Nm^{2}\\&=&\sum x^{2}&-&Nm^{2}\,.\end{array}}$

So the mean and standard deviation may be estimated by

${\begin{array}{ccl}m&=&{\tfrac {1}{N}}\sum x\,,\\s&=&{\sqrt {{\tfrac {1}{N-1}}\left(\sum x^{2}-Nm^{2}\right)}}\,.\end{array}}$

What you need to do to get this rolling – after the first 12 months – is to get these two summations rolling. Define

$S_{m}^{(k)}=\sum _{i=m-11}^{m}x_{i}^{k}\,,$

in which the data values are indexed by the month. Then

$S_{m+1}^{(k)}=\sum _{i=m-10}^{m+1}x_{i}^{k}=\left(\sum _{i=m-11}^{m}x_{i}^{k}\right)-x_{m-11}^{k}+x_{m+1}^{k}=S_{m}^{(k)}-x_{m-11}^{k}+x_{m+1}^{k}\,.$

 --Lambiam^Talk 08:26, 17 April 2007 (UTC)

Generalizing Hoelder's inequality

Hi, studying for one of those pesky qualifying examinations again. (This time it's in Analysis.) I have a hard time playing with the exponents in order to get full usefulness out of Hoelder's inequality, so I was hoping you can help me with this problem. I have seen generalizations of Hoelder's inequality in the past that use k functions, but the proofs confuse me. Suppose I just want to prove it for 3 functions. (The question is for a general measure space, so we don't use anything particular to Lebesgue measure on the real line.) That is,

Suppose $f\in L^{p},g\in L^{q},$ and $h\in L^{r}$, with 1/p + 1/q + 1/r = 1. Show that $fgh\in L^{1}$ and that $||fgh||_{1}\leq ||f||_{p}||g||_{q}||h||_{r}.$

I'm also allowed to use the "regular" Hoelder inequality, so I suppose that I want to show something to the effect of $fg\in L^{p'}$, where $p'=(1/p+1/q)^{-1}$, but this is where I'm stuck. Again, I'm not clever enough to play with the exponents properly.

So, if anyone out there can give me some good hints, or tell me exactly what's going on, that would be great. (This isn't homework, this is just regular studying for a qualifying exam.) Hints are greatly appreciated over straight up solutions, but I'm almost dying over here. Thanks in advance! –King Bee ^{(τ • γ)} 16:38, 17 April 2007 (UTC)

Well, there aren't really so many options. You want to prove $\int fgh\leq \left(\int f^{p}\right)^{\frac {1}{p}}\left(\int g^{q}\right)^{\frac {1}{q}}\left(\int h^{r}\right)^{\frac {1}{r}}$ when ${\frac {1}{p}}+{\frac {1}{q}}+{\frac {1}{r}}=1$ Start with the left hand side and try and fix it so you get some of the terms on the right hand side. E.g. write $fgh=(fg)h$ and try and use regular Hölder to get the term involving h on the rhs. Does that help? Stefán 17:02, 17 April 2007 (UTC)

Indeed, that's what I want to do. To do so, I need to have $fg\in L^{p'}$, where p' is as described above. Any hints towards getting that done? –King Bee ^{(τ • γ)} 17:19, 17 April 2007 (UTC)

You now have $\left(\int (fg)^{r'}\right)^{\frac {1}{r'}}$ to attack where ${\frac {1}{p}}+{\frac {1}{q}}=1-{\frac {1}{r}}={\frac {1}{r'}}$. Perhaps it is better to write that as ${\frac {r'}{p}}+{\frac {r'}{q}}=1$. This suggests using Hölder again but now with ${\frac {p}{r'}}$ and ${\frac {q}{r'}}$ as your powers. Does that look more appealing? Stefán 18:11, 17 April 2007 (UTC)

I'm with you; that's what I want to do. I suppose in order to pull that off, I need to show that $f\in L^{p/r'}$ and $g\in L^{q/r'}$ first (the result would follow soon after). Again, this is precisely where my issue lies. I simply cannot figure out how to play with the exponents in any meaningful way. Let me show you the types of things that I'm playing with, and you can tell me where I'm going wrong, or try to direct me toward something I'm missing.

$\int |f|^{p/r'}=\int \left(|f|^{p}\right)^{1/r'}=\int \left(|f|^{p}\right)^{(p+q)/pq}=\int |f|^{(p+q)/q}=\cdots$

...and I'm pretty much at a loss at that point. Do I want $f\in L^{q/r'}$ and $g\in L^{p/r'}$ instead? Thanks for your patience and your help so far. –King Bee ^{(τ • γ)} 20:35, 17 April 2007 (UTC)

The integral you are working with is $\int (fg)^{r'}=\int f^{r'}g^{r'}$. This is an integral of a product of two things, $f^{r'}$ and $g^{r'}$. What happens if you use Hölder on the integral of this product with exponents ${\frac {p}{r'}}$ and ${\frac {q}{r'}}$? If you prefer to write it using norms, I am suggesting the following: $\|f^{r'}g^{r'}\|_{1}\leq \|f^{r'}\|_{\frac {p}{r'}}\|g^{r'}\|_{\frac {q}{r'}}$. Stefán 21:03, 17 April 2007 (UTC)

Ahh! So, $f^{r'}\in L^{p/r'}$ and $g^{r'}\in L^{q/r'}$! I think this is making more sense. Let me get a coffee and then get back to you. –King Bee ^{(τ • γ)} 12:23, 18 April 2007 (UTC)

• (resetting indent) Here's the argument, as I see it. Let r' be as above and first note that $f^{r'}\in L^{p/r'}$ since $\int |f^{r'}|^{p/r'}=\int |f|^{p}<\infty$ as $f\in L^{p}$. Similarly, $g^{r'}\in L^{q/r^{'}}$. Next, since $r'/p+r'/q=1$ we can use the standard Hölder to note that $(fg)^{r'}\in L^{1}$ (so $fg\in L^{r'}$) and that $||fg||_{r'}^{r'}=||(fg)^{r'}||_{1}\leq ||f^{r'}||_{p/r'}\cdot ||g^{r'}||_{q/r'}=||f||_{p}^{r'}\cdot ||g||_{q}^{r'}$. Taking the $r'$^th root of both sides, we achive $||fg||_{r'}\leq ||f||_{p}\cdot ||g||_{q}$. Abusing Hölder again, this time with r' and r, and $fg$ and $h$, we note that $1/r'+1/r=1$, so $fgh\in L^{1}$ and

$||fgh||_{1}\leq ||fg||_{r'}\cdot ||h||_{r}\leq ||f||_{p}\cdot ||g||_{q}\cdot ||h||_{r}$, as desired. Commentary. I don't see any holes here, do you? This is great! Stefán, you lovable scamp, I could kiss you! It wasn't playing with exponents that was my problem, it was realizing which functions lived in which L space. Beautiful!–King Bee ^{(τ • γ)} 13:41, 18 April 2007 (UTC)

Nope, there are no holes in this. Good job, it was my pleasure to help. Stefán 15:33, 18 April 2007 (UTC)

Our article Hölder's inequality contains a proof that, it appears to me, is readily extended to this generalization.  --Lambiam^Talk 07:32, 18 April 2007 (UTC)

I know. Should you really have to use Young's inequality to prove Hölder? I'm looking for a different proof. –King Bee ^{(τ • γ)} 12:23, 18 April 2007 (UTC)