text:
Let's return to the problem of providing lines for water, electricity, and natural gas to three homes which we discussed in the introduction to this chapter. How can we model this problem using a graph? The best way is to have a vertex for each utility and a vertex for each of the three homes. Then what we're asking is if we can draw the graph that has an edge from each utility to each home so that none of the edges cross. This graph is shown in Figure 5.29. You should recognize it as the complete bipartite graph $\bfK_{3,3}$ we introduced earlier in the chapter.

While this example of utility lines might seem a bit contrived, since there's really no good reason that the providers can't bury their lines at different depths, the question of whether a graph can be drawn in the plane such that edges intersect only at vertices is a long-studied question in mathematics that does have useful applications. One area where it arises is in the design of microchips and circuit boards. In those contexts, the material is so thin that the option of placing connections at different depths either does not exist or is severely restricted. There is much deep mathematics that underlies this area, and this section is intended to introduce a few of the key concepts.

By a drawing of a graph, we mean a way of associating its vertices with points in the Cartesian plane $\reals^2$ and its edges with simple polygonal arcs whose endpoints are the points associated to the vertices that are the endpoints of the edge. You can think of a polygonal arc as just a finite sequence of line segments such that the endpoint of one line segment is the starting point of the next line segment, and a simple polygonal arc is one that does not cross itself. (Our choice of polygonal arcs rather than arbitrary curves actually doesn't cause an impediment, since by taking very, very, very short line segments we can approximate any curve.) A planar drawing of a graph is one in which the polygonal arcs corresponding to two edges intersect only at a point corresponding to a vertex to which they are both incident. A graph is planar if it has a planar drawing. A face of a planar drawing of a graph is a region bounded by edges and vertices and not containing any other vertices or edges.

Figure 5.30 shows a planar drawing of a graph with $6$ vertices and $9$ edges. Notice how one of the edges is drawn as a true polygonal arc rather than a straight line segment. This drawing determines $5$ regions, since we also count the unbounded region that surrounds the drawing.

Figure 5.31 shows a planar drawing of the complete graph $\bfK_4\text{.}$ There are $4$ vertices, $6$ edges, and $4$ faces in the drawing.

What happens if we compute the number of vertices minus the number of edges plus the number of faces for these drawings? We have \begin{align*} 6-9+5 \amp = 2\\ 4-6+4 \amp =2 \end{align*}

While it might seem like a coincidence that this computation results in $2$ for these planar drawings, there's a more general principle at work here, and in fact it holds for any planar drawing of any planar graph.

In fact, the number $2$ here actually results from a fundamental property of the plane, and there are a corresponding theorems for other surfaces. However, we only need the result as stated above.

##### Proof

Taken by itself, Euler's formula doesn't seem that useful, since it requires counting the number of faces in a planar embedding. However, we can use this formula to get a quick way to determine that a graph is not planar. Consider a drawing without edge crossings of a graph on $n$ vertices and $m$ edges, with $n\ge3\text{.}$ We consider pairs $(e,F)$ where $e$ is an edge of $\bfG$ and $F$ is a face that has $e$ as part of its boundary. How many such pairs are there? Let's call the number of pairs $p\text{.}$ Each edge can bound either one or two faces, so we have that $p\leq 2m\text{.}$ We can also bound $p$ by counting the number of pairs in which a face $F$ appears. Each face is bounded by at least $3$ edges, so it appears in at least $3$ pairs, and so $p\geq 3f\text{.}$ Thus $3f\leq 2m$ or $f\leq 2m/3\text{.}$ Now, utilizing Euler's formula, we have \begin{equation*} m = n+f-2 \leq n + \frac{2m}{3} - 2 \iff \frac{m}{3} \leq n-2. \end{equation*} Thus, we've proven the following theorem.

The contrapositive of this theorem, namely that an $n$-vertex graph with more than $3n-6$ edges is not planar, is usually the most useful formulation of this result. For instance, we've seen (Figure 5.31) that $\bfK_4$ is planar. What about $\bfK_5\text{?}$ It has $5$ vertices and $C(5,2)=10 > 9 = 3\cdot 5-6$ edges, so it is not planar, and thus for $n\geq 5\text{,}$ $\bfK_n$ is not planar, since it contains $\bfK_5\text{.}$ It's important to note that Theorem 5.33 is not the be-all, end-all of determining if a graph is planar. To see this, let's return to the subject of drawing $\bfK_{3,3}$ in the plane. This graph has $6$ vertices and $9$ edges, so it passes the test of Theorem 5.33. However, if you spend a couple minutes trying to find a way to draw $\bfK_{3,3}$ in the plane without any crossing edges, you'll pretty quickly begin to believe that it can't be done—and you'd be right!

To see why $\bfK_{3,3}$ is not planar, we'll have to return to Euler's formula, and we again work with edge-face pairs. For $\bfK_{3,3}\text{,}$ we see that every edge would have to be part of the boundary of two faces, and faces are bounded by cycles. Also, since the graph is bipartite, there are no odd cycles. Thus, counting edge-face pairs from the edge perspective, we see that there are $2m = 18$ pairs. If we let $f_k$ be the number of faces bounded by a cycle of length $k\text{,}$ then $f= f_4 + f_6\text{.}$ Thus, counting edge-face pairs from the face perspective, there are $4f_4 + 6f_6$ pairs. From Euler's formula, we see that the number of faces $f$ must be $5\text{,}$ so then $4f_4+6f_6\geq 20\text{.}$ But from our count of edge-face pairs, we have $2m=4f_4+6f_6\text{,}$ giving $18\geq 20\text{,}$ which is clearly absurd. Thus, $\bfK_{3,3}$ is not planar.

At this point, you're probably asking yourself “So what?” We've invested a fair amount of effort to establish that $\bfK_5$ and $\bfK_{3,3}$ are nonplanar. Clearly any graph that contains them is also nonplanar, but there are a lot of graphs, so you might think that we could be at this forever. Fortunately, we won't be, since at its core, planarity really comes down to just these two graphs, as we shall soon see.

If $\GVE$ is a graph and $uv\in E\text{,}$ then we may form a new graph $\bfG'$ called an elementary subdivision of $\bfG$ by adding a new vertex $v'$ and replacing the edge $uv$ by edges $uv'$ and $v'v\text{.}$ In other words, $\bfG'$ has vertex set $V'=V\cup\{v'\}$ and edge set $E'=(E-\{uv\})\cup \{uv',v'v\}\text{.}$ Two graphs $\bfG_1$ and $\bfG_2$ are homeomorphic if they can be obtained from the same graph by a (potentially trivial) sequence of elementary subdivisions.

The purpose of discussing homeomorphic graphs is that two homeomorphic graphs have the same properties when it comes to being drawn in the plane. To see this, think about what happens to $\bfK_5$ if we form an elementary subdivision of it via any one of its edges. Clearly it remains nonplanar. In fact, if you take any nonplanar graph and form the elementary subdivision using any one of its edges, the resulting graph is nonplanar. The following very deep theorem was proved by the Polish mathematician Kazimierz Kuratowski in 1930. Its proof is beyond the scope of this text.

Kuratowski's Theorem gives a useful way for checking if a graph is planar. Although it's not always easy to find a subgraph homeomorphic to $\bfK_5$ or $\bfK_{3,3}$ by hand, there are efficient algorithms for planarity testing that make use of this characterization. To see this theorem at work, let's consider the Petersen graph shown in Figure 5.17. The Petersen graph has $10$ vertices and $15$ edges, so it passes the test of Theorem 5.33, and our argument using Euler's formula to prove that $\bfK_{3,3}$ is nonplanar was complex enough, we probably don't want to try it for the Petersen graph. To use Kuratowski's Theorem here, we need to decide if we would rather find a subgraph homeomorphic to $\bfK_5$ or to $\bfK_{3,3}\text{.}$ Although the Petersen graph looks very similar to $\bfK_5\text{,}$ it's actually simultaneously too similar and too different for us to be able to find a subgraph homeomorphic to $\bfK_5\text{,}$ since each vertex has degree $3\text{.}$ Thus, we set out to find a subgraph of the Petersen graph homeomorphic to $\bfK_{3,3}\text{.}$ To do so, note that $\bfK_{3,3}$ contains a cycle of length $6$ and three edges that are in place between vertices opposite each other on the cycle. We identify a six-cycle in the Petersen graph and draw it as a hexagon and place the remaining four vertices inside the cycle. Such a drawing is shown in Figure 5.35. The subgraph homeomorphic to $\bfK_{3,3}$ is found by deleting the black vertex, as then the white vertices have degree two, and we can replace each of them and their two incident edges (shown in bold) by a single edge.

We close this section with a problem that brings the current section together with the topic of graph coloring. In 1852 Francis Guthrie, an Englishman who was at the time studying to be lawyer but subsequently became a professor of mathematics in South Africa, was trying to color a map of the counties of England so that any two counties that shared a boundary segment (meaning they touched in more than a single point) were colored with different colors. He noticed that he only needed four colors to do this, and was unable to draw any sort of map that would require five colors. (He was able to find a map that required four colors, an example of which is shown in Figure 5.36.)

Could it possibly be true that every map could be colored with only four colors? He asked his brother Frederick Guthrie, who was a mathematics student at University College, London, about the problem, and Frederick eventually communicated the problem to Augustus de Morgan (of de Morgan's laws fame), one of his teachers. It was in this way that one of the most famous (or infamous) problems, known for a century as the Four Color Problem and now the Four Color Theorem, in graph theory was born. De Morgan was very interested in the Four Color Problem, and communicated it to Sir William Rowan Hamilton, a prominent Irish mathematician and the one for whom hamiltonian cycles are named, but Hamilton did not find the problem interesting. Hamilton is one of the few people who considered the Four Color Problem but did not become captivated by it.

We'll continue our discussion of the history of the Four Color Theorem in a moment, but first, we must consider how we can turn the problem of coloring a map into a graph theory question. Well, it seems natural that each region should be assigned a corresponding vertex. We want to force regions that share a boundary to have different colors, so this suggests that we should place an edge between two vertices if and only if their corresponding regions have a common boundary. (As an example, the map in Figure 5.36 corresponds to the graph $\bfK_4\text{.}$) It is not difficult to see that this produces a planar graph, since we may draw the edges through the common boundary segment. Furthermore, with a little bit of thought, you should see that given a planar drawing of a graph, you can create a map in which each vertex leads to a region and edges lead to common boundary segments. Thus, the Four Color Problem could be stated as “Does every planar graph have chromatic number at most four?”

Interest in the Four Color Problem languished until 1877, when the British mathematician Arthur Cayley wrote a letter to the Royal Society asking if the problem had been resolved. This brought the problem to the attention of many more people, and the first “proof” of the Four Color Theorem, due to Alfred Bray Kempe, was completed in 1878 and published a year later. It took $11$ years before Percy John Heawood found a flaw in the proof but was able to salvage enough of it to show that every planar graph has chromatic number at most five. In 1880, Peter Guthrie Tait, a British physicist best known for his book Treatise on Natural Philosophy with Sir William Thomson (Lord Kelvin), made an announcement that suggested he had a proof of the Four Color Theorem utilizing hamiltonian cycles in certain planar graphs. However, consistent with the way Tait approached some conjectures in the mathematical theory of knots, it appears that he subsequently realized around 1883 that he could not prove that the hamiltonian cycles he was using actually existed and so Tait likely only believed he had a proof of the Four Color Theorem for a short time, if at all. However, it would take until 1946 to find a counterexample to the conjecture Tait had used in his attempt to prove the Four Color Theorem.

In the first half of the twentieth century, some incremental progress toward resolving the Four Color Problem was made, but few prominent mathematicians took a serious interest in it. The final push to prove the Four Color Theorem came with about at the same time that the first electronic computers were coming into widespread use in industry and research. In 1976, two mathematicians at the University of Illinois announced their computer-assisted proof of the Four Color Theorem. The proof by Kenneth Appel and Wolfgang Haken led the University of Illinois to add the phrase “FOUR COLORS SUFFICE” to its postage meter's imprint. 1

Appel and Haken's proof of the Four Color Theorem was at a minimum unsatisfactory for many mathematicians, and to some it simply wasn't a proof. These mathematicians felt that the using a computer to check various cases was simply too uncertain; how could you be certain that the code that checked the 1,482 “unavoidable configurations” didn't contain any logic errors? In fact, there were several mistakes found in the cases analyzed, but none were found to be fatal flaws. In 1989, Appel and Haken published a 741-page tome entitled Every Planar Map is Four Colorable which provided corrections to all known flaws in their original argument. This still didn't satisfy many, and in the early 1990's a team consisting of Neil Robertson from The Ohio State University; Daniel P. Sanders, a graduate student at the Georgia Institute of Technology; Paul Seymour of Bellcore; and Robin Thomas from Georgia Tech announced a new proof of the Four Color Theorem. However, it still required the use of computers. The proof did gain more widespread acceptance than that of Appel and Haken, in part because the new proof used fewer than half ($633$) of the number of configurations the Appel-Haken proof used and the computer code was provided online for anyone to verify. While still unsatisfactory to many, the proof by Robertson, et al. was generally accepted, and today the issue of the Four Color Theorem has largely been put to rest. However, many still wonder if anyone will ever find a proof of this simple statement that does not require the assistance of a computer.


text:
### Bayesian Statistics by Example¶

###### Who is this lecture for?¶

I begin every course/lecture with a brief description of the hypothetical student I had in mind when designing the course. This is in part to set the audience's expectations, but also to keep me true to the intended spirit of the course as I write it. This course is intended for those with only some experience with statistics. You are probably vaguely familiar with simple problems like coin flips, t tests, and the monty hall problem...but you approach statistics as you would that guy you once said hi to in the elevator that one time (i.e. awkwardly).

However, you WANT to know more. You are interested not only in applying statistical methodologies to problems, but actually understanding where the methodologies come from and the philosophic paradigms from which they were spawned. You understand that applying math can be as much an art as a science, and not, as many think, a game of rock-paper-scissors where one need only guess the right method for the right situation.

There are many more advanced and thorough treatments of bayesian statistics out there. Unfortuantely, they are often written with a more advanced student body in mind. This is rather tragic, as the beauty of Bayesian statistics is that it presents a philosophy of statistics which is intuitive, explainable, and simple. This lecture sets out to prove that Bayesian statistics, even in it's most complex and powerful forms, can be explained in english through a set of simple, common problems any practitioner of the dark probablistics arts may encounter. At times we will delve deep into the math behind our concepts, but the course is (hopefully) structed such that you can skip most of the more tedious proofs/derivations and simply focus on concepts and practice.

DO NOT read this whole lecture in one sitting. Read a section and let it sit and ferment in your head. The point of these examples isn't to memorize them, but to really understand them. Bayesian statistics is about building intuition around data and quantifying that intuition in a clear and powerful way...not memorizing formulas. Try to take an active part in the lessons by tweaking the code, changing parameters, or making up your own examples for the concepts!

While I have shaped and ammended much of the content shown here, almost 100% of this lecture is taken from other source material (which I reference when possible). Nothing here is new, I've just molded it into a more palatable form than you might find elsewhere. If you enjoy this course, please keep an eye out for my other courses and blog posts at jamesmontgomery.us!

I have mostly drawn material in this course from Thomas Wiecki, John Kruschke, and Andrew Gelman and encourage you to look up their works on bayesian statistics. I would also like to thank Mack Sweeney, Jason Wittenbach, Josh Touyz, and Keegan Hines without whom I wouldn't have nearly the grasp of Bayes' Theorem that I have today.

###### What is statistics?¶

At the risk of immediately losing your attention, I start with a purely philosophical question: what is statistics? I'm not asking for a dictionary definition...we all know that statisitics is a branch of mathmatics. I'm really asking: what is the goal or point of using statistics?

I believe that the purpose of statistics is to quanitfy our beliefs. To not only state that something has or will occur, but also the certainty that it has or will occur. We want to state these beliefs in a way that is standardized and logical so that we can convince others to share our beliefs or at least have a reasonable dialogue as to why they might not share our beliefs. To this end, our beliefs become only as powerful as the medium through which we express ourselves to convince others of the truth of our beliefs. In other words, academia often demands that we put our math where our mouth is...so we should be good at math.

There have been many tries to create a universally accepted paradigm for expressing opinions in statistics. We will discuss the two most prominent ones: the frequency based philosophy and the belief based philosophy...aka Frequentist statistics and Bayesian Statitistics.

For those strict adherants to the cults of Frequentism and Bayesianism...I apologize in advance for breaking down what are nuanced and complex methodologies into heuristics and crude analogies, but I'll reiterate that this is not meant to be a rigorous course on statistics, only an illustrative pass through the philosophy behind Bayes' Theorem.

###### The Frequentist Philosophy¶

You're probably quite familiar with frequentist statistics, even if you don't know it. It's the philosophy which guides most high school and college stats courses. This philosophy has inspired such famous methodologies as the student t test and bootstrap sampling.

Unfortuantely, you're most likely more familiar with the methodologies produced by this philosophy than the philosophy itself. But we don't want to take methodologies on blind faith; we want to know where they come from! Buried in the assumptions of every frequentist model of the world are a few guiding principles.

To explain these principles, I'll borrow (and bastardize) an analogy from Plato. Let's say that we're looking at the wall of a cave. Behind us is a fire lighting up the cave. Someone places an object behind us and in front of the fire such that we can't see the object but we can see it's shadow. We carefully take notes on the characteristics of it's shadow over time as the flame flickers and dances about. We might note the frequncy with which the shadows take certain shapes and sizes. This provides us with information about the nature of the object behind us, but also some ability to predict the nature of shadows that the object might cast were we to continue to sit and watch the wall.

In this example the shadows are samples that we observe through testing. The object represents some 'true' distribution of data that is fixed but that we can not directly observe. By collecting samples over time (observing data) we can gather information about the frequency of various events.

Probability, under this paradigm, becomes an expression of relative frequency (how often an event occurs comapred to other events).

Let's work through an example! Let's say that we have a coin of unknown bias. This means that we don't know the probability of it coming up heads or tails. First, we'll try to answer a very simple question: "what is the probability of getting heads on our next flip?"

The subtext in this example is that when we ask the question "what is the probability of getting heads?", we are actually asking "given the observed relative frequency of getting heads, how likely am I to observe heads if I flip again?".

We define this probability as the reatively frequency with which we see heads during experimentation as the number of samples observed goes to infinity.

$P(heads) = \lim_{n\to\infty} (n_{heads}/n$)
$n_{heads}$ = # of trials where we got heads
n = number of trials total

Now we can't realistically perform an infinite number of flips. Let's say we take a single sample of 10 observations (1 = heads, 0 = tails):

$[0,1,0,0,1,0,1,1,1,0]$

The relative frequency of seeing heads is 5/10 (you'll note that this is merely the mean of the observations or the 'sample mean'). Our expectation for the next flip being heads is 50%. We'll assume for now that consecutive coin flips do not affect each other (they are independant).

However, the point estimate of our probability (50%) holds no information about how certain we are that we have captured the 'true' probability of getting heads in our next flip. It provides no information as to how certain we are of our prediction. What if we haven't conducted enough trials? What if there is noise in our experiment that is unaccounted for?

We could try to come up with some range of values wherein we think the 'true' value lies. The magnitude of this range is proportional to the uncertainty within our sample. Well, here we start to get into the math a bit. Feel free to skip the derivations if you're not interested!

We've said that the probability of seeing an event is proportional to the relative frequency with which we see that event. Let's write that down in math.

$P(heads|p)=p^{\sum_1^n x_i}(1-p)^{\sum_1^n1-x_i}= p^{x}(1-p)^{n-x}$
p = relative frequency of seeing heads
$x_i$ represents an individual trial
n = the total number of trials

This equation gives the probability of seeing heads in n trials given the relative frequency of seeing heads that we have observed. We call this the liklihood. The probability of getting heads if we only flip the coin once, given that the relative frequency of heads we previously observed was 50%, is:

$(.5)^1(1-.5)^{(1-1)}=.5$

Just as we would expect. It's neat to note that the liklihood above is maximized when p = x / n (test this by setting the derivative of the log liklihood with respect to p to zero and solving for p).

We take the log of our liklihood (the logliklihood):

$l(p;x)=x\text{log}p+(n-x)\text{log}(1-p)$

The first derivative of the logliklihood:

$l'(p;x)=\dfrac{x-np}{p(1-p)}$

And the second derivative of the logliklihood:

$l''(p;x)=-\dfrac{x-2xp+np^2}{p^2(1-p)^2}$

We use these to calculate the Fisher information of our parameter. Without going into too much detail, the Fisher information is a way of measuring the amount of information that an observable random variable X carries about an unknown parameter θ upon which the probability of X depends.

$I(p)= \sum_{i=1}^{n} \dfrac{1}{p(1-p)} =\dfrac{n}{p(1-p)}$

Each observation carries a certain amount of information (dive into the fisher information). The sum of this information gives us the cummulative amount of information contained in the sample about a particular unknown variable (in this case the 'true' mean). We could say that the inverse of the information in the sample is the variance of the sample.

$I(p)=\dfrac{1}{\sigma^2}$

$\sigma^2=\dfrac{p(1-p)}{n}$

This makes sense given that our variance/uncertainty will decrease as the number of observations increases.

Now that we have a measure of uncertainty/variance, let's define our range of values in which we think the 'true' mean may lie. We design this range such that it increases with our uncertainty. We set a tuning parameter Z depending on how sensitive we want our range to be to capturing the 'true' parameter.

$\hat{p}\pm Z \sqrt{\dfrac{\hat{p}(1-\hat{p})}{n}}$
$\hat{p}$ = sample mean
n = number of trials
Z = z score constant

We typically call this a confidence interval and set Z to 1.96 (95% confidence interval). This interval roughly captures 95% of the observations within our sample. For a more thorough treatment of binomial confidence intervals, see here.

Now the point estimate was easy to interpret. it represented the relative frequency of seeing a particular event. How do we interpret this range of values?

We can interprete this interval as follows: were this test to be repeated on numerous samples, the fraction of calculated confidence intervals (which would differ for each sample) that encompass the true population parameter would tend toward 95%.

At least for me, this is unintuitive and disappointing because, as you'll note if you read carefully, we are not able to say much about our certainty of a specific outcome in a specific sample. We are quantifying our uncertinty across samples, rather than of seeing any particular sample. The probability that any particular sample confidence interval captures the 'true' mean is either zero or one (and we don't know which)!

At this point you might justly respond, "So what if 95 out of 100 theoretical experiments yield a confidence interval that includes the true value? I don't care about 99 experiments that I DIDN'T DO; I care about the experiment I DID DO. Additionally, this methodology allows 5 out of the 100 theoretical experiments to yield complete nonsense as long as the other 95 are correct; that's ridiculous." If you look carefully at our equaltion for capturing the Fisher information, you'll note that for small sample sizes there is a very real possibility of capturing an outcome that pushes the lower bound of the confidence interval below zero (realistically impossible) or to have a confidence interal of zero width (again, unrealistic).

We can mitigate the risk of these events occuring at low sample sizes by amendeding our calculation of the expectation from p = x/n to:

$p = \dfrac{x + 0.5}{n + 1}$

This is the same as saying we observed half a success and half a failure and serves to keeps the confidence interval from becoming degenerate. If that makes you feel uncomfortable...good! We've imposed some strange prior belief (that we expect the coin to be fair) upon our experiment even before we take into account our observations.

Well, let's take one more shot at quantifying the uncertainty in our prediction. Let's assume that the distribution of outcomes in our sample is representative of the 'true' population. This doesn't seem like a horrible assumption given that if the sample wasn't representative of the 'true' population there would be no point in using it to make predictions at all!

We could sub-sample our sample and calculate the variance among our sub-samples! Let's say we take twenty sub-samples (with replacement) of five from our ten observations and calculate the variance of the means of these sub-samples. We get a standard deviation of 14.8%. This metric seems a bit odd. For one thing, it is independant of the number of samples. I could have performed this methodology on a sample with one observation! We call this method Bootstrap Sampling

Okay, so expressing probability completely in terms of frequencies is a bit of a let down. What's the alternative?

###### The Bayesian Philosophy¶

Bayesians reject the Frequentist idea that there is a 'true' population from which we pluck samples with some probability. Bayesian statistics tries to set up a framework for evaluating how well sets of hypothesis describe the process by which observed data was generated.

Rather than defining probability as sets of relative frequencies, bayesians define probability as plausibility. This is a huge difference! A Frequentist can't say that they are X% sure of their prediction, only that X% of experiments of similar methodology would produce conclusions that would help arrive at accurate predictions. A Bayesian could say that they are X% sure of their prediction!...but would you believe them?

First, let's write out the Bayesian philosophy of probability in math jargon (as we did with the frequentist philosophy).

We start with a very basic axiom of probability, the joint probability:

$P(A,B)=P(A)*P(B|A)$

This says that the joint probability of A and B (the probability of both events occuring together) is equal to the probability of event A occuring mutliplied by the probability of event B occuring given the fact that A has occured. That is pretty fundamental.

Let's say that A is the probaility of my mother visiting. B is the probability that I am eating Indian food (my mother is Indian if that helps). My mother randomly visits once a month (1/30). My mother insists on eating Indian food with me every other visit (1/2). The probability that my mother is visting AND that I am eating Indian food is therefore (1/30)*(1/2)=1/60.

From the joint probability, we can show that:

$P(A,B)=P(A)*P(B|A)=P(B)*P(A|B)$

and so:

$P(A)*P(B|A)=P(B)*P(A|B)$

Dividing both sides by P(B) gives us:

$P(A|B)=\frac{P(A)*P(B|A)}{P(B)}$

We call P(A) our prior belief. It represents our belief about the outcome before we see any test data. P(B|A) is our liklihood. It represents the probability of seeing our test data given some outcome is true. P(B) is our evidence. It represents the probability of seeing the data that we saw. Finally, P(A|B) is out posterior. It is our belief in the outcome given our prior beliefs and the data that we observed. This is called Bayes Theorem and is the under pinning of Bayesian Statistics.

To illustrate how to use this theorem, let's try calculating the probability that a card (from a standard deck) is a King given that it was a face card (jack, queen, king).

$p(King|Face)=\frac{p(Face|King)p(King)}{p(Face)}=\frac{1*(1/13)}{(3/13)}=1/3$

Let's try this theorem out with our coin flip problem. To spice things up and keep you interested, let's assume that we just saw 10 heads in a row! Wow, now that is weird.

First, let's define our prior assumptions. I don't know about you, but almost every coin I've encountered has been a fair coin (50% chance of heads). I therefore create a strong prior belief that the coin is fair (remember, I haven't flipped the coin yet! This is my belief with no data). However...I have this naging feeling that the coin might be unfair. Perhaps it dropped from a magician's pocket or it has some manufacturing imperfection. I therefore say that I am 97.9% certain that the probability of getting heads is 50%, I am 1% certain that the coin fell from a magicians pocket and is perfectly biased (always heads or tails), and that I am .1% sure that it has some other biasing imperfection.

$p(A)=0.979\delta(A-0.5)+0.01\delta(A)+0.01\delta(A-1)+0.001,$
$\delta$ is the dirac delta function

Next we calculate the liklihood. This is rather simple as it's the product of the outcome of each of our observations.

$p(B|A)=A^{n}$
n = # of trials

Finally we can put the evidence, P(B), in terms of the prior and the liklihood by integrating over every posible value of A. This is like calculating the probability of see the data that we did given every possible bias of the coin.

$P(B)={\int_0^1 p(B,A)}dA={\int_0^1 p(B|A)p(A)dA}={\int_0^1 A^{10}p(A)dA}$

Let's put it all together:

$p(A|B)=\frac{p(B|A)p(A)}{\int_0^1 p(B|A)p(A)dA} = \frac{A^{10}p(A)}{\int_0^1 A^{10}p(A)dA}.$

And we can now solve for our belief:

$\begin{multline} \int_0^1 A^{10}p(A)dA=0.979\cdot0.5^{10}+0.01\cdot 1^{10}+0.01 \cdot 0^{10} • 0.001\int_0^1 A^{10}dA = 9.56\cdot 10^{-4} + 0.01 + 9.09\cdot 10^{-5}=0.0110 \end{multline}$

$p(A|B)=0.087\delta(A-0.5)+0.905\delta(A-1)+0.091A^{10}$

We now have our posterior belief. We are 90.5% sure that the coin will always return heads. We are 8.7% sure that the coin is fair and the data was just coincidence. And we are 0.8% sure that the coin has some other bias.

Now our posterior belief describes how certain we are that the coin is baised. How do we find the probability that the next flip will be heads? That part is simple, we calcualte the probability of getting heads given our data and belief that the coin is biased:

$\begin{multline} p(Heads|B) = \int_0^1 p(Heads|B,A)p(A|B)dA = \int_0^1 A \, p(A|B)dA = 0.087\cdot 0.5+0.905\cdot 1+0.091\cdot \int_0^1A^{11}dA = 0.956. \end{multline}$

After seeing 10 consecutive heads, we are 90.5% sure that the probability of getting heads is 100%. And after seeing 10 consecutive heads, we are 95.6% certain that we will see heads on the next flip. That is a lot of useful information!

Now these conclusions are heavily dependant on our prior beliefs. A Frequentist might challenge us to justify why our result should be impacted by our intuitions before observing data. It is up to us to identify a prior that makes sense and that we can defend infront of our peers.

In this case I used a very strong prior centered around 50% that had a reasonable impact on our posterior (look at that 8.7% belief), but I could have engineered a weak prior (such as a uniform distribution between 0 and 1) that would have had very little impact on the posterior. I rather like the prior that I used given that in real life it would take more than 10 consecutive observations of heads to make me believe that a coin was completely biased.

It's also worth noting that the more observations that we have, the more the liklihood will influence the posterior versus the prior. This makes sense. The more data we see, the more it will over power our previous beliefs.

It's interesting to consider how the frequentist would have reacted to the ten consecutive heads. The frequency of getting heads was 100%. The variance around that estimate was 0%. The Frequentist might say that they are 100% sure that they will get heads if they flip again. Does that seem right?

This problem illustrates a weakness in describing probability in terms of frequencies. As the number of trials decreases, the assumptions of Frequentist methodologies tend to break down. Now, to make sure I'm giving Frequentists a fair shake, it's worth noting that there are strategies for accounting for the degeneracies of low sample sizes (mentioned briefly in the last section) ...but in my opinion, they suspiciously resemble the injection of prior beliefs into the Fisher Information characteristic, so why not go all in on Bayes anyway?

Reference: Example by Roman Cheplyaka

###### Bayesians vs Frequentists (Cookie Example)¶

We just covered a lot of material. We dove deep into the Frequentist and Bayesian philosophies of probability. Additionally, we ran through simple coin flipping exercises to provide tagible examples of how each philosophy might be applied in practice. To make sure we really understand both approachs, we're going to run through another example.

My girlfriend loves chocolate-chip cookies! Who doesn't? She orders cookies from a particular baker that sells cookies in four different packages: A,B,C,D. Each package type contains cookies with different amounts of chocolate-chips. My girlfriend orders a new package every time we run out of cookies. Each package always has 100 cookies.

Over time, I collect data on the expectation of getting X number of chocolate-chips when I pull a random cookie out of a particular package type.

P(chips | package) A B C D
0 1 12 13 27
1 1 19 20 70
2 70 24 0 1
3 28 20 0 1
4 0 25 67 1
Total 100% 100% 100% 100%

The A package, as an example, has 70 cookies with two chips each, and no cookies with four chips or more. The D package has 70 cookies with one chip each. Since each column sums to one, each column is a probability mass function (pmf)for a particular package!

Now when my girlfriend brings home a new package of cookies I randomly take one cookie, count the chips, and try to express my uncertainty (at the 70% level) about what package she bought. I am trying to guess the identity of the package, so the package identity is the parameter being estiamted. The number of chips in the cookie I sampled is the outcome/observation.

Now the frequentist in me went straight to calculating 70% confidence intervals. Remember that chip count is my observable, so I construct my confidence intervals along the rows in my table. >=70% of the pmf of each column should be covered within my confidence intervals.

P(chips | package) A B C D
0 1 12 13 27
1 1 [19 20 70]
2 [70 24] 0 1
3 28 [20] 0 1
4 0 [25 67] 1
Total 100% 100% 100% 100%

For example, if the number of chips in the cookie I draw is 1, my confidence interval will be {B,C,D}. If the number is 4, my confidence interval will be {B,C}. Notice that since each column sums to 70% or greater, then no matter which column we are truly in (no matter which package my girlfriend bought), the interval resulting from this procedure will include the 'correct' jar with at least 70% probability based on the historical data.

Notice also that the procedure I followed in constructing the intervals had some discretion. In the column for type-B, I could have just as easily made sure that the intervals that included B would be 0,1,2,3 instead of 1,2,3,4. That would have resulted in 75% coverage for type-B jars (12+19+24+20), still meeting the lower bound of 70%.

The bayesian in me thought that this was rediculous. I was completely ignoring my girlfriend as part of the system! I should assume that the identity of the package is a random variable and that she chooses randomly when selecting packages (I have a prior belief that she doesn't care about chocolate chip density and so chooses randomly). Assuming she picks the package randomly, let's look at the joint probability of getting a particular package and pulling out a cookie wih a certain number of chips.

P(chips,package) A B C D Total
0 1/4 12/4 13/4 27/4 13.25%
1 1/4 19/4 20/4 70/4 27.50%
2 70/4 24/4 0/4 1/4 23.75%
3 28/4 20/4 0/4 1/4 12.24%
4 0/4 25/4 67/4 1/4 23.25%
Total 25% 25% 25% 25%

Before, each column was a probability mass function. Now, the whole table is the probability mass function! This happens because we now consider the probability of choosing a particular package as well as picking a particualr cookie.

I was previously looking at the conditional probability of the number of chips given the package. But what I really cared about was the conditional probability of which package she bought given the number of chips in the cookie I sampled.

Let's say that we found 3 chips in our cookie. We can ignore all rows except the 3 chip row and treat that particular row as the pmf. First, we rescale each row so the pmf sums to 100%.

P(package | chips) A B C D Total
0 1.9 22.6 24.5 50.9 100%
1 0.9 17.3 18.2 63.6 100%
2 73.7 25.3 0.0 1.1 100%
3 57.1 40.8 0.0 2.0 100%
4 0.0 26.9 72.0 1.1 100%

We've flipped the conditional probabilities we started out with! Now we're considering the probability that my girlfriend bought a particular package given the chips in the sampled cookie instead of the probability of the number of chips given a particular package.

We look at each row and highlight an interval representing 70% of that row's pmf. We call these 'credibility intervals' (the bayesian measure of uncertainty as opposed to frequentist confidence interval).

P(package | chips) A B C D Credibility
0 1.9 22.6 [24.5 50.9] 75%
1 0.9 17.3 [18.2 63.6] 82%
2 [73.7] 25.3 0.0 1.1 74%
3 [57.1 40.8] 0.0 2.0 98%
4 0.0 26.9 [72.0] 1.1 72%

Okay. Let's pause and consider the overlap of our confidence and credibility intervals.

Confidence A B C D Credibility
0 1 12 13 27 0%
1 1 [19 20 70] 99%
2 [70 24] 0 1 99%
3 28 [20] 0 1 41%
4 0 [25 67] 1 99%
Coverage 70% 88% 87% 70%
Credibility A B C D Credibility
0 1 12 [13 27] 75%
1 1 19 [20 70] 82%
2 [70] 24 0 1 74%
3 [28 20] 0 1 89%
4 0 25 [67] 1 72%
Coverage 98% 20% 100% 97%

Those confidence intervals are looking pretty crazy. For example, we don't even have a sensible prediction if we draw a cookie with no chips. Also consider the 3 chip scenario, our 70% confidence interval is only 'correct' 41% of the time, given past data...I wouldn't call that 70% confidence.

But the credibility intervals are a bit odd as well. The confidence intervals are right 70% of the time, given past data, agnostic of what package my girlfriend buys. Look at our credibility interval for package B. Our interval is wrong, based on past data, 80% of the time!

Under the bayesian approach, our mistakes will be correlated with the type of jar. If I send out 100 'Bayesian' robots to assess what type of package I have, each robot sampling one cookie, on type B days, I will expect 80 of the robots to get the wrong answer, each having >73% belief in its incorrect conclusion! That's troublesome, especially if I want most of the robots to agree on the right answer.

Plus we had to make the assumption that my girlfriend randomly picks packages! How well do I know that?

But if my assumption is correct that she does pick randomly, then type B packages happen only 25% of the time. Poor predictions for type B are balanced out by my good coverage of type A, C, and D packages. And, unlike the frequentist approach, I never publish nonsense if I pull out a zero chip cookie.

On the other hand, while it's true that my confidence interval does perform poorly when I've drawn a cookie with zero chips, so what? Chipless cookies happen, at most, 27% of the time in the worst case (a type D package). I can afford to give nonsense for this outcome because NO jar will result in a wrong answer more than 30% of the time, based on historical data.

Hopefully this example has helped explain some of the differences between the Bayesian and Frequentist approaches. If not, try re-reading the examples. These are complicated philosophies that become even more convoluted in practice. Take your time, take deep breathes, and try working through everything yourself step by step.

Reference: Example from Keith Winstein

###### Author's Note: Taking Sides¶

So right about now you might be asking, who is right? Since this course is called Bayes by Example, you might assume that I'm taking the Bayesian side. No! ... well, kind of. I definitely prefer the Bayesian approach. I'm skeptical of theoretical 'true' populations, embedded assumptions (as opposed to clearly stated priors), and unintuitive uncertainty measurements. However, Bayesian and Frequentist approaches will often yield very similar results and conclusions (if executed and interpreted correctly).

Additionally, as a physics major in a former life, I'm quite confortable with the inverse problem where we are given some data and asked to hypothesize the process by which it was generated. This slides in comfortably next to the Bayesian philosophy of hypothesizing sets (possibly infinite sets) of parameters and quantifying the probability that those parameters generated our data. We can visualize this conceptual difference below:

In machine learning the difference between the methodologies widens a bit. The bayesian philosophy has lead to radically different ways of thinking about model training and optimization, the bread and butter of machine learning, as well as ways of quantifying the uncertainties of model predictions.

At this point we drop the Frequentist point of view (with a few exceptions) and put on our Bayesian thinking caps. Throughout the rest of the course, we're going to go through a set of examples of how Bayesian statistics affects modern machine learning and data science.

In [ ]:

format: plain


text:
# Rotational Symmetry

What is rotational symmetry?

When the figure is turned about a fixed point; it is called rotation.

This rotation can be: (a) clockwise (b) anticlockwise

The fixed about which the figure is rotated is called centre of rotation.

The angle of turning during rotation is called the angle of rotation.

A quarter turn means a rotation of 90°

A half turn means a rotation of 180°

A full turn means a rotation of 360°

A figure is said to have rotational symmetry if it onto more than once during a complete rotation, i.e., 360°

`

Related Concepts


text:
Gaussian Function

In 1-D, the Gaussian function is the function from the Gaussian Distribution,

 (1)

sometimes also called the Frequency Curve. The Full Width at Half Maximum (FWHM) for a Gaussian is found by finding the half-maximum points . The constant scaling factor can be ignored, so we must solve
 (2)

But occurs at , so
 (3)

Solving,
 (4)

 (5)

 (6)

 (7)

The Full Width at Half Maximum is therefore given by
 (8)

In 2-D, the circular Gaussian function is the distribution function for uncorrelated variables and having a Gaussian Bivariate Distribution and equal Standard Deviation ,

 (9)

The corresponding elliptical Gaussian function corresponding to is given by
 (10)

The above plots show the real and imaginary parts of together with the complex absolute value .

The Gaussian function can also be used as an Apodization Function, shown above with the corresponding Instrument Function.

The Hypergeometric Function is also sometimes known as the Gaussian function.

See also Erf, Erfc, Fourier Transform--Gaussian, Gaussian Bivariate Distribution, Gaussian Distribution, Normal Distribution

References

MacTutor History of Mathematics Archive. Frequency Curve.'' http://www-groups.dcs.st-and.ac.uk/~history/Curves/Frequency.html.


text:
error in mathematical expression

I type in the code shown below for a displayed formula. However the output is not what it should be. Can you tell me what is the mistake over here?

$$\frac{(1-a)\frac{q_{f}}{{q_{n}}^a}}{p_{n}} \cdot q_{f} \cdot \Delta p$$

-
I removed the thanks (just the style here). Thanks is best expressed by upvoting helpful answers. –  qubyte May 19 '12 at 12:28

First of All, You can't nest $in $$. Therefore your formula should be like $$ \frac{(1-a)\frac{q_{f}}{{q_{n}}^a}}{p_{n}} \cdot q_{f} \cdot \Delta p $$ - Great, thanks!! – Abhimanyu Arora May 19 '12 at 12:41 Building on Hassan Zakeri's answer, you have two potential problems. As Hassan says, you can't nest. But it is also much better not to use $$ to start display maths. Here's a better solution: $\frac{(1-a)\frac{q_{f}}{{q_{n}}^a}}{p_{n}} \cdot q_{f} \cdot \Delta p$  For further explanation, please read this question and its answers: Why is [ … ] preferable to$\$?


text:
# Equivalent Resistance

What is the equivalent resistance $$R_{AZ}$$ in the circuit from $$A$$ to $$Z$$ ?

×

Problem Loading...

Note Loading...

Set Loading...


text:
## Tailored Overlap for Learning Under Distribution Shift

05 Oct 2022, 00:13 (modified: 29 Nov 2022, 02:52)NeurIPS 2022 Workshop DistShift PosterReaders: Everyone
Abstract: Distributional overlap is a critical determinant of learnability in domain adaptation. The standard theory quantifies overlap in terms of $\chi^2$ divergence, as this factors directly into variance and generalization bounds agnostic to the functional form of the $Y$-$X$ relationship. However, in many modern settings, we cannot afford this agnosticism; we often wish to transfer across distributions with disjoint support, where these standard divergence measures are infinite. In this note, we argue that tailored'' divergences that are restricted to measuring overlap in a particular function class are more appropriate. We show how $\chi^2$ (and other) divergences can be generalized to this restricted function class setting via a variational representation, and use this to motivate balancing weight-based methods that have been proposed before, but, we believe, should be more widely used.


text:
# Teenager solves Newton dynamics problem – where is the paper?

From Ottawa Citizen (and all over, really):

An Indian-born teenager has won a research award for solving a
mathematical problem first posed by Sir Isaac Newton more than 300
years ago that has baffled mathematicians ever since.

The solution devised by Shouryya Ray, 16, makes it possible to
calculate exactly the path of a projectile under gravity and subject
to air resistance.

This subject is of particular interest to me. I have been unable to locate his findings via the Internet. Where can I read his actual mathematical work?

Edit:
So has he written an actual paper, and if so, will anyone get to read it?

#### Solutions Collecting From Web of "Teenager solves Newton dynamics problem – where is the paper?"

In the document Comments on some recentwork by Shouryya Ray by Prof. Dr. Ralph Chil and Prof. Dr. Jürgen Voigt (Technische Universität Dresden), dated June 4, 2012 it is written:

Conducting an internship at the Chair of Fluid Mechanics at TU
Dresden, Shouryya Ray encountered two ordinary differential equations
which are special cases of Newton’s law that the derivative of the
momentum of a particle equals the forces acting on it. In the first
one, which describes the motion of a particle in a gas or fluid, this
force is the sum of a damping force, which depends quadratically on
the velocity, and the (constant) gravitational force.
$$\begin{eqnarray*} \dot{u} &=&-u\sqrt{u^{2}+v^{2}},\qquad u(0)=u_{0}>0 \\ \dot{v} &=&-v\sqrt{u^{2}+v^{2}}-g,\quad v(0)=v_{0}. \end{eqnarray*}\tag{1}$$ Here, $u$ and $v$ are the horizontal and
vertical velocity, respectively.

(…)

The second equation reads $$\ddot{z}=-\dot{z}-z^{3/2},\qquad z(0)=0,\dot{z}(0)=z_{1},\tag{2}$$ and describes the trajectory of the
center point $z(t)$ of a spherical particle during a normal collision
with a plane wall.
(…)

Let us come back to problem (1) which was the starting point of the media stories. In the context of Shouryya Ray’s work it was an unfortunate circumstance, that a recent article from 2007$^8$ claims that no analytical solution of problem (1) was known, or that it was known only in special cases, namely falling objects$^9$. This might have misled Shouryya Ray who was not aware of the classical theory of ordinary differential equations.
(…)

To conclude, Shouryya Ray has obtained analytic solutions of the problem (1), by transforming it successively to the problems (3)-(5), and by applying a recent result of D. Dominici in order to obtain a recursive formula for the coefficients of the power series representation of $\psi$. He then validated his results numerically. Given the level of prerequisites that he had, he made great progress. Nevertheless all his steps are basically known to experts and we emphasize that he did not solve an open problem posed by Newton.
(…)

We hope that this small text gives the necessary information to the mathematical community, and that it allows the community to both put in context and appreciate the work of Shouryya Ray who plans to start a career in mathematics and physics.

The function $\psi$ is given by

$$\psi (t)=(v_{0}-g\Psi (t))/u_{0},$$

where

$$\Psi (t)=\int_{0}^{t}\exp \left[ \int_{0}^{\tau }\sqrt{u^{2}(s)+v^{2}(s)}ds \right] d\tau .$$

PS. Also in Spanish the Francis (th)E mule Science’s News post El problema de Newton y la solución que ha obtenido Shouryya Ray (16 años) discusses these problems.

Here’s summmary of what I’m reading through the interwebs:

The original post is here

“The problem he solved is as follows:

Let $(x(t),y(t))$ be the position of a particle at time $t$. Let $g$ be the acceleration due to gravity and $c$ the constant of friction. Solve the differential equation:

$$(x”(t)^2 + (y”(t)+g)^2 )^{1/2} = c(x'(t)^2 + y'(t)^2 )$$

subject to the constraint that $(x”(t),y”(t)+g)$ is always opposite in direction to $(x'(t),y'(t))$.

Finding the general solution to this differential equation will find the general solution for the path of a particle which has a drag proportional to the square of the velocity (and opposite in direction). Here’s an explanation of how this differential equation encodes the motion of such a particle:

The square of the velocity is:

$$x'(t)^2 + y'(t)^2$$

The total acceleration is:

$$( x”(t)^2 + y”(t)^2 )^{1/2}$$

The acceleration due to gravity is g in the negative y direction. Thus the drag (acceleration due only to friction) is [the preceding should probably read “the impedance (acceleration due to friction plus gravity) is”]:

$$\bigg( x”(t)2 + (y”(t)+g)2 \bigg)(1/2)$$

Thus path of such a particle satisfies the differential equation:

$$( x”(t)^2 + (y”(t)+g)^2 )^{1/2} = c(x'(t)^2 + y'(t)^2 )$$

Of course, we also require the direction of the drag $(x”(t),y”(t)+g)$ to be opposite to the direction of the velocity $(x'(t),y'(t))$. Once we find the intial position and velocity of the particle, uniqueness theorems tell us its path is uniquely determined.”

The original post is here

“Here’s a forward solution (found by reverse-engineering the answer):

Consider a projectile moving in gravity with quadratic air resistance. The governing equations are

$$u’ = -a u \sqrt{ u^2 + v^2 }$$

$$v’ = -a v \sqrt{ u^2 + v^2 } – g$$

where $a$ is the coefficient of air resistance defined by $|F| = ma|v|^2$.

Cross-multiply and rearrange to find

$$a \sqrt{ u^2 + v^2 } (uv’-vu’) = gu’$$

Substitute $v = su$ and separate variables:

$$a \sqrt{ 1 + s^2} s’ = g\frac {u’}{u^3}$$

Integrate both sides to get the answer:

$$\frac g {u^2} + a \left(\frac{v \sqrt{ u^2 + v^2 }}{u^2} + \sinh^{-1}\left|\frac v u\right| \right)= C”$$

“From what I can tell from the image the solution in the image is implicit and was derived by Parker at NCSU in 1977. It is still impressing for a 16-year-old. Here’s the paper by Parker if anyone’s is interested.”

“Am I crazy… or is the equation not anywhere in the paper?”

“It isn’t the same equation, but there are solutions using the logarithm definition of inverse hyperbolic functions. The solution isn’t the same, but there’s an implicit solution too. It’s impressing because he found a way to solve the differential equation while Parker stopped at the hairy integral at the end of the “Exact Solutions” section. But yeah, my comment does look confusing, as the exact same equation isn’t there.”

“It was of little interest, thus nobody was really breaking their teeth on it.
But it still is amazing, especially at such a young age.”

“Exactly. This solution is implicit, therefore it has little use in actual calculations as you would need to numerically solve it in order to use it, you might as well solve the differential equation numerically directly. Exact solutions similar to the one presented here have been known since 1977 in a paper I posted in another thread. Anyway, the trick used to solve the ODE is quite clever, especially for a 16-year-old.”

Knowing some German helps. When you go to this page and you click the picture, it enlarges it.

You can see some math symbols above his right shoulder. That may be all we can get until he puts the text of his presentation on the web somewhere.

Here’s the full equation (also from the original site). It reads:

$$\frac{g^2}{2u^2}+\frac{\alpha g}2\left(\frac{v\sqrt{v^2+u^2}}{u^2}+\mathrm{arsinh}\,\left|\frac{v}u\right|\right)=\mathrm{const.}$$

Today I found this on arxiv.org Shouryya Ray Paper

It’s the official paper from Shouryya Ray:

An analytic solution to the equations of the motion of a point
mass with quadratic resistance and generalizations

Shouryya Ray · Jochen Frohlich

why did he write it two years later from his original solution ?


text:
Initial Velocity Question

by MaNiFeST
Tags: initial, velocity
 P: 36 Ok So if I were to launch a waterballoon with a waterballoon launcher VERTICALLY , how could I find out the Initial Velocity With OUT a stop watch? My other supplies include a meter stick
 P: 4,780 Are you familiar with conservation of energy?
 P: 36 This is for a lab at school and you get Extra Credit if you can figure out the first part without a stop watch. Would i have to weigh it? And sorry, im not familiar with conservation of energy
 P: 4,780 Initial Velocity Question Ok, are you familiar with the equations of motion?
 P: 36 I am familiar with the equations for angles ( sin, cos), displacement in X,Y , etc,, for constant/non constant velocities and Trajectories
 P: 4,780 Look through them and try to find one that involves the parameters you think are going to be important and post it.
 P: 36 This isnt really a homework question but w/e Thanks again
 P: 36 Well if I am shooting an object vertically then Displacment X will be 0m, and Vy = Vo * sin(90) because the degrees will be 90 VFy = 0 m/s Thats about all the variables i know atm Im unsure of which equation to use
 P: 4,780 Well, dont solve any equations yet, just look for some that might be useful, and well work from there.
 P: 36 Would this work VFy^2 = VOy^2 + 2a*Displacment Y
 P: 4,780 Aha, you are on to something. Keep going.
 P: 36 Displacment Y = {(Vo^2+sin(2*angle)} / g Only other one i know that doesnt involve time
 P: 4,780 where did this come from? You were on the right track before. Maybe you should take a closer look at your first equation.
 P: 36 its equation for X or Y displacment I am looking for Initial Velocity (Vo) and those two are the only ones that do not include time because i wont have a stop watch when doing this experiment
 P: 4,780 Yes, look at your first equation, and you tell me what each of those terms mean.
 P: 36 VFy^2 = VOy^2 + 2a*Displacment Y I am looking for Initial Velocity and not just VOy Final Velocity of Y = is 0 m/s in this case VOy^2 = is unknown a = 9.81m/s^2 in this case Displacment Y = is also unknown
P: 4,780
Ok, we need to get this terminology straight.

$$V_{fy}$$ means the final velocity in the y direction.

$$V_{oy}$$ means the initial velocity in the y direction.

Does this help at all?

 Final Velocity of Y = is 0 m/s in this case
Yes, that's correct. Now when does this occur?
 P: 36 VFy That occurs when the object stops right before it comes back down I Know what the terminology means,

 Related Discussions Introductory Physics Homework 3 Introductory Physics Homework 9 Introductory Physics Homework 1 Introductory Physics Homework 7 Introductory Physics Homework 1


text:
# Hebbian theory

Hebbian theory

Hebbian theory describes a basic mechanism for synaptic plasticity wherein an increase in synaptic efficacy arises from the presynaptic cell's "repeated" and "persistent" stimulation of the postsynaptic cell. Introduced by Donald Hebb in 1949, it is also called Hebb's rule, Hebb's postulate, and cell assembly theory, and states:

:Let us assume that the persistence or repetition of a reverberatory activity (or "trace") tends to induce lasting cellular changes that add to its stability.… When an axon of cell "A" is near enough to excite a cell "B" and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that "A"'s efficiency, as one of the cells firing "B", is increased.

The theory is often summarized as "cells that fire together, wire together", although this is an oversimplification of the nervous system not to be taken literally, as well as not accurately representing Hebb's original statement on cell connectivity strength changes. The theory is commonly evoked to explain some types of associative learning in which simultaneous activation of cells leads to pronounced increases in synaptic strength. Such learning is known as Hebbian learning.

Hebbian engrams and cell assembly theory

Hebbian theory concerns how neurons might connect themselves to become engrams. Hebb's theories on the form and function of cell assemblies can be understood from the following:

:"The general idea is an old one, that any two cells or systems of cells that are repeatedly active at the same time will tend to become 'associated', so that activity in one facilitates activity in the other." harv|Hebb|1949|p=70

:"When one cell repeatedly assists in firing another, the axon of the first cell develops synaptic knobs (or enlarges them if they already exist) in contact with the soma of the second cell." harv|Hebb|1949|p=63

Gordon Allport posits additional ideas regarding cell assembly theory and its role in forming engrams, along the lines of the concept of auto-association, described as follows:

:"If the inputs to a system cause the same pattern of activity to occur repeatedly, the set of active elements constituting that pattern will become increasingly strongly interassociated. That is, each element will tend to turn on every other element and (with negative weights) to turn off the elements that do not form part of the pattern. To put it another way, the pattern as a whole will become 'auto-associated'. We may call a learned (auto-associated) pattern an engram." harv|Hebb|1949|p=44

Hebbian theory has been the primary basis for the conventional view that when analyzed from a holistic level, engrams are neuronal nets or neural networks.

Work in the laboratory of Eric Kandel has provided evidence for the involvement of Hebbian learning mechanisms at synapses in the marine gastropod "Aplysia californica".

Experiments on Hebbian synapse modification mechanisms at the central nervous system synapses of vertebrates are much more difficult to control than are experiments with the relatively simple peripheral nervous system synapses studied in marine invertebrates. Much of the work on long-lasting synaptic changes between vertebrate neurons (such as long-term potentiation) involves the use of non-physiological experimental stimulation of brain cells. However, some of the physiologically relevant synapse modification mechanisms that have been studied in vertebrate brains do seem to be examples of Hebbian processes. One such study reviews results from experiments that indicate that long-lasting changes in synaptic strengths can be induced by physiologically relevant synaptic activity working through both Hebbian and non-Hebbian mechanisms

Principles

From the point of view of artificial neurons and artificial neural networks, Hebb's principle can be described as a method of determining how to alter the weights between model neurons. The weight between two neurons will increase if the two neurons activate simultaneously; it is reduced if they activate separately. Nodes which tend to be either both positive or both negative at the same time will have strong positive weights while those which tend to be opposite will have strong negative weights. It is sometimes stated more simply as "neurons that fire together, wire together."

This original principle is perhaps the simplest form of weight selection. While this means it can be relatively easily coded into a computer program and used to update the weights for a network, it also prohibits the number of applications of Hebbian learning. Today, the term "Hebbian learning" generally refers to some form of mathematical abstraction of the original principle proposed by Hebb. In this sense, Hebbian learning involves weights between learning nodes being adjusted so that each weight better represents the relationship between the nodes. As such, many learning methods can be considered to be somewhat Hebbian in nature.

The following is a formulaic description of Hebbian learning: (note that many other descriptions are possible)

:$,w_\left\{ij\right\}=x_ix_j$

where $w_\left\{ij\right\}$ is the weight of the connection from neuron $j$ to neuron $i$ and $x_i$ the input for neuron $i$. Note that this is pattern learning (weights updated after every training example). In a Hopfield network, connections $w_\left\{ij\right\}$ are set to zero if $i=j$ (no reflexive connections allowed). With binary neurons (activations either 0 or 1), connections would be set to 1 if the connected neurons have the same activation for a pattern.

Another formulaic description is:

:$w_\left\{ij\right\} = frac\left\{1\right\}\left\{n\right\} sum_\left\{k=1\right\}^p x_i^k x_j^k,$ ,

where $w_\left\{ij\right\}$ is the weight of the connection from neuron $j$ to neuron $i$, $n$ is the dimension of the input vector, $p$ the number of training patterns, and $x_\left\{i\right\}^k$ the $k$th input for neuron $i$. This is learning by epoch (weights updated after all the training examples are presented). Again, in a Hopfield network, connections $w_\left\{ij\right\}$ are set to zero if $i=j$ (no reflexive connections).

A variation of Hebbian learning that takes into account phenomena such as blocking and many other neural learning phenomena is the mathematical model of Harry Klopf. Klopf's model reproduces a great many biological phenomena, and is also simple to implement.

Generalization and stability

Hebb's Rule is often generalized as

:$,Delta w_i = eta x_i y$,

or the change in the $i$th synaptic weight $w_i$ is equal to a learning rate $eta$ times the $i$th input $x_i$ times the postsynaptic response $y$. Often cited is the case of a linear neuron,

:$,y = sum_j w_j x_j$,

and the previous section's simplification takes both the learning rate and the input weights to be 1. This version of the rule is clearly unstable, as in any network with a dominant signal the synaptic weights will increase or decrease exponentially. However, it can be shown that for "any" neuron model, Hebb's rule is unstable. Therefore, network models of neurons usually employ other learning theories such as BCM theory, Oja's rule [cite web |url=http://nba.uth.tmc.edu/homepage/shouval/Hebb_PCA.ppt |title=The Physics of the Brain |accessdate=2007-11-14 |last=Shouval |first=Harel |coauthors= |date=2005-01-03 |work=The Synaptic basis for Learning and Memory: A theoretical approach |publisher=The University of Texas Health Science Center at Houston] , or the Generalized Hebbian Algorithm.

ee also

* Neural Networks
* BCM theory
* long-term potentiation
* memory
* Tetanic stimulation
* Coincidence Detection in Neurobiology
* Metaplasticity

References

*
*
*
*
*
*

* [http://diwww.epfl.ch/~gerstner/SPNM/node71.html Overview]
* Hebbian Learning tutorial ( [http://blog.peltarion.com/2006/05/11/the-talented-dr-hebb-part-1-novelty-filtering Part 1: Novelty Filtering] , [http://blog.peltarion.com/2006/06/20/the-talented-drhebb-part-2-pca/ Part 2: PCA] )

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Anti-Hebbian learning — In neuroethology and the study of learning, anti Hebbian learning describes a particular class of learning rule by which synaptic plasticity can be controlled. These rules are based on a reversal of Hebb’s postulate, and therefore can be… …   Wikipedia

• BCM theory — BCM theory, BCM synaptic modification, or the BCM rule, named for Elie Bienenstock, Leon Cooper, and Paul Munro, is a physical theory of learning in the visual cortex developed in 1981. Due to its successful experimental predictions, the theory… …   Wikipedia

• Generalized Hebbian Algorithm — The Generalized Hebbian Algorithm (GHA), also known in the literature as Sanger s rule, is a linear feedforward neural network model for unsupervised learning with applications primarily in principal components analysis. First defined in 1989cite …   Wikipedia

• Long-term potentiation — (LTP) is a persistent increase in synaptic strength following high frequency stimulation of a chemical synapse. Studies of LTP are often carried out in slices of the hippocampus, an important organ for learning and memory. In such studies,… …   Wikipedia

• Metaplasticity — is a term originally coined by W.C. Abraham and M.F. Bear to refer to the plasticity of synaptic plasticity. Until that time synaptic plasticity had referred to the plastic nature of individual synapses. However this new form referred to the… …   Wikipedia

• Gaussian adaptation — Articleissues citations missing = July 2008 COI = y expert = Mathematics notability = July 2008 jargon = July 2008 OR = September 2007 primarysources = July 2008 technical = July 2008Gaussian adaptation (GA) is an evolutionary algorithm designed… …   Wikipedia

• Models of neural computation — are attempts to elucidate, in an abstract and mathematical fashion, the core principles that underlie information processing in biological nervous systems, or functional components thereof. This article aims to provide an overview of the most… …   Wikipedia

• Donald O. Hebb — Donald Olding Hebb Born July 22, 1904(1904 07 22) Chester, Nova Scotia, Canada …   Wikipedia

• Coincidence detection in neurobiology — For the electronic device, see Coincidence circuit. Coincidence detection in the context of neurobiology is a process by which a neuron or a neural circuit can encode information by detecting the occurrence of timely simultaneous yet spatially… …   Wikipedia

• Sound localization — refers to a listener s ability to identify the location or origin of a detected sound in direction and distance. It may also refer to the methods in acoustical engineering to simulate the placement of an auditory cue in a virtual 3D space (see… …   Wikipedia


text:
## Linear Algebra and Its Applications, Exercise 3.1.3

Exercise 3.1.3. In the $x$$y$ plane two lines are perpendicular if the product of their slopes is -1. Use this fact to derive the condition for two vectors $(x_1, x_2)$ and $(y_1, y_2)$ being orthogonal.

Answer: The line through the origin and $(x_1, x_2)$ has slope $x_2/x_1$ and the line through the origin and $(y_1, y_2)$ has slope $y_2/y_1$. If the two lines are perpendicular we have

$(x_2/x_1)(y_2/y_1) = -1$

Multiplying both sides of the equation by $x_1y_1$ we have

$x_2y_2 = -x_1y_1$

or

$x_1y_1 + x_2y_2 = 0$

which is the condition for the two vectors $(x_1, x_2)$ and $(y_1, y_2)$ being orthogonal.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

This entry was posted in linear algebra and tagged . Bookmark the permalink.


text:
### galen_colin's blog

By galen_colin, 24 hours ago, ,

Hi everyone! I've gotten a few recommendations to start screencasting/making video solutions, and I was initially reluctant, but I realized it's kinda fun to do it. I've started out by screencasting today's Div. 3 and explaining my solution ideas at the end, arguably a bit awkwardly, but I'll get better as I get more experience with it. There are, of course, other awesome youtubers like SecondThread who do the same thing (and better), but I figured the more resources, the better for everyone.

Anyway, my first video is here. The quality's a bit bad for this one, but I know how to fix it for the future so it's just a one-time thing. In this video, you can see me spending too much time on C and F, watching my rank falling over time, and somehow still placing 14th with no mistakes. Enjoy!

As it's my first video, some of the explanations may be confusing (especially F). If you have questions about them or just feedback in general, feel free to leave comments (preferably on this blog, since there's math mode here). Expect more screencasts for the upcoming Div. 2's, contests on other sites like AtCoder and maybe CodeChef, and probably algorithm tutorials in the future.

edit: jesus christ, 100 subs in less than a day. You guys are insane, and I love you all!

• +131

By galen_colin, 10 days ago, ,

I've found that an interesting way to waste pass time is by watching the standings as rounds happen. As far as I know, there are mainly three ways to do this:

• Watch a contest as it happens
• Watch a contest as system tests run
• Virtually participate, and watch standings that way

Obviously, the first two are time-dependent and won't work for past contests. The third option is more viable, but it both introduces meaningless data into the CF system and also forces you to watch with ICPC rules, which is inaccurate and doesn't work for other scoring systems. There's also no way to rewind, you have to watch in real-time, etc. It should be easier than that. And now it is!

I introduce you to Contest Replay — a simple website that will let you "watch" a contest's standings at any point in time. You can also target a user and watch their ranking instead of the overall leaderboard, as well as customize a ton of things to your preference. I've kept it mostly consistent with CF's design because it's nice and classic.

There are also some cool results you can find from watching past rounds — for example, in round 632 (id 1333), some troll held first place in official standings from 1:20 to 1:25 without having solved problem B!

A note: you'll have to pause "autoplay" and press Enter to change some of the settings because I'm bad at UI design. Sorry about that. Also, try not to enter invalid values.

If the thing crashes, anything about the site is unclear, or you have suggestions, feel free to comment below.

Some things I plan to implement:

• API key support — this means "friends standings", viewing private groups/contests, and more.
• Similar to "friends standings", an option to track just a subset of users.
• Data validation, so it won't crash so easily
• Support for IOI contests (might be simple, but it seems like it won't be)
• Leaderboard improvement (distinguishment between systest/hack/pretest fails, also make the "-x" that show up when a problem is never solved consistent with the current time)
• The two things above both require requesting all of the submissions made for the contest. This might be too much.

The site's hosted on repl.it, and you can view the source code at the repl here. It's... not exactly great, but you can see it if you want to.

This blog post is way too long already, but one final thing: autoplay works with negative numbers :)

UPD #1: major changes — API key support and friends standings. Also, a changelog so I don't have to update the blog for small changes; you can find it on the footer.

It also seems like it doesn't work for the edu round today. I think this is because people have changed their handles after competing. On the leaderboard, it shows their old handles, but since they've changed, the API thinks I'm requesting an invalid handle and returns a 400 error. Not really sure what to do about this.

Looks like the issue with the edu resolved itself — maybe handles auto-fix themselves on the standings given time, or there was some manual configuration involved. Anyway, if you see again that it gets permanently stuck on "Loading handles... ", that probably means something is wrong. An error message should pop up, but it may not (more bad UI design).

• +243

By galen_colin, 3 weeks ago, ,
A1
A2
B
C
D
E

Some notes/backstory about the round in general:

• Sorry about the mistake in C! I hope it didn't affect you too much, if at all. You can blame this on my bad organization — a tester did actually catch this mistake, but somehow I forgot to correct it.
• The only tester feedback I received besides corrections was to swap the problems C and D. Based on the solve counts, I guess it worked out.
• A lot of people received WA17 or WA20 on D because of not making the default values in the array small enough. With $0$ as the default, you'd get WA17. Others, who used $-10^9$ or $-10^{10}$, got WA20. I actually made this mistake myself, and my brute-force didn't catch it because it only seemed to happen with large enough $n, k$.
• I was skeptical about placing E at the end because of how simple the solution was, but that seems like it was a good choice now.
• I understand criticism about the problems being too "standard" — in fact, I'm not really proud of having a problem like D, but I thought it was necessary for balance (turns out it wasn't anyway). At the very least, they could serve to teach people new algorithms.

Tutorial of Testing Round #XVII

• +33

By galen_colin, 3 weeks ago, ,

Since the two failures of the contests last weekend, a lot of people have expressed that they want to help Codeforces in some way, but there isn't much many of us can actually do about the system. At the same time, there have also been a lot of (reasonable) requests for a testing round before round 656. So let's put those two together. Why don't we set some potential testing rounds? Maybe they should be rated, maybe they shouldn't, but in any case, they should be interesting enough to draw in participants like normal rounds do. It's probably not a good idea to "sacrifice" rounds not rated for Div. 1, as some have suggested, because that still wastes the efforts of the setters. So what I'm suggesting is that we prepare rounds with the specific intent of them being testing rounds.

• If these rounds are unrated, there's much less pressure for original/novel problems (and probably fewer problems will be rejected), so more of these rounds will be able to be prepared
• On this same point, it's a great entry point for new problemsetters: rounds are easier to prepare and there will likely be fewer participants (meaning it's easier to manage during the contest)
• It reduces pressure on MikeMirzayanov and the Codeforces team
• You get more problems to solve!

• If problems are of lower quality, then they might pollute CF! But there's a simple solution to this: if this becomes an issue, just don't add the problems to "Problemset"
• People would be preparing rounds with a larger chance of the whole round failing! While this is true, these rounds support CF in a different way: they test its infrastructure. And it's not like the whole round is wasted if something goes wrong — after all, that's what we possibly expect from a testing round.

I think it would help, and some testing round would especially be necessary before round 656. So... I'm not one to just throw around words. I have a few problems of my own prepared (not the most "novel", but they should be somewhat educational — I tried to include some common topics, as people have been wanting lately), and am willing to offer them to a testing round. I'll probably host it in the gym, unless it becomes an "official" testing round, and I've adjusted the constraints/time limits to take longer per test case to better simulate the judge pressure of an actual round, since there will likely be fewer people.

Tentatively (it's still in the testing phase, so things may change), there will be 5 problems and the round will last 2 hours. Expect the difficulty to be around Div. 3, maybe somewhat easier. When it's ready, I'll post it in the gym.

I think a good time to schedule it would be around a day before the upcoming round 656, perhaps at the time that Monogon's round was to be held before it was rescheduled. So for now, it will be held at this time (later changed to 1 hour earlier — ignore this link).

UPD: you can now view the contest in the gym. Registration opens 6 hours before it starts, which I don't think I have control over. It will start at Jul/16/2020 16:35 (Moscow time), which is 1 hour earlier than it was initially set to.

Thanks to 12tqian, meiron03, and Kaunta for testing. A special thanks to 12tqian for letting me theme the problems around him. And, of course, thanks to MikeMirzayanov for the awesome Polygon, the even more awesome Codeforces, and the platform issues so that this round can be possible :P

UPD 2: the scoring distribution is $(1 + 1) - 1 - 1 - 1 - 1$ (it's ICPC mode lol)

A is split into subtasks. A1 has a time limit of 15 seconds (maximum setting) with 20 tests, and I highly encourage submitting slow solutions that get close to TL. The rest of the problems have relatively normal constraints. If more people register than I expect, I'll lower these numbers.

If you really want to put load on the queue, you can stall your program until it gets close to 15 seconds. An example of this in C++:

code

Other languages have stuff like this too, you can check the documentation for it.

UPD 3: Editorial is out. I hope you enjoyed the round! It seems like there were way too few participants for it to be effective, though. I hope the div. 3 tomorrow goes well.

Congrats to the winners!

$~$ 1. Geothermal
$~$ 2. Andreii
$~$ 3. Lumberjackman
$~$ 3. NotGivingUp
$~$ 5. komiel

And an honorable mention to Ashwathama and erekle for full-solving.

Announcement of Testing Round #XVII

• +257

By galen_colin, history, 6 weeks ago, ,

Hi everyone! I'm writing this blog to hopefully throw out a bit of inspiration.

With any measure of skill such as rating, people are always going to tie up their self-confidence with it. Unfortunately, that means when rating is lost, people lose confidence and/or motivation, which always sucks, especially with huge rating losses that seem impossible to overcome. But I want to demonstrate with an example that in the long run, even the largest rating losses won't affect much.

We'll use my performance on Global Round 7 as an example. A whopping -166*. Devastating, right? Well, let's see about that...

Let's look at the alternate timeline where I didn't participate in the round and the rating loss never happened (but my performance in the later contests was the same). Thanks to sjsakib and cfviz for allowing me to break the rules of the universe (probably not an intended use case, but you never know with users...).

• +446

By galen_colin, history, 2 months ago, ,

Author's editorial

This is a duplicate of my comment here. I've gotten a couple of requests to make it a blog (for some reason), so here it is. Note: this is unofficial, I was just a competitor

A
B
C
D
E
F

• +25

By galen_colin, 4 months ago, ,

If you failed on test 66 on (this problem | div2 version), you probably haven't reset enough of your array in between. This problem gives rise to a very unique type of bug, since we access the array beyond the part where we initially read elements into. What I mean is, if you have a large case followed by a small one, on the small one, you'll read the first $2^n - 1$ elements in, but the elements in indices $2^n$ to $2^{n+1}-1$ may also be filled with values from the last test case. Many people adapted the function definition from the problem statement, treating an index like a leaf iff the two elements 'below' it (i.e. $a_{2i}$ and $a_{2i+1}$) are both $0$. But if the array isn't reset, then values that are supposed to be leaves may be treated differently. Unfortunately, I made this mistake too :(

Not resetting the state between test cases is common. But this is a very unique type of mistake, specific to this problem. I don't think it's reasonable to blame the setter for overlooking this in the pretests. Surprising that none of the testers made this same mistake, though...


text:
# Age of Universe (estimated)

Not Reviewed
"Age"_"(Universe)" =
Tags:
Rating
ID
MichaelBartmess.Age of Universe (estimated)
UUID
3df48781-7f90-11e6-9770-bc764e2038f2

This vCalc equation provides the estimated age of the universe, along with the upper and lower bounds of error in that estimate.


text:
Question

# Perxenate ion is:A.$Xe{O_6}^{4 - }$B.$HXe{O_4}^ -$C.$Xe{O_4}^{2 - }$D.$Xe{O_4}^ -$

Hint: Perxenate belongs to compounds of xenon having the valency of xenon more than eight. They are also referred to as hypervalent compounds of xenon. They exhibit octahedral geometry.

Step by step solution:
Perxenates are oxides of xenon compounds. They are the anions having octahedral geometry. They are yellow in colour. The $Xe - O$ bond length is $1.875{\text{ }}{A}$ as measured using X-ray crystallography. The bond angles of $O - Xe - O$ vary in the range of $87^\circ$ to $93^\circ$. The molecular formula of perxenate ion is $Xe{O_6}^{4 - }$ .
The correct answer is A i.e. $Xe{O_6}^{4 - }$. The structure of perxenate ion can be shown as:

The valence electrons of $Xe$ are eight so the covalency of $Xe$ is eight. The number of hybrid orbitals is equal to six (six bond pairs + zero lone pairs). Therefore, the hybridization of $Xe{O_6}^{4 - }$ is $s{p^3}{d^2}$. As seen in the structure two oxygen atoms form double and four oxygen atoms form single for fulfilling the octet.
The perxenate ion is produced by treating xenon trioxide with strong alkali.
$2Xe{O_3}(s) + 4O{H^ - }\xrightarrow{{}}Xe(g) + Xe{O_6}^{4 - }(aq) + {O_2}(g) + 2{H_2}O(l)$
Perxenate ions are strong oxidizing agents and can oxidize a variety of metals like silver, copper and manganese. They are reduced to $HXe{O_4}^ -$ in presence of acids.
$HXe{O_4}^ -$ are known as xenates. They are prepared by the reaction of xenon trioxide with aqueous hydroxides. Actually they are the intermediates during the formation of perxenate. The xenon trioxide reacts with hydroxide ion to give xenates which on further reaction with hydroxide ion to yield perxenate.
$Xe{O_3}(aq) + 2O{H^ - }(aq)\xrightarrow{{}}2HXe{O_4}^ - (aq)$
$2HXe{O_4}^ - (aq) + 2O{H^ - }(aq)\xrightarrow{{}}Xe{O_6}^{4 - }(aq) + Xe(aq) + {O_2}(g) + 2{H_2}O(l)$
$Xe{O_4}$ is one of the existing oxides of xenon, but $Xe{O_4}^{2 - }$ and $Xe{O_4}^ -$ do not exist.

Note: Perxenates should not be confused with peroxides of xenon. Perxenate does not contain any peroxide linkages. Perxenates only have single and double bonds with oxygen atoms.


text:
# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Mechanism of flow instability and transition to turbulence. (English) Zbl 1160.76353
Summary: A new mechanism of flow instability and turbulence transition is proposed for wall bounded shear flows. It is stated that the total energy gradient in the transverse direction and that in the streamwise direction of the main flow dominate the disturbance amplification or decay. Thus, they determine the critical condition of instability initiation and flow transition under given initial disturbance. A new dimensionless parameter $K$ for characterizing flow instability is proposed which is expressed as the ratio of the energy gradients in the two directions for the flow without energy input or output. It is suggested that flow instability should first occur at the position of ${K}_{max}$ which may be the most dangerous position. This speculation is confirmed by Nishioka et al.’s experimental data. Comparison with experimental data for plane Poiseuille flow and pipe Poiseuille flow indicates that the proposed idea is really valid. It is found that the turbulence transition takes place at a critical value of ${K}_{max}$ of about 385 for both plane Poiseuille flow and pipe Poiseuille flow, below which no turbulence will occur regardless the disturbance. More studies show that the theory is also valid for plane Couette flows which holds a critical value of ${K}_{max}$ of about 370.
##### MSC:
 76F06 Transition to turbulence
##### Keywords:
instability; transition; turbulence; energy gradient; energy loss


text:
So reading about how it's impossible to accelerate an object to the speed of light relative to another, I thought of this hypothetical situation:

What if you had this row of rocks, floating in space at the speed of 10m/s relative to another row of rocks (let's call the rocks going at 10 m/s row 2, and the ones floating at a relative speed of -10m/s row 1). In this situation, let's say these "rows" are infinite. Then you get another row of rocks and accelerate it to the speed of 10m/s relative to row 2 (row 3). Now row 3 should have a speed of 100 m/s relative to row 1, right? If you continue this, until you have a row going at the speed of 100 000 000m/s relative to row 1, and you get another row and get it to go at a speed of 10m/s relative to that, would it not be moving away from row 1 at a speed greater than the speed of light?. Because relative to row 2, it would just be going at 1/3 of the speed of light, and that should be possible.

Or what about this, you have this row going at a speed of 100 000 000m/s relative to row 1, and then you accelerate row 1 by 10m/s in the opposite direction. What would happen then? Because the speed at which they are moving away from the rock rows with the "in between speeds" is FACT. Isn't it?

• You are aware of how velocities add in special relativity? – mikuszefski May 12 '17 at 5:41
• Where did you get 100 m/s from? In non-relativistic mechanics, row 3 would be moving at (10 m/s + 10 m/s) = 20 m/s relative to row 1. Using Special Relativity, the relative speed would be a tiny bit slower: a shade under 19.999999999999977747 m/s. – PM 2Ring May 12 '17 at 12:34
• Oh right, I think I forgot how to add velocities there, thanks! ...although, on second thought, I'm not sure I agree... If the rocks are situated 1 meter apart that would mean that the row (row 2) going at 10m/s passes 10 rocks in 10 seconds. Then you have row 3 which passes 10 of row 2's rocks every 10 seconds. Wouldn't that make for a relative speed of 100 m/s? – E. Holm May 12 '17 at 22:07

In special relativity velocities don't add linearly. Suppose you have a Person $T$ sitting in a train and a person $S$ standing next to the rails at a train station. Person $S$ will say that the train moves with some velocity $v$ and person $T$ will say that the train station moves with velocity $-v$. Now, if person $T$ stood up and walked along the train (in the direction in which the train is moving), how fast would $T$ move according to $S$?

You assumed the Newtonian law of velocity addition: $v+u=v_T$ , where $u$ is the velocity of person $T$ relative to the train and $v_T$ is the velocity of person $T$ relative to $S$. For example, if the train was moving with $100 km/h$ and the person inside the train was walking with $3km/h$, the person standing at the train station would say that $T$ moves with $103km/h$.

According to special relativity, this law is false. The first postulate of special relativity is that light does always have the same velocity in every reference frame. So if person $T$ switched on a torch and pointed it in the direction of motion of the train, both $T$ and $S$ would say that the light was moving with $c$ (where $c=299,792,458 m/s$). But according to the law of velocity addition from above, the light would have velocity $v+c$ according to $S$ - which is false because it always moves with the same velocity no matter whom you ask.

The Einstein velocity addition formula is the correct way to calculate the velocity. It says that $v_T=\frac {v+u}{1+\frac{vu}{c^2}}$. In everday life, where velocities usually are much smaller compared to the speed of light, this formula reduces to the Newtonian law of velocity addition. In the case of our train $v_T\approx102.999971362km/h$ which is almost equal to $103km/h$. That's why you still can use the normal velocity addition formula when you are dealing with very small velocities - the error is neglegible. The velocity of the light emitted by the torch on the other hand is $c$ according to the formula above - the classical velocity addition formula gives a false result. Also notice that $v_t$ can never be equal to $c$ or be bigger. That's why the speed of light can't be attained by any object that has mass.

Now calculate the different speeds of the stones in your thought experiment using the correct velocity addition formula and you'll see that the speed of light will never be exceeded by your objects (although the involved velocities can become arbitrarily close to $c$).

The thing with special relativity is that the faster an object is moving away from the reference object, the slower the time seems to run for the speedy object. Because of this the speed at which it is flying away from anything else is always below the speed of light. Btw, expansion of space is not the same as moving away because it's not actualy moving trough space. Just the space and the object with it is being moved away.

• Oh, wait, so does that explain why you would need to add infinite energy to accelerate something to c? Because if the impuls on an object is F*t, and one second becomes longer and longer the faster you move, you would need to keep adding F forever eventually. Or am I getting this wrong... – E. Holm May 12 '17 at 22:14
• This is correct. – MaDrung May 18 '17 at 10:45


text:
knn1 {class} R Documentation

1-Nearest Neighbour Classification

Description

Nearest neighbour classification for test set from training set. For each row of the test set, the nearest (by Euclidean distance) training set vector is found, and its classification used. If there is more than one nearest, a majority vote is used with ties broken at random.

Usage

knn1(train, test, cl)

Arguments

 train matrix or data frame of training set cases. test matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case. cl factor of true classification of training set.

Value

Factor of classifications of test set.

References

Ripley, B. D. (1996) Pattern Recognition and Neural Networks. Cambridge.

Venables, W. N. and Ripley, B. D. (2002) Modern Applied Statistics with S. Fourth edition. Springer.

knn
train <- rbind(iris3[1:25,,1], iris3[1:25,,2], iris3[1:25,,3])


text:
# Chapter 10: Perimeter and Area

Difficulty Level: At Grade Created by: CK-12

## Introduction

Now that we have explored triangles, quadrilaterals, polygons, and circles, we are going to learn how to find the perimeter and area of each. First we will derive each formula and then apply them to different types of polygons and circles. In addition, we will explore the properties of similar polygons, their perimeters and their areas.

Chapter Outline

## Summary

This chapter covers perimeter and area of all the basic geometric figures. Perimeter and area are compared and calculated for rectangles, parallelograms, triangles, and then for composite shapes of those figures. The chapter then branches into perimeter and area for other special geometric figures, namely trapezoids, rhombuses, and kites, as well as similar polygons. The chapter wraps up with the circumference of circles and arc length followed by the area of a circle and the area of sectors and segments.

### Chapter Keywords

• Perimeter
• Area of a Rectangle: A=bh\begin{align*}A=bh\end{align*}
• Perimeter of a Rectangle P=2b+2h\begin{align*}P=2b+2h\end{align*}
• Perimeter of a Square: P=4s\begin{align*}P=4s\end{align*}
• Area of a Square: A=s2\begin{align*}A=s^2\end{align*}
• Congruent Areas Postulate
• Area of a Parallelogram: A=bh\begin{align*}A=bh\end{align*}.
• Area of a Triangle: A=12bh\begin{align*}A= \frac{1}{2} bh\end{align*} or A=bh2\begin{align*}A=\frac{bh}{2}\end{align*}
• Area of a Trapezoid: A=12h(b1+b2)\begin{align*}A=\frac{1}{2} h(b_1+b_2)\end{align*}
• Area of a Rhombus: A=12d1d2\begin{align*}A=\frac{1}{2} d_1 d_2\end{align*}
• Area of a Kite: A=12d1d2\begin{align*}A=\frac{1}{2} d_1 d_2\end{align*}
• Area of Similar Polygons Theorem
• π\begin{align*}\pi\end{align*}
• Circumference: C=πd\begin{align*}C=\pi d\end{align*} or C=2πr\begin{align*}C=2 \pi r\end{align*}
• Arc Length
• Arc Length Formula: length of ABˆ=mABˆ360πd\begin{align*}\widehat{AB}=\frac{m \widehat{AB}}{360^\circ} \cdot \pi d\end{align*} or mABˆ3602πr\begin{align*}\frac{m \widehat{AB}}{360^\circ} \cdot 2 \pi r\end{align*}
• Area of a Circle: A=πr2\begin{align*}A=\pi r^2\end{align*}
• Sector of a Circle
• Area of a Sector: A=mABˆ360πr2\begin{align*}A=\frac{m \widehat{AB}}{360^\circ} \cdot \pi r^2\end{align*}
• Segment of a Circle
• Perimeter of a Regular Polygon: P=ns\begin{align*}P=ns\end{align*}
• Apothem
• Area of a Regular Polygon: A=12asn\begin{align*}A=\frac{1}{2} asn\end{align*} or A=12aP\begin{align*}A=\frac{1}{2} aP\end{align*}

### Chapter Review

Find the area and perimeter of the following figures. Round your answers to the nearest hundredth.

1. square
2. rectangle
3. rhombus
4. regular pentagon
5. parallelogram
6. regular dodecagon

1. triangle
2. kite
3. isosceles trapezoid
4. Find the area and circumference of a circle with radius 17.
5. Find the area and circumference of a circle with diameter 30.
6. Two similar rectangles have a scale factor 43\begin{align*}\frac{4}{3}\end{align*}. If the area of the larger rectangle is 96 units2\begin{align*}96 \ units^2\end{align*}, find the area of the smaller rectangle.

Find the area of the following figures. Round your answers to the nearest hundredth.

1. find the shaded area (figure is a rhombus)

### Texas Instruments Resources

In the CK-12 Texas Instruments Geometry FlexBook, there are graphing calculator activities designed to supplement the objectives for some of the lessons in this chapter. See http://www.ck12.org/flexr/chapter/9695.

Show Hide Details
Description
Difficulty Level:
Authors:
Tags:
Subjects: