text:
# Fourier transform on finite groups

In mathematics, the Fourier transform on finite groups is a generalization of the discrete Fourier transform from cyclic to arbitrary finite groups.

## Definitions

The Fourier transform of a function ${\displaystyle f:G\rightarrow \mathbb {C} \,}$ at a representation ${\displaystyle \varrho :G\rightarrow GL(d_{\varrho },\mathbb {C} )\,}$ of ${\displaystyle G\,}$ is

${\displaystyle {\widehat {f}}(\varrho )=\sum _{a\in G}f(a)\varrho (a).}$

For each representation ${\displaystyle \varrho \,}$ of ${\displaystyle G\,}$, ${\displaystyle {\widehat {f}}(\varrho )\,}$ is a ${\displaystyle d_{\varrho }\times d_{\varrho }\,}$ matrix, where ${\displaystyle d_{\varrho }\,}$ is the degree of ${\displaystyle \varrho \,}$.

Let ${\displaystyle \varrho _{i}\,}$ be a complete set of inequivalent irreducible representations of ${\displaystyle G}$. Then the matrix entries of the ${\displaystyle \varrho _{i}}$ are mutually orthogonal functions on ${\displaystyle G}$.[1] Since the dimension of the transform space is equal to ${\displaystyle |G|}$, it follows that ${\displaystyle \sum _{i}d_{\varrho _{i}}^{2}=|G|}$.

The inverse Fourier transform at an element ${\displaystyle a\,}$ of ${\displaystyle G\,}$ is given by

${\displaystyle f(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left(\varrho _{i}(a^{-1}){\widehat {f}}(\varrho _{i})\right).}$

## Properties

### Transform of a convolution

The convolution of two functions ${\displaystyle f,g:G\rightarrow \mathbb {C} \,}$ is defined as

${\displaystyle (f\ast g)(a)=\sum _{b\in G}f(ab^{-1})g(b).}$

The Fourier transform of a convolution at any representation ${\displaystyle \varrho \,}$ of ${\displaystyle G\,}$ is given by

${\displaystyle {\widehat {f\ast g}}(\varrho )={\widehat {f}}(\varrho ){\widehat {g}}(\varrho ).}$

### Plancherel formula

For functions ${\displaystyle f,g:G\rightarrow \mathbb {C} \,}$, the Plancherel formula states

${\displaystyle \sum _{a\in G}f(a^{-1})g(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left({\widehat {f}}(\varrho _{i}){\widehat {g}}(\varrho _{i})\right),}$

where ${\displaystyle \varrho _{i}\,}$ are the irreducible representations of ${\displaystyle G.\,}$

## Fourier transform on finite abelian groups

Since the irreducible representations of finite abelian groups are all of degree 1 and hence equal to the irreducible characters of the group, Fourier analysis on finite abelian groups is significantly simplified. For instance, the Fourier transform yields a scalar- and not matrix-valued function.

Furthermore, the irreducible characters of a group may be put in one-to-one correspondence with the elements of the group.

Let ${\displaystyle {\widehat {G}}}$ be the set of group homomorphisms ${\displaystyle G\to \mathbb {C} ^{*}}$. This forms a group under point-wise multiplication. We may define the Fourier transform for finite abelian groups for an element ${\displaystyle f\in {\widehat {G}}}$ as the function ${\displaystyle {\widehat {f}}:{\widehat {G}}\to \mathbb {C} }$ given by

${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in G}f(a){\bar {\chi }}(a).}$

Note that the right-hand side is simply ${\displaystyle \langle f,\chi \rangle }$ for the inner product on the vector space of functions from ${\displaystyle G\,}$ to ${\displaystyle \mathbb {C} \,}$ defined by

${\displaystyle \langle f,g\rangle =\sum _{a\in G}f(a){\bar {g}}(a).}$

The inverse Fourier transform is then given by

${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$

Since ${\displaystyle G}$ is finite abelian, the irreducible characters of a group may be put into one-to one correspondence with elements of the group. If we fix an isomorphism of ${\displaystyle {\widehat {G}}\to G}$ for each ${\displaystyle g\in G}$, we may write ${\displaystyle \chi _{g}}$ for the character corresponding to ${\displaystyle g}$. Thus the Fourier transform can be rewritten as a function ${\displaystyle {\widehat {f}}:G\to \mathbb {C} }$.

${\displaystyle {\widehat {f}}(g)=\sum _{a\in G}f(a){\bar {\chi _{g}}}(a).}$

and the inverse is given by

${\displaystyle f(a)={\frac {1}{|G|}}\sum _{g\in G}{\widehat {f}}(\chi _{g})\chi (a).}$

Note that the inverse fourier transform is technically an element of ${\displaystyle {\widehat {\widehat {G}}}}$, but using the isomorphism from ${\displaystyle G}$ to ${\displaystyle {\widehat {G}}}$, we get an element of ${\displaystyle {\widehat {G}}}$ that equals ${\displaystyle f}$

A property that is often useful in probability is that the Fourier transform of the uniform distribution is simply ${\displaystyle \delta _{a,0},\,}$ where 0 is the group identity and ${\displaystyle \delta _{i,j}\,}$ is the Kronecker delta.

## Relationship with representation theory

There is a direct relationship between the Fourier transform on finite groups and the representation theory of finite groups. The set of complex-valued functions on a finite group, ${\displaystyle G}$, together with the operations of pointwise addition and convolution, form a ring that is naturally identified with the group ring of ${\displaystyle G}$ over the complex numbers, ${\displaystyle \mathbb {C} [G]}$. Modules of this ring are the same thing as representations. Maschke's theorem implies that ${\displaystyle \mathbb {C} [G]}$ is a semisimple ring, so by the Artin–Wedderburn theorem it decomposes as a direct product of matrix rings. The Fourier transform on finite groups explicitly exhibits this decomposition, with a matrix ring of dimension ${\displaystyle d_{\varrho }}$ for each irreducible representation.

## Applications

This generalization of the discrete Fourier transform is used in numerical analysis. A circulant matrix is a matrix where every column is a cyclic shift of the previous one. Circulant matrices can be diagonalized quickly using the fast Fourier transform, and this yields a fast method for solving systems of linear equations with circulant matrices. Similarly, the Fourier transform on arbitrary groups can be used to give fast algorithms for matrices with other symmetries (Åhlander & Munthe-Kaas 2005). These algorithms can be used for the construction of numerical methods for solving partial differential equations that preserve the symmetries of the equations (Munthe-Kaas 2006).

format: plain


text:
Search   Memberlist   Usergroups
 Page 1 of 1 [10 Posts]
Author Message
John Baez
science forum Guru Wannabe

Joined: 01 May 2005
Posts: 220

Posted: Thu Jun 29, 2006 9:05 pm    Post subject: Maximal entropy from Bayes' law?

I was walking on the beach with Chris Lee and James Dolan last
weekend, and we came across a problem about statistical inference.

Suppose we repeatedly observe a system in a well-understood but
stochastic way and get some frequency distribution of outcomes.
What's our best guess for the probability that the system is in a
given state? I'm hoping that under some conditions the Bayesian
approach gives results that match Jaynes' maximum entropy method.

Let's make the problem very finitistic to keep it simple.

Suppose X is a finite set of "states" and Y is a finite set
of "observation outcomes". Suppose we have a function

f: Y x X -> [0,1]

giving the conditional probability f(y|x) for the outcome of
an observation to equal y given that the system's state is x.

We can think of f as a "stochastic function" from states to
observation outcomes, sending each point of X to a probability
measure on Y. By linearity, f gives a map from probability measures
on X to probability measures on Y. I'll also call this f.

Given a probability measure q on Y, what's our best guess
for a probability measure p on X with f(p) = q? Assume such
a measure exists.

One approach is Jaynesian: maximize entropy! In other words,
look at the probability measures p with f(p) = q and choose
the p with maximum entropy.

Of course to define entropy we need a "prior" measure on X;
let's use counting measure. So, we are trying to maximize

sum_{x in X} p(x) ln(p(x))

over p satisfying the linear constraint f(p) = q. This is something
people know how to do.

Another approach is Bayesian: use Bayes' rule! The conditional
probability for any measurement outcome y given the state x is f(y|x).
Use counting measure on X as our "prior", and use Bayes' law to
update this prior when we do an observation and get the outcome y.

In fact, let's imagine that we keep doing observations, getting
outcomes distributed according to the probability measure q, and
use these to keep updating our probability measure on X. In the
limit of infinitely many observations, this measure should converge
(almost surely) to some fixed measure on X.

Do we get the same answer using both approaches?

If so, we might say we had a "derivation" of the maximal entropy
principle from Bayes' law... or vice versa.

Feel free to fix my question; my description of the Bayesian
approach is pretty sketchy, and I may have something screwed up.
Herman Rubin
science forum Guru

Joined: 25 Mar 2005
Posts: 730

Posted: Fri Jun 30, 2006 6:23 pm    Post subject: Re: Maximal entropy from Bayes' law?

In article <e81fac$29a$1@glue.ucr.edu>,
John Baez <baez@math.removethis.ucr.andthis.edu> wrote:
 Quote: I was walking on the beach with Chris Lee and James Dolan last weekend, and we came across a problem about statistical inference. Suppose we repeatedly observe a system in a well-understood but stochastic way and get some frequency distribution of outcomes. What's our best guess for the probability that the system is in a given state? I'm hoping that under some conditions the Bayesian approach gives results that match Jaynes' maximum entropy method. Let's make the problem very finitistic to keep it simple. Suppose X is a finite set of "states" and Y is a finite set of "observation outcomes". Suppose we have a function f: Y x X -> [0,1] giving the conditional probability f(y|x) for the outcome of an observation to equal y given that the system's state is x.

As Einstein said, we should make things as simple as
possible, but not too simple. This is too simple, as
it is quite difficult to come up with a real problem
with X finite.

 Quote: We can think of f as a "stochastic function" from states to observation outcomes, sending each point of X to a probability measure on Y. By linearity, f gives a map from probability measures on X to probability measures on Y. I'll also call this f.

Also, typically the function f is of a restricted type.
We generally assume that observations are independent,
or have some restricted type of dependence. Otherwise,

 Quote: Given a probability measure q on Y, what's our best guess for a probability measure p on X with f(p) = q? Assume such a measure exists. One approach is Jaynesian: maximize entropy! In other words, look at the probability measures p with f(p) = q and choose the p with maximum entropy. Of course to define entropy we need a "prior" measure on X; let's use counting measure. So, we are trying to maximize sum_{x in X} p(x) ln(p(x)) over p satisfying the linear constraint f(p) = q. This is something people know how to do.

But other than knowing how, why should we do this?

 Quote: Another approach is Bayesian: use Bayes' rule! The conditional probability for any measurement outcome y given the state x is f(y|x). Use counting measure on X as our "prior", and use Bayes' law to update this prior when we do an observation and get the outcome y.

Which Bayes rule? The counting measure on X, even if it is
finite, is rarely even a remotely reasonable prior. All
attempts to come it with reasonable "natural" priors seem
to fail at several points. I have given reasonable finite
examples where the universe would not be large enough to
contain the information needed for a reasonable prior.

Another approach is to consider consequences, and to try to
act in a consistent manner. In this case, it is well known
that only the product of loss and prior is relevant to the
action to be taken. More than this cannot be done except
by fiat; one can use conditional measures, and they are
always probability measures. See my paper in _Statistics
and Decisions_, 1987, for a weak set of axioms, and why
the two factors cannot be separated.

With this, maximum entropy is NOT consistent, as the prior
changes with the type of observation. A self-consistent
approach must use the SAME prior on x, regardless of which
f is considered.

 Quote: In fact, let's imagine that we keep doing observations, getting outcomes distributed according to the probability measure q, and use these to keep updating our probability measure on X. In the limit of infinitely many observations, this measure should converge (almost surely) to some fixed measure on X. Do we get the same answer using both approaches?

This requires that Y change with each additional observation,
or that only part of Y is observed. Both of these can be
handled, and they give different results with maximum
entropy, although not with a particular Bayes prior.

And yes, in the limit with infinitely many identically
distributed observations with finite X, if the f's are
all different, anything which does not exclude some
elements of X works. With infinitely many, there are
problems, but if the problem is simple enough, again
just about anything works. But as the complexity
increases, the prior becomes more important, and I am
unaware of situations where "objectivity" can be used
to get reasonable results for reasonable sized samples,
say 10^10 or so.

 Quote: If so, we might say we had a "derivation" of the maximal entropy principle from Bayes' law... or vice versa. Feel free to fix my question; my description of the Bayesian approach is pretty sketchy, and I may have something screwed up.

The Bayesian approach is to use SOME prior (and loss) in
combination. The prior to use must not depend on the
distribution f of the observations, as "maximum entropy"
does. If some cases with densities, maximum entropy can
even give what are known to be bad results, as the maximum
entropy distribution, which needs constraints, will not
have the right properties.

There are many ways to show that all self-consistent
procedures are at least approximately Bayesian. However,
it is generally the case that attempting to come up with
"natural" priors leads to difficulties, some of which can
be quite serious. This is a hard problem.

To give an example, suppose one is interested in testing
whether a parameter is within a distance q of 0. Set up
a loss-prior combination. Assume the sample size is large
enough that normality of the observations can be assumed.
I have discussed the problem, and there are things which I
can recommend, but not covering all cases.

--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
John Baez
science forum Guru Wannabe

Joined: 01 May 2005
Posts: 220

Posted: Sat Jul 01, 2006 7:48 am    Post subject: Re: Maximal entropy from Bayes' law?

In article <e83q7p\$4i8o@odds.stat.purdue.edu>,
Herman Rubin <hrubin@stat.purdue.edu> wrote:

 Quote: In article , John Baez wrote: Let's make the problem very finitistic to keep it simple. Suppose X is a finite set of "states" and Y is a finite set of "observation outcomes". Suppose we have a function f: Y x X -> [0,1] giving the conditional probability f(y|x) for the outcome of an observation to equal y given that the system's state is x. As Einstein said, we should make things as simple as possible, but not too simple.

In math, a question can only be too simple if you already know

 Quote: This is too simple, as it is quite difficult to come up with a real problem with X finite.

That's okay. I'm trying to understand the answer to
the very simplest case of a class of conjectures before
tackling harder and more interesting ones.

 Quote: We can think of f as a "stochastic function" from states to observation outcomes, sending each point of X to a probability measure on Y. By linearity, f gives a map from probability measures on X to probability measures on Y. I'll also call this f. Also, typically the function f is of a restricted type. We generally assume that observations are independent, or have some restricted type of dependence. Otherwise, little progress can be made.

That's okay - I just want to know whether my conjecture is
true, false, or if there's some actual logical inconsistency
in my statement of it.

 Quote: One approach is Jaynesian: maximize entropy! In other words, look at the probability measures p with f(p) = q and choose the p with maximum entropy. This is something people know how to do. But other than knowing how, why should we do this?

As you probably know, there's a vast literature on this
issue starting with Jaynes' book:

http://omega.albany.edu:8008/JaynesBook.html

or in some sense even the work of Boltzmann and Gibbs.
It's fascinating and controversial.

But it's sort of no fair, when someone states a mathematical conjecture
claiming that the left-hand of some putative equation equals the
right-hand side, to ask "but why should we compute the left-hand side?"

 Quote: Another approach is Bayesian: use Bayes' rule! The conditional probability for any measurement outcome y given the state x is f(y|x). Use counting measure on X as our "prior", and use Bayes' law to update this prior when we do an observation and get the outcome y. Which Bayes rule?

I think there's a rule which says how to compute the posterior
probability for an event x if you 1) know the probability of y
given x, 2) know the probability of y, and 3) have chosen a
prior probability for x:

http://en.wikipedia.org/wiki/Bayes'_rule

definitely like to know.

 Quote: The counting measure on X, even if it is finite, is rarely even a remotely reasonable prior.

That's okay. I'm trying to state the simplest possible
case of a class of conjectures, so I'm taking the simplest
possible prior. If the conjecture turns out to be true,
then I can see if it's still true with a more general class
of priors.

 Quote: All attempts to come it with reasonable "natural" priors seem to fail at several points.

Right. I'm just choosing some completely stupid prior in
order to keep the problem simple.

 Quote: In fact, let's imagine that we keep doing observations, getting outcomes distributed according to the probability measure q, and use these to keep updating our probability measure on X. In the limit of infinitely many observations, this measure should converge (almost surely) to some fixed measure on X. Do we get the same answer using both approaches? This requires that Y change with each additional observation, or that only part of Y is observed.

Okay, now you're tackling my question! Great!

But, I'm not sure I get your point. I'm definitely keeping Y fixed.
I'm letting the observation outcome y in Y depend in a stochastic
way on the state x in X. So, even if I fix a particular state x,
and keep doing observations, I'll keep getting different results y;
they'll be distributed with probabilities f(y|x). I guess I
should have said that they're independently distributed! Sorry.

So, for example, I could have a 6-sided die, so

X = {1,2,3,4,5,6}

and you could ask me if the number on it is even or odd, so

Y = {0,1}

and I could look at the die and tell you the correct answer with
probability 3/4 and the wrong answer with probability 1/4 -
say I'm not very good at this even vs. odd business, or I've
got bad eyesight. This gives the function f with

f(y|x) = 3/4 if y = x mod 2
f(y|x) = 1/4 otherwise

Now say I keep rolling the die and you keep asking me whether
the number that comes up is even or odd. Suppose I say
it comes up even 2/3 of the time.

Now comes a question: "what's the probability that I roll a 2?"
To answer this, I'll use as my prior the one where the die is fair.
I can then try to answer my question in a maximum entropy way,
or a Bayesian way, as sketched above... and my question is
whether these give the same answers.

Let me do it the maximum entropy way, just for kicks.
I want to find a probability distribution p on X that
maximizes

sum p(x) ln(p(x))

subject to the constraint that

3/4 (p(2) + p(4) + p(6)) + 1/4 (p(1) + p(3) + p(5)) = 2/3

meaning that I report the die coming up "even" 2/3
of the time. This constraint is of the form

sum g(x) p(x) = constant

so I can use Lagrange multipliers and get

p(x) = Z exp(-g(x)/c)

for some constants c and Z, which I can work out using
the fact that the sum of the p(x) should be 1, and

3/4 (p(2) + p(4) + p(6)) + 1/4 (p(1) + p(3) + p(5)) = 2/3

Hmm, I'm too tired to actually grind it out right now -
it's almost 1 am. But anyway....

 Quote: And yes, in the limit with infinitely many identically distributed observations with finite X, if the f's are all different, anything which does not exclude some elements of X works.

I'm sorry, I don't get what you mean about "if the f's
are all different". I'm picking one finite set X, one
finite set Y, and one function f: Y x X -> [0,1] at the
very start of the problem.

I have a feeling that communication has barely begun.
question and may be using terminology in a funny way.
thomaswc@gmail.com
science forum beginner

Joined: 03 Jul 2006
Posts: 1

Posted: Mon Jul 03, 2006 10:50 pm    Post subject: Re: Maximal entropy from Bayes' law?

In my understanding, the "orthodox Bayesian" solution to your
set-up would involve a prior on p, the probability measure on X.
If you wish, you may call this P(p) a hyper-prior.

Next, you need to formalize what you mean by a best guess.
Here are two possiblities:

1) The p maximizing P(p) subject to the constraint f(p) = q.
This may not be unique.

2) The p' minimizing the expected loss function
EL(p') = sum_{p | f(p) = q} L(p', p) P(p)
where L is some loss function specifying how embarassed you
would feel about guessing p' when the real answer is p. Note
that the expected loss minimizing p' isn't guaranteed to satisfy
f(p') = q (but it might anyhow).

If you are willing to bend the rules a bit, you can fit maximum
entropy into this framework. Just think of maximum entropy
as an unnormalized hyper-prior P(p) that says P(p) is infinitely
greater than P(q) whenever p has higher entropy than q. (You
could make this precise with probability measures valued in
non-Archimedean fields, but where's the fun in that?)

 Quote: From the above description, it should be clear that maximum entropy is a shockingly strong assumption. It should only be

used if

A) Your probability measure really is being generated by an
astronomically large number of microstates interacting. I'm
told this sometimes happens in physics.

B) You don't care. Or perhaps more precisely, when you'd
rather compute a partition function than come up with a loss
function and do the integral in above possibility #2.

John Baez writes:
 Quote: Another approach is Bayesian: use Bayes' rule! The conditional probability for any measurement outcome y given the state x is f(y|x). Use counting measure on X as our "prior", and use Bayes' law to update this prior when we do an observation and get the outcome y. In fact, let's imagine that we keep doing observations, getting outcomes distributed according to the probability measure q, and use these to keep updating our probability measure on X. In the limit of infinitely many observations, this measure should converge (almost surely) to some fixed measure on X.

wouldn't just hop around all of the various p where p = f(q).

But let's see. We'll do n observations, y_1 .. y_n, and see what
happens
to

E( P( x | y_1 .. y_n ) ) = sum_{y_1} .. sum_{y_n} P(y_1 .. y_n ) P( x |
y_1 .. y_n )

By Bayes' law,
E( P( x | y_1 .. y_n ) ) = sum_{y_1} .. sum_{y_n} P(x) P( y_1 .. y_n |
x )

Let's assume the y_i are independent,
E( P( x | y_1 .. y_n ) ) = P(x) sum_{y_1} .. sum_{y_n} P( y_1 | x ) ..
P( y_n | x )

Re-arranging,
E( P( x | y_1 .. y_n ) ) = P(x) ( sum_y f(y|x) )^n

But wait! sum_y f(y|x) = 1, so

E( P( x | y_1 .. y_n ) ) = P(x)

So I guess it does converge, just to the boring P(x) and not to the
interesting maximum entropy solution.

-Thomas C
Ian1
science forum beginner

Joined: 16 Feb 2005
Posts: 22

Posted: Thu Jul 06, 2006 8:48 am    Post subject: Re: Maximal entropy from Bayes' law?

John Baez wrote:
 Quote: I was walking on the beach with Chris Lee and James Dolan last weekend, and we came across a problem about statistical inference. Suppose we repeatedly observe a system in a well-understood but stochastic way and get some frequency distribution of outcomes. What's our best guess for the probability that the system is in a given state? I'm hoping that under some conditions the Bayesian approach gives results that match Jaynes' maximum entropy method.

http://bayes.wustl.edu/etj/articles/stand.on.entropy.pdf.

Pages 38 - 41 discuss a relationship between maximum entropy and Bayes'
theorem. As I understand it, it is the following. Let X be the 'state
space', Y = X^{n}, and F be a function from X to somewhere suitable.

1) Given the constraint <F> = f, one can maximize entropy over measures
on X to get a measure on X.

2) Given that (1/n) \sum_{i = 1}^{n} F(y_{i}) = f for an unknown sample
y \in Y, one can use Bayes' theorem to compute the posterior measure
for y, and then marginalize to get the posterior measure for x \in X.

As n -> \infty, these two procedures agree. The Darwin-Fowler method in
statistical physics does more or less the same thing to get from the
microcanonical to canonical ensemble I think.

I am not sure if this really addresses your question, but perhaps it

Ian.
Ian1
science forum beginner

Joined: 16 Feb 2005
Posts: 22

Posted: Thu Jul 06, 2006 10:52 am    Post subject: Re: Maximal entropy from Bayes' law?

John Baez wrote:
 Quote: I was walking on the beach with Chris Lee and James Dolan last weekend, and we came across a problem about statistical inference. Suppose we repeatedly observe a system in a well-understood but stochastic way and get some frequency distribution of outcomes. What's our best guess for the probability that the system is in a given state? I'm hoping that under some conditions the Bayesian approach gives results that match Jaynes' maximum entropy method.

Further to my previous post: as you have probably noticed, the
situation you are discussing is more complex in one way, and more
simple in another, than the one Jaynes is discussing in the reference I
gave.

Jaynes is discussing the case where there is a deterministic relation
between your x and y (rather than my x and y - sorry my notation was
confusing). In other words, f(y, x) = \delta(y, F(x)) for some function
F. Then, given <F>, the mean of F under an unknown measure on X,
maximum entropy furnishes a measure on X. Alternatively, given the
average of y over m samples of y (equivalently, the average of F(x)
over m samples of x), Bayes' theorem furnishes a posterior measure on
X^{m}. Marginalizing gives a measure on X. As m -> \infty, the two
measures agree, essentially because the second method counts the number
of ways that (m - 1) x's can produce a given average value of F given
that the m^{th} value is fixed.

Your situation involves a stochastic function f, which, what is more,
is not measured directly. There are two ways to think about
constructing a measure on X, as you say. One is to take the maximum
entropy measure on X under the constraint q = f(p). (It should be
noted, though, that you do not have q. You have samples from q.) The
other is to look at n samples of y coming from a single unknown value
x, and to construct the posterior measure on x. It is hard to see how
the latter will produce a maximum entropy distribution, though, as it
does not 'count the number of ways' of producing something, or at
least, I cannot see how it does.

The combination of the two cases would involve m different points in
Y^{n} coming from m points in X (so for each x sample, there are n
samples from f(y, x)). Bayes theorem would then construct a measure on
X^{m}, which could be marginalized to given a measure on X. Jaynes'
argument suggests that it is in the case m -> \infty (and probably,
because you have a stochastic function and not a deterministic one, n
-> \infty as well) that the equivalence will exist.

To put it another, I think equivalent, way: the constraint q = f(p) is
equivalent to a large number of constraints of Jaynes' type, because
q(y) = \int dx f(y, x) p(x) = <f_{y}>, where f_{y}(x) = f(y, x). To fit
in with his argument then, requires being given, for each y, the
average value of f_{y} over m samples of x, and then to let m ->
\infty. In practice, the values of f_{y} are not available directly,
but something similar would be the average of the frequencies of
occurrence of y across the different samples of x. For these to be
'precise' measures of the average values of the f_{y} though, indeed
to guarantee having an average value for every y, means taking n ->
\infty. This seems equivalent to the previous paragraph.

Ian.
Ian1
science forum beginner

Joined: 16 Feb 2005
Posts: 22

Posted: Fri Jul 07, 2006 11:35 am    Post subject: Re: Maximal entropy from Bayes' law?

Dear Thomas,

thomaswc@gmail.com wrote:
 Quote: In my understanding, the "orthodox Bayesian" solution to your set-up would involve a prior on p, the probability measure on X. If you wish, you may call this P(p) a hyper-prior. Next, you need to formalize what you mean by a best guess. Here are two possiblities: 1) The p maximizing P(p) subject to the constraint f(p) = q. This may not be unique. 2) The p' minimizing the expected loss function EL(p') = sum_{p | f(p) = q} L(p', p) P(p) where L is some loss function specifying how embarassed you would feel about guessing p' when the real answer is p. Note that the expected loss minimizing p' isn't guaranteed to satisfy f(p') = q (but it might anyhow).

So if the loss function is \delta(p', p), we are doing MAP estimation,
and we are back to (1).

 Quote: If you are willing to bend the rules a bit, you can fit maximum entropy into this framework. Just think of maximum entropy as an unnormalized hyper-prior P(p) that says P(p) is infinitely greater than P(q) whenever p has higher entropy than q.

The 'infinite difference' seems unnecessary to me. If the prior is
simply e^H(p), then the MAP estimate will be to maximize H(p) subject
to the constraint f(p) = q, which is exactly the maximum entropy
solution suggested by John Baez. Or am I missing something?

 Quote: From the above description, it should be clear that maximum entropy is a shockingly strong assumption. It should only be used if A) Your probability measure really is being generated by an astronomically large number of microstates interacting. I'm told this sometimes happens in physics.

The relation between Bayes' theorem and maximum entropy that I outline
in my posts does suggest that maximum entropy should only be applied
when the 'measurement' you have is a very good estimate at least of
the mean of p. It is an interesting question when this assumption is
justified (deviations from it would mean deviations from the canonical
ensemble in statistical physics, for example, because the Bayes'
theorem argument should be applied with finite m). In physical systems,
perhaps it is because of the time-averaging that would be involved in
any real measurement?

 Quote: John Baez writes: Another approach is Bayesian: use Bayes' rule! The conditional probability for any measurement outcome y given the state x is f(y|x). Use counting measure on X as our "prior", and use Bayes' law to update this prior when we do an observation and get the outcome y. In fact, let's imagine that we keep doing observations, getting outcomes distributed according to the probability measure q, and use these to keep updating our probability measure on X. In the limit of infinitely many observations, this measure should converge (almost surely) to some fixed measure on X. I'm skeptical about this converging; I don't see any reason why it wouldn't just hop around all of the various p where p = f(q).

I do not think the rest of your post (snipped) is analysing what John
Baez was suggesting. The result certainly converges, according to my
interpretation of what he was saying.

Ian.

Ian.
Ian1
science forum beginner

Joined: 16 Feb 2005
Posts: 22

Posted: Fri Jul 07, 2006 11:46 am    Post subject: Re: Maximal entropy from Bayes' law?

Sorry that this reply is so broken up into separate posts. I keep

John Baez wrote:
 Quote: I was walking on the beach with Chris Lee and James Dolan last weekend, and we came across a problem about statistical inference. Suppose we repeatedly observe a system in a well-understood but stochastic way and get some frequency distribution of outcomes. What's our best guess for the probability that the system is in a given state? I'm hoping that under some conditions the Bayesian approach gives results that match Jaynes' maximum entropy method.

If we observe a number n of y's coming from a single x (denoting the
set of outcomes by Y - the set is sufficient since the y samples are
independent given x), then

P(x | Y) \propto P(Y | x) P(x) .

If we take P(x) to be uniform, then we have

P(x | Y) \propto \prod_{y \in Y) f(y, x)^{n_{y}} ,

where n_{y} is the number of occurrences of y in the n observations. As
n gets large, we will have

n_{y} ~ n. f(y, x)

so

ln P(x | Y) ~ \sum_{y \in Y} n f(y, x) ln f(y, x)

so assuming we evenutally observe every possible value of y, we will
have

P(x | Y) ~ e^{- n H[f](x)}

where H[f](x) is the entropy of f(y, x) as a distribution on y. As n
gets very large, P(x | Y) will concentrate on those x's which minimize
H[f](x), which is not the maximum entropy result, at least not in the
way you defined it in your post.

Ian.
kunzmilan@atlas.cz
science forum beginner

Joined: 21 Feb 2006
Posts: 42

Posted: Sat Jul 08, 2006 11:48 am    Post subject: Re: Maximal entropy from Bayes' law?

Thoma wrote
 Quote: From the above description, it should be clear that maximum entropy is a shockingly strong assumption. It should only be

used if
A) Your probability measure really is being generated by an
astronomically large number of microstates interacting. I'm
told this sometimes happens in physics.

1)>Boltzmann, trying to explain his formula for thermodynamical
entropy, published (1877) the following table:

(7,0,0,0,0,0,0)
(6,1,0,0,0,0,0)
(5,2,0,0,0,0,0)
(4,3,0,0,0,0,0)
(5,1,1,0,0,0,0)
(4,2,1,0,0,0,0)
(3,3,1,0,0,0,0)
(3,2,2,0,0,0,0)
(4,1,1,1,0,0,0)
(3,2,1,1,0,0,0)
(2,2,2,1,0,0,0)
(3,1,1,1,1,0,0)
(2,2,1,1,1,0,0)
(2,1,1,1,1,1,0)
(1,1,1,1,1,1,1)

He calculated entropy of each partition using the polynomial
coefficient. He suggested, that the logarithm of it is the equal to
entropy. It is thus possible to use it even for small sets.
Shannon realization of previous table in information theory:

(a,a,a,a,a,a,a)
(a,a,a,a,a,a,b)
(a,a,a,a,a,b,b)
(a,a,a,a,b,b,b)
(a,a,a,a,a,b,c)
(a,a,a,a,b,b,c)
(a,a,a,b,b,c,c)
(a,a,a,b,b,b,c)
(a,a,a,b,b,c,c)
(a,a,a,a,b,c,d)
(a,a,a,b,b,c,d)
(a,a,b,b,c,c,d)
(a,a,a,b,c,d,e)
(a,a,b,c,d,e,f)
(a,b,c,d,e,f,g)

Here, another polynomial coefficient is applicable, connected with
another measure of entropy. Both entropies are additive, nevertheless
they can not solve the mixing problem, how to distinguish strings:
000000111111
010101010101
111010110000.
kunzmilan
DGoncz@aol.com
science forum Guru Wannabe

Joined: 25 Oct 2005
Posts: 122

Posted: Mon Jul 10, 2006 11:40 am    Post subject: Re: Maximal entropy from Bayes' law?

It has been a while for me since posting to sci.math.research..

I just finished MTH 241 Statistics and wrote a bit in Wikipedia and
news:sci.math about Bayesian probabilites to exercise my new skills; I
worked out the power (beta) of an HIV test example, which differs in a
striking manner from the picture you get looking at the specificity and
selectivity of the antibody test. (The forward probability, I think
that is called.)

I collected some links here and have tried to fit them into the OP with
a few quotes from the linked documents.

John Baez wrote in the referenced post that:

 Quote: I was walking on the beach with Chris Lee and James Dolan last weekend, and we came across a problem about statistical inference.

I don't know about you, but I love it when I come across things on the
beach. :)

 Quote: Suppose we repeatedly observe a system in a well-understood but stochastic way and get some frequency distribution of outcomes. What's our best guess for the probability that the system is in a given state? I'm hoping that under some conditions the Bayesian approach gives results that match Jaynes' maximum entropy method.

In general,

http://mathworld.wolfram.com/InverseProblem.html

but specifically,

http://citeseer.ifi.unizh.ch/12595.html

"A Comparison Of Two Approaches: Maximum Entropy On The Mean (MEM) And
Bayesian Estimation (BAYES) For Inverse Problems "

may be of use.

So now the question is "What are the conditions?"

 Quote: Let's make the problem very finitistic to keep it simple. Suppose X is a finite set of "states" and Y is a finite set of "observation outcomes". Suppose we have a function f: Y x X -> [0,1] giving the conditional probability f(y|x) for the outcome of an observation to equal y given that the system's state is x.

That seems more like a, or even *the* general observation problem. What
we see is not always what is there.

 Quote: We can think of f as a "stochastic function" from states to observation outcomes, sending each point of X to a probability measure on Y. By linearity, f gives a map from probability measures on X to probability measures on Y. I'll also call this f. Given a probability measure q on Y, what's our best guess for a probability measure p on X with f(p) = q? Assume such a measure exists.

How is what we see colored by our expectation of what is there? How do
we take the color of our expectations away from what we see? Zen
actual problems.

http://en.wikipedia.org/wiki/Prior_probability provides:

"Some attempts have been made at finding probability distributions in
some sense logically required by the nature of one's state of
uncertainty; these are a subject of philosophical controversy. "

 Quote: One approach is Jaynesian: maximize entropy! In other words, look at the probability measures p with f(p) = q and choose the p with maximum entropy. Of course to define entropy we need a "prior" measure on X; let's use counting measure. So, we are trying to maximize sum_{x in X} p(x) ln(p(x)) over p satisfying the linear constraint f(p) = q. This is something people know how to do.

http://en.wikipedia.org/wiki/Prior_probability provides:

""Another idea, championed by Edwin T. Jaynes, is to use the principle
of maximum entropy. The motivation is that the Shannon entropy of a
probability distribution measures the amount of information contained
the distribution. The larger the entropy, the less information is
provided by the distribution. Thus, by maximizing the entropy over a
suitable set of probability distributions on X, one finds that
distribution that is least informative in the sense that it contains
the least amount of information consistent with the constraints that
define the set. "

 Quote: Another approach is Bayesian: use Bayes' rule! The conditional probability for any measurement outcome y given the state x is f(y|x). Use counting measure on X as our "prior", and use Bayes' law to update this prior when we do an observation and get the outcome y.
 Quote: In fact, let's imagine that we keep doing observations, getting outcomes distributed according to the probability measure q, and use these to keep updating our probability measure on X. In the limit of infinitely many observations, this measure should converge (almost surely) to some fixed measure on X. Do we get the same answer using both approaches?

Once again, from http://en.wikipedia.org/wiki/Prior_probability :

-----

"...Edwin T. Jaynes has published an argument (Jaynes 1968) based on
Lie groups that suggests that the prior for the proportion p of voters
voting for a candidate, given no other information, should be

p ^(- 1) * (1 - p) ^(- 1)

If one is so uncertain about the value of the aforementioned proportion
p that one knows only that at least one voter will vote for Smith and
at least one will not, then the conditional probability distribution of
p given this information alone is the uniform distribution on the
interval [0, 1], which is obtained by applying Bayes' Theorem to the
data set consisting of one vote for Smith and one vote against, using
the above prior."

---------

Now that is something similar to what I did to work out the HIV testing
example. I think I could do or at least follow that, but would have
some difficulty as the population parameter p (not probability but
proportion) wasn't covered in MTH 241 Statistics. But Bayes's rule was.
I don't know my right foot from a Lie group yet.

 Quote: If so, we might say we had a "derivation" of the maximal entropy principle from Bayes' law... or vice versa. Feel free to fix my question; my description of the Bayesian approach is pretty sketchy, and I may have something screwed up.

Oh, I can't do that, but I hope those who read these inserted links
will have something to add. I'm just a machinist studying math at the
community college!

http://mathworld.wolfram.com/BayesianAnalysis.html

This, I think, is more helpful, clear, rigorous, and general than the
Wikipedia article referenced in John's second post to this thread. My 2
cents...

Finally,

"A Full Bayesian Approach for Inverse Problems"

Doug Goncz
Replikon Research
Seven Corners, VA 22044-0394

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [10 Posts]
 The time now is Wed Jun 28, 2017 7:18 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Maximal dimension + subspace of invertible matrices eugene Math 3 Thu Jul 13, 2006 8:04 pm MALIGNANT ENTROPY GROWTH IN EINSTEIN'S ZOMBIE WORLD Pentcho Valev Relativity 2 Thu Jul 06, 2006 6:24 am John Cramer's Type II Transaction explains low entropy of... Jack Sarfatti Math 0 Sat Jul 01, 2006 8:49 pm IS ENTROPY A STATE FUNCTION? Pentcho Valev Relativity 9 Fri Jun 30, 2006 6:19 am Entropy On A Psychrometric Chart Bret Cahill Mechanics 0 Mon Jun 26, 2006 2:58 am


text: I'm a student at the Euler Circle Mathematics Institute. The classes I've taken are Cryptography, Infinite Series, Abstract Algebra, Proofs from the Book, Markov Chains, and Complex Analysis. NanoMath is a student-run nonprofit organization I founded that organizes math contests and other events.


text:
Name: ____________________________________________________ Alpha: _____________________

## Problem 1

Use the algorithm below to convert the following Nondeterministic Finite Automaton into a Deterministic Finite Automaton
M = ({1,2,3},{a,b,c},{(1,a,3),(1,a,2),(2,a,3),(2,a,1),(2,b,2),(2,c,2)},1,{1,3})
Your solution should be a diagram of the machine produced by the algorithm.
Input: a nondeterministic finite automaton M = (Q,Σ,Δ,s,W), which has no λ-transitions
Output: a deterministic finite automaton M' such that L(M') = L(M).
M' = (2Q,Σ,δ, {s}, {R ∈ 2Q | R ∩ W ≠ ∅}) , where δ(H,x) = {q ∈Q | (p,x,q) ∈ Δ for some p ∈ H}

## Problem 2

If the above algorithm is called on an NDFA $M$ with 8 states, how many states might the resulting DFA $M'$ have in the worst case?

## Problem 3

Show how to modify the below machine to remove the $\lambda$-transition without changing the language the machine accepts.

## Problem 4

Write an algorithm that matches the following specification (Hint: Think about Problem 3!):

Input: NDFA M = (Q,Σ,Δ,s,W) and triple (p,λ,q) ∈ Δ, where (p,λ,q) is the only λ-transition in the machine M.
Output: NDFA M' such that L(M') = L(M) and M' has no λ-transitions.

In case you're wondering what the point of this is, remember that the algorithm from Problem 1 is only valid if we have no λ-transitions. So getting rid of λ-transitions is an important job!


text:
# [texhax] default length of a space

Gerard E. Seibert jerry at seibercom.net
Tue Nov 4 12:33:14 CET 2014

This is probably a dumb question; however, I have not been able to find a
definitive answer. Exactly how wide is a "space" in LaTeX? I found that the
default for a line was "0.4pt", or at least that is what it states in one
publication. I want to know what the length of a "space" is. Is it dependent
on the font size? If so, how would I compute it? Is there a list anywhere
that shows all of the common lengths and their measurements?

One last question. I tried using "\the \rightmargin" and it always displays
"0"; however "\the \leftmargin" shows the margin size. Why is the
"\rightmargin" not shown?

Thanks!

--
Jerry


text:
## Intermediate Algebra: Connecting Concepts through Application

Published by Brooks Cole

# Chapter 2 - Systems of Linear Equations and Inequalities - 2.5 Absolute Value Equations and Inequalities - 2.5 Exercises - Page 186: 4

#### Answer

$m=\{ -20,2 \}$

#### Work Step by Step

$\bf{\text{Solution Outline:}}$ Use the definition of absolute value equality to solve the given equation, $|m+9|=11 .$ Do checking of the solution/s. $\bf{\text{Solution Details:}}$ Since for any $c\gt0$, $|x|=c$ implies $x=c \text{ or } x=-c,$ the equation above is equivalent to \begin{array}{l}\require{cancel} m+9=11 \\\\\text{OR}\\\\ m+9=-11 .\end{array} Solving each equation results to \begin{array}{l}\require{cancel} m+9=11 \\\\ m=11-9 \\\\ m=2 \\\\\text{OR}\\\\ m+9=-11 \\\\ m=-11-9 \\\\ m=-20 .\end{array} If $m=2,$ then \begin{array}{l}\require{cancel} |m+9|=11? \\\\ |2+9|=11? \\\\ |11|=11? \\\\ 11=11 \text{ (TRUE)} .\end{array} If $m=-20,$ then \begin{array}{l}\require{cancel} |m+9|=11? \\\\ |-20+9|=11? \\\\ |-11|=11? \\\\ 11=11 \text{ (TRUE)} .\end{array} Hence, $m=\{ -20,2 \} .$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
Last modified on 01/21/16 13:49:15

Input file rfd

Description

TODO: Add description.

Parameters

TODO: Add parameters.

FEM/files0.cpp

$-Keywords FEM/tools.cpp #-Keywords $-Keywords

Last modified: 2016-01-21 13:48:59.137910

This page has been generated automatically. Do not edit it manually! It will be overwritten in regular intervals.

If you want to edit the handwritten part of this page, please do so here.


text:
# scipy.stats.hmean#

scipy.stats.hmean(a, axis=0, dtype=None, *, weights=None, nan_policy='propagate', keepdims=False)[source]#

Calculate the weighted harmonic mean along the specified axis.

The weighted harmonic mean of the array $$a_i$$ associated to weights $$w_i$$ is:

$\frac{ \sum_{i=1}^n w_i }{ \sum_{i=1}^n \frac{w_i}{a_i} } \, ,$

and, with equal weights, it gives:

$\frac{ n }{ \sum_{i=1}^n \frac{1}{a_i} } \, .$
Parameters:
aarray_like

Input array, masked array or object that can be converted to an array.

axisint or None, default: 0

If an int, the axis of the input along which to compute the statistic. The statistic of each axis-slice (e.g. row) of the input will appear in a corresponding element of the output. If None, the input will be raveled before computing the statistic.

dtypedtype, optional

Type of the returned array and of the accumulator in which the elements are summed. If dtype is not specified, it defaults to the dtype of a, unless a has an integer dtype with a precision less than that of the default platform integer. In that case, the default platform integer is used.

weightsarray_like, optional

The weights array can either be 1-D (in which case its length must be the size of a along the given axis) or of the same shape as a. Default is None, which gives each value a weight of 1.0.

New in version 1.9.

nan_policy{‘propagate’, ‘omit’, ‘raise’}

Defines how to handle input NaNs.

• propagate: if a NaN is present in the axis slice (e.g. row) along which the statistic is computed, the corresponding entry of the output will be NaN.

• omit: NaNs will be omitted when performing the calculation. If insufficient data remains in the axis slice along which the statistic is computed, the corresponding entry of the output will be NaN.

• raise: if a NaN is present, a ValueError will be raised.

keepdimsbool, default: False

If this is set to True, the axes which are reduced are left in the result as dimensions with size one. With this option, the result will broadcast correctly against the input array.

Returns:
hmeanndarray

See dtype parameter above.

numpy.mean

Arithmetic average

numpy.average

Weighted average

gmean

Geometric mean

Notes

The harmonic mean is computed over a single dimension of the input array, axis=0 by default, or all values in the array if axis=None. float64 intermediate and return values are used for integer inputs.

Beginning in SciPy 1.9, np.matrix inputs (not recommended for new code) are converted to np.ndarray before the calculation is performed. In this case, the output will be a scalar or np.ndarray of appropriate shape rather than a 2D np.matrix. Similarly, while masked elements of masked arrays are ignored, the output will be a scalar or np.ndarray rather than a masked array with mask=False.

References

[1]

“Weighted Harmonic Mean”, Wikipedia, https://en.wikipedia.org/wiki/Harmonic_mean#Weighted_harmonic_mean

[2]

Ferger, F., “The nature and use of the harmonic mean”, Journal of the American Statistical Association, vol. 26, pp. 36-40, 1931

Examples

>>> from scipy.stats import hmean
>>> hmean([1, 4])
1.6000000000000001
>>> hmean([1, 2, 3, 4, 5, 6, 7])
2.6997245179063363
>>> hmean([1, 4, 7], weights=[3, 1, 3])
1.9029126213592233


text:
# Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph

2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
4 MORPHEO - Capture and Analysis of Shapes in Motion
Inria Grenoble - Rhône-Alpes, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology, LJK - Laboratoire Jean Kuntzmann
Abstract : A standard way to approximate the distance between two vertices $p$ and $q$ in a graph is to compute a shortest path from $p$ to $q$ that goes through one of $k$ sources, which are well-chosen vertices. Precomputing the distance between each of the $k$ sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources.
In this paper, we analyze the stretch factor $\mathcal{F}_{\text{FPS}}$ of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that $\mathcal{F}_{\text{FPS}}$ can be bounded in terms of the minimal value $\mathcal{F}^\ast$ of the stretch factor obtained using an optimal placement of $k$ sources as $\mathcal{F}_{\text{FPS}}\leq 2 r_e^2 \mathcal{F}^\ast+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor $r_e$ is not an artefact of the analysis by providing a class of graphs for which $\mathcal{F}_{\text{FPS}} \geq \frac{1}{2} r_e \mathcal{F}^\ast$.
Keywords :
Document type :
Journal articles

Cited literature [17 references]

https://hal.inria.fr/hal-01297624
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Wednesday, May 25, 2016 - 4:00:54 PM
Last modification on : Thursday, January 20, 2022 - 4:16:35 PM

### Files

ShortestPaths_final.pdf
Files produced by the author(s)

### Citation

Pegah Kamousi, Sylvain Lazard, Anil Maheshwari, Stefanie Wuhrer. Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph. Computational Geometry, Elsevier, 2016, 57, pp.1-7. ⟨10.1016/j.comgeo.2016.05.005⟩. ⟨hal-01297624v2⟩

### Metrics

Les métriques sont temporairement indisponibles


text:
# Move an object with other objects connected (via joints) the right way

What is the best way to move an object with other objects connected to it via joints?

Let's assume we have the following setup:

• A player that can move on the x and the z axis
• "Normally configured" RigidBody
• Moving like this:
    void FixedUpdate() {
Vector3 movement = new Vector3(Input.GetAxisRaw("Horizontal"), 0f, Input.GetAxisRaw("Vertical"));
movement = movement.normalized * 2f * Time.deltaTime;

// m_rb is the RigidBody of the player
m_rb.MovePosition(transform.position + movement);
}

• Another object that should be moving with the player as it were its child
• Connected to the player via a fixed joint
• "Normally configured" RigidBody

When moving the player without any object connected the movement looks as expected:

Now moving the player with the object connected results in some kind of dragging effect as seen here:

One way to solve this behaviour would be to also move the connected object:

// m_otherRb is the RigidBody of the connected object (m_other)
m_otherRb.MovePosition(m_other.transform.position + movement);

Is there a better way to solve this? Shouldn't the joint handle the movement of the other object? Moving the connected object like this results in many problems like to high impulse forces when colliding with something as both elements get pushed towards the collider. Also handling the rotation of the connected object isn't as easy as the position.

• The joint is handling the movement of the object, in an approximation of how a real physical joint would: by applying an off-center torque on the leading object. Give it a try: stick together two LEGO bricks, then push one of them across the table. Left to rotate freely, it will tend to rotate toward the second brick. As it applies forces through their joint (the plastic bumps) to move the second brick along with it, the second brick applies an equal and opposite force back on the lead brick, torquing it around. If you don't want standard physical behaviour, you need to override it yourself. Jun 2 '20 at 14:27
• That totally makes sense! Thank you! Jun 2 '20 at 15:36
• Do you have an explanation for the way to high impulse force when the object connected to the player collides with something? The added weight to the impulse of course increases the impulse force seems to be way higher no matter how heavy the connected object is. Jun 2 '20 at 15:39
• Have you tried moving with velocity/acceleration/forces rather than MovePosition? It's possible MovePosition says "get to exactly this position in one step, at all costs" and so it ramps up the impulse to an extreme value that exceeds what you'd actually need to travel there smoothly with velocity. Jun 2 '20 at 15:40
• Thanks alot! Setting the velocity direct worked out great! Jun 2 '20 at 18:13

## 1 Answer

As DMGregory pointed out the behaviour of the joint connected to the image is totaly right (See his first comment for an explanation).

The problem with the to high impulse force when colliding was solved by changing the velocity instead of using MovePosition like this:

void FixedUpdate() {
Vector3 movement = new Vector3(Input.GetAxisRaw("Horizontal"), 0f, Input.GetAxisRaw("Vertical"));
movement = movement.normalized * 150f * Time.deltaTime;

// m_rb is the RigidBody of the player
m_rb.velocity = movement;

// m_otherRb is the RigidBody of the connected object
m_otherRb.velocity = movement;
}

I've just had to turn up the speed multiplyer.


text:
# Interaction of light with the quantum gravitational field

1. Sep 2, 2005

### marcus

I want to gather some links about this. If you know of some good articles and can add some links to the stash, please do. The gravitational field is the geometry of spacetime and can be roughly equated with spacetime itself, or a general idea of the vacuum----the ideas tend to overlap because in some sense spacetime is nothing besides its quantum geometry and because the other fields are defined on spacetime.

I became aware from a Turbo thread that in 1920 Einstein was recklessly speaking of the gravitational field as a sort of "Machian aether" which he defined different from the old aether in that it agreed with relativity and had no preferred rest-frame. But even if it is given a special definition and used in a logically OK manner, merely using this word runs a risk of precipitating much confusion and argument. So probably we should just say (quantum) "gravitational field" among ourselves and not use the AE word.

R. Loll and B. Dittrich recently posted an article that is very much about the paths of light through the CDT spacetime "counting a black hole"---
this paper is looking at the optical behavior of different simplex-assemblages, how beams are spread and concentrated
Also Loll and Westra were using optical criteria to determine how much and what kind of topology change they could allow.
http://arxiv.org/abs/hep-th/0507012
"Taming the cosmological constant in 2D causal quantum gravity with topology change"
http://arxiv.org/abs/gr-qc/0506035
"Counting a black hole in Lorentzian product triangulations"
So in these papers which are the most recent, save one, from Loll, light is playing an important and explicit role in quantum gravity. Maybe you think this is naive but I take it as a possible hint that I should learn about different interactions of light with the gravitational field including the flat-case vacuum so I am prepared in case some of these things come up in the CDT quantum spacetime.

So I want some links. If you have some good ones please volunteer them. I will mine Turbo's references first.

Last edited: Sep 2, 2005
2. Sep 2, 2005

### marcus

these are grubbed from something Turbo mentioned

http://arxiv.org/gr-qc/0107091 [Broken]
Faster-than-c signals, special relativity, and causality
Stefano Liberati (U Maryland), Sebastiano Sonego (U Udine, Italy), Matt Visser (Washington University in Saint Louis)
25 pages; 4 embedded figures. To appear in Annals of Physics
Annals Phys. 298 (2002) 167-185
"Motivated by the recent attention on superluminal phenomena, we investigate the compatibility between faster-than-c propagation and the fundamental principles of relativity and causality. We first argue that special relativity can easily accommodate -- indeed, does not exclude -- faster-than-c signalling at the kinematical level. As far as causality is concerned, it is impossible to make statements of general validity, without specifying at least some features of the tachyonic propagation. We thus focus on the Scharnhorst effect (faster-than-c photon propagation in the Casimir vacuum), which is perhaps the most plausible candidate for a physically sound realization of these phenomena. We demonstrate that in this case the faster-than-c aspects are `"benign'' and constrained in such a manner as to not automatically lead to causality violations."

http://arxiv.org/gr-qc/9807067 [Broken]
Superluminal propagation of light in gravitational field and non-causal signals
A.D. Dolgov, I.D. Novikov
Phys.Lett. B442 (1998) 82-89
"It has been found in several papers that, because of quantum corrections, light front can propagate with superluminal velocity in gravitational fields and even in flat space-time across two conducting plates. We show that, if this is the case, closed time-like trajectories would be possible and, in particular, in certain reference frames photons could return to their source of origin before they were produced there, in contrast to the opposite claim made in the literature."

http://arxiv.org/hep-th/9810221 [Broken]
The velocities of light in modified QED vacua
K. Scharnhorst (Humboldt University Berlin)
Comments: 7 pages, 5 figures... to appear as a special issue of the Annalen der Physik (v2: typos in the references corrected, minor stylistic changes)
Annalen Phys., 8. Series, 7 (1998) 700-709
"QED vacua under the influence of external conditions (background fields, finite temperature, boundary conditions) can be considered as dispersive media whose complex behaviour can no longer be described in terms of a single universal vacuum velocity of light c. Beginning in the early 1950's (J.S. Toll), quantum field theoretic investigations have led to considerable insight into the relation between the vacuum structure and the propagation of light. Recent years have witnessed a significant growth of activity in this field of research. After a short overview, two characteristic situations are discussed: the propagation of light in a constant homogeneous magnetic field and in a Casimir vacuum. The latter appears to be particularly interesting because the Casimir vacuum has been found to exhibit modes of the propagation of light with phase and group velocities larger than c in the low frequency domain omega<<m where m is the electron mass. The impact of this result on the front velocity of light in a Casimir vacuum is discussed by means of the Kramers-Kronig relation."

I should point out that I am not primarily interested in "FTL"-----I don't care whether the interaction with spacetime makes the signal travel faster or slower. I am happy if it travels SLOWER. this is not a "trekkie" thread. The only thing I care about is that there is discussed SOME INTERACTION of the light with the vacuum or with the gravitational field. this may reveal itself by making the light go a little faster or a little slower, or some other effect.

Also these references are all peer-ified JOURNAL publications. One is "Annals of Physics" and one is "Annalen der Physik" and one is "Physical Review Letters". So as not to pursue the goose, let us require this of our links.

Last edited by a moderator: May 2, 2017
3. Sep 2, 2005

Staff Emeritus
When I googled I found a lot of interest in the Schrnhorst effect, but nearly all of it, even the most sober scientific papers, was focused on "FTL". As your abstract from Scharnhorst's review article suggests, the QED interaction of light with the virtual vacuum goes back a long way, and Scharnhorst's own Casimir suggestion came in 1990.

This is all perfectly good physics, and stands to reason given the nature of the QED vacuum (I had a forehead hitting moment!). Apparently though, the easiest ways to observe the effect (like birefringence) won't work. To get a pair of plates flat enough around and 1 mm apart and actually measure the speed oof light between them sounds like heroic experimentation to me, but who knows? The capabilities of experimenters seem to expand at something like Moore's law rates.

4. Sep 2, 2005

### marcus

the impression I got was of general agreement that these effects aren't presently measurable or detectable, which agrees with what you say.

also I want to keep open to other kinds of effects besides Scharnhorst. would like if someone could supply links about effects on light of strong gravitational fields.

I have the nagging suspicion that very high energy GRB light should go slightly slower because it is interacting more with a chaotic uncertain-curved smallscale regime. this goes counter to what I have read and is not grounded on mathematical foundations, and it bothers me.

5. Sep 4, 2005

### hellfire

Could you please give some heuristic explanation of the effect? I always was under the impression that virtual particles arise only in case of interacting fields and that light does not interact with the modes of vacuum of a free field (so that their suppression leads to a faster propagation of light).

Last edited: Sep 4, 2005
6. Sep 4, 2005

Staff Emeritus
That was my impression too, but it's wrong. There are good reasons why a photon cannot induce real pair production; it violates conservation laws. But those laws are only true up to observability. For virtual particles which don't last long enough, or don't have enough energy, to be observed as real, non-conservational things can happen, and this is an echt prediction of relativistic quantum field theory, although I haven't been able to find it mentioned in Peskin and Schroeder.

So photons move through the q-vacuum pretty much the way they move through glass, making e^+e^- pairs instead of being absorbed by atoms, and slowing down. The Scharnhorst paper that Marcus linked to has a reference to an early paper (early in QED history) that developed this idea.

7. Sep 4, 2005

### Chronos

The Scharnhorst effect is, at best, difficult to measure, and deemed unlikely to cause superluminal propogation. To quote John Baez:
"However, further theoretical investigations have shown that once again there is no possibility of FTL communication using this [Scharnhorst] effect."
http://math.ucr.edu/home/baez/physics/Relativity/SpeedOfLight/FTL.html#12

Several papers disputing the Scharnhorst result were published circa 1990, unfortunately, finding free sources of these papers has proven difficult.

Another source:
Quantum Noise and Superluminal Propagation
http://www.arxiv.org/abs/quant-ph/0004047

Regarding slips in the arrival time of high energy GRB photons:

Testing models for quantum gravity
http://www.cerncourier.com/main/article/42/7/18

Selected topics in Planck-scale physics
http://www.arxiv.org/abs/gr-qc/0305019

8. Sep 4, 2005

### Hans de Vries

There are a number of interesting publications in the field of very high energy
density lasers and the breakdown of the vacuum beyond Schwingers critical
field strength.

"The spontaneous breakdown of the vacuum"
http://arxiv.org/PS_cache/hep-ph/pdf/9805/9805507.pdf [Broken]

Interestingly puts an upper limit to the fine structure constant of 1/(16pi)
as a necessary condition for the spontaneous breakdown of the vacuum.

X-RAY lasers (free electron lasers):
"Pair Production from Vacuum at the Focus of an X ray laser"
http://arxiv.org/PS_cache/hep-ph/pdf/0103/0103185.pdf [Broken]
"Boiling the vaccum with an X ray free electron laser"
http://arxiv.org/PS_cache/hep-ph/pdf/0304/0304139.pdf [Broken]

Ultra high energy density lasers may also allow experimental tests of the
http://www-ssrl.slac.stanford.edu/lcls/workshops/12jan1999/hf_physics.html
http://www.aps.anl.gov/conferences/FLSworkshop/proceedings/papers/wgSum1I.pdf

Regards, Hans

Last edited by a moderator: May 2, 2017
9. Sep 5, 2005

### hellfire

This is my understanding from Peskin and Schröder, please correct me if I am wrong: The amplitudes for the fluctuations in the vacuum state of a free field can be computed as $<0|\phi(x_1) \phi(x_2) ... \phi(x_n)|0>$. According to Wick's theorem, an expression like this can be decomposed as a product of Feynman propagators, leading to Feynman diagrams with no loops. Only if an interaction exists, a term $$e^{-i\int dt H_I}$$ appears within the product <0|...|0> due to the fact that one does not consider $|0>$ anymore but $|\Omega>$, the vacuum state of an interacting field expressed in terms of the free vacuum state. Only this term with the integral leads to loops in the Feynman diagramms after expanding the exponential as a power series. Thus, I do not understand how Scharnhorst is considering "2-loop diagrams" at all. Basically, I still have problems to understand what roles these "virtual particles" are playing here and how do they arise.

Last edited: Sep 5, 2005
10. Sep 6, 2005

### Spin_Network

Here's one for a good start:http://arxiv.org/abs/astro-ph/0210124

another good thread marcus, I am a bit busy with things, but great postings, thanks.

11. Sep 6, 2005


text:
### How to find the quadrature points and weights of a mesh?

426
views
1
11 months ago by
Hi,

Is there any way to find all the quadrature points and weights of a given function space? I tried the solution in this post, but it does not work for the current version of fenics.
https://fenicsproject.org/qa/9633/quadrature-points?show=9633#q9633

Community: FEniCS Project

2
11 months ago by
Based on the post you mentioned and on https://fenicsproject.org/qa/9635/quadrature-element and https://fenicsproject.org/qa/3932/accessing-the-coordinates-of-a-degree-of-freedom, this should work in the current version
from fenics import *

mesh = UnitSquareMesh(10, 10)
gdim = mesh.geometry().dim()

cell = mesh.ufl_cell(),
degree = 2,

xq = V.tabulate_dof_coordinates().reshape((-1, gdim))
xq0 = xq[V.sub(0).dofmap().dofs()]

Thanks for the reply. This code works for finding the quadrature points. Will there be any way to find the associate quadrature weight? Like in this post:
https://fenicsproject.org/qa/12309/quadrature-weights (which does not work either).
written 11 months ago by Mohan Wu
The code from the post works with
from ffc.fiatinterface import create_quadrature
written 11 months ago by Adam Janecka
This will give the quadrature points and weights for a reference cell, how to get this relation for the global index?
written 11 months ago by Mohan Wu
There surely must be a better solution but I was only able to come up with this ugly (hopefully correct) one:
from __future__ import print_function

from fenics import *

mesh = UnitSquareMesh(2, 2)
gdim = mesh.geometry().dim()

shape = mesh.ufl_cell()
degree = 4
scheme = 'default'

cell = shape,
degree = degree,

xq = V.tabulate_dof_coordinates().reshape((-1, gdim))

print('\n\t Point \t\t\t Weight')
for i in range(len(xq)):
u = Function(V)
u.vector()[i] = 1.0;
print(xq[i], ':\t', assemble(u*dx))

(points, weights) = create_quadrature(str(shape), degree, scheme)
print('\nReference element:')
print(' Points:\n', points)
print(' Weights:\n', weights)

written 11 months ago by Adam Janecka


text:
# Suboptimal Alignments

## Application

The corollary to the above theorem ensures that we can highlight parts of an optimal alignment by looking at the -stable points. The biological meaning however of -stable points lies in the fact that with rising the percentage of -stable points that agree with the correct structural alignment of two sequences tends (monotonically) towards 100%. This does not allow for a mathematical proof but is the result of the analysis of many example comparisons of different proteins where the three dimensional structures are known and the quality of the calculated results can be assessed objectively. The data are summarized in the following table.

 casenumber comparisonof %homology % of correct extent x 100 / no. of alignable pairs 1 cytochrome c andcytochrome c2 39 051015 9297100100 92876956 2 aplysia globin andlamprey globin 33 051015 8495100100 84777354 3 Immunoglobulinvariable domain: heavyand light chain 24 051015 62100100100 63553414 4 alpha hemoglobinand leghemoglobin 16 051015 8797100100 87644118 5 cytochrome c andcytochrome c551 25 051015 4995100100 402563 6 copper bindingproteins: azurinand plastocyanin 22 051015 486585100 4738245

case 1 share a rather high sequence similarity (the biologically correct alignment contains 39 % identities) and the alignment is consequently very well defined. The two sequences in case 5 are very difficult to align and consequently the plot shows many alternative points.

The data in the table indicate that the 10-stable points in 5 out of 6 cases agree with the correct alignment. We conclude that those parts of an alignment should be trusted more than other points, namely the ones that allow for alternative 10-suboptimal alignments. Additionally the table shows that with increasing there are more cases of comparisons for which misaligned pairs are eliminated from the set of -stable points. A detailed discussion of these facts in their biological context is given in [ViA90].

The utility of this observation is limited by the fact that for larger contains very few points. In this case the increased security was gained at too high a cost to be helpful. Only if a reasonable number of residue pairs are established in , can the approach of highlighting reliably aligned regions be considered effective. Therefore a quantity ("extent") is introduced to measure the effectiveness of the stable regions. As sequences and with them their alignments can vary in length, counting is not a good measure. Instead we correlate this to the number of residue pairs in the correct structural alignment and define the extent as the number of -stable points divided by the number of residue pairs in the structural alignment. Of course this is a biologically reasonable measure only when contains 100 % correct points. In the table these figures (in percent) are given in the last column of the table. The theoretical conclusion that the extent is decreasing with increasing security is confirmed by these data. The extent of the prediction also seems closely connected to what one intuitively refers to as the "difficulty" to correctly align a certain pair of sequences. For comparisons, however, where the optimal alignment has nothing in common with the biologically correct alignment these quanitities carry no meaning.


text:
# EXPS 1 | Lesson 4 | Explore (Doubling)

Assume that a certain virus being studied is currently doubling each day.  Suppose that one unit of virus is contained now. Complete the table below to show the growth of the virus over time with 0 representing now,  1 representing one day from now, and $$-1$$ representing one day ago.

Considering this pattern, let’s explore how much virus would be present in $$\frac{1}{2}$$ days from now.  We know that the amount of virus is between 1 and 2 units since $$\frac{1}{2}$$ days is between 0 and 1 days.

• First, we can write this amount as an exponential expression with base 2 and days $$\frac{1}{2}$$ as $$2^\frac{1}{2}$$.
• Second, we can use the exponent multiplication rule to show that $$2^\frac{1}{2}\cdot 2^\frac{1}{2}=2^{\frac{1}{2}+\frac{1}{2}}=2^1=2$$.
• Therefore, we know that $$2^\frac{1}{2}$$ is equal to $$\sqrt{2}$$ since $$\sqrt{2}\cdot \sqrt{2}=2$$.
1. Use a calculator to determine the amount of virus present in $$\frac{1}{2}$$ days from now which is the same as $$2^\frac{1}{2}$$. Round the answer to the nearest 0.001.
2. Using the example above, write an exponential expression and a radical expression to represent the amount of virus present for the following days:

a) $$\frac{1}{3}$$ days

b) $$\frac{1}{4}$$ days

c) $$\frac{5}{6}$$ days


text:
# Find the function f whose derivative is $\sin^2 x$ [closed]

Find the function $f$ whose derivative is

$$f'(x)=\sin^2(x)$$

and where $f(\pi)=\pi$.

$$f(x)=\frac12(x-\sin x\cos x)$$ What do I do from here?

• Make sure that letting $x=\pi$ makes $f(x)=\pi$. Note that the antiderivative of $f'(x)$ is $f(x)+C$ for some constant $C$. – abiessu Sep 10 '13 at 15:12

You label this as differential equations, is this supposed to be integral calculus?

You have solved the indefinite integral and forgot to add +c.

$$\int \sin^2(x)dx=\int \frac{1-\cos(2x)}{2}dx=\frac{x}{2}-\frac{\sin(2x)}{4}+c.$$

Now evaluate at $f(\pi)=\pi$ to see $\pi=\frac{\pi}{2}+c$ and solve.

$$f'(x)=\sin^2x\implies f(x)=\frac12(x-\sin x\cos x) \color{red}{+ C}\;,\;\;C=\;\text{a constant} .$$
$$\pi=f(\pi)=\frac{\pi}2+C\implies C=\frac{\pi}2\implies \color{blue}{f(x)=\frac12(x-\sin x\cos x)+\frac{\pi}2}$$
$$f'(x) = \sin^2(x) \Rightarrow f(x) = \int \sin^2 x \ dx = \int \frac{1}{2} \left(1 - \cos 2x \right) \ dx = \frac{x}{2} - \frac{\sin 2x}{4} + C$$
$$f(\pi) = \pi \Rightarrow \frac{\pi}{2}+ C = \pi\Rightarrow C = \frac{\pi}{2}$$
$$\Rightarrow f(x) = \frac{x}{2} - \frac{\sin 2x}{4} + \frac{\pi }{2}$$


text:
# Is this method of finding a “dual curve” correct?

I have a very limited exposure to projective geometry, but I'm having fun exploring the concept of duality. In particular I'd like to know if this naive method of finding a "dual" curve to a given curve $\Gamma$ (in the real projective plane) could be correct. Here's the idea. Let $P(t)$ be a point of $\Gamma$ with (homogeneous) coordinates $(a(t),b(t),1)$, and let $P_t^*$ be the line dual to $P$, i.e. $$P_t^*:\qquad a(t)x+b(t)y+1=0$$ Now, and this is where problems could arise, I'd like to assume that the set $$P^*=\{ a(t)x+b(t)y+1=0\quad|\quad t\in\mathbb{R}\}$$ is the set of tangents to the dual curve $\Gamma^*$. In this case, I could find the equation for $\Gamma^*$ by considering the following limit: $$\lim_{h\rightarrow 0}P_t^*\cap P_{t+h}^*$$ My question is: is this method plausible or is it complete nonsense? I have checked it only for the case of a parabola $\Gamma$ given by $P(t)=(t,at^2,1)$, which yields a "dual" parabola $\Gamma^*$ given by $P(t)=(t,\frac{t^2}{4a},1)$.

I am afraid that the assumption of $P^*$ being a set of tangents is way too strong and basically unmotivated. If it's the case, is there an elementary method of obtaining a dual curve from a given one?

• * sits on a rock and waits * – marco trevi Apr 15 '16 at 13:39
• * bounties to the sharks * – marco trevi Apr 18 '16 at 16:54


text:
# Newton's second law?

$F=ma$. A car strikes a wall at 60 mph. Its acceleration is zero at the time. The force of the car against the wall or vice versa is? To look at the car the force is not zero. Please explain.

-
Can you clarify what you are asking? As soon as the car touches the wall it will start decelerating (as it's bodywork crumples) and the force between the wall and the car will be the deceleration multipled by the mass of the car. –  John Rennie Apr 3 '13 at 15:14
You seem to be assuming that you measure the instantaneous acceleration at a time before the the impact can be communicated to "the car". You can do that but this simply means that you are examining the car "before" the impact. As the impact develops both the force and the acceleration will grow rapidly (starting with the mass of the bumper in particular and propagating backwards at the speed of sound in the material of the car's frame) toward some maximum value. –  dmckee Apr 3 '13 at 16:04
add comment

## 1 Answer

The minute the car touches the wall, it will decelerate rapidly (and crumple in the process). This deceleration/crumpling will be from the force the wall exerts on the car, which can be calculated from $F=ma$.

The car also exerts a force on the wall. However, the wall is attached to the ground, and the ground exerts a balancing force on the wall, keeping it in place. This means that the wall exerts an equal and opposite force on the ground. But, the ground (Earth) is so massive that we can just assume that the mass is infinite, giving us zero acceleration for the ground.

-
add comment


text:
# How do you simplify and write 8a^5 d^-5 with positive exponents?

$8 {a}^{5} / {d}^{5}$
When you have ${a}^{-} b$ you convert it with positive exponents by doing $\frac{1}{a} ^ b$.
So $8 {a}^{5} {d}^{-} 5 = 8 {a}^{5} \left(\frac{1}{d} ^ 5\right) = 8 {a}^{5} / {d}^{5}$