Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

May 2

Information theory terminology

The entropy of a probability distribution $p$ over a discrete random variable $X$ is $\sum _{i=1}^{n}{-p(x_{i})\log p(x_{i})}$. I'm trying to find out what I should call one term of this sum. For example, what is $-p(x_{i})\log p(x_{i})$ called for $x_{i}$? It's not $x_{i}$'s surprisal, because that's $-\log p(x_{i})$. Thanks. --Bkkbrad (talk) 01:10, 2 May 2010 (UTC)

The entropy contribution from $x_{i}$, or the mean surprisal of $x_{i}$ ? Bo Jacoby (talk) 06:02, 2 May 2010 (UTC).

Winning games

Where can I find a list of just the winning games in TicTacToe, preferably with each move displayed in the format of the game? 71.100.1.71 (talk) 15:30, 2 May 2010 (UTC)

The Tic-tac-toe article states that "When winning combinations are considered, there are 255,168 possible games." hydnjo (talk) 15:52, 2 May 2010 (UTC)

My expectation is that these would be computer generated and each game might consist of a row of 9, 0-2 values for each move for a maximum of 81 characters per game. That is a file of only 20 megs - well within the reach of even older personal computers. 71.100.1.71 (talk) 16:57, 2 May 2010 (UTC)

I don't think the number is anywhere near that large if you mod out by symmetries. Michael Hardy (talk) 19:07, 2 May 2010 (UTC)

Where can I find a list of just the winning games in TicTacToe, preferably with each move displayed in the format of the game? 71.100.1.71 (talk) 15:30, 2 May 2010 (UTC)

Copying your question verbatim is rude and isn't going to help. The question is a bit vague, you should elaborate on it. -- Meni Rosenfeld (talk) 08:37, 3 May 2010 (UTC)

Check this [1], for a close problem. --pma 17:22, 3 May 2010 (UTC)

There's an interesting discussion there, and even a link to yet another discussion! I'll go check that one out...

Error: Stack overflow. Suspect an infinite recursion.

-- Meni Rosenfeld (talk) 17:56, 3 May 2010 (UTC)

Shared Zeros of Quadratic forms

Hi there everyone,

I was hoping you could point me in the right direction on this one - it's for revision purposes so I certainly don't want the final solution, so please don't overhelp! :)

Suppose now that k = C and that $q_{1},...,q_{d}:\mathbb {C} ^{n}\to \mathbb {C}$ are quadratic forms. If n$\geq 2^{d}$, show that there is some non-zero $x\in \mathbb {C} ^{n}$ such that $q_{1}(x)=...=q_{d}(x)=0$

I've already shown that there is a basis $\{v_{1},...,v_{n}\}$ for $k^{n}$ such that, writing $x=x_{1}v_{1}+...+x_{n}v_{n}$, we have $q(x)=a_{1}x_{1}^{2}+...+a_{n}x_{n}^{2}$ for some scalars $a_{1},...,a_{n}\in \{-1,0,1\}$. The 2^n makes me think of some sort of loose relation to binary (in terms of maybe having two 'options' for something n times) and the whole problem makes me think of induction, on d perhaps. However, I'm unsure how to actually formulate an approach to the program, and inductively whilst I've looked at things like defining $x_{j}$ such that $\forall 1\leq i\leq n,i\neq j,q_{i}(x_{j})=0$ for $1\leq j\leq n$, but even if that is the right approach I'm not sure where to go from here inductively.

Many thanks for any help or advice you can provide! Simba31415 (talk) 18:58, 2 May 2010 (UTC)

Here are some hints. The key point is: the zero-set of a quadratic form q on Cⁿ contains a linear subspace W of dimension at least $\scriptstyle \lfloor n/2\rfloor .$ (A linear subspace W contained in the zero-set of q is called a "totally isotropic subspace" for q). You can easily prove it using the normal form you wrote (for example, x²+y² on C² vanishes on the complex line of vectors of the form (x,ix) and so on). That said, prove the claim by induction on d. If d=0 there is nothing to prove: a system of no equation on Cⁿ with n≥2⁰=1 certainly has a non-zero linear space of solutions. Assume the claim is true for systems of d quadratic equations on Cⁿ when n≥2^d. Consider then a system of d+1 quadratic equations on Cⁿ with n≥2^d+1. Apply the induction hypothesis to the first d quadratic forms restricted on a totally isotropic subspace of dimension $\scriptstyle \lfloor n/2\rfloor$ for the last quadratic form. Note that $\scriptstyle \lfloor n/2\rfloor \geq 2^{d}$ because n≥2^d+1. --pma 14:45, 3 May 2010 (UTC)

Ideals in a PID

How would I go about showing that for ideals I = Ra, J = Rb in a PID, R, IJ = I $\cap$ J if and only if I + J = R? I can only seem to get so far with either implication. IJ is always contained in the intersection, so I've tried taking an x which is in both I and J, and showing I can write it as x = r(ab) for some r in R...with limited success. I tried toying with the idea of writing 1 = sa + tb (s, t in R), but couldn't get the expression in a helpful form. The result is easily true if I = R or J = R, so we can assume I and J contain no units, but I'm struggling to cobble all these facts together into a useful argument. Help is appreciated! Icthyos (talk) 22:01, 2 May 2010 (UTC)

You have x in I∩J, so x=ra=sb for r,s in R. Also, 1=ta+ub for t and u in R. Thus s=sta+sub, and so since a divides the RHS it also divides s, so x=sb=vab for v in R, and x is in IJ as desired. This is essentially the same proof as in the special case R=Z, with a and b being coprime (Za+Zb=Z being the coprimality assumption). Algebraist 22:50, 2 May 2010 (UTC)

In fact, you can prove both implications at once and more besides by showing that ab=gcd(a,b)*lcm(a,b) (up to associates). This works since Ra∩Rb=Rlcm(a,b), while Ra+Rb=Rgcd(a,b). Algebraist 23:00, 2 May 2010 (UTC)

A-ha, thanks - I had a feeling it would be something to do with writing 1 like that. How do you go about defining gcd and lcm for a general (not necessarily ordered?) PID though, or were you just referring to the case R = Z in your second comment? Thanks, Icthyos (talk) 11:26, 3 May 2010 (UTC)

You define GCD the same way you do (or at least should) in Z, or in any commutative ring for that matter: gcd(a,b) is a largest common divisor of a and b, with "largest" being interpreted in the divisibility order (a≤b iff a divides b). Thus a gcd is a common divisor which is divisible by all other common divisors. This means of course that the gcd is only defined up to associates. Algebraist 11:43, 3 May 2010 (UTC)

Ah, right. That makes a lot of sense. Thanks again! Icthyos (talk) 14:52, 3 May 2010 (UTC)

May 3

show that cos(2pi/7)+cos(4pi/7)+cos(6pi/7)=-1/2

solving the equation $1+Z+Z^{2}+Z^{3}+Z^{4}+Z^{5}+Z^{6}=0$ yields the solutions $Z=e^{\frac {-6i\pi }{7}},e^{\frac {-4i\pi }{7}},e^{\frac {-2i\pi }{7}},e^{\frac {2i\pi }{7}},e^{\frac {4i\pi }{7}},e^{\frac {6i\pi }{7}}$. Hence show that $\sum _{r=1}^{3}{cos({\frac {2r\pi }{7}})}={\frac {-1}{2}}$ Show me where to begin plz.--115.178.29.142 (talk) 01:11, 3 May 2010 (UTC)

If the sum is 0 then subtracting 1 from each side, you get that the sum of the six roots is −1. The real parts of those six roots are the cosines. The roots come in pairs. Two roots in a pair have equal real parts. You're summing only three of them—one from each pair—and not the other three, so the sum is only half as much. Michael Hardy (talk) 01:15, 3 May 2010 (UTC)

Oh.... I guess I'd better mention: the six roots are just the 1st through 6th powers of one of the roots. Therefore you really are summing the six roots if you're summing the 1st through 6th powers of that one root. Michael Hardy (talk) 01:21, 3 May 2010 (UTC)

...and by the way, notice the difference between this:

$cosx\,$

and this:

$\cos x\,$

Writing \cos x, with a backslash has three effects: (1) "cos" doesn't get italicized along with x; (2) proper spacing appears between "cos" and "x"; and (3) when TeX is used in the normal way (as opposed to the way it's used on Wikipedia, then no line-break will appear between "cos" and x. (In Wikipedia, no line-break will ever appear anyway....) Michael Hardy (talk) 01:18, 3 May 2010 (UTC)

In real TeX, no line breaks will ever appear inside $cos x$ either: a math formula can only be broken at the outermost brace level after an explicit penalty (e.g., \break), a discretionary break (e.g., \-), a relation sign (e.g., =), or a binary operation sign (e.g., +), the last three incurring a \hyphenpenalty/\exhyphenpenalty, \relpenalty, and \binoppenalty, respectively. Not that I would advocate using <math>cos x</math> (it's clearly wrong for the other reasons you gave), but let's get the facts straight.—Emil J. 14:36, 3 May 2010 (UTC)

Formal proof that (2^x-1)/(3x!+x^2-1) converges to 0

Prove that ${\frac {2^{x}-1}{3x!+x^{2}-1}}$ converges to $0$
This is what I've done so far:

$|{\frac {2^{x}-1}{3x!+x^{2}-1}}-0|<\epsilon$

⇔$|{\frac {2^{x}-1}{3x!+x^{2}-1}}|<\epsilon$

$\Leftarrow {\frac {2^{x}}{3x!-1}}<\epsilon$

but now I'm stuck —Preceding unsigned comment added by 115.178.29.142 (talk) 02:05, 3 May 2010 (UTC)

Are you allowed to use Stirling's formula? (Igny (talk) 02:37, 3 May 2010 (UTC))

First you want to get rid of the -1 to make things cleaner. For example you could say ${\frac {2^{x}}{3x!-1}}<{\frac {2^{x}}{x!}}$ for all x ≥ 0 (note that the constant factors don't really matter for any argument you're going to make). Then you want to make an argument for why a factorial grows faster than an exponential. In particular, when x increases by 1, 2^x increases by a factor of 2, while x! increases by a factor of x (which is much bigger than 2 when x gets large). For any specific choice of ε, you need to find any large enough x such that 2^x/x! has definitely decreased below ε. Rckrone (talk) 03:06, 3 May 2010 (UTC)

Begin by rearranging

${\frac {2^{x}-1}{3x!+x^{2}-1}}={\frac {2^{x}}{x!}}{\frac {1-{\frac {1}{2^{x}}}}{3+{\frac {x^{2}}{x!}}-{\frac {1}{x!}}}}$

Then prove that each of the four fractions $\scriptstyle {\frac {2^{x}}{x!}},{\frac {1}{2^{x}}},{\frac {x^{2}}{x!}},{\frac {1}{x!}}$ converges to 0 for x going to infinity. Bo Jacoby (talk) 06:09, 3 May 2010 (UTC).

The core of the problem is to get an estimate for $\scriptstyle {\frac {2^{x}}{x!}}$. If x is assumed an integer (usually the gamma function is used for non-integer x) then it should be easy to construct an inductive argument that $\scriptstyle {\frac {2^{x}}{x!}}<{\frac {C}{2^{x}}}$ for some value of C. If x is not an integer then it gets back to whether you can use Stirling's formula.--RDBury (talk) 15:02, 3 May 2010 (UTC)

No need of Stirling formula even for real x. Follow Bo Jacoby's directions and use e.g the obvious bound x!≥3^x-3 for x≥3.--pma 17:43, 3 May 2010 (UTC)

Paying a point for lower mortgage rate

My local bank offers 5.125% 30 year fixed mortgage for 0 points and 5.000% for 1 point (1% of principal paid as a fee to get the lower rate). To determine which is more fair, I used Excel functions RATE() and PMT() in the following way

rate=5.125%/12

duration=30*12

payment=PMT(rate,duration,100000) <---- monthly payment on $100k loan at 5.125 APR

guess=rate

fv=0

type=0

fairrate=RATE(duration,payment,101000,fv,type,guess)*12

For this particular exercise, payment per month at 5.125% is $544.49, and the "fair rate" is 5.037%. That is, owing $100k at 5.125% mean the same payments as owing $101k at 5.037% APR. But because the bank offers 5% for 1 point fee, it seems like a good deal, right? Is there a mistake in my reasoning? (Igny (talk) 03:14, 3 May 2010 (UTC))

I don't know if the mathematics desk is the right place to ask. You have to take the tax deduction on the interest into account, and the point may not be deductable the same way. You have to think about potential changes in your tax bracket over the next 30 years, either because your income changes or because the tax code changes. And even if one deal is better from a linear perspective, the marginal utility of paying a chunk of cash now instead of spreading it across multiple years may not work out the same way. Finally, you're presumably getting a fixed mortage instead of an ARM because you anticipate inflation levels to increase compared to now. But in that case, why would you want to pay valuable cash now instead of worthless cash later? 69.228.170.24 (talk) 08:07, 3 May 2010 (UTC)

No, mathematics is the right place to ask these questions. I did not come here for tax advice, philosophical ramifications, legal or other consequences of having two different loans. I believe that two loans with a certain set of parameters can be compared to each other, for example by looking at the present values of the payments. In my example, owing $100k at 5.125% have the same payments as owing $101k at 5.037%, isn't owing $100k at 5.000% better if I pay $1k for the discount, thus adding $1k to PV of my payments? I consider simple assumptions that I do not prepay loan or the rates stay the same in 30y, and other simplifying assumptions you can think of. After all the banks do use some algorithms saying that for 1 point fee I am getting a discounted rate of 5%, not 4.5% or 4%, but 5%. How do they figure it out? (Igny (talk) 05:59, 4 May 2010 (UTC))

If which loan you take affects how much you're paying in taxes and when, that has some value too which needs to be taken into account. Rckrone (talk) 17:47, 4 May 2010 (UTC)

But otherwise it seems like it would be a good deal if you have the money to pay. Compare it to if you were allowed to pay off 1% of the loan now and only owe $99,000 at 5.125%. That payment would be slightly higher than $100,000 at 5%. Of course presumably the ability to borrow money is worth more to you than 5.125% APR, in which case borrowing more might be favorable even at a premium. You should figure out what the cost of that addition $1000 is. Rckrone (talk) 17:57, 4 May 2010 (UTC)

I think that to properly compare the two loans for yourself, you do have to take tax issues and utility into account. Since your user page says you have a PhD in mathematics I'm sure you can figure out the PV of the payment stream from the bank's point of view (it is just $PV=\sum _{k=1}^{n}Pz^{k}$ where P is the monthly payment, z is the discount coefficient 1/(1+i) and i is the monthly interest rate. That summation is in turn just the difference between two geometric series, $PV=\sum _{k=1}^{\infty }Pz^{k}-\sum _{k=n+1}^{\infty }Pz^{k}={1-z^{k+1} \over {1-z}}$ unless I made an error someplace. 69.228.170.24 (talk) 23:16, 4 May 2010 (UTC)

I know this is a little late, but I wanted to throw in my advice as someone who has studied this stuff. No one has suggested that you subtract the common portion of the monthly payment out of both equations so that the math is easier. Suppose that the 30 year (12 monthly payments) = 360 payments @ 5.000% interest equals $536.82 per month. Thus the difference in monthly payment on owing $100k at 5.125% interest vs 5.000% interest equals $7.67 per month. (line break for new paragraph)

Now you mathematician/PhD guys can look at this problem simplified. What is more valuable to the OP? Would he prefer to be given $1,000 cash today or would he prefer to be given $7.67 per month for the next 360 months? (trivially, when you multiply $7.67 times 360 equals $2761.20) If the OP prefers to be given $1000 cash today, then he should take the 5.125% loan. If the OP prefers $7.67 cash per month for the next 360 months, then he should take the 5.000% loan. (line break for new paragraph)

If you want my advice, you should go with the loan which has a higher interest because you can avoid a sunk cost (the $1000 loan origination fee to the bank) which makes refinancing at a lower interest rate in the future more "profitable" if interest rates go down, if your credit rating goes up, or if markets predict/forecast low inflation expectations. Also built in to the "utility" of a lower rate is the consumer's peace of mind that he has acquired a lower interest rate (which is always good, right?) and by giving customer's a choice, some customer's will take the "wrong choice" which the bank simply got a free few dollars simply by giving all customers a choice, and some customers picking the option which is slightly more profitable for the bank, by a few dollars. 66.231.146.7 (talk) 12:57, 8 May 2010 (UTC)

Thank you 66. I think I figured out solution to my question, and I made a mistake in the formulas above. Consider a loan of $100k at 5.125%APR fixed for 30years. That is $544.49 per month. The formula for the "fair rate" above is close but not exact,

fair rate= RATE(30*12,-544.49,100000/.99)*12, approximately 5.0363% APR 

To better understand what I mean, compare the following scenarios for a loan for a home valued at $125k. I could use 1 point to pay for a rate discount or towards a downpayment.

Scenario	Downpayment	Discount fee	Loan	Monthly payment	Principal in 10y
5.125%APR, 0 points	$26,000	$0	$99,000	$539.04	$80,830
5.0363%APR, 1 point	$25,000	$1,000	$100,000	$539.04	$81,430
5.000%APR, 1 point	$25,000	$1,000	$100,000	$536.82	$81,342

In all 3 cases the closing payment is the same. First two have identical monthly payments, that is what I meant when I said to get a "fair rate" if you pay 1 point. It seems that the third scenario is a clear winner since we save approximately $2.22 per month for 30 years, while paying the same money at the closing.

I could be saving by taking the discounted offer, but only if I plan to keep the loan for full 30 years. However, as 66. noted, I may lose later if I make prepayments, or if I refinance, or if I sell the house early because the principal balance say 10 years from now is higher in 2nd or 3rd scenario. (Igny (talk) 01:18, 9 May 2010 (UTC))

Uniform distribution

If we assume that a number on a computer screen ticks over every three seconds (say, percentage downloaded or something), and the person previously sitting at the computer walks out of the room, makes a cup of tea and walks back in, then the point along the 0-3 second cycle at which they walk in (X, say) is uniformly distributed on [0,3], right? So if walking in within 0.1 seconds of the number ticking over counts as seeing it tick over as soon as one walks in, then $P\left({\text{ticks over straight away}}\right)=\int \limits _{2.9}^{3}{\frac {1}{3}}dx=\left[{\frac {x}{3}}\right]_{2.9}^{3}={\frac {1}{30}}$.

However, what if the length of the cycle is itself a random variable? What if, due to fluctuations in signal strength (or something), the time it takes for the number to tick over, Y, is itself uniformly distributed on [0.5,5.5]; what then is $f(x)$ and hence $P\left({\text{ticks over straight away}}\right)$, defined as above? It Is Me Here ^{t / c} 11:45, 3 May 2010 (UTC)

The probability to walk in during a cycle of length l is proportional to l. Therefore (after some calculations), the result is $P\left({\text{ticks over straight away}}\right)={\frac {0.1\cdot 2}{5.5+0.5}}={\frac {1}{30}}$. -- Meni Rosenfeld (talk) 13:32, 3 May 2010 (UTC)

What calculations, if I may? It Is Me Here ^{t / c} 14:10, 3 May 2010 (UTC)

In fact, there's a more general result: Let t be the mean time in seconds between two ticks. Then, trivially, the mean number of ticks per second is 1/t, and therefore the expected number of ticks observed during a randomly chosen s-second interval is s/t. This holds regardless of the distribution of interval lengths. Further, if the distribution is such that no more than one tick can occur within any s-second interval, then the probability of observing a tick during such an interval is also s/t. —Ilmari Karonen (talk) 15:07, 3 May 2010 (UTC)

Ramsey Theory and TCS

How are results of Ramsey theory applied in the field of theoretical computer science? Thanks-Shahab (talk) 13:32, 3 May 2010 (UTC)

Um, try google? 69.228.170.24 (talk) 18:24, 5 May 2010 (UTC)

line and curve fitting algorithms

I'm interested in learning about curve fitting using something considerably more sophisticated than the traditional least squares method. Least-squares has two significant disadvantages, I think:

• The distances it minimizes are always along lines perpendicular to the x-axis, meaning that, in effect, x coordinates are always assumed to be perfectly accurate.
• By squaring the errors, outlying points are given disproportionate weight. The farther out a point is, the less weight I'd like to give it (not more, as squaring it does). Ideally I'd like the fit to embody an assumption of Gaussian error distribution.

I'm also interested in fitting fancier curves than simple lines or polynomials -- ideally I'd like to be able to fit parametric equations (x=f(t) and y=g(t)), as well.

I'm sure this is a well-studied problem, but I don't know where to start. Thanks for any pointers. —Steve Summit (talk) 18:53, 3 May 2010 (UTC)

• For the problem of x values being assumed accurate, see Errors-in-variables models. But usually accounting for measurement errors is unnecessary, see this.
• I think your intuition with regards to squaring the errors is wrong. In fact the least-squares model does embody an assumption of Gaussian error distribution. It looks like what you are really trying to do is an error which is a mixture of a Gaussian with a small, non-negligible chance of being an extreme outlier. So the weight will increase at first but then decrease past the point where the error could be in the Gaussian part. This is less elegant computationally but I'm sure something can be worked out.

For non-linear\polynomial curves, you need Nonparametric regression. Kernel regression is simple and effective, but the more general Local regression has some advantages. I don't know how much fitting a parametric equation has been studied but I suspect that simple modifications can address it. -- Meni Rosenfeld (talk) 19:23, 3 May 2010 (UTC)

Our kernel regression article is unsatisfying. It doesn't seem to address how to choose a bandwidth, which is typically by cross-validation. All of Nonparametric Statistics by Larry Wasserman discusses these matters, but I'm neutral as to how good the book is. -- Meni Rosenfeld (talk) 19:32, 3 May 2010 (UTC)

Squaring the errors is the maximum likelihood estimate given an assumption of a Gaussian distribution. Outliers are given higher weight precisely because they are unlikely to occur under Gaussian distribution. The first level of improvement is probably a technique like total least squares that considers errors in both x and y. You might consider other general techniques like generalized least squares. There are also various iterative procedures for determining if an outlier is so improbable that you are better off assuming it is totally erroneous and excluding it, but I don't see any articles about that. Dragons flight (talk) 19:27, 3 May 2010 (UTC)

There is a very very extensive literature on this. You might start with some of the Wikipedia articles mentioned above.

You say both that you want to assume a Gaussian error distribution, and that you don't want to use least squares. But least squares is in some senses optimal for a Gaussian error distribution, and in fact the reason it's called "Gaussian" is that Gauss showed that it's the error distribution for which least squares is optimal in at least one sense. I see someone's mentioned above that least squares coincides with maximum likelihood when the errors have a Gaussian distribution. Michael Hardy (talk) 01:47, 4 May 2010 (UTC)

The farther out a point is, the less weight I'd like to give it (not more, as squaring it does). That is easily done. Just pick one point to be credible and discard all the others. (That is what many people do, I think, but good statisticians do not throw valid data away). Bo Jacoby (talk) 14:00, 5 May 2010 (UTC).

Thanks for all the pointers, and for correcting my misapprehension about outliers. —Steve Summit (talk) 13:21, 7 May 2010 (UTC)

May 4

Completing rows/columns in a character table

I'm currently trying to complete the character tables of A₆ and S₆. The 7x7 A₆ table is complete except for one ('non-trivial') column, which is entirely blank, except for the top entry, corresponding to the trivial character. My plan of attack would be to use the orthogonality relations to generate six equations, in the six unknown entries of the final column (taking the product of this column with each other column, which must be zero), then solving this system. Is there some simpler trick I'm missing? The problem I'm attempting is from an exam, so I'm assuming there's some time-saving method I'm not seeing.

Similarly, for the 11x11 S₆ table: it is complete except for two rows. I've managed to fill in the first entry of each, corresponding to the trivial conjugacy class, but my plan of attack would be the same: to generate ten equations in the ten unknowns. Again, I'm hoping for some alternative method! Thanks, Icthyos (talk) 12:29, 4 May 2010 (UTC)

Symmetric group characters are easy because they can all be derived from characters induced from the trivial characters on subgroups. In fact you only have to look at the subgroups S₆, S₅×S₁, S₄×S₂, S₄×S₁×S₁, ... . Once you have S₆ you should be able to get nearly all of the A₆ characters by restriction since A₆ has such a low index.

Btw, the character table for S₆ is interesting because it has an unexpected symmetry. This corresponds to the outer automorphism that's unique to S₆ (among symmetric groups).--RDBury (talk) 14:15, 4 May 2010 (UTC)

Ah, thanks a lot. That cuts down the work. For general groups though, if the situation is as I described, is setting up the system of equations and solving them the only sure fire way of completing it? Icthyos (talk) 14:46, 4 May 2010 (UTC)

First, I'm by no means a group theorist so take what I say with a grain of NaCl. In my experience the symmetric groups and related groups are somewhat exceptional because you can get all the representations by inducing trivial representations of subgroups. With other groups it gets trickier because the orthogonality relations only get you so far. There is a theorem (we probably have an article on it but I don't remember the name off hand) that states that any representation is a linear combination of characters induced from cyclic subgroups. As a practical matter though, finding which linear combinations of these characters give you the irreducible characters can be tricky. So I guess my answer to your question for general groups is probably yes, but I never got far enough in group theory to know what they are.--RDBury (talk) 18:14, 4 May 2010 (UTC)

PS. For a real test, try finding character tables for some of the small linear groups, such as psl(2,11). It's order is 660, not that much bigger than the order of A6, but the level of difficulty is much higher.--RDBury (talk) 18:20, 4 May 2010 (UTC)

Brauer's theorem on induced characters is probably the article you want.

You may find James and Liebeck's textbook helpful. S6 is worked out in some detail on pages 201–205 using only the earlier tools: linear characters, tensor products of characters, the permutation character, and orthogonality. In particular, it avoids the exceptionally effective technique of inducing from Young subgroups and using Gram-Schmidt to pull out the irreducibles. A6 is left as an exercise, but a large portion of a chapter is devoted to making this exercise easy: pages 216–220 cover restriction to a normal subgroup of index 2, a very, very important technique. Page 220–222 cover using the table of S5 to get the table of A5. To get the table of A6 is exercise 2. You use (20.13).(1) to see that the restrictions of the characters of S6 of degree 1,5,10,9,5 (and their signed friends) reduce to irreducible characters of A6 of degree 1,5,10,9,5 (only one copy each). The only character left is the one of S6 of degree 16, which you know must restrict to the sum of two Galois conjugate characters of A6 of degree 8. Writing out the character table of A6, I thus need 5 variables to denote the missing values, and each value follows easily from column orthogonality and the definition of the character value (sums of n'th roots of unity, where n is the order of the element). The character values of S6 give me the trace of the numbers, and column orthogonality gives me their (complex) norm. JackSchmidt (talk) 21:30, 4 May 2010 (UTC)

Retrieving the Metric from Christoffel Symbols

Lets say we know the Christoffel Symbols of a geometry in some coordinate system. How does one obtain the metric in terms of its Christoffel Symbols? Thanks.The Successor of Physics 14:09, 4 May 2010 (UTC)

An easy way could be to try to find the Lagrangian that will yield the equations for the geodesic. Count Iblis (talk) 14:43, 4 May 2010 (UTC)

I don't really get what you mean. May you please clarify?The Successor of Physics 15:17, 4 May 2010 (UTC)

The equations for a geodesic are given by

${\frac {d^{2}x^{\mu }}{du^{2}}}+\Gamma _{\rho \sigma }^{\mu }{\frac {dx^{\rho }}{du}}{\frac {dx^{\sigma }}{du}}=0$

But these are also generated by the Lagrangian:

$L={\frac {1}{2}}g_{\mu \nu }{\frac {dx^{\mu }}{du}}{\frac {dx^{\nu }}{du}}$ Count Iblis (talk) 15:52, 4 May 2010 (UTC)

Thanks!The Successor of Physics 13:07, 5 May 2010 (UTC)

Number of conjugacy classes

Suppose G is a non-abelian group of order pq, where p and q are primes such that p divides q - 1. I know that the size of the conjugacy classes of G have to divide pq, and since the group is non-abelian, there are none of size pq. How would I go about finding the number of distinct conjugacy classes of each size? I know from the class equation we must have pq = a + bp + cq = a + bp + c(kp + 1), where a, b and c are the number of classes of each type and k is some integer, but I'm not sure how to go much further. Thanks, Icthyos (talk) 14:58, 4 May 2010 (UTC)

If S is a Sylow q-subgroup of G, then it is necessarily normal (this follows from certain fundamental results in Sylow theory). Furthermore, the size of the conjugacy class of any non-identity element s of S must be p (since the center of G is necessarily trivial, the centralizer of any such s is S). However, any element of G conjugate to s must have order q (since s has order q), and any such element must therefore be in S since S is the (unique) Sylow q-subgroup of G. Consequently, there are precisely ${\frac {q-1}{p}}$ conjugacy classes of size p in G.

Since the center of G is trivial (since I have already used this fact, I shall quickly note that it is equivalent to the statement that the quotient G/Z(G) can never be a non-trivial cyclic group for any finite group G), the class equation yields that there are precisely ${\frac {pq-q}{q}}$ or $(p-1)$ conjugacy classes of size q. (Of course, there is precisely one conjugacy class of size 1, since G is centerless.) Hope this helps (and I hope I have not made any mistakes; I am a bit tired). PST 15:52, 4 May 2010 (UTC)

2x(edit conflict) Not sure how much this will help to compute the conjugacy classes, but note that your assumptions determine the group uniquely up to isomorphism, as follows. Let P and Q be a Sylow p-subgroup and q-subgroup of G, respectively. Since the number m of Sylow q-subgroups divides p < q and is congruent to 1 mod q, the only possibility is m = 1, which means that Q is a normal subgroup of G. (Incidentally, a symmetric argument shows that the assumption that p divides q − 1 can be weakened to just p < q.) Moreover, P and Q are cyclic groups of orders p and q, respectively, and it is easy to see from $Q\trianglelefteq G$ that G is their semidirect product $Q\rtimes _{\varphi }P$. Such a semidirect product is determined by the action $\varphi$ of P on Q (i.e., a homomorphism $\varphi \colon P\to \operatorname {Aut} (Q)$), which has to be nontrivial as G is nonabelian. Since Aut(Q) is a cyclic group of order q − 1, and P is cyclic of order p, there is (up to an automorphism of P) only one nontrivial homomorphism of P to Aut(Q), namely one which sends the generator of P to an element of Aut(Q) of order (q − 1)/p. To sum it up, G is isomorphic to the group consisting of elements (a,b) where $a\in \mathbb {Z} _{q}$, $b\in \mathbb {Z} _{p}$, with multiplication defined by

$(a,b)(c,d)=(a+\xi ^{b}c,b+d),$

where $\xi$ is a fixed primitive pth root of unity in $\mathbb {Z} _{q}$.—Emil J. 15:55, 4 May 2010 (UTC)

It may be worthwhile to supplement a reading of EmilJ's argument with an attempt at the problem of determining the isomorphism classes of groups of order 6 (this corresponds to p=2 and q=3), and in particular, an attempt to determine the non-abelian groups of order 6. PST 16:15, 4 May 2010 (UTC)

Icthyos, you said, "since the group is non-abelian, there are none [conjugacy classes] of size pq". While it is indeed true that there are no conjugacy classes of size pq in G, this follows more directly (and accurately) from the fact that the identity element constitutes a single conjugacy class (that is, the identity element is not conjugate to any non-identity element in G). (With virtually no extra effort, you can establish that no finite group with more than two elements has precisely two conjugacy classes; it is interesting to note that that this is not the case for infinite groups (that is, there do exist infinite groups in which any two non-identity elements are conjugate!).) PST 16:06, 4 May 2010 (UTC)

Thanks PST, that's exactly what I needed. I'd gone down the route of Sylow subgroups (and had in fact shown that your S was normal), but thought I was just stumbling in the dark. Huzzah! Thanks to you too, Emil J - I've seen that sort of thing before, but I'd never have spotted it for this question. Icthyos (talk) 16:33, 4 May 2010 (UTC)

Actually, I have another question: how do we know that there isn't some conjugacy class of size p entirely disjoint from S? You showed that a general element g being conjugate to s shows that g is in S, but how do we know that there isn't a conjugacy class of size p containing no elements of S? I've shown that g being in a conjugacy class of size p implies that the centraliser of g is S...but does that force g to be in S? Icthyos (talk) 19:35, 4 May 2010 (UTC)

Oops, got it - if gs = sg because the centraliser of g is S, then g is also in the centraliser of s, which we have already shown is S! Icthyos (talk) 20:31, 4 May 2010 (UTC)

I thought I might mention the following neat (and basic) result, since it is somewhat relevant to your question (and might interest you if you have not heard of it already). If G is a finite group, the probability that two elements of G chosen at random (with replacement) commute is given by ${\frac {k(G)}{|G|}}$ where k(G) is the number of conjugacy classes in G. Since we have computed k(G) in terms of p and q for non-abelian groups of order pq (where p divides q−1), this formula yields:

$P({\mbox{Two elements chosen at random from G (with replacement) commute}})={\frac {{\frac {q-1}{p}}+p-1+1}{pq}}={\frac {p^{2}+q-1}{p^{2}q}}$

Note that for the fundamental case corresponding to G being the permutation group on three letters, this formula yields the correct value of ${\frac {1}{2}}$. Further information (if you are curious) may be found at this source.PST 04:29, 5 May 2010 (UTC)

Thanks for that; I consider myself a group theorist (in training, admittedly...), so it's quite fun to collect new and interesting facts like that. Icthyos (talk) 10:23, 5 May 2010 (UTC)

Constructible Universe

From the article Constructible Universe:

"An alternate definition, due to Gödel, characterizes each L_(α+1) as the intersection of the powerset of L_α with the closure of L_α under a collection of nine explicit functions."

Does anyone here know what these functions are? JumpDiscont (talk) 17:42, 4 May 2010 (UTC)

Various choices work, for example

${\begin{aligned}F_{1}(u)&=\operatorname {dom} (u)=\{x:\exists y\,\langle x,y\rangle \in u\},\\F_{2}(u)&=\{\langle x,y\rangle \in u:x\in y\},\\F_{3}(u)&=u^{-1}=\{\langle x,y\rangle :\langle y,x\rangle \in u\},\\F_{4}(u)&=\{\langle \langle y,z\rangle ,x\rangle :\langle \langle x,y\rangle ,z\rangle \in u\},\\F_{5}(u,v)&=\{u,v\},\\F_{6}(u,v)&=u-v,\\F_{7}(u,v)&=u\times v.\end{aligned}}$

(This is obviously not the original Gödel's list, as there are only seven of them.)—Emil J. 18:19, 4 May 2010 (UTC)

Also, I'm afraid the article is in error: for some technical reason which I forget, one has to take the intersection of ${\mathcal {P}}(L_{\alpha })$ with the closure of $L_{\alpha }\cup \{L_{\alpha }\}$, rather than just $L_{\alpha }$, under the operations.—Emil J. 18:26, 4 May 2010 (UTC)

Aha, one reason is that the operations take finite sets to finite sets, which means that under the wrong definition we would end up with $L=L_{\omega }=V_{\omega }$. (Putting preventively ω in L₀ wouldn't help, we would get stuck at ω₁ for the same reason again: in general the operations take sets of cardinality <κ to sets of cardinality <κ, for any infinite κ.)—Emil J. 18:30, 4 May 2010 (UTC)

It seems like F_5 takes subsets of L_α to not-necessarily-subsets of L_α.

Do you just restrict F_5 to when u and v are both elements of L_α?

JumpDiscont (talk) 19:42, 4 May 2010 (UTC)

On the other hand, I now realize you said "the intersection of ${\mathcal {P}}(L_{\alpha })$ with the closure", so it wouldn't have to be a subset of L_α.

However, would replacing F_5 with F_8(u) := {u} work?

JumpDiscont (talk) 21:09, 4 May 2010 (UTC)

I doubt it. How would you ever construct {u,v} using singletons and the other operations, if u ≠ v?—Emil J. 12:43, 5 May 2010 (UTC)

Oh, if $u,v\in L_{\alpha }$, then $\{u,v\}=L_{\alpha }-((L_{\alpha }-\{u\})-\{v\})$. Now, this does not quite apply when u,v are only in the closure of $L_{\alpha }\cup \{L_{\alpha }\}$ instead of in $L_{\alpha }$, though at the very least this means the two definitions of $L_{\alpha }$ would catch up for limit α. However, I have gone through the proof and it appears that even with F₅ replaced by {u} it is possible to show that the closure contains Def(L_α), hence it should actually give the correct L_α for all α. (This also prompted me to change the definition of F₄ above, as I don't know how to make the proof work with the original one; the book I copied it from gave the list without a proof, so it may have been a typo.) So, yes, replacing F₅ with {u} works.—Emil J. 15:11, 5 May 2010 (UTC)

request algorithm for vertex-weighted bipartite graph problem

Let D be a (finite) digraph whose underlying graph is bipartite and connected. Assume that the vertices of D are the union of P and N where the only directed edges in D go from vertices in P to those in N. Assume that the vertices V(D) (not edges!) in D have nonzero integral weights and vertices in P have positive weights and those in N have negative weights. Assume also

• (a) the sum of weights over all v in V(D) is zero
• (b) for all p in P, the sum of weights of adjacent vertices to p plus the weight of p is nonnegative
• (c) for all n in N, the sum of weights of incident vertices to n plus the weight of n is nonnegative

Is there an algorithm (other than brute force) to decide if we can redistribute vertex weights by sharing (positive integrally) weights of vertices in P amongst adjacent (negative) weight vertices such that all vertices in D now have zero weight? If so, what is its complexity?

This isn't a homework question! I know of a domain which gives rise to such graphs and the need for the decision algorithm. The domain also gives rise to other graphs where the needed algorithm is for a maximal cardinality matching, with the Hopcroft–Karp algorithm solving the problem, for example, but this seems to be computationally expensive, and worst case all the time, whereas I've reason to believe the requested algorithm would be more efficient, especially as most of the time we do essentially no work as D has only two vertices, so (a) provides a trivial solution. —Preceding unsigned comment added by Puzl bustr (talk • contribs) 19:40, 4 May 2010 (UTC)

Answered my own question: replace vertex of weight W, say, by abs(W) new vertices of weight sign(W) with new edges inherited in the obvious way. This reduces to bipartite matching. Puzl bustr (talk) 12:18, 5 May 2010 (UTC)

Modular forms/eta function

I am currently reading the proof of Proposition 20 on P130 of the "Introduction to Elliptic Curves and Modular Forms" by Koblitz. He defines $g(z)=(\eta (z)\eta (2z))^{8}$ (the $\eta$ function is famous so I imagine if you don't know what it is you can't help maybe, and thus I won't define it) and I understand that its q-expansion about infinity is $q\prod (1-q^{n})^{8}(1-q^{2n})^{8}$ so that g vanishes at infinity. Now, the sentence I do not get, which may be very easy:

"Using the relation $\eta (-1/z)={\sqrt {z/i}}\eta (z)$, we easily see that g(z) vanishes at the cusp 0 as well."

Just to be sure, I understand the relation is just the functional equation for the eta function and I have already gone through the proof of that. I am just not understanding how to use this relation to show that g vanishes at 0 as well. These q-series do not make a lot of sense to me at times. Thanks. StatisticsMan (talk) 20:01, 4 May 2010 (UTC)

Perhaps someone else can add to this if it needs clarification or more rigor. I believe you are supposed to use that relation to get $g(-1/z)=(\eta (-1/z)\eta (-2/z))^{8}=({\sqrt {z/i}}\eta (z){\sqrt {z/2i}}\eta (z/2))^{8}=z^{8}/16(\eta (z)\eta (z/2))^{8}$. The q-expansion of $\eta$ tells us that $\eta$ has a zero of order 1 at infinity (and g has a zero of order 16 at infinity). If you think about plugging in "the point at infinity" for z in the equation above and compare orders of zero, you see that g has a zero of order 8 at z=0.146.186.131.95 (talk) 13:32, 6 May 2010 (UTC)

Actually, this is good. I just wasn't thinking about it this way. I was thinking of taking $\eta (z)$ and transforming it to ${\frac {\eta (-1/z)}{\sqrt {z/i}}}$ and then g has $\eta (-1/z)\eta (-1/2z)$ and I didn't see how to get a q-series out of that. But, what you say is exactly what I needed. Thanks. StatisticsMan (talk) 14:20, 6 May 2010 (UTC)

May 5

line integrals with respect to arc length versus x or y

I'm a little confused how to picture these as opposed to line integrals with respect to arc length. Suppose you have a line through a field that "curls back" or even forms a circle. Normally what I see happen is that an integral with a dx term gets added to an integral with a dy term. But what if you just evaluated one of them? Is it possible? And how would you set its bounds? (You would start at x=0, for example, and end back at x=0.) John Riemann Soong (talk) 21:18, 5 May 2010 (UTC)

If (x(t),y(t)), 0<t<1 is a curve, the line integral with respect to arc length of the function f(x,y) is

$\int _{0}^{1}f(x(t),y(t)){\sqrt {\left({\frac {dx}{dt}}\right)^{2}+\left({\frac {dy}{dt}}\right)^{2}}}dt$

while the integral with respect to x is

$\int _{0}^{1}f(x(t),y(t)){\frac {dx}{dt}}dt$

Bo Jacoby (talk) 23:22, 5 May 2010 (UTC).

1D projection

It is really easy to make a 2D projection of a 3D shape, but what does a 1D projection of a 2D shape look like? —Preceding unsigned comment added by 93.96.113.87 (talk) 21:56, 5 May 2010 (UTC)

A 1D projection of any shape in any number of dimensions is either a point or a line segment or a collection of points and/or line segments. That's all you can have in 1D space - it's not very exciting. Gandalf61 (talk) 22:23, 5 May 2010 (UTC)

—————————————————— — Knowledge Seeker দ 17:26, 7 May 2010 (UTC)

May 6

Maclaurin expansion for e^(x^2+x)

Find the first 3 terms of the macluarin expansion for $e^{x^{2}+x}$

I know the first three terms for $e^{x}$ are $1+x+{\frac {x^{2}}{2}}$

so presumably the first three terms for $e^{x^{2}+x}$ are $1+(x^{2}+x)+{\frac {(x^{2}+x)^{2}}{2}}=1+x+x^{2}+{\frac {x^{4}+2x^{3}+x^{2}}{2}}$

but apparently the answer is $1+x+{\frac {3x^{2}}{2}}$ --115.178.29.142 (talk) 01:56, 6 May 2010 (UTC)

Just combine the x² terms in the expression you got. You can can generally (meaning with all due attention to convergence issues) manipulate power series like this and then collect like terms to get a new power series.--RDBury (talk) 02:43, 6 May 2010 (UTC)

If you are familiar with multiplication of power series you can just multiply the series for exp(x) and the series for exp(x²) and obtain quickly several terms by hand. In fact the resulting series has coefficient a_n/n! where a_n is an interesting sequence [2]. --84.221.69.102 (talk) 07:49, 6 May 2010 (UTC)

Just to clarify: in the question, "the first three terms of the expansion" refers to monomials like a, bx, cx². So what you did is correct; just forget about the higher order terms you got (that is, x³ and x⁴/2). Note that if you further expand e^x2+x you will find (x²+x)³/3! and so on, so there is no more powers of x of degree 0 1 or 2 around. If you wanted the fourth term of the expansion too, you have to consider (x²+x)³/3! too, of course.--pma 08:56, 6 May 2010 (UTC)

Alternative approach:

$e^{x^{2}+x}=e^{x}e^{x^{2}}=\left(1+x+{\frac {x^{2}}{2}}+O(x^{3})\right)\left(1+x^{2}+O(x^{3})\right)$

$=1+x+{\frac {x^{2}}{2}}+x^{2}+O(x^{3})=1+x+{\frac {3x^{2}}{2}}+O(x^{3})$ Gandalf61 (talk) 11:32, 6 May 2010 (UTC)

don't get why I don't get my moment for this disc doesn't become zero

I have half a disc with a hole in it -- the outer border is r=2 and the inner border is r=1, with restriction x>0. The density function given is x/(x^2 + y^2) which I converted to cos t. Setting up the double integral with bounds -pi/2 to pi/2 with respect to t, and 2 to 1 for r, I get a mass of 3. OK.

Using the formulae for two-dimensional moments:

M_x = (double integral) y * rho * dy dx = (double integral) r sin t cos t r dr dt = 7/3 * 0.5 * (sin^2 pi/2 - sin^2(-pi/2)) = 7/3

M_y = (double integral) x * rho * dy dx = (double integral) r (cos t)^2 r dr dt 
    = 7/3 * 0.5 (t + (sin pi/2 * cos pi/2 - cos(-pi/2) * sin(-pi/2))  = 7/6

Center of mass is then: (7/18, 7/9)

This puzzles me, since x-component of the center of mass appears to be quite firmly in a whole, but the density should be biased towards the end of the disc. The y-component isn't zero.

It's the trig function part that I think is responsible.... integrating cos t sin t can yield 0.5 (sin t)^2 or -0.5(cos t)^2. Using the latter formula gives me an M_x value that is quite zero. They appear to differ by a constant... which should disappear in an indefinite integral ... except when cos(pi/2) is involved. Help? John Riemann Soong (talk) 04:38, 6 May 2010 (UTC)

Is the density ${\frac {x}{x^{2}+y^{2}}}$ or ${\frac {x}{\sqrt {x^{2}+y^{2}}}}$? The latter is $\cos t$, the former is $\cos t/r$. -- Meni Rosenfeld (talk) 06:28, 6 May 2010 (UTC)

More importantly, $\sin ^{2}{\tfrac {\pi }{2}}-\sin ^{2}{\tfrac {-\pi }{2}}=0$, not 2. -- Meni Rosenfeld (talk) 09:01, 6 May 2010 (UTC)

Random walk oddity

I have a non-gaussian distribution that I made up to model the steps in a stochastic time series. As such, it fits the actual histogram quite well. The distribution has a sharper, taller peak and fatter tails than the normal distribution, and it has infinite kurtosis.

So I use the inverse cumulative form of my distribution to create my own random walk. That works fine too. I get a bunch of steps distributed according to my distribution.

Then I decide that each step should be made of 100 smaller steps having 1/100 the variance of the larger steps. Each of those smaller steps is distributed according to my distribution.

When I look at the histogram of the larger steps, the distribution looks gaussian! The peak and tails fit a gaussian distribution. If I use, say, 20 steps per large step, the resulting distribution is something in between mine and a gaussian. It seems the more small steps I use to build a large step, the more gaussian the resulting large steps appear.

Why? Does that make sense? What would I do to ensure that the larger steps maintain the same distribution as the smaller steps? ~Amatulić (talk) 05:52, 6 May 2010 (UTC)

Surely you are familiar with the Central limit theorem? As long as the variance is finite, adding many independent copies will give something that is roughly Gaussian.

However, the situation may not be that bad - it may look like Gaussian for small values of x, but it will still have infinite kurtosis and hence, black swans that are significantly more probable than in Gaussian.

Stable distributions usually have infinite variance, so you may not be able to find exactly what you are looking for. -- Meni Rosenfeld (talk) 06:38, 6 May 2010 (UTC)

Central Limit Theorem -- looking at the article, it looks familiar, like something I learned 27 years ago when I was in college and never encountered since. OK, I get it now. So much to re-learn.... I'm basically a layman again.

Actually, adding many independent copies looks exactly like a gaussian, tails and all, so black swans are really no more probable than with a gaussian. I mean, my distribution at 5-sigma from the mean is 100K more likely to generate black swan events than this.

Stable distributions -- that's another topic I looked at before I spent all this effort rolling my own. Can't be written out analytically? Need numerical methods for everything? I honestly gave up trying to work with such a thing. All I'd need is a general expression for β=0 and α<2.

Illustration for my comments

Here's what I'm trying to simulate. Take any time series of prices for any market: could be soybeans, copper, Euro currency, Dow Jones index, NASDAQ, orange juice, whatever. Sample the step sizes between log prices 10,000 times at any interval, you get a distribution similar in appearance to mine (see picture - I did a lot of tests, I believe that one shown is the S&P 500 index). Sample it at any other interval, and you get the same distribution. Always.

So I spent a couple weeks inventing this beautifully tractable distribution that seems to fit the data almost perfectly. It's integrable, it's invertible, it's closed-form. You helped me out in characterizing variance and kurtosis (thanks). Then I used my distribution to generate a random walk. Its histogram of step sizes practically overlays that of the actual market I'm simulating. Visually it looks the same, tails and all. But when I sample the step size at any interval other than 1, it isn't the same, and approaches a gaussian distribution at high sample intervals.

Now, I understand that what I observe is because my distribution has a finite variance. OK, fine. My observations imply that the actual underlying market distribution has infinite variance.

But this is where I stumble: I have a finite data set (say 12,000 samples), and you said yourself to me that a finite data set often results in benign values for variance and kurtosis because it can't contain all the possible outliers. Yet, I built my own distribution to characterize the market's, using all the data I have, so it should model this finite data set rather well. What I'd like to know is, why does this finite data set exhibit the same non-normal distribution at any sample interval? I hope I stated the problem clearly through my befuddled brain. ~Amatulić (talk) 06:16, 7 May 2010 (UTC)

The simplest explanation I can think of is that the differences between successive days are not independent - that is, if it increases one day it has a higher probability than usual to increase the next. You should try to find this dependence and generate your random walk accordingly. -- Meni Rosenfeld (talk) 08:19, 7 May 2010 (UTC)

Hmm, but then that would have to be true on any time frame -- minutes, hours, days, weeks, months. A fractal dependency, if you will. I can investigate, but I have doubts. If one knows such a dependency, one could become wealthy quite easily and quickly. I rather doubt the dependency exists (or is discoverable) considering the efforts people have put into technical analysis of markets over the past several decades to find such a "holy grail". All I'm trying to do here is generate an artificial time series with the same characteristics as a real time series. ~Amatulić (talk) 16:48, 7 May 2010 (UTC)

Update

All right, that took all day! I figured out an algorithm to generate random walks with my distribution such that it gets past the Central Limit Theorem. If I want daily steps made up of n smaller steps, and both daily steps and smaller steps must be distributed according to my distribution, then the mean value used for the smaller steps must be varied by my distribution. That is:

$\sigma _{s}={\frac {\sigma _{L}}{n}}$

$\mu _{s}={\frac {\mu _{L}+F^{-1}(Z,0,\sigma _{L})}{n}}$

where

• Subscript L indicates the large step
• Subscript s indicates the small steps making up the large step
• F⁻¹ is my inverse cumulative distribution
• Z is a uniformly distributed random number between 0 and 1
• n is the number of steps that make up a large step

Then, each new small step v_s is:

$v_{s}=F^{-1}(Z,\mu _{s},\sigma _{s})$

and the sum of n small steps equals one large step. I have verified that the large steps have the desired probability density function $f(x,\mu _{L},\sigma _{L})$.

As for the question if there's a dependency from one step to the next: Yes, slightly. I found that in the market data, a large step has a tendency to be followed by another large step with greater frequency than steps generated randomly. I observed no directional dependency; both the market and randomly-generated steps looked the same in that regard. ~Amatulić (talk) 01:35, 8 May 2010 (UTC)

Ok, there's not much more I can add. If you haven't already, make sure to take a close look at the Wiener process (aka Brownian motion), in particular Construction of Brownian Motion - the way it's constructed is reminiscent of what you've done here. Brownian Motion is a more detailed discussion. -- Meni Rosenfeld (talk) 18:58, 8 May 2010 (UTC)

Thank you for your help and the links. I especially like the easy informal tone of the more detailed PDF document. ~Amatulić (talk) 22:16, 8 May 2010 (UTC)

Problem with product rule and second derivatives

I'm having problem in understanding the result of differentiating two times a compostion, that is

$D^{2}(F\circ G)[h,k]$

I can't understand wheter (and why) the result should be

$((D^{2}F)\circ G)[DG[h],DG[k]]+((DF)\circ G)[D^{2}G[h,k]]$

rather than

$((D^{2}F)\circ G)[h,DG[DG[k]]]+((DF)\circ G)[D^{2}G[h,k]]$

I just start with

$D(F\circ G)[h]=(DF\circ G)[DG[h]]$

and apply the rule

$D(M[v])[h]=(DM[h])[v]+M[Dv[h]]$

to $M[\cdot ]:=D(F\circ G)[\cdot ]$ and $v:=DG[h]$ but at a certain point I'm not able to evaluate $D(M[v])[h]$ because I've to decide wheter

$D(((DF)\circ G)[h])[v]=((D^{2}F)\circ G)[DG[h],v]$

or

$D(((DF)\circ G)[h])[v]=((D^{2}F)\circ G)[h,DG[v]]$

and this whould make a great difference since I have $v=DG[k]$.

What am I missing?--Pokipsy76 (talk) 15:20, 6 May 2010 (UTC)

Is D an arbitrary differential operator? I may be being stupid, but why are G and D²G functions of two variables and DG a function of one? --Tango (talk) 15:29, 6 May 2010 (UTC)

Maybe I've not been very clear. Well D is the usual differential operator in an euclidean (or a Banach) space (so D²G(x) is a bilinear operator and DG(x) is a linear operator), F(x) and G(x) are differentiable functions from a vector space U to itself and their variables are never considered in the formulas above: the only variables which appear are the variables of the linear operators. I'm using the notation which can be found also here. Thank you for your attention.--Pokipsy76 (talk) 15:45, 6 May 2010 (UTC)

You want to differentiate the map $M(x)[v(x)]$, where $M(x):=DF(G(x))$ and $v(x):=DG(x)[h]$ as you said. (I'll keep the x, even if it makes a bit heavier the notation). Applying your rule $D(M(x)[v(x)])[k]=(DM(x)[k])[v(x)]+M(x)[Dv(x)[k]]$ you get

$D^{2}F(G(x))[DG(x)k,DG(x)h]+DF(G(x)[D^{2}G(x)[k,h]],$

and this is $D^{2}(F\circ G)(x)[k,h]$ (note that the result is symmetric in h,k as it has to be).

POssibly you mixed a bit the role of h and k; in all the computation h is fixed. Remark: I think we agree that $D^{2}B(x)[k,h]$ coincides with the differential of $x\mapsto DB(x)[h]$ evaluated in k (we used this more that once). Indeed you may apply again your product rule for M(x)[v(x)] with M(x):=DB(x) and v(x):=h; or consider $x\mapsto DB(x)[h]$ directly as a composition of $x\mapsto DB(x)$ and $L\mapsto L[h]$; the latter is the evaluation at h and is linear. Is everything ok? --pma 06:04, 7 May 2010 (UTC)

I'm not sure... I need to think about it.--Pokipsy76 (talk) 15:56, 7 May 2010 (UTC)

In any case, the second possibility you wrote at the beginnning is not symmetric in h,k, and couldn't be correct. As to the term

$D(((DF)\circ G)[h])[v]$

that you want (where v is fixed), observe that it represents the differential of the map $((DF)\circ G)(x))[v]$ , evaluated in the variation h; this is different from the differential of the map $((DF)\circ G)(x))[h]$ evaluated in v as variation. The notation may have confused you a bit, but the point is that the former object is exactly what is wanted by the computation, not the latter (whatever notation you adopt). Now, the map $x\mapsto DF(G(x))[v]$ is a composition of three maps: G, DF, "evaluation at v": $x\mapsto G(x)\mapsto DF(G(x))\mapsto DF(G(x))[v]$, and the last (evaluation at v) is linear. Therefore the differential of this composed map computed in the variation h, is the composition of differentials: $h\mapsto DG(x)[h]\mapsto D^{2}F(G(x))[DG(x)[h]]\mapsto D^{2}F(G(x))[DG(x)[h],v]$. --pma 08:42, 8 May 2010 (UTC)

Algebra question

Hey I was playing around with math a bit and I was wondering if it was possible to solve certain types of equations for $x$ by algebraic means (i.e. - no calculator graphing and finding points of intersection). Specifically, I was wondering about ones where $x$ might appear within a trig function and outside the trig function. Also, the same question applies for ones containing logarithms and exponentials. For example, would it be possible to solve the equation $5={\frac {e^{x}}{x^{2}+4}}$ without a calculator? Thanks!!! — Trevor K. — 20:54, 6 May 2010 (UTC) —Preceding unsigned comment added by Yakeyglee (talk • contribs)

Generally, the answer is that there is no elementary analytical solution. An equation like the one you posted can probably be solved in terms of the Lambert W function, but to say that the solution to x = y*e^y is y = W(x) isn't really a genuine solution, since that's just the definition of the W function. The same goes for equations that include logarithms, and probably trigonometric functions (since they can generally be written in terms of complex exponentiation). Confusing Manifestation(Say hi!) 23:56, 6 May 2010 (UTC)

"The solution to $x=ye^{y}$ is $y=W(x)$" isn't any less of a genuine solution than "The solution to $x=e^{y}$ is $y=\log x$", since that's just the definition of the log function.

Anyway, the solution to the OP's particular example apparently cannot be expressed even with Lambert's W (it doesn't handle addition very well). This goes for trigonometric functions too, as their reduction to exponentiation requires addition.

The OP should note that there are root-finding algorithms significantly more sophisticated than "calculator graphing", which can even be done by hand with some work. -- Meni Rosenfeld (talk) 05:40, 7 May 2010 (UTC)

No, you cannot do it algebraically, and I don't think you can do it by hand either, but you can expand the exponential (or the trig functions) into a polynomial of degree, say, 19. Download the J (programming language) and type |.{:>p.(^-20 0 5&p.)t.i.20 and get the real root 4.96444. There are also nonreal complex roots such as 0.0465684+2.02331i. Check that 4.96444 is a solution to the original equation by typing (^%4 0 1&p.)4.96444 and get the result 5, which is what you wanted. Bo Jacoby (talk) 16:00, 7 May 2010 (UTC).

May 7

Urgent question to someone with a copy of SPSS in front of him/her

(moved this over from the computer desk because it seems more appropriate at the statistics desk)

I have a very urgent, very quick & very simple question to someone with SPSS in front of him/her, related to the ominous "spss.err" file. If you have a copy, would you kindly contact me by e-mail (just click here). I'll explain in my reply. Thanks a million!!!!! --Thanks for answering (talk) 07:19, 7 May 2010 (UTC) [edited by Thanks for answering (talk) 08:46, 7 May 2010 (UTC)]

Just to emphasize: You need zero computer or stats knowledge, just a computer with SPSS. Just want to know if it's there. Please help. --Thanks for answering (talk) 08:46, 7 May 2010 (UTC)

Generally refdesk questions are answered at refdesk rather than by email. You'll probably have better luck if you put your question here. You could also try usenet (comp.soft-sys.stat.spss). 69.228.170.24 (talk) 04:51, 8 May 2010 (UTC)

Discrete maths

                                                                  QUESTION    1

The armed forces of Ghana want an algorithm that can efficiently solve a particular decision problem T in the worst –case.Three algorithms are currently available .They are A,B and C with running times ,

= 
= 
= 

(i) Explain why B should not be in the list (ii) Which program ( A,B or C ) would you recommend to the armed forces .Justify your answer.

                                                                   QUESTION 2

The population at time N U of two nations Messi and Xavi , are noted by the recurrence relation ,

X(n)= and M(n) = respectively where a , r ∈ N and g is defined on the positive integers .Show that X(n) = g(i) for some constant ∈ R . Hence or otherwise determine the value of if r=4 a=6 and g(n)= .

Find Big-oh expression for X(n) and M(n) . —Preceding unsigned comment added by 41.218.226.79 (talk) 15:32, 7 May 2010 (UTC)

Wikipedia is not a place for people to answer your badly copy and pasted homework for you, without you even showing any attempt at doing it yourself. --Fangz (talk) 15:40, 7 May 2010 (UTC)

Flows with equal time 1 maps

Let $\phi ^{t}$ and $\psi ^{t}$ be regular (say $C^{\infty }$) flows on a simply connected open region of $\mathbb {R} ^{2}$. Suppose that the time 1 maps $\phi ^{1}$ and $\psi ^{1}$ coincide everywere. Can we infere that $\phi ^{t}\equiv \psi ^{t}$ for any t?

(Notice that the answer is no when the domain is not simply connected.)

--Pokipsy76 (talk) 16:01, 7 May 2010 (UTC)

Of course we can't. Think of 1-periodic flows on R²: they all have φ¹(x)=x. Also, given any flow φ^t you can reparametrize time, that is, consider φ^σ(t) (the vector field correspondingly changes by some scalar factor). Take any σ:R→R such that σ(0)=0 and σ(1)=1: then the time 1 map remains the same. --pma 18:38, 7 May 2010 (UTC)

Ok, you are right, I was erroneously thinking that there was a problem in cnstructing a periodic flow in a simply connected domain but now I realize that there is a trivial example v(x,y)=(y,-x).--Pokipsy76 (talk) 21:29, 7 May 2010 (UTC)

I have still problems in understanding how you can reparametrize the time in such a way that the family of maps still behaves like a flow unless you use a linear transformation (but then the condition σ(0)=0 and σ(1)=1 would be satisfied only by the identity function) indeed we have φ^σ(t+s)=ψ^s+t=ψ^s(ψ^t)=φ^σ(s)(φ^σ(t))=φ^σ(t)+σ(s).--Pokipsy76 (talk) 21:51, 7 May 2010 (UTC)

Yes, you are right. I had in mind a σ also depending on x, but doesn't seems to work. --pma 09:08, 8 May 2010 (UTC)

Is it reasonable to think that my statement is true if we assume that the vector fields must be always different from 0? This idea is connected to my problem posted below.--Pokipsy76 (talk) 09:42, 8 May 2010 (UTC)

Yes because any closed orbit of the flow bounds an open set containing a zero of the field, because the topological degree of the field wrto 0 is non-zero. --pma 10:43, 8 May 2010 (UTC)

May I ask you what do you think about my problem here? Does it seem to you to be true and provable?--Pokipsy76 (talk) 15:15, 8 May 2010 (UTC)

I was wandering what is the connection between the case of a flow with the time 1 map equal to the identity and the case of two flows whose time 1 maps are equal to each other?--Pokipsy76 (talk) 08:23, 9 May 2010 (UTC)

My point is: if I have two vector fields v and w which are always positive why their difference v-w couldn't have a periodic orbit? The degree of v and w on this orbit is obviously 0 but why should it also be the case for the degree of their difference?--Pokipsy76 (talk) 15:12, 9 May 2010 (UTC)

The statistical r and P, in scientific reports. What do they and their various values tell?

Years ago I got a good grade at a college level "Introduction to probability"-course, but sadly I do no longer remember much of it.

While reading scientific journals, I often encounter statements like this:

"Rates of <something measurable> were inversely correlated with <some other measurable fact or quantity> (r = -0.84, P less than 0.01)."

I would like to know, and get a short explanation (summary) of:

1. What information do the r and P values give?
2. What do their various value-levels tell?
3. And (if applicable) where are the threshold value-levels?

Could you please help me? 89.8.27.189 (talk) 16:23, 7 May 2010 (UTC)

The r-value is a measure of correlation and ranges from -1 to 1. When it's close to -1 as in your example, the two variables would move in opposite directions. The p-value, in this case, is the probability of obtaining the data (or sample) assuming that the variables are uncorrelated. Since the probability is so small we can deduce that the variables are likely not uncorrelated.

(I'm assuming that the null hypothesis is that the variables are uncorrelated - I suppose it could be something else but that's not likely. Also, since the p-value < 1%, we say that we can reject the null hypothesis at a 99% confidence level.) Zain Ebrahim (talk) 17:06, 7 May 2010 (UTC)

Thank you!  :-) 89.8.27.189 (talk) 17:29, 7 May 2010 (UTC)

Close flows => close vector fields?

Suppose I have two flows $\phi ^{t}$ and $\psi ^{t}$ and let $v_{\phi }$ and $v_{\psi }$ be their vector fields. Suppose that

• $|\phi ^{1}-\psi ^{1}|_{C^{k}}<\epsilon$ (notice that I have the relation only for the time 1)
• $|v_{\phi }|_{C^{k}}>\delta$, $|v_{\psi }|_{C^{k}}>\delta$

then I would say that $|v_{\phi }-v_{\psi }|<{\frac {\epsilon }{\delta }}$.

While trying to prove this statement it seems that the only available relation between the vector field and its time 1 map is the following fixed point relation

$v_{\phi }(\phi ^{1}(x))-D\phi ^{1}(x)v_{\phi }(x)\equiv 0$

and this is not an easy tool to build a proof because the hypothetically possible fixed points are more than one and because to estimate the distance between fixed points of two maps which are close I would need the implicit function theorem but here the theorem must be applyed in a functional space. Any advice?--Pokipsy76 (talk) 18:07, 7 May 2010 (UTC)

Finding joint distribution from two marginal distributions

Is this possible?

I have, say, a random variable $\theta \sim {\mbox{N}}(\mu ,\sigma ^{2})$ and I derive two random variables $S=\sin(\theta )$ and $C=\cos(\theta )$, so I have pdfs for S and C. I then want to find the distribution (or density) of $D=(mS+nC)^{2}$ but this requires me to know what the joint distribution (or joint density) function is. They aren't independent as they're dependent on a common variable.

I think I'm missing something blindingly simple but it's not getting into my head.

Also, I'm unfortunately aware that it will end up fairly messy. 155.198.201.36 (talk) 21:15, 7 May 2010 (UTC)

• Probability density function#Dependent_variables_and_change_of_variables

69.228.170.24 (talk) 09:25, 8 May 2010 (UTC)

May 8

sin(sin t)?

What is the solution to t = sin(sin t)? In other words, how can I find all points common to the helices C_1 and C_2 where C_1(t) = (cos t, sin t, t), t is real; and C_2(s) = (cos s, s, sin s), s is real? 60.240.101.246 (talk) 03:23, 8 May 2010 (UTC)

t=0 is the obvious one... 69.228.170.24 (talk) 04:53, 8 May 2010 (UTC)

...and t=0 is the only solution (assuming t is in radians), because

${\frac {d}{dt}}(t-\sin(\sin(t)))=1-\cos(t)\cos(\sin(t))$

which is 0 at t=0, and

${\frac {d^{2}}{dt^{2}}}(t-\sin(\sin(t)))=\sin(t)\cos(\sin(t))+\cos ^{2}(t)\sin(\sin(t))$

which is also 0 when t=0, but positive away from t=0, so slope of t-sin(sin(t)) increases as you move away from 0 in either direction. So helices only intersect at (1,0,0). Gandalf61 (talk) 09:26, 8 May 2010 (UTC)

(EC) And note that for t≠0 |sin(sin(t))|≤|sin(t)|<|t|, so there's no other solution.--84.221.69.102 (talk) 10:33, 8 May 2010 (UTC)

The armed force of Ghana ...

                                                                  QUESTION    1

The armed forces of Ghana want an algorithm that can efficiently solve a particular decision problem T in the worst –case.Three algorithms are currently available .They are A,B and C with running times , T_A (n)={█(4T_A (n-1) + Ѳ(2^n) , n>0@6 , n=0 )┤ T_B (n)={█(Ѳ(1) if 1≤n<3@2T_B (⌊n/3⌋) + Ѳ(T_A (n) ) if n≥3)┤ T_C (n)={█(Ѳ(1) if 1≤n≤3@2T(⌈n/3⌉ ) + Ѳ(n) if n≥3)┤ (i) Explain why B should not be in the list (ii) Which program ( A,B or C ) would you recommend to the armed forces .Justify your answer.

                                                                   QUESTION 2

The population at time N U {0} of two nations Messi and Xavi , are noted by the recurrence relation ,

X(n)={█(rX(n-1) + g(n) if n>0@a if n=0)┤ and M(n) ={█(3T(⌈n/3⌉ ) + n√(n+1) if n>1@2 if 0≤n≤1 )┤respectively where a , r ∈ N and g is defined on the positive integers .Show that X(n) = r^n a + ⋋∑_(i=1)^n▒r^(n-1) g(i) for some constant ⋋ ∈ R . Hence or otherwise determine the value of lim┬(n⟶∞)⁡〖(M(n))/(X(n))〗 if r=4 a=6 and g(n)=2^(n ).

Find Big-oh expression for X(n) and M(n) . —Preceding unsigned comment added by Waslimp (talk • contribs) 12:00, 8 May 2010 (UTC)

Please explain what aspect of these problems you are needing help with. How far have you got with your analysis? BTW I see a big black square between the { and the ( in X(n)={█(rX(n-1). What is it meant to be? -- SGBailey (talk) 14:31, 8 May 2010 (UTC)

This post is just a repetition of a "Discrete_maths" question above dated May 7 (maybe both could be removed) --pma 07:04, 9 May 2010 (UTC)

May 9

Best statistical method to compare sensitivity in 2 binary tests?

I need to compare 2 different tests on known cancer patients. Should I use both tests on all patients and use McNemara's/Liddell's/Kappa/Fisher's Exact test or group them and compare between the 2 groups using chi-square? Are there any differences in the reliability of the results? And how do I chose among the alternatives above? —Preceding unsigned comment added by Makischa (talk • contribs) 05:29, 9 May 2010 (UTC)

It's definitely preferable from a statistical perspective to perform both tests on all patients, provided it's practical, ethical and affordable. This maximises the precision with which you can measure the accuracy of each test separately, and also maximises the power of the comparison between them. Qwfp (talk) 07:29, 9 May 2010 (UTC)

Thank you for your answer. But how should I choose between all the different statistical methods? And how can I show on the results the advantages you mentioned? (talk) 10:03, 9 May 2010 (UTC)

Markov chain on an n-cycle

Hi all, I was hoping you could help me with this.

We construct a Markov chain on an n-gon by joining adjacent vertices - our state space being {0, 1,... N-1} and our transition probabilities are given by P(i,j)=1/2 if j=i±1, 0 otherwise - i.e. we move from vertex to vertex in the obvious way, like 'walking around a fence'. Starting from (say) 0, how would one go about finding the probability distribution of the very last vertex to be reached? Obviously it's going to be symmetric about N/2, but I'm not sure how to go about finding the probability that each vertex is the last to be reached given that this can happen in a vast number of ways.

I've calculated the invariant distribution fairly trivially - the valency of each vertex is 2, so the invariant distribution is h=(1/N,1/N,...,1/N) satisfying hP=h, and I'm aware the long-term probability of being found in any given vertex tends to h_i=1/N, but that doesn't really seem to help me. Any suggestions?

Thanks a lot, 82.6.96.22 (talk) 13:11, 9 May 2010 (UTC)

The probability is 1/(N+1), independent of which vertex you want to be last. This is fairly easy to see: it doesn't matter what the chain does until it moves adjacent to the chosen vertex for the first time, and once that's happened it doesn't matter which vertex you chose. Algebraist 14:43, 9 May 2010 (UTC)

Can you clarify the question? Algebraist's answer above makes no sense to me, which means that at least one of us has completely misunderstood it. I thought you were talking about k-step transition probabilities $p_{0\to i}^{(k)}$ for some unspecified k. Finding these for any specific k and N is trivial (for example, for $N=5,\ k=3$ you have {0, 3/8, 1/8, 1/8, 3/8}), and presumably you are after some sort of closed form. -- Meni Rosenfeld (talk) 15:12, 9 May 2010 (UTC)

Sure - sorry if it was unclear. What I'm trying to do is say, starting at vertex '0', and continuing to move around your 'fence' with p=1/2 in each direction until you have reached every vertex at least once, what is the probability that the last vertex you reach is vertex 'k' (where k is arbitrary); i.e. how likely is it that you end up on any given vertex last, having visited every other vertex at least once (so the probability would be 0 for vertex 0 e.g., since you start on 0). 131.111.185.75 (talk) 15:37, 9 May 2010 (UTC)