Wikipedia:Reference desk/Archives/Mathematics/2009 December 30

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.

December 30

non polynomial difference

When using master theorem, f(n) and n^log_ba must have a polynomial difference. The example shown is f(n)=n/log n. With a=2 and b=2, n^log_ba=n. So, the claim is that n/log n and just n have a non-polynomial difference. Another example I saw changes a to 4 so n^log_ba=n². The claim is that n/log n and n² have a polynomial difference. I'm left wondering exactly what the "polynomial difference" is. Is it taking (n/log n)-(n) and claiming that is non-polynomial? -- kainaw™ 02:30, 30 December 2009 (UTC)

"Difference" here is being used multiplicatively -- the quotient of n and $n/\log n$, which is $\log n$, is not polynomial. Formally, the master theorem requires $f(n)\in O(n^{\log _{a}(b)-\epsilon })$ for some positive $\epsilon$; or equivalently, requires ${\frac {f(n)}{n^{\log _{a}(b)}}}\in O(n^{-\epsilon })$ or ${\frac {n^{\log _{a}(b)}}{f(n)}}\in \Omega (n^{\epsilon })$. Eric. 131.215.159.171 (talk) 03:21, 30 December 2009 (UTC)

In any case, what everybody would do as a first step with this $T(n)=aT(n/b)+f(n)$ is writing $n=b^{k}$ and turning the recurrence into the form $\tau (k+1)=a\tau (k)+\phi (k);$ solutions of the latter have an immediate representation in terms of discrete convolutions, and a whole machinery for growth estimates is available, to bound the solution in terms of $\phi (k).$ As I see it, in these cases it should be better not to make everything into a theorem (especially with such a name), that makes things more rigid. --pma (talk) 10:09, 30 December 2009 (UTC)

Calculate my age as percentage of USA age.

I was born on September 21, 1944; the USA was born on July 4, 1776. How do I calculate on what date I will become exacty 25% as old as the USA? 206.54.145.254 (talk) 18:00, 30 December 2009 (UTC)

here then here. use the first link to work out the number of days old the US was when you were born, the date you want is 1/3 of that number of days later (as for you to be 1/4 the age of the US on a date the US was 3/4 that age when you were born, and 1/4 is 1/3 of 3/4. Even if you could do the calculations yourself the site's a useful check.--JohnBlackburne (talk) 18:24, 30 December 2009 (UTC)

Solving for x giving the min

I have this function:

$y=\arcsin {\frac {{\sqrt {3}}{\sqrt {n^{2}-sin^{2}\theta }}-sin\theta }{2}}+\theta$

If I know "n", I can easily find the minimum value of y: just use a graphing calculator to graph y against theta ad ask it to find the minimum. If I know the minimum and the standard deviation on the minimum, how do I find "n" and the standard deviation on "n"? --99.237.234.104 (talk) 20:54, 30 December 2009 (UTC)

You'll have to explain a bit better. The way I understand the function, it is unbounded for values of n for which it is defined, so you can't speak of its (global) minimum. Also, I don't understand what standard deviation means in this context. -- Meni Rosenfeld (talk) 06:53, 31 December 2009 (UTC)

OK, here's a short explanation. If you're interested, also read the long explanation (which is pretty cool, IMHO).

Short explanation: "n" is a constant. If I know the numerical value of "n", I can plot a y vs. theta graph and compute the graph's minimum y value between theta=0 and theta=pi/2.

However, I don't know the numerical value of "n"; that's what I'm trying to calculate. I experimentally measured the minimum y value, and as with any experiment, there is an error margin associated with the measured value. How do I calculate "n" from this data? Also, how do I calculate the margin of error on n?

Long explanation:

I'm doing an experiment to determine the refractive index of ice (this is the "n"). To do this, I'm taking a photograph of a 22 degree halo and measuring its radius. I've worked out, using some physics, that $y=\arcsin {\frac {{\sqrt {3}}{\sqrt {n^{2}-sin^{2}\theta }}-sin\theta }{2}}+\theta -pi/3$ gives the angle of deflection (the y value) in terms of the angle of incidence of light on an ice crystal. The minimum possible angle of deflection is equal to the radius of the halo. It follows that if I measure the radius of the halo, I can calculate the refractive index of ice. It turns out that the radius of the halo depends VERY sensitively on "n": a difference of 0.01 in "n" corresponds to a difference of 0.8 degrees in the radius. Since I can measure radius to an accuracy of 0.02 degrees, I should get a very precise fix on "n". --99.237.234.104 (talk) 10:43, 31 December 2009 (UTC)

That's much better - in particular $0<\theta <\pi /2$ was an important piece of information. Is it also true that $1\leq n\leq 2$? Otherwise there's a problem.

So you have a function $f(n,\theta )=\arcsin {\frac {{\sqrt {3}}{\sqrt {n^{2}-sin^{2}\theta }}-sin\theta }{2}}+\theta$. For any n, we let $a(n)$ be the value of $\theta$ for which f is minimal, and $b(n)=f(n,a(n))$ the value of the minimum. What you want is to find the inverse function of b.

Since b is computed using a, it is natural to first find an expression for a. This requires finding where the derivative of f is 0, but the resulting equation seems unsolvable algebraically. It can still be found numerically.

I've done some numeric calculations; the first interesting thing to note is that $b(n)=2a(n)$ (though this is irrelevant for the solution). The second is that b can be approximated fairly well with a polynomial - for example, $b(n)\approx -4.51+11.41n-7.91n^{2}+2.04n^{3}$. Given b you can solve for n numerically, for example by graphing.

If it happens to be known that $1\leq n\leq 1.5$, then a much better, and simpler, approximation is $b(n)\approx 0.2654+0.4413n+0.3412n^{2}$.

The error in n is simply the error in b divided by $b'(n)$. -- Meni Rosenfeld (talk) 11:39, 31 December 2009 (UTC)

Thanks for the response! Yes, n is between 1 and 1.5 (in fact, it's around 1.31). How accurate are your approximations? I'm expecting this experiment to be capable of giving 5 significant digits for "n", and I don't want rounding errors to worsen the accuracy of the result. --99.237.234.104 (talk) 22:20, 31 December 2009 (UTC)

A better approximation can be found by optimizing for $1.30\leq n\leq 1.32$, resulting in $b(n)\approx 0.3460547+0.3289593n+0.3795664n^{2}$. This one can easily give you 5 significant figures for n (the difference is less than $2\cdot 10^{-7}$ in the specified range). -- Meni Rosenfeld (talk) 08:27, 1 January 2010 (UTC)

'Reproducing generations problem' or 'sum of 2 to the power n'

I'm working through a problem concerning the size of a population after n generations, assuming that no members of the population die, and that the number of members of each generation is given by 2^n-1, where n is the generation number. For example, in the first generation there is 1 member, the second generation has 2, the third 4, the fourth 8, etc.

I know that I require a total population of roughly 1.5 x 10²⁵ and want to know how many generations I require. So far, all I have is:
$\sum _{k=1}^{n}2^{k}\approx 1.5\times 10^{25}$
Any body know the formula for the sum of 2 to the power n? Searching on Google just seems to bring up things like the sum of n to the power 2, which I already know and doesn't appear to be of much use to me in this instance. Logarithms tell me it's a bit less than 84 generations, which is confirmed by a quick Excel spreadsheet, but I was hoping for something a bit more 'mathematical'.--80.229.152.246 (talk) 20:59, 30 December 2009 (UTC)

I think the formula $\sum _{k=0}^{n}2^{k}=2^{n+1}-1$ may be of some use. At the scale of your application, the "-1" really doesn't matter, of course, but the formula itself does provide justification for your answer. --Kinu ^t/_c 22:29, 30 December 2009 (UTC)

See also Geometric series. -- Meni Rosenfeld (talk) 06:47, 31 December 2009 (UTC)