Mathematics desk
< September 23	<< Aug \| September \| Oct >>	September 25 >

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.

September 24[edit]

Beta Distribution Selection[edit]

Hello, I went through the article on Beta distribution in Wikipedia. It says you need to have estimation of alpha and beta parameters for computing mean, variance etc for a beta distribution. But how to estimate it if the question is like this: 5,000 parts are produced in a day. 50% of time there are less than 6% defective, 25% of time there are 6% to 8% defective and 25% of time, there are more than 8% defective. How to select a beta distribution for the defects?--68.119.80.51 (talk) 01:32, 24 September 2008 (UTC)[reply]

This isn't really about estimation, in the statistician's sense of the word. I take it you mean the percent defective is the thing that has a Beta distribution. So you want the median of the distribution to be 0.06, since you said "50% of the time". And then you want the 75th percentile of the Beta distribution to be 0.08. You need to choose α and β so that F(0.06) = 0.5 and F(0.08) = 0.75, where F is the cumulative distribution function. Unfortunately, the cdf of the Beta distribution is somewhat messy, so I can't give details without spending more time on this. Michael Hardy (talk) 01:52, 24 September 2008 (UTC)[reply]

What is the mean of the distribution?--68.119.80.51 (talk) 10:29, 24 September 2008 (UTC)[reply]

OK, just doing this very crudely, plugging in numbers into a standard software package, I'm finding that if α = 4 and β = 60 (which means the mean is α/(α + β) = 4/(60 + 4) = 1/15 = 0.066666...., then F(0.06) is about 0.53 and F(0.08) is about 0.752, so that's not far from what you're looking for. The software requires one to put in α and β, rather than telling you what those have to be, so you just have to fiddle a bit more to get it accurate.

But let's apply some common sense: since the median of 0.06 is so close to the left end of the interval, you've obviously got to have β much bigger than α, and since it goes all the way up from 0.5 to 0.75 with a change from 0.06 to 0.08, a very short distance, you got to have the sum α + β fairly big. That gives you some idea where to start if you're just trying to do this numerically with software with these sorts of limitations. Michael Hardy (talk) 22:30, 26 September 2008 (UTC)[reply]

The 1-D Wave Equation (d'Alembert)[edit]

I am just beginning to learn about Partial Differential Equations and have been given a confusing problem.

I have been given a solution to the Wave equation $u(x,t)=3x^{2}-2cxt+3c^{2}t^{t}-sin(x)cos(ct)$

And the question is, find F(x) and G(x) such that $u(x,t)=F(x+ct)+G(x-ct)$

This is D'Alembert's method for finding a solution to the Wave Equation, but in the examples in my book, you do this when you have been given a set of initial conditions. I have no initial conditions but am supposed to find it anyway.

Well I tried to do it by substituting $v=x+ct$ and $z=x-ct$ , and then finding the partial derivative of u with respect to v, which gives $6v-8ct-cos(v-ct)cos(ct)$

Then integrate this with respect to v, and end up with $F(v)=F(x+ct)=3x^{2}-2cxt+9c^{2}t^{2}-sin(x+ct-ct)cos(ct)$ so if $u(x,t)=F(x+ct)+G(x-ct)$ , then $G(x-ct)=-6c^{2}t^{2}$ , but there's no x-ct in it.

If anyone knows what to do here I would very much appreciate any help. —Preceding unsigned comment added by Damian Eldridge (talk • contribs) 04:22, 24 September 2008 (UTC)[reply]

The wave equation is a red herring. Just substitute x=(v+z)/2 and t=(v-z)/2c in the expression for u, and simplify. Bo Jacoby (talk) 14:30, 24 September 2008 (UTC).[reply]

Ah! It's always so obvious when you know what to do. Thanks so much. —Preceding unsigned comment added by Damian Eldridge (talk • contribs) 22:48, 24 September 2008 (UTC)[reply]

Graph theory question-- order of magnitude of possible set-of-visited-points....[edit]

How would I go about tackling this.

I'm given a graph containing n locations and an associated adjacency matrix telling me which of the locations I have visited. I also start at location 0.

Suppose I define a set called my "passport" that has a list of every location I have visited. Order is not important-- visited location a and then location b is the same as going to b first and then a.

The question is: what is the total number of states my passport can take on?

Obviously, an upperbound on the number of total states is 2^n-- each n location can be in two states-- already visited or haven't visited.

But, the fact that not all points are adjacent imposes a substantial restriction. Suppose the only way to ever get to location Z is to have already visited location Y.

So, to give a concrete example. Suppose I have the graph

0 - 1 - 2 -3

this simple graph can have 4 different passports: {0}, {0,1}, {0,1,2} and {0,1,2,3}

Suppose instead I add a connection between location 0 and location 3

 0 - 1 - 2 -3
 |          |
 ------------

Now the passport can have 7 different states: {0}, {0,1} , {0,3}, {0,1,2}, {0,1,3},{0,2,3}, {0,1,2,3}

This is all well and good when n is small. I'm considering a case where n=242, so actually enumerating all the possibilities isn't going to work.

Any idea how I can tackle this?

Alecmconroy (talk) 06:55, 24 September 2008 (UTC)[reply]

So, for a given undirected graph, you want to know the number of connected subsets of nodes containing a given node there are? Sounds hard.... Eric. 131.215.159.210 (talk) 09:23, 24 September 2008 (UTC)[reply]

You are trying to count the number of connected subgraphs of your graph which contain a given node. In general this problem seems like it will be quite computationally difficult, but there may be useful features of your particular graph that simplify it (for example, if your graph is a tree, the solution is easy). It seems to me that cycles are what make things complicated as they give several ways to have visited the same node. Does your graph contain many cycles? Are they disjoint? Maelin (Talk | Contribs) 09:53, 24 September 2008 (UTC)[reply]

Following on to that there's a description in Aho and Ullman's book Algorithms of how to turn a directed graph into a tree of connected subgraphs where every vertex in a subgraph can get to any other. As Maelin says he tree part isn't bad, connected subgraphs just consisting of a simple cycle are the next easiest. Next easiest I think would be if it were all structured like the possible paths in a computer program without goto statements just ifs and loops. After that it just gets plain nasty as far as I can see. Dmcq (talk) 22:39, 24 September 2008 (UTC) Um perhaps I should just say loop instead of loops. Having a nested loop makes things much more difficult. Dmcq (talk) 22:46, 24 September 2008 (UTC)[reply]

If it's any help, it is equivalent (up to linear time slowdown) to the same problem, without the restriction that the connected subset must contain the specified node. I've been trying to prove that it is equivalent (up to polynomial time slowdown) to: given a set H of nodes, how many connected subsets of nodes contain all of H? -- i.e., allowing to specify more than one node. But I've had no luck with proving that equivalence. Eric. 131.215.159.187 (talk) 00:27, 25 September 2008 (UTC)[reply]

Sorry I should have said closed not connected for the directed graph to describe where every node can reach every other one. Wiki doesn't seem to mention it. Dmcq (talk)

I think there is some confusion, because my 00:27 comment was in reply to the OP and not to your 22:46 comment. (Also, the OP's example suggests that s/he means an undirected graph, anyhow.) Eric. 131.215.159.210 (talk) 08:49, 25 September 2008 (UTC)[reply]

I have found a proof of that equivalence that I said I had trouble proving. But it is very messy, and by itself doesn't solve the OP's question, so I won't bother typing it up. Eric. 131.215.159.210 (talk) 08:49, 25 September 2008 (UTC)[reply]

Integration by substitution[edit]

Is $y={\frac {1}{Be^{2x}-2xe^{2x}}}$ the integral of ${\frac {1}{y^{3}}}{\frac {dy}{dx}}+{\frac {1}{y^{2}}}=e^{2x}$ for some constant B? 92.3.238.32 (talk) 18:06, 24 September 2008 (UTC)[reply]

Why don't you plug your

y(x)

into the equation and just verify whether the function satisfies it or not? --CiaPan (talk) 18:37, 24 September 2008 (UTC)[reply]

It took me ages to determine the integral and plugging it back into the differential equation is hardly a trivial matter - this isn't a homework question where I have to answer true or false, it's an integration question that I've done and was hoping someone could check as I think I'm likely to go wrong somewhere in the differentiation. 92.3.238.32 (talk) 18:45, 24 September 2008 (UTC)[reply]

Integration can be hard, but differentiation is easy and that's all that's required for plugging it into the formula to see if it's right. --Tango (talk) 20:12, 24 September 2008 (UTC)[reply]

I won't deny this hasn't been the response I was hoping for since I tried quite hard to abide by the rules above. Anyway, irritatingly I seem to have gone wrong so it's back to the drawing board. 92.3.238.32 (talk) 20:29, 24 September 2008 (UTC)[reply]

Well, we could just tell you if you got it right or not, but that only helps you with this question. In an exam, say, you need to know how to check your answers. With maths, you rarely need an answer sheet, you can generally work out for yourself whether or not you've done it right. --Tango (talk) 23:38, 24 September 2008 (UTC)[reply]

Ok. Here we go.

y=(B-2x)^{-1}e^{-2x}=z^{-1}e^{-2x}\,

where

z=B-2x\,

Differentiate:

dy=d(z^{-1}e^{-2x})=d(z^{-1})e^{-2x}+z^{-1}d(e^{-2x})=-z^{-2}dze^{-2x}+z^{-1}e^{-2x}d(-2x)\,

=(-z^{-2}+z^{-1})e^{-2x}d(-2x)=2(z^{-2}-z^{-1})e^{-2x}dx\,

The differential expression

dy+(y-y^{3}e^{2x})dx=2(z^{-2}-z^{-1})e^{-2x}dx+(z^{-1}e^{-2x}-(z^{-1}e^{-2x})^{3}e^{2x})dx\,

=(2z^{-2}-2z^{-1}+z^{-1}-z^{-3}e^{-2x})e^{-2x}dx=(2z^{-2}-z^{-1}-z^{-3}e^{-2x})e^{-2x}dx\neq 0\,

Sorry, your expression for y is not a solution to the differential equation. Bo Jacoby (talk) 23:59, 24 September 2008 (UTC).[reply]

After some more hard work I think I have found my error in my original expression. I think that

y^{2}={\frac {1}{Be^{2x}-2xe^{2x}}}

is the integral of

{\frac {1}{y^{3}}}{\frac {dy}{dx}}+{\frac {1}{y^{2}}}=e^{2x}

. This time, I have tried twice to differentiate my expression in the hope of getting the original but with so many square roots, 'x's and 'e's flying around the place, it hasn't worked out, though I am fairly sure the fault lies in my differentiation. Could someone please check for me? If it's of interest to anyone, I integrated using the substitution

u={\frac {1}{y^{2}}}

Thanks 92.3.238.32 (talk) 17:51, 25 September 2008 (UTC)[reply]

Use the equations rather than the solutions in order to avoid square roots and fractions, just as I did above.

If

y^{2}=z^{-1}e^{-2x}\,

where

z=B-2x\,

then

ydy=(z^{-2}-z^{-1})e^{-2x}dx\,

Multiply the differential expression with y to get

y(dy+(y-y^{3}e^{2x})dx)=ydy+(y^{2}-y^{4}e^{2x})dx\,=(z^{-2}-z^{-1})e^{-2x}dx+(z^{-1}e^{-2x}-z^{-2}e^{-4x}e^{2x})dx\,

=(z^{-2}-z^{-1}+z^{-1}-z^{-2})e^{-2x}dx=0\,

Congratulations, you solved it. Bo Jacoby (talk) 18:37, 25 September 2008 (UTC).[reply]

Cheers Bo Jacoby, really appreciate! 92.3.238.32 (talk) 19:40, 25 September 2008 (UTC)[reply]

re-encrypting an encrypted file[edit]

Truecrypt claims that it can encrypt (some) files so that it "appears to consist of nothing more than random data (it does not contain any kind of "signature")". If such a file was re-encrypted with a different key or even a different method:

how would a cracker detect "success"?

If one were to re-encrypt an encrypted file:

if a cracker knew it, could both decryptions be accomplished in parallel?
is there a notion of "orthogonality" between keys? That is, given a key, can a dissimilar key be computed without sacrificing the first? Or two same-strength keys good enough?
given two orthogonal keys with the same strength, is a doubly-encrypted file more or less secure than if it were encrypted with a 2×-strength key? —Preceding unsigned comment added by Saintrain (talk • contribs) 20:38, 24 September 2008

The details will depend on the algorithms involved (of which I know nothing), but broadly speaking, if it would be useful to encrypt data twice, then the encryption algorithm should be written to do that already. So if you're using a good encryption algorithm, encrypting twice will be useless. Algebraist 20:49, 24 September 2008 (UTC)[reply]

Encrypting twice with two different algorithms could be useful, though. Modern encryption algorithms are so good, however, that there is really no point - the gain would be minimal (it talking a billion years to crack instead of a million isn't really any better). --Tango (talk) 21:21, 24 September 2008 (UTC)[reply]

Essentially all password-protected file formats have some way of verifying the password so that they can warn you when you mistype it instead of silently decrypting the file to gibberish. TrueCrypt containers are indistinguishable from random bits if you don't know the passphrase, but if you do know the passphrase then (by design) you can tell it's the right passphrase even if the files inside the container are themselves encrypted with keys you don't know. So putting a TrueCrypt container inside another one only doubles the attacker's work; they can break the outer container and then the inner one.

In principle, though, you can double-encrypt a file with no authentication information in the outer layer, so that the only way to check that you've got the right key for the outer layer is to crack the inner layer too. TrueCrypt supports some chained cipher modes like this. I don't think this ever gets you x+y-bit security, though. At a minimum it's vulnerable to a meet-in-the-middle attack (which is not very practical—but then you have to be pretty paranoid to use chained ciphers in the first place). I think there are even cases where the combination of two ciphers is weaker than either individual cipher, though I can't remember any examples.

I don't understand your other two questions. Can you explain what you mean by "dissimilar" and "sacrificing"? -- BenRG (talk) 03:18, 25 September 2008 (UTC)[reply]

I read the meet-in-the-middle attack is for finding keys given prior knowledge of a plaintext and its doubly-encrypted ciphertext. Then the next time the cracker is presented with a doubly-encrypted file, it's a simple matter to decrypt, yes?

If a plaintext file is encrypted once then I expect that it's pretty simple to tell, after some kind of search for keys, when you have found the right key. But if the inner, encrypted file is unrecognizable how does the cracker know the the outer layer has been cracked?

As to the other questions (and it's not paranoia; I wish I was as catlike in my agility as curiosity) given any 2 keys, and in the sense that orthogonal vectors do not share any components - so zero "similarity", can two keys be "orthogonal"? Is there a conceptual "dissimilarity" between two equal-strength keys? So, if the cracker discovered one key, would "orthogonality" help or hinder guessing the second? Saintrain (talk) 14:27, 25 September 2008 (UTC)[reply]

The meet-in-the-middle attack requires some known plaintext, but you'd be surprised how often that's available. Once the keys have been worked out, depending on the details of the algorithm, it might be possible to immediately decrypt another file that was encrypted with the same keys/password.

Again, I think all encrypted file formats found in the wild have some way of verifying that you've got the right password. In the case of TrueCrypt, the first thing you do when mounting a volume is decrypt the 512-byte header using a key derived from the passphrase. The format of the header is shown here. As you can see, there are lots of things you can check: a four-byte signature "TRUE", two CRCs, 124 bytes which are always zero, etc. The chance that you'd get something resembling a TrueCrypt header using the wrong password are negligibly small. Even if that weren't the case, TrueCrypt volumes contain a whole file system and the file system has lots of identifying information of its own, even if the files don't.

There is something called a related-key attack to which I guess some ciphers are vulnerable. But good ciphers are not supposed to be vulnerable to that; there shouldn't be any exploitable similarity in the behavior with any two different keys. So there's no concept of orthogonality of keys, or, if you prefer, all keys are "orthogonal". -- BenRG (talk) 12:31, 26 September 2008 (UTC)[reply]

Thanks. Appreciate the follow-up. Saintrain (talk) 14:44, 26 September 2008 (UTC)[reply]