Support NeoGAF

[Stumpokapow]

Brain fart. I have some data. One of my observable covariates is a mixture distribution (a mix of two univariate normal random variables). I have both theoretical reason to believe this is the case and observational evidence: the density function of the covariate looks like a the distribution of heights in the population. There's a mode, and then slightly to the right of the mode, there's another little peak.

In other words:
Z = wX + (1-w)Y
where w = 1 with probability p, 0 with probability 1-p
X ~ Norm(mu_1, sd_1)
Y ~ Norm(mu_2, sd_2)
Z is the observed covariate
mu_1, mu_2, sd_1, sd_2, w, and p are unknown
I want to jointly estimate mu_1, mu_2, sd_1, sd_2, and p given the dataset Z, and then classify each observation as w=1 or w=0.
I know I can do the last step with various Bayesian decision things, like MAP or whatever. But it's the first part.

This is neither homework nor publishable research, it's just me fiddling around with something.

Edit: I think I might want E-M.

Edit: I definitely want Expectation-Maximization. Thanks.

 

[VegiHam]

If I'm looking at partial derivatives of a multi-variable function where I'm told z=f(x,y); and I'm given it in the form F(x,y,z)=0, is there any particular reason I can't separate the variables to get back to z=f(x,y) and then differentiate both sides? Doing that gets me very quickly to integer values of dz/dx and dz/dy. But I've been asked to find their value given certain values of x y and z; and my solution gets the same answer regardless of the different inputs; so I think I'm expected to not seperate the variables and to solve it implicitly. I'm really hoping I've just forgotten a rule that means my thing isn't allowed...

 

[boviscopophobic]

If I'm looking at partial derivatives of a multi-variable function where I'm told z=f(x,y); and I'm given it in the form F(x,y,z)=0, is there any particular reason I can't separate the variables to get back to z=f(x,y) and then differentiate both sides? Doing that gets me very quickly to integer values of dz/dx and dz/dy. But I've been asked to find their value given certain values of x y and z; and my solution gets the same answer regardless of the different inputs; so I think I'm expected to not seperate the variables and to solve it implicitly. I'm really hoping I've just forgotten a rule that means my thing isn't allowed...

The surface described by F(x,y,z) = 0 might not, in general, be describable by a relation of the form z = f(x,y). For instance, the unit sphere x^2 + y^2 + z^2 - 1= 0 needs to be decomposed into two hemispheres. Other than this potential issue, there isn't anything wrong with solving for z first -- and if you're in a situation where a decomposition into multiple "patches" is required, then you just have to be careful that you're using the right one at the right time. It's hard to be any more specific since you don't give details, but if you suspect your answer is wrong, the mistake probably isn't simply that you chose to solve for z.

 

[VegiHam]

The surface described by F(x,y,z) = 0 might not, in general, be describable by a relation of the form z = f(x,y). For instance, the unit sphere x^2 + y^2 + z^2 - 1= 0 needs to be decomposed into two hemispheres. Other than this potential issue, there isn't anything wrong with solving for z first -- and if you're in a situation where a decomposition into multiple "patches" is required, then you just have to be careful that you're using the right one at the right time. It's hard to be any more specific since you don't give details, but if you suspect your answer is wrong, the mistake probably isn't simply that you chose to solve for z.

Thanks for this insight; but I've just puzzled it out myself. I thought my answers were reached far to quickly because I used some trig tricks instead of going the long way we were shown. But when I did it the long way and got answers in the form dz/dx=f(z,y) and dz/dy=f(z,x); subbing in the values I've been given gives me back the same answers I had originally so I'm pretty confident in them. Thank you again for answering though!

 

[Consumer]

Quick question, can't seem to find it on Google...

Can you take the dot product of a 2D point and a 3D point?

EX: (5,2,1) [DOT] (1,3)

It's regarding a lesson in matrix multiplication.

 

[B2B50]

Quick question, can't seem to find it on Google...

Can you take the dot product of a 2D point and a 3D point?

EX: (5,2,1) [DOT] (1,3)

It's regarding a lesson in matrix multiplication.

Wouldn't you just assume that the last term in the 2d point is 0?

Its clearer if you write it out in terms of unit vectors.

(5i + 2j + 1k) * (1i + 3j + 0k) = 5*1 + 2*3 + 1*0 = 5+6 = 11

 

[Snow]

Quick question, can't seem to find it on Google...

Can you take the dot product of a 2D point and a 3D point?

EX: (5,2,1) [DOT] (1,3)

It's regarding a lesson in matrix multiplication.

Not as such, I think. I suppose you could do something like:

[a]
times [d e]
[c]

=

[ d*a e*a ]
[ d*b e*b ]
[ d*c e*c ]

Which is a matrix product between a 3x1 and a 1x2 matrix, but I'm not sure it fits the term 'dot product'.

 

[Consumer]

Perhaps more context might help. Looking back on class notes, we tried to multiply 2 matrices: matrix A and matrix C, and concluded that matrix AC exists but CA does not exist, presumably because of the dot product situation.

A=
[1] [2]
[3] [4]

C=
[5] [2] [1]
[-1] [0] [-3]

Matrix AC=
[3] [2] [-5]
[11] [6] [-9]

But solving for matrix CA brings us to the aforementioned dot product, which according the prof.'s notes, doesn't seem to be valid. So is it true that in this situation, that we cannot take the dot product?

 

[B2B50]

Perhaps more context might help. Looking back on class notes, we tried to multiply 2 matrices: matrix A and matrix C, and concluded that matrix AC exists but CA does not exist, presumably because of the dot product situation.

A=
[1] [2]
[3] [4]

C=
[5] [2] [1]
[-1] [0] [-3]

Matrix AC=
[3] [2] [-5]
[11] [6] [-9]

But solving for matrix CA brings us to the aforementioned dot product, which according the prof.'s notes, doesn't seem to be valid. So is it true that in this situation, that we cannot take the dot product?

Yeah, CA is not valid due to the dimensions not matching. Generally for matrix multiplication you have an n x m matrix multiplied with an m x p. For AC this is satisfied, but not for CA.

Spoiler

Someone please correct me if im wrong, matrices aren't my strongest suit.

 

[Consumer]

Yeah, CA is not valid due to the dimensions not matching. Generally for matrix multiplication you have an n x m matrix multiplied with an m x p. For AC this is satisfied, but not for CA.

Spoiler

Someone please correct me if im wrong, matrices aren't my strongest suit.

Ah yes, turns out my notes explain the rule a few pages later (why not before this question? Who knows).

For those curious, to make matrix product AB, A must be [m x n] and B must be [n x p] so that AB will be [m x p].

As in, [number of rows x number of columns].

 

[oreomunsta]

Yeah, CA is not valid due to the dimensions not matching. Generally for matrix multiplication you have an n x m matrix multiplied with an m x p. For AC this is satisfied, but not for CA.

Spoiler

Someone please correct me if im wrong, matrices aren't my strongest suit.

You're correct for matrix basics at first, you get taught that two matrices can only be multiplied if the number of columns of the first equals the number of rows of the second.

In quantum mechanics, you can multiply an n x 1 vector and a 1 x n vector and end up with an n x n outer product, but that's probably out of the scope of this problem

 

[B2B50]

You're correct for matrix basics at first, you get taught that two matrices can only be multiplied if the number of columns of the first equals the number of rows of the second.

In quantum mechanics, you can multiply an n x 1 vector and a 1 x n vector and end up with an n x n outer product, but that's probably out of the scope of this problem

Considering I had an exam in quantum mechanics on monday, I feel kinda stupid for not thinking about that, but yes, you are right.

 

[VegiHam]

So I've been asked to show that a function is continuous at a point with the whole epsilon delta stuff. But I've been told to 'start by showing |f(x,y)-f(4,1)| is less than 2|x-4|+8|y-1| on the corners of a given square'. I don't really get how to prove continuity anyway, but I especially don't get how showing the extra thing is the first step to doing so. Any hints or ideas?

 

[Therion]

So I've been asked to show that a function is continuous at a point with the whole epsilon delta stuff. But I've been told to 'start by showing |f(x,y)-f(4,1)| is less than 2|x-4|+8|y-1| on the corners of a given square'. I don't really get how to prove continuity anyway, but I especially don't get how showing the extra thing is the first step to doing so. Any hints or ideas?

It's hard to say for sure without knowing the full context of the problem, but a proof of continuity at the point (x,y)=(4,1) will involve showing that for e>0 there exists some domain around (4,1) such that |f(x,y)-f(4,1)|<e. So if the given square was, say, the one with opposite corners (4-e, 1-e) and (4+e,1+e), then |x-4|<e and |y-1|<e for all (x,y) inside the square. So if you showed that the given inequality held throughout the square, you would have |f(x,y)-f(4,1)|<10e, which should go a long way toward completing the proof.

 

[VegiHam]

It's hard to say for sure without knowing the full context of the problem, but a proof of continuity at the point (x,y)=(4,1) will involve showing that for e>0 there exists some domain around (4,1) such that |f(x,y)-f(4,1)|<e. So if the given square was, say, the one with opposite corners (4-e, 1-e) and (4+e,1+e), then |x-4|<e and |y-1|<e for all (x,y) inside the square. So if you showed that the given inequality held throughout the square, you would have |f(x,y)-f(4,1)|<10e, which should go a long way toward completing the proof.

I think I get the idea behind what I'm supposed to be doing; but I don't really know how to start. f(x,y) = (5x + y)/(x - y); and I've shown that |f(x,y)-f(4,1)| < or = 2*|x-4|+8*|y-1| for (3,0), (3,2), (5,0) and (5,2). I don't get where the 2 and the 8 in the question came from and I don't really see how to use them to get to a proof with epsilons; but I have a vague sense that the square is a region with radius sqrt(2)? Or something? Urgh, I suck at multivariable calculus...

 

[oreomunsta]

Considering I had an exam in quantum mechanics on monday, I feel kinda stupid for not thinking about that, but yes, you are right.

I wouldnt stress too much about that. If I remember correctly, an outer product isn't a sound mathematical object; it's sort of a pseudo matrix

 

[kgtrep]

A few mates and I like to play Spot It! after sports. The deck comes with 55 cards, and each card has 8 symbols (50 symbols total).

Cool thing is, for any pair of two cards, there is exactly one symbol that they share. I found the explanation today: The Intersection Game

 

[kingwingin]

Can anyone tell my how to better show my work better? I feel like I'm being marked very harsh on work shown and don't understand what I'm doing wrong. When I ask all I get for a response is "refer to your notes"

 

[cpp_is_king]

Can anyone tell my how to better show my work better? I feel like I'm being marked very harsh on work shown and don't understand what I'm doing wrong. When I ask all I get for a response is "refer to your notes"

The thing you wrote down doesn't make any sense. In particular this:

     1
-----------
2.447 cos^-1

Basically just doean't mean anything. The correct way to write it is:

arcsec 2.447
= arccos 1/2.447
= arccos .40866
= 65.88 degrees

At this point I guess you just have to punch it in your calculator, because there's not a good way to do this by hand without more information.

You got dinged for the same reason on the next problem. You're given csc x = 3.2746. You wrote x = 1 / (3.2746 csc^-1). Regardless of whether you punched something into your calculator and got the right answer, what you wrote there basically amounts to a bunch of random letters and numbers stringed together in a way that doesn't mean anything. What you should have written is:

csc x = 3.2746
sin x = 1/3.2746
sin x = .3054
x = arcsin .3054
x = 17.8 degrees

 

[FortuneFaded]

Can anyone tell my how to better show my work better? I feel like I'm being marked very harsh on work shown and don't understand what I'm doing wrong. When I ask all I get for a response is "refer to your notes"

You might want to cover up your name if it matters. The trignometric functions are, as the name suggests, functions in which you put in a number and it spits out a different one. Putting the function after the number you are performing it on doesn't make sense. I've written how I would write the 2nd question:

Edit: Fucking beaten. I put effort in dammit.

 

[kizzmaul]

What grade math is that sin cos etc? Sounds kinda dumb for a test just to put those values almost as they are on the paper to the calculator.

EDIT: i know trigonometric functions, i just wabt to know where does one get tests where you put the values almost as on paper to the calc.

 

[cpp_is_king]

What grade math is that sin cos etc? Sounds kinda dumb for a test just to put those values almost as they are on the paper to the calculator.

Usually you learn it in 10th or 11th grade, but this looks like a college course for people who didn't get an intro to trig in high school.

 

[Stumpokapow]

A few mates and I like to play Spot It! after sports. The deck comes with 55 cards, and each card has 8 symbols (50 symbols total).

Cool thing is, for any pair of two cards, there is exactly one symbol that they share. I found the explanation today: The Intersection Game

I loved the way this article unfolded.

 

[HTupolev]

Can anyone tell my how to better show my work better? I feel like I'm being marked very harsh on work shown and don't understand what I'm doing wrong. When I ask all I get for a response is "refer to your notes"

x = 7+1
x = 8

This is the same as:

x = addOneToThisNumber(7)
x = 8

Now for some algebra:

addOneToThisNumber(x) = 8
subtractOneFromThisNumber(addOneToThisNumber(x)) = subtractOneFromThisNumber(8)
x = subtractOneFromThisNumber(8)
x = 7

And with trigonometric functions instead of silly addition functions:

cos(x) = -1
arccos(cos(x)) = arccos(-1)
x = arccos(-1)
x = 180

 

[kgtrep]

I loved the way this article unfolded.

Yep, me too!

 

[Exuro]

Hoping someone can help. Learning about continuous wavelet transforms and am having trouble with this problem which seems rather simple.

What I know is I can write this in either

or

format, and

So I know that I can use either, which I want to use the first since its a convolution and I can do a fourier transform to simplify it. I figure the functions being typical fourier transforms is why i should do it, seems like a hint. So i have to do the fourier transform on psi which becomes a convolution of the two and I get to using sifting since cos becomes two delta functions/goal posts so I get two gaussians that are sifted to s0. Then the harmonic is a delta function so I'm left with sifted gaussians with respect to a and b times a sifting function with respect to s. This seems wrong as I feel I should only have a and b in the output. I'm still trying to grasp these concepts and I'm having an extremely hard time finding actual examples of this. Everything is very generalized and doesn't give actual functions to psi so its hard to determine how to do this.

 

[triplestation]

help!

in my integral there should be a 25 being multiplied with the pi but i have no clue where it comes from?

this is as far as i got before realizing theres a 25 missing in front of the pi when i looked at the solution

 

[Massive_Edge]

it's amazing to think that Godel literally shut down 20th century mathematics with his Incompleteness Theorems

poor David Hilbert

 

[Biggest-Geek-Ever]

help!

in my integral there should be a 25 being multiplied with the pi but i have no clue where it comes from?

this is as far as i got before realizing theres a 25 missing in front of the pi when i looked at the solution

Second line: (10 - 5e^-x)^2 - (10-5)^2 = (5(2-e^-x))^2 - (5(2-1))^2 = 5^2 [(2-e^-x)^2 - 1] = 25[(2-e^-x)^2 - 1]

Excellent drawing, by the way! I wish had that artistic ability when I was tutoring calc students.

 

[triplestation]

Second line: (10 - 5e^-x)^2 - (10-5)^2 = (5(2-e^-x))^2 - (5(2-1))^2 = 5^2 [(2-e^-x)^2 - 1] = 25[(2-e^-x)^2 - 1]

Excellent drawing, by the way! I wish had that artistic ability when I was tutoring calc students.

thanks so much, now it totally makes sense! lol

and yeah i like to doodle outside of math hw so these problems are fun for me when i have to imagine whats going on lol

for the (10-5)^2 term im not sure if you are supposed to simplify it down to (2-1)^2 by dividing 10 and 5 by 2

would (10-5)^2 = 25 be a problem?

 

[Stumpokapow]

it's amazing to think that Godel literally shut down 20th century mathematics with his Incompleteness Theorems

poor David Hilbert

Alternatively, he allowed mathematics to be focused in a better direction: around applied statistics, which ended up being a great growth area as the computational power revolution took us from "calculating a single variate regression is arduous" to "lol machine learning just crunched the entire earth's supply of data and outputted the secret of the universe".

Like, Bayes came up with the underpinnings of Bayesian inference in the 18th century, and until 15 years ago it wasn't taken seriously because we didn't have the power to do it usefully. Now Fisherian frequentist statistics is largely a joke.

Hell, for an example of how far statistics has come so fast, the Monty Hall problem was a subject of actual professional debate in my lifetime.

 

[Massive_Edge]

Alternatively, he allowed mathematics to be focused in a better direction: around applied statistics, which ended up being a great growth area as the computational power revolution took us from "calculating a single variate regression is arduous" to "lol machine learning just crunched the entire earth's supply of data and outputted the secret of the universe".

Like, Bayes came up with the underpinnings of Bayesian inference in the 18th century, and until 15 years ago it wasn't taken seriously because we didn't have the power to do it usefully. Now Fisherian frequentist statistics is largely a joke.

Hell, for an example of how far statistics has come so fast, the Monty Hall problem was a subject of actual professional debate in my lifetime.

speaking of statistics.....i dont know much about the field....but isn't there a general sort of skepitcism of statistics among mathematicians...

not like a hatred, but more of a skepticism, is there sort of a dispute between mathematicians and statisticians

 

[Stumpokapow]

speaking of statistics.....i dont know much about the field....but isn't there a general sort of skepitcism of statistics among mathematicians...

not like a hatred, but more of a skepticism, is there sort of a dispute between mathematicians and statisticians

Mathematics is axiomatically true. Start with assumptions and proceed. If there are no mistakes in the proof, you found something. Statistics can often be analytically proven as can mathematics (i.e. the sample mean is an unbiased estimator) but many of the more interesting applications of statistics often rely on a sort of faith, and artistry, and are subject to interpretation when used to infer things. Pure mathematics is ill-equipped to deal with problems in the real world. Especially the social world, where operationalization and measurement are significant challenges and inference is subject to real limitations, but also in the natural/natural sciences world. Much of statistics can also be analytically proven, but I have found that analytic proof is kinda overrated when you can use something empirically and get the result you want. Like, I'm not sure I could prove the properties of gradient descent, but I can have my computer do one when I want to minimize a function, which is fine by me because mostly the minimization is more of interest for me as the input into some sort of empirical or modeling problem. It's just a tool in my toolbox, not the puzzle I'm trying to solve.

I think because my interest in mathematics came from my interest in Comp Sci and programming, for me I've always been drawn to techniques like simulation rather than analytical proof. It was a big debate in early Computer Science whether programming ought to be designed around ease of programming and getting results, or rigor of proof and mathematical structure. If the rigor people had won, we'd have a lot more stable and less buggy code, but I think we'd have got less done. The debate continues today in that functional programming people are holdouts about something closer to mathematical structure in code, hahaha.

Some of the skepticism or disrespect is lack of professional overlap. I can think of very few influential modern mathematicians who work in statistics and very few influential modern statisticians who work in math. Normally when I read a statistician's CV and look for something closer to actual real professional math, it's something like "well looks like in grad school they were one author of 5 that worked on a proof" and then they never do actual math again. Hahaha. A brief Wiki check tells me only two Fields Medals have been awarded for statistics related topics.

But we have more in common than we have different. We both love Carl Gauss. Who doesn't?

 

[Two Words]

I'm having trouble with a proof. A tree is considered graceful if it is possible to label each vertex from 1 to n (as in if you have 5 vertices, each one will be labeled a different number from 1 to 5) and such that the absolute difference of the labels of all adjacent vertices will each be different.

I have to prove that all trees with a single path, basically a linked list, of any size is graceful. I thought about it and I know how you could make it work for any arbitrary sized tree with this property, but I don't really see an easy proof. Here is how I think about proving it. You follow this pattern of any size. I'll just use a linked list with 8 vertices.

You label the vertices from 1 to 8.
1 connects to 8- absolute difference is 7
8 connects to 2- absolute difference is 6
2 connects to 7- absolute difference is 5
7 connects to 3- absolute difference is 4
3 connects to 6- absolute difference is 3
6 connects to 4- absolute difference is 2
4 connects to 5- absolute difference is 1

So your tree would be labeled from root to leaf in this case:
1-8-2-7-3-6-4-5

This works with any n sized linked list. But how do I prove it?

 

[Stumpokapow]

I'm having trouble with a proof. A tree is considered graceful if it is possible to label each vertex from 1 to n (as in if you have 5 vertices, each one will be labeled a different number from 1 to 5) and such that the absolute difference of the labels of all adjacent vertices will each be different.

I have to prove that all trees with a single path, basically a linked list, of any size is graceful. I thought about it and I know how you could make it work for any arbitrary sized tree with this property, but I don't really see an easy proof. Here is how I think about proving it. You follow this pattern of any size. I'll just use a linked list with 8 vertices.

You label the vertices from 1 to 8.
1 connects to 8- absolute difference is 7
8 connects to 2- absolute difference is 6
2 connects to 7- absolute difference is 5
7 connects to 3- absolute difference is 4
3 connects to 6- absolute difference is 3
6 connects to 4- absolute difference is 2
4 connects to 5- absolute difference is 1

So your tree would be labeled from root to leaf in this case:
1-8-2-7-3-6-4-5

This works with any n sized linked list. But how do I prove it?

I'm not sure the structure of the proof your prof wants, but you've proven it.

Label nodes from 1 to n. So then the possible differences are 1 through n-1. Given an even number of nodes, divided the nodes into two lists: order one list from 1 to n/2; the other list from n downwards to 1. All nodes are accounted for. Alternate nodes between the two lists. The vertex edges will then have difference n-1, n-2, ... 1. Is this not a sufficient proof for even numbered lists? For odd nodes, split the list at the median, excluding the median (so all nodes except the median are represented). Follow the same structure; the vertex edges will have the differences n-1, n-2, ... 2 and the final node will be (n-1)/2 in the first list and (n+3)/2 in the second list, and the difference between the final node in either list and the remaining node (n+1)/2 is 1.

Edit: Searching for "proof path graphs are graceful" brings me to this slide set here which uses the same approach and uses no more detail than what we just did. (slides 8-10)

 

[Two Words]

I'm not sure the structure of the proof your prof wants, but you've proven it.

Label nodes from 1 to n. So then the possible differences are 1 through n-1. Given an even number of nodes, divided the nodes into two lists: order one list from 1 to n/2; the other list from n downwards to 1. All nodes are accounted for. Alternate nodes between the two lists. The vertices will then have difference n-1, n-2, ... 1. Is this not a sufficient proof for even numbered lists? For odd nodes, split the list at the median, excluding the median (so all nodes except the median are represented). Follow the same structure; the vertices will have the differences n-1, n-2, ... 2 and the final node will be (n-1)/2 in the first list and (n+3)/2 in the second list, and the difference between the final node in either list and the remaining node (n+1)/2 is 1.

Edit: Searching for "proof path graphs are graceful" brings me to this slide set here which uses the same approach and uses no more detail than what we just did. (slides 8-10)

I suppose I was looking for a proof that was more mathematical than a set of instructions. I suspect that there could be a proof by induction.

 

[Stumpokapow]

I suppose I was looking for a proof that was more mathematical than a set of instructions. I suspect that there could be a proof by induction.

node_1 = 1
diff = (N-1...1)
node_{i>1} = node_{i-1} + (-1)^(i) * (diff_{i-1})

It's 2AM here but does this work for you? Or does this not do enough to prove the uniqueness of the node labels even as it proves the uniqueness of the differences?

 

[Two Words]

node_1 = 1
diff = (N-1...1)
node_{i>1} = node_{i-1} + (-1)^(i) * (diff_{i-1})

It's 2AM here but does this work for you? Or does this not do enough to prove the uniqueness of the node labels even as it proves the uniqueness of the differences?

You may be right in that is all they are not looking for a lot more. I'll ask about it.


Maybe it can be shown recursively look at the image below. If you notice, going from n to n+1 has you flipping the n vertices in pairs, if it's odd then the last one is left alone. Then the new n+1 vertex is added to the top. The 2 nodes erased are 3s.

 

[Two Words]

node_1 = 1
diff = (N-1...1)
node_{i>1} = node_{i-1} + (-1)^(i) * (diff_{i-1})

It's 2AM here but does this work for you? Or does this not do enough to prove the uniqueness of the node labels even as it proves the uniqueness of the differences?

New stump, and this one seems a lot harder.

A graph is a caterpillar if there is a simple path in the graph such that every vertex not in the simple path is adjacent to a vertex on the simple path. Basically, you could think of a caterpillar as the same single path trees we had on the previous proof, but each vertex on the path can have as many vertices as it wants. They are like the legs of the caterpillar. I need to prove or disprove that all caterpillar graphs are graceful.

 

[cpp_is_king]

New stump, and this one seems a lot harder.

A graph is a caterpillar if there is a simple path in the graph such that every vertex not in the simple path is adjacent to a vertex on the simple path. Basically, you could think of a caterpillar as the same single path trees we had on the previous proof, but each vertex on the path can have as many vertices as it wants. They are like the legs of the caterpillar. I need to prove or disprove that all caterpillar graphs are graceful.

Start by showing that for a caterpillar with body segment consisting of a single vertex, you can add as many legs as you want while maintaining gracefulness.

Then use induction on the number of body vertices. I haven't actually written out the proof, but I think this should work.

 

[Two Words]

node_1 = 1
diff = (N-1...1)
node_{i>1} = node_{i-1} + (-1)^(i) * (diff_{i-1})

It's 2AM here but does this work for you? Or does this not do enough to prove the uniqueness of the node labels even as it proves the uniqueness of the differences?

Start by showing that for a caterpillar with body segment consisting of a single vertex, you can add as many legs as you want while maintaining gracefulness.

Then use induction on the number of body vertices. I haven't actually written out the proof, but I think this should work.

I can make the body vertex n or 1 and make every other vertex that connects to it all of the other numbers, but I don't see how I can make it true inductively. I first thought appending a body vertex with value 0 and increment each vertex's value by 1. I don't get the rest though.

 

[cpp_is_king]

I can make the body vertex n or 1 and make every other vertex that connects to it all of the other numbers, but I don't see how I can make it true inductively. I first thought appending a body vertex with value 0 and increment each vertex's value by 1. I don't get the rest though.

When you add a second body vertex (which might itself have an arbitrary number of legs), you may have to re-assign the numbers on the first vertex. Suppose you've got a single body vertex with 10 legs. So 11 vertices total. You make the body vertex 1, and then use 2-11 for the rest.

Now suppose you add another body vertex with 5 legs. So 6 vertices total. The new graph is going to have 6+11 = 17 verticies. This new segment was originally assigned 1 for the body, and 2-6 for the legs. Set the first body vertex to 17-5=12. And set its legs to 2-11. Set the second body vertex to 1, and set its legs to 13-17.

The idea here is to partition the set of differences into high values and low values, and get the first segment to use all the ones in one partition, and the second segment to use all the ones in the other partition. If you try to visualize it, it looksl ike this:

1      2      3      4      5      6      7      8      9      10     11     12     13     14     15     16     17
B2    -------------------------- Segment 1 Legs ------------------------     B1     ------- Segment 2 Legs -------

going from 2 segments to 3 segments might have an additional kink involved, but I think the same concept applies, except that now you do the partitioning recursively. i.e. if you have n segments and you're adding an n+1'th segment, you still partition it into two groups. One for the new segment and one for the original n segments. After you find the numbers to assign to the new segment, you then partition the original graph into its last segment plus the preceding n-1 segments. etc

Edit: Actually i don't think a recursive partitioning will work, because you'll end up trying to reuse the lower valued differences again. So you need to do the partitioning all at once. Which means that maybe induction isn't even the right answer, although I still think the same approach probably works, you just have to show the partitioning strategy.

 

[Two Words]

When you add a second body vertex (which might itself have an arbitrary number of legs), you may have to re-assign the numbers on the first vertex. Suppose you've got a single body vertex with 10 legs. So 11 vertices total. You make the body vertex 1, and then use 2-11 for the rest.

Now suppose you add another body vertex with 5 legs. So 6 vertices total. The new graph is going to have 6+11 = 17 verticies. This new segment was originally assigned 1 for the body, and 2-6 for the legs. Set the first body vertex to 17-5=12. And set its legs to 2-11. Set the second body vertex to 1, and set its legs to 13-17.

The idea here is to partition the set of differences into high values and low values, and get the first segment to use all the ones in one partition, and the second segment to use all the ones in the other partition. If you try to visualize it, it looksl ike this:

1      2      3      4      5      6      7      8      9      10     11     12     13     14     15     16     17
B2    -------------------------- Segment 1 Legs ------------------------     B1     ------- Segment 2 Legs -------

going from 2 segments to 3 segments might have an additional kink involved, but I think the same concept applies, except that now you do the partitioning recursively. i.e. if you have n segments and you're adding an n+1'th segment, you still partition it into two groups. One for the new segment and one for the original n segments. After you find the numbers to assign to the new segment, you then partition the original graph into its last segment plus the preceding n-1 segments. etc

Edit: Actually i don't think a recursive partitioning will work, because you'll end up trying to reuse the lower valued differences again. So you need to do the partitioning all at once. Which means that maybe induction isn't even the right answer, although I still think the same approach probably works, you just have to show the partitioning strategy.

Hmm, I'm having a little trouble following this. I'll try to think it over here.

 

[Massive_Edge]

Mathematics is axiomatically true. Start with assumptions and proceed. If there are no mistakes in the proof, you found something. Statistics can often be analytically proven as can mathematics (i.e. the sample mean is an unbiased estimator) but many of the more interesting applications of statistics often rely on a sort of faith, and artistry, and are subject to interpretation when used to infer things. Pure mathematics is ill-equipped to deal with problems in the real world. Especially the social world, where operationalization and measurement are significant challenges and inference is subject to real limitations, but also in the natural/natural sciences world. Much of statistics can also be analytically proven, but I have found that analytic proof is kinda overrated when you can use something empirically and get the result you want. Like, I'm not sure I could prove the properties of gradient descent, but I can have my computer do one when I want to minimize a function, which is fine by me because mostly the minimization is more of interest for me as the input into some sort of empirical or modeling problem. It's just a tool in my toolbox, not the puzzle I'm trying to solve.

I think because my interest in mathematics came from my interest in Comp Sci and programming, for me I've always been drawn to techniques like simulation rather than analytical proof. It was a big debate in early Computer Science whether programming ought to be designed around ease of programming and getting results, or rigor of proof and mathematical structure. If the rigor people had won, we'd have a lot more stable and less buggy code, but I think we'd have got less done. The debate continues today in that functional programming people are holdouts about something closer to mathematical structure in code, hahaha.

Some of the skepticism or disrespect is lack of professional overlap. I can think of very few influential modern mathematicians who work in statistics and very few influential modern statisticians who work in math. Normally when I read a statistician's CV and look for something closer to actual real professional math, it's something like "well looks like in grad school they were one author of 5 that worked on a proof" and then they never do actual math again. Hahaha. A brief Wiki check tells me only two Fields Medals have been awarded for statistics related topics.

But we have more in common than we have different. We both love Carl Gauss. Who doesn't?

Carl Gauss is like a demi-god in the mathematical community

 

[cpp_is_king]

Hmm, I'm having a little trouble following this. I'll try to think it over here.

yea so it doesn't even need to use induction. I don't really want to just write out the solution, and my original idea needs a little tweaking, but I wrote it out and I'm pretty convinced it works. To prove that it's true, you only need to show that for any caterpillar, there is some strategy -- doesn't matter what -- to assign the numbers in a way that makes the graph graceful. So for this type of proof, a construction can often be useful. Look for a way of assigning the numbers to an arbitrary caterpillar "gracefully". Start with a simple graph like this:

\     /
 \___/
 /   \
/     \

and see if you can figure out how to number them. Then add some edges and see if your algorithm still works.

Spoiler

How many possible differences are there? Try assigning the differences before you assign the vertices. Your strategy for assigning differences should be fairly simple, in the sense that the strategy is easily reproducible on an arbitrary caterpillar.

The key is the maximal difference. For example, in a caterpillar with 11 edges (i.e. 11 differences), you will need all difference values in the range 1-11. There will be multiple ways to subtract 2 numbers to get, for example, 3, but how many ways will there be to subtract 2 numbers to get 11?

You'll probably get half or more credit for coming up with the construction. But you need to prove that the construction actually works (i.e. show that it leads to no 2 adjacent differences being the same)

 

[Two Words]

yea so it doesn't even need to use induction. I don't really want to just write out the solution, and my original idea needs a little tweaking, but I wrote it out and I'm pretty convinced it works. To prove that it's true, you only need to show that for any caterpillar, there is some strategy -- doesn't matter what -- to assign the numbers in a way that makes the graph graceful. So for this type of proof, a construction can often be useful. Look for a way of assigning the numbers to an arbitrary caterpillar "gracefully". Start with a simple graph like this:

     /
 ___/
 /   
/

and see if you can figure out how to number them. Then add some edges and see if your algorithm still works.

Spoiler

How many possible differences are there? Try assigning the differences before you assign the vertices. Your strategy for assigning differences should be fairly simple, in the sense that the strategy is easily reproducible on an arbitrary caterpillar.

The key is the maximal difference. For example, in a caterpillar with 11 edges (i.e. 11 differences), you will need all difference values in the range 1-11. There will be multiple ways to subtract 2 numbers to get, for example, 3, but how many ways will there be to subtract 2 numbers to get 11?

You'll probably get half or more credit for coming up with the construction. But you need to prove that the construction actually works (i.e. show that it leads to no 2 adjacent differences being the same)

Right, I see that n and 1 must be adjacent. But n-1 and 1 or n and 2 are options for the n-2 value and so on. I'm figuring out different caterpillars, but I'm not really using a general technique besides knowing that certain bricked must be adjacent. I was trying to do a contrapositive technique, as in prove that if it is not graceful then it is not a caterpillar, but I can't make any strong arguments about not being graceful.

 

[cpp_is_king]

Right, I see that n and 1 must be adjacent. But n-1 and 1 or n and 2 are options for the n-2 value and so on. I'm figuring out different caterpillars, but I'm not really using a general technique besides knowing that certain bricked must be adjacent. I was trying to do a contrapositive technique, as in prove that if it is not graceful then it is not a caterpillar, but I can't make any strong arguments about not being graceful.

So n and 1 must be adjacent, as you've noted. N-1 and 1 is only an option if 1 was on the body, and N and 2 is only an option if N was on the body. So if you choose the body vertex first, there is only one way to proceed. In fact, I claim that with your differences labeled correctly, and the correct choice of initial body vertex, every other vertex is uniquely determined.

Draw out the actual caterpillar with differences and vertex labels that i gave using that number line above, for an example

 

[cpp_is_king]

A possible wrench in this whole thing. This is obviously a caterpillar:

 •     •
 |     |
 •-----•
 |     |
 •     •

What about this?

C•-----•D
 |     |
A•-----•B
 |     |
E•     •F

If A and B are the body vertices, the condition for a caterpillar seems to be met.

A graph is a caterpillar if there is a simple path in the graph such that every vertex not in the simple path is adjacent to a vertex on the simple path

the vertices not in the simple path are C, D, E, F. C is adjacent to A, D is adjacent to B, E is adjacent to A, F is adjacent to B. If this is a caterpillar then I dont' think my argument works anymore. I'm inclined to believe that this is not a valid caterpillar, and that either you or the teacher left off a condition. For example, "A graph is a caterpillar if there is a simple path in the graph such that every vertex not in the simple path is of degree 1, and is adjacent to a vertex on the simple path". Without this, you have really bizarre graphs that are caterpillars, like this:

C•-----•D
 |  _  |
 | / \ |
 |/   \|
A•-----•B
 |     |
E•     •F

If you can allow graphs like this, then the original statement is trivially false, because you can have a trivial caterpillar with just A and B (body vertices), and 2 edges connecting them. you require 2 distinct differences, but there are only 2 vertices, so 1 difference. Pigeonhole principle.

 

[Daria]

Tried to do a google search but couldn't get what I'm looking for. I blame finals.

Quadtratic functions: ax^2+bx+c = 0, A*C, A+C = B.

Problem is I forgot how to produce the table of variables that will show the sums and multiplications of each number on my TI-84. I know it's a formula that's inputted under "Y=" where

Y1 = [something]
Y2 = [something

Then is just generated like any other table by using "TABLE". Can anyone shed some light?

 

[cpp_is_king]

Tried to do a google search but couldn't get what I'm looking for. I blame finals.

Quadtratic functions: ax^2+bx+c = 0, A*C, A+C = B.

Problem is I forgot how to produce the table of variables that will show the sums and multiplications of each number on my TI-84. I know it's a formula that's inputted under "Y=" where

Y1 = [something]
Y2 = [something

Then is just generated like any other table by using "TABLE". Can anyone shed some light?

It's possible I'm being dense, but I have no idea what your question is. Are you trying to solve a quadratic equation? What does A*C, A+C = B mean?