Wikipedia:Reference desk/Archives/Mathematics/2011 June 28

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.

June 28

quick math question

Hi, I'm in the middle of doing a math problem and I was wondering if it would be okay to take the equation (x^2-9)^2-100x^2 and square root it all into x^2-10x-9? Thanks — Preceding unsigned comment added by 174.5.131.59 (talk) 01:32, 28 June 2011 (UTC)

If you want to solve (x² –9)² – 100x² = 0 then you can rewrite it as (x² –9)² = 100x². Both sides are greater than, or equal to, zero; that means we can take the square root without worrying about complex numbers. Taking the square root gives x² – 9 = ±10x. So you missed the ±. You should be able to solve from here. Remember that, counted with multiplicities, you should get four solutions for x. Solve x² – 9 = –10x for x (giving two solutions for x), and then solve x² – 9 = 10x for x (giving another two solutions for x).— Fly by Night (talk) 01:41, 28 June 2011 (UTC)

ohh that makes sense. Instead I fooled around with difference of squares and got (x^2-10x-9)(x^2+10x-9) but that looks like the same answer I got. Sorry for sounding dumb, but why does the square root need ± again? — Preceding unsigned comment added by 174.5.131.59 (talk) 02:10, 28 June 2011 (UTC)

If you multiply five by five you get 25. If you multiply minus five by minus five you again get 25. Symbolically, 5 × 5 = 25 and (–5) × (–5) = 25. That means that the answer to x² = 25 is either plus five or minus five, i.e. x = ±5. The difference of squares method is equally valid. Nice work. — Fly by Night (talk) 02:27, 28 June 2011 (UTC)

thanks that makes sense! — Preceding unsigned comment added by 174.5.131.59 (talk) 03:08, 28 June 2011 (UTC)

Widely accepted measure/metric of order

Is there a widely accepted measure or metric of order in a set? For example, 3127312631233128312 has a frequently recurring sequence 312, so there is a clear order throughout most of the data. However, 123456 has no order because each item occurs once. If that doesn't explain what I mean by "order", please ask for clarification. My idea is to use file compression which encodes frequent sequences of items in a series with a single code. Sets with high order will compress much further than sequences with no order. However, this is a short section in a mathematics paper, so I am hesitant to use something too computerish. -- kainaw™ 15:50, 28 June 2011 (UTC)

Not a direct answer, but I don't see the compression working very well, unless you have longer repeated sequences than 3 digits and more total digits. That's because the overhead involved in defining the repeating pattern(s) and assigning each a code (which you must assure doesn't exist in the rest of the digits) might actually make such a compression method increase the size. Then there's the question, with disk space so cheap these days, of whether the CPU time required to compress and decompress, and the additional complexity created, would be worth such a small space savings. StuRat (talk) 16:02, 28 June 2011 (UTC)

The sequences being used in this paper have around 200 million events. So, the overhead will be dwarfed by the size of the data sequence. I'm merely writing a section that is supposed to prove that the data sequences do have order. Given one event in the sequence, there is a probability that another specific event will show up later. An example in another section of the paper is: "Given that book 4 of the Harry Potter series is in a sequence of books purchased by a user of Amazon, there is a high probability that book 5 will occur later." -- kainaw™ 16:14, 28 June 2011 (UTC)

What you're talking about sounds like Entropy (information theory). I don't know much about information theory, but the compression you're talking about is maybe a Dictionary coder. Rckrone (talk) 16:18, 28 June 2011 (UTC)

I know Shannon entropy very well. I can't believe that I didn't make the correlation. I will define their term "order" as an absence of entropy and then I'm set. Thanks. -- kainaw™ 16:22, 28 June 2011 (UTC)

Entropy is a property of a random process, not of a specific sequence. Maybe what you're looking for is Kolmogorov complexity. -- Meni Rosenfeld (talk) 18:28, 28 June 2011 (UTC)

Entropy can be associated with a specific sequence, but it's not a property of the sequence alone. It's a property of how much information the sequence contains that an opponent does not have. So if you have say 1000000 bits of disk-time-access behavior that's fairly but not completely predictable, so that it contains 150 bits of entropy, you can use that together with a hash function to get a 128-bit key with confidence that the method of generation gives an opponent no advantage over trying all keys. However, if half the collection of access times were to be made public somehow, then you would only have 75 bits of entropy available (under the simplest assumptions), even though the collection itself has not changed. --Trovatore (talk) 00:06, 30 June 2011 (UTC)

Thanks. I vaguely remember that from undergrad networking algorithms class. I'm surprised it doesn't show up more in algorithms. Seeing as I'm already basing my little section on works by Levenshtein and Minkowski, why not toss in another Russian! -- kainaw™ 18:52, 28 June 2011 (UTC)

If anyone is interested, studying Kologorov complexity turns up that the standard practice is to perform sequence compression by replacing subsequences and then measuring the change in sequence length. The greater the change, the less entropy the sequence has. -- kainaw™ 00:13, 29 June 2011 (UTC)

Take your sequence and compress it with gzip or bzip2. Then take a random sequence of A, C, G, T (or whatever your alphabet is) of the same length as your original, and compress that. If your sequence compresses shorter than the random sequence, then it has structure. HTH, Robinh (talk) 20:02, 29 June 2011 (UTC)

That is what I'm doing, but I can't use bzip2 directly. I have to rewrite it to use values larger than 255 because my alphabet is a set of integers from 1 to 999,999,999. I already wrote Burrows-Wheeler transform to handle large integers. Now, I'm finishing the move-to-front transform. Then, I will write Huffman encoding and I'll have a bzip2 clone for large integers. -- kainaw™ 19:42, 4 July 2011 (UTC)