Wikipedia:Reference desk/Archives/Mathematics/2010 July 8

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.

July 8

basic probability

I have two normally-distributed random variables X and Y. X has mean 100 and s.d. 10. Y has mean 105 and s.d. 20. Is there a clean way to find the Prob[Y < X]? I just see a real messy integral. Thanks. 71.141.88.179 (talk) 01:28, 8 July 2010 (UTC)

I assume they're independent, otherwise, I don't know. But, an easy way to do it is to consider the random variable Y - X. Perhaps you have seen that a linear combination of independent normals is normal. So, Y - X would be normal and the mean would be the mean of Y minus the mean of X and the variance would be Variance Y + Variance X. Then, you just need to do one integral from -infinity to 0 of that one random variable. StatisticsMan (talk) 01:43, 8 July 2010 (UTC)

Oh yes, of course. Then I just use an approximation to see where the cdf crosses zero. I just got discouraged when I thought of blasting it out directly. Thanks. 71.141.88.179 (talk) 03:23, 8 July 2010 (UTC)

No. You need to subtract the variables, which is completely different from subtracting the cdfs. You get a new random variable $Z=Y-X$ which is distributed normally with mean 5 and s.d. ${\sqrt {500}}$. $\mathrm {Pr} (Y<X)=\mathrm {Pr} (Z<0)$ so you need to use the standard techniques to find the probability that a normal variable is less than some value.

Again, all of this is under the unstated assumption that X and Y are independent. -- Meni Rosenfeld (talk) 04:58, 8 July 2010 (UTC)

Yes, independent variables. Yes I understood about subtracting the variables. Thanks. 71.141.88.179 (talk) 06:17, 8 July 2010 (UTC)

I like the notation (105±20)−(100±10) = (105−100)±√(20²+10²) = 5±22.4. This is < 0 when (5±22.4)/22.4 < 0 or ±1 < −0.224. Here ±1 has mean 0 and s.d. 1. Bo Jacoby (talk) 07:51, 8 July 2010 (UTC).

Ah, I get it now. I thought you meant something else, sorry. -- Meni Rosenfeld (talk) 08:09, 8 July 2010 (UTC)

If you misunderstood I might improve my communication? Bo Jacoby (talk) 09:37, 8 July 2010 (UTC).

I was responding to the OP, as can be understood from my level of Indentation. -- Meni Rosenfeld (talk) 13:37, 8 July 2010 (UTC)

No one else has tried being explicit yet, so I will. If X and Y are independent then

$X-Y\sim N(100-105,10^{2}+20^{2})=N(-5,500).$

So the mean of X − Y is −5 and the SD is √500 = 10√5 = 22.36. So you want the probability that that random variable is less than 0. Michael Hardy (talk) 19:57, 8 July 2010 (UTC)

....oh. I see that Meni Rosenfeld said that already. Michael Hardy (talk) 19:58, 8 July 2010 (UTC)

And, I, as the first responder, said that, with the exception that I didn't fill in the numbers, which is pretty trivial. StatisticsMan (talk) 00:42, 9 July 2010 (UTC)

Kernel and Range of an Operator

So an exercise regarding operators on a Banach space says to find the kernel and range of the linear operator

$K:C([0,1])\rightarrow C([0,1])$

defined by

$K(f(x))=\int _{0}^{1}\sin(\pi (x-y))f(y)dy.$

My problem is that the solution the teacher wrote up says to just split the integral (using the sine subtraction formula) to

$\sin(\pi x)\int _{0}^{1}\cos(\pi y)f(y)dy-\cos(\pi x)\int _{0}^{1}\sin(\pi y)f(y)dy.$

I have no problem with this. This makes sense and I agree. Then he says that looking at this you know that the range is the span (linear combination) of $\sin(\pi x)$ and $\cos(\pi x)$. This is also good. But then he says that the kernel contains all functions which satisfy

$\int _{0}^{1}\cos(\pi y)f(y)dy=0$ and $\int _{0}^{1}\sin(\pi y)f(y)dy=0$

simultaneously. I have two issues with this. First, how do we know that this is all that is in the kernel. What if we have a function where

$\sin(\pi x)\int _{0}^{1}\cos(\pi y)f(y)dy=\cos(\pi x)\int _{0}^{1}\sin(\pi y)f(y)dy$

and second, can we do a little better and figure out a better description of such functions. To me this seems like, "all functions with Kf=0 are functions in the kernel of K". Well duh, doesn't seem very enlightening to me. Thanks!-Looking for Wisdom and Insight! (talk) 05:25, 8 July 2010 (UTC)

The kernel of K is functions of x that are mapped to the zero function of x. K(f)(x) = a sin(πx) + b cos(πx) where a and b are constants. Notice that $a=\int _{0}^{1}\cos(\pi y)f(y)dy$ and $b=\int _{0}^{1}\sin(\pi y)f(y)dy$ don't depend on x. For K(f)(x) to be identically zero for all x, we need both a=0 and b=0 since sin(πx) and cos(πx) are linearly independent. Rckrone (talk) 07:54, 8 July 2010 (UTC)

Quoting:

What if we have a function where

$\sin(\pi x)\int _{0}^{1}\cos(\pi y)f(y)dy=\cos(\pi x)\int _{0}^{1}\sin(\pi y)f(y)dy$

That doesn't happen unless both integrals are zero. The two integrals DO NOT depend on x, and the identity needs to be construed as holding for ALL values of x. Michael Hardy (talk) 19:19, 10 July 2010 (UTC)

Non-Hamiltonian k-critical graph

Does anyone know of an example of a k-critical graph (that is, a graph with chromatic number k such that all proper subgraphs have chromatic number less than k) that is not Hamiltonian? I found a reference in Bollobás (Extremal Graph Theory, Theorem 2.1) to a theorem of Dirac: "If G is k-critical then either G is Hamiltonian or its circumference is at least 2k − 2." Reading between the lines, this would seem to imply that some non-Hamiltonian k-critical graphs are known; otherwise I would expect to see that theorem followed by at least a conjecture that all k-critical graphs are Hamiltonian. —Bkell (talk) 07:21, 8 July 2010 (UTC)

Rational numbers with integer sums

Let (x,y,z) be an ordered triple of positive rational numbers such that x + 1/y, y + 1/z, and z + 1/x are all integers. Find all possible ordered pairs (x,y,z).

The only ones I've been able to find are (1,1,1), (1/2, 2/3, 3), and (1/3, 3/2, 2) (as well as their cyclic permutations), but I haven't been able to prove that there are no more. --138.110.206.101 (talk) 12:22, 8 July 2010 (UTC)

There is also (1, 1/2, 2) and its cyclic permutations, but then there are no more. Is this a homework? Here is an outline. Write x = a/u, y = b/v, z = c/w, with gcd(a,u) = gcd(b,v) = gcd(c,w) = 1. Since x + 1/y is an integer, ub divides ab + uv, and using coprimeness of u and b, this gives easily u = b. Symmetrically, v = c and w = a, i.e., x = a/b, y = b/c, z = c/a, and a, b, c are pairwise coprime. The assumption on x + 1/y etc. being integers means that a + b + c is divisible by lcm(a,b,c). Assuming WLOG c ≥ a, b, we have a + b + c < 3c (unless a = b = c = 1 = x = y = z), thus lcm(a,b,c) is c or 2c, which implies that a and b divide 2. This, together with c | a + b, gives finitely many choices which can be checked to give the triples written above.—Emil J. 13:04, 8 July 2010 (UTC)

(ec). Let a=x+1/y, b=y+1/z, and c=z+1/x. Solve for x.

x=a-1/y, y=b-1/z, z=c-1/x. 
x=a-1/(b-1/(c-1/x))
x(b-1/(c-1/x))=a(b-1/(c-1/x))-1
bx-x/(c-1/x)=ab-a/(c-1/x)-1
bx(c-1/x)-x=ab(c-1/x)-a-(c-1/x)
bcx-b-x=abc-ab/x-a-c+1/x
bcxx-bx-xx=abcx-ab-ax-cx+1
(bc-1)xx+(a+c-b-abc)x+ab-1=0

y,z also satisfy quadratic equations.

(ca-1)yy+(b+a-c-abc)y+bc-1=0
(ab-1)zz+(c+b-a-abc)z+ca-1=0

Then the problem is reduced to find integers a,b,c such that the quadratic equations have rational solutions. Bo Jacoby (talk) 13:55, 8 July 2010 (UTC).

probability

we have a scratch off card with 25 squares and 5 have pots of gold underneath. If you scratch off exactly 5 squares revealing 5 pots of gold you win. what is the probability of winning? —Preceding unsigned comment added by 129.120.185.7 (talk) 15:35, 8 July 2010 (UTC)

Well, the chance of hitting a pot of gold on the first scratch is 5/25. If you do that successfully, then the chance of hitting a pot of gold on the second scratch is 4/24 since there are 4 pots left under 24 possible squares. So the chance of hitting on the first 2 is (5/25)*(4/24). And then continue that way down the line for 3, 4 and 5. Rckrone (talk) 16:04, 8 July 2010 (UTC)

See binomial coefficient. The probability of winning is $\scriptstyle {\frac {1}{\binom {25}{5}}}$ = 0.0000188218. Bo Jacoby (talk) 16:39, 8 July 2010 (UTC).

Probabilistic proof of the squared triangular number identity.

Hi all. I'm wondering how to put as simple as possible the following probabilistic proof of the famous squared triangular number identity,

$\sum _{k=1}^{n}k^{3}=\left(\sum _{k=1}^{n}k\right)^{2}$,

or also, if there is a ready reference (in which case I would add it to the other quoted proofs in the wiki article). The idea is normalize over $n^{4}$ and see the LHS and RHS as probabilities of two suitable equiprobable events. Precisely: choose randomly 4 numbers $\scriptstyle X,\ Y,\ Z,\ W$ between $1$ and $n$, uniformly and indipendently. How would you justify in the quickest way that $\scriptstyle \{\max(X,Y,Z)\leq W\}$ has the same probability than $\scriptstyle \{X\leq Y\}\cap \{Z\leq W\}$? As a first step, one could start noticing that the first event is the same as $\scriptstyle \{\max(X,Y)\leq \max(Z,W)\}\cap \{Z\leq W\}$... Thank you for your suggestions.--pma 18:42, 8 July 2010 (UTC)

That first step seems kind of problematic since the distribution of max(Z,W) is not independent of whether Z ≤ W because of the asymmetry involved in including the cases where Z = W, and so {X ≤ Y} does not have the same probability as {max(X,Y) ≤ max(Z,W)}. Rckrone (talk) 05:48, 10 July 2010 (UTC)

yes, of course $\scriptstyle \{\max(X,Y)\leq \max(Z,W)\}$ and $\scriptstyle \{Z\leq W\}$ are not independent, as one already sees with $n=2$. Anyway, the proof I see for the original statement is a bit too close to a reformulation of other geometrical proofs, still I think there is a more genuinely probabilistic one. --pma 08:10, 11 July 2010 (UTC)

Tweaked Konigsberg

The bridges of Konigsberg

Hey all. I'm afraid I'd have no idea how to describe the problem put in front on in a standard way, but then, you lot are better than google anyways :)

It's like the Bridges of Konigsberg problem - so I'm guessing topologists are the people to ask - except with a load more islanda and bridges (100 islands 250 bridges to be precise), plus two restrictions:

• Instead of being focused around the bridges, it is focused around the islands: you can visit each only once.
• Instead of wanting an answer of "it's possible" or "it's impossible" (it's definitely impossible to visit every island - some islands have only one bridge, some have none), we want the route that visits the most islands before bring forced to revisit an island.

Are there any algorithms / methods that would help with this? Thanks in advance, - Jarry1250 ^{[Humorous? Discuss.]} 20:53, 8 July 2010 (UTC)

This is the longest path problem. Algebraist 20:57, 8 July 2010 (UTC)

With distance 1 between each point? Also, I am not given the starting point or ending point, though I guess I could arbitrarily choose them. - Jarry1250 ^{[Humorous? Discuss.]} 21:31, 8 July 2010 (UTC)