text:
# resubMargin

Resubstitution classification margins for naive Bayes classifier

## Syntax

``m = resubMargin(Mdl)``

## Description

example

````m = resubMargin(Mdl)` returns the resubstitution Classification Margin (`m`) for the naive Bayes classifier `Mdl` using the training data stored in `Mdl.X` and the corresponding class labels stored in `Mdl.Y`.`m` is returned as a numeric vector with the same length as `Y`. The software estimates each entry of `m` using the trained naive Bayes classifier `Mdl`, the corresponding row of `X`, and the true class label `Y`.```

## Examples

collapse all

Estimate the resubstitution (in-sample) classification margins of a naive Bayes classifier. An observation margin is the observed true class score minus the maximum false class score among all scores in the respective class.

Load the `fisheriris` data set. Create `X` as a numeric matrix that contains four petal measurements for 150 irises. Create `Y` as a cell array of character vectors that contains the corresponding iris species.

```load fisheriris X = meas; Y = species;```

Train a naive Bayes classifier using the predictors `X` and class labels `Y`. A recommended practice is to specify the class names. `fitcnb` assumes that each predictor is conditionally and normally distributed.

`Mdl = fitcnb(X,Y,'ClassNames',{'setosa','versicolor','virginica'})`
```Mdl = ClassificationNaiveBayes ResponseName: 'Y' CategoricalPredictors: [] ClassNames: {'setosa' 'versicolor' 'virginica'} ScoreTransform: 'none' NumObservations: 150 DistributionNames: {'normal' 'normal' 'normal' 'normal'} DistributionParameters: {3x4 cell} Properties, Methods ```

`Mdl` is a trained `ClassificationNaiveBayes` classifier.

Estimate the resubstitution classification margins.

```m = resubMargin(Mdl); median(m)```
```ans = 1.0000 ```

Display the histogram of the in-sample classification margins.

```histogram(m,30,'Normalization','probability') xlabel('In-Sample Margins') ylabel('Probability') title('Probability Distribution of the In-Sample Margins')```

Classifiers that yield relatively large margins are preferred.

Perform feature selection by comparing in-sample margins from multiple models. Based solely on this comparison, the model with the highest margins is the best model.

Load the `fisheriris` data set. Specify the predictors `X` and class labels `Y`.

```load fisheriris X = meas; Y = species;```

Define these two data sets:

• `fullX` contains all predictors.

• `partX` contains the last two predictors.

```fullX = X; partX = X(:,3:4);```

Train a naive Bayes classifier for each predictor set.

```FullMdl = fitcnb(fullX,Y); PartMdl = fitcnb(partX,Y);```

Estimate the in-sample margins for each classifier.

```fullM = resubMargin(FullMdl); median(fullM)```
```ans = 1.0000 ```
```partM = resubMargin(PartMdl); median(partM)```
```ans = 1.0000 ```

The two models have similar performance. However, `PartMdl` is less complex.

## Input Arguments

collapse all

Full, trained naive Bayes classifier, specified as a `ClassificationNaiveBayes` model trained by `fitcnb`.

collapse all

### Classification Edge

The classification edge is the weighted mean of the classification margins.

If you supply weights, then the software normalizes them to sum to the prior probability of their respective class. The software uses the normalized weights to compute the weighted mean.

When choosing among multiple classifiers to perform a task such as feature section, choose the classifier that yields the highest edge.

### Classification Margin

The classification margin for each observation is the difference between the score for the true class and the maximal score for the false classes. Margins provide a classification confidence measure; among multiple classifiers, those that yield larger margins (on the same scale) are better.

### Posterior Probability

The posterior probability is the probability that an observation belongs in a particular class, given the data.

For naive Bayes, the posterior probability that a classification is k for a given observation (x1,...,xP) is

`$\stackrel{^}{P}\left(Y=k|{x}_{1},..,{x}_{P}\right)=\frac{P\left({X}_{1},...,{X}_{P}|y=k\right)\pi \left(Y=k\right)}{P\left({X}_{1},...,{X}_{P}\right)},$`

where:

• $P\left({X}_{1},...,{X}_{P}|y=k\right)$ is the conditional joint density of the predictors given they are in class k. `Mdl.DistributionNames` stores the distribution names of the predictors.

• π(Y = k) is the class prior probability distribution. `Mdl.Prior` stores the prior distribution.

• $P\left({X}_{1},..,{X}_{P}\right)$ is the joint density of the predictors. The classes are discrete, so $P\left({X}_{1},...,{X}_{P}\right)=\sum _{k=1}^{K}P\left({X}_{1},...,{X}_{P}|y=k\right)\pi \left(Y=k\right).$

### Prior Probability

The prior probability of a class is the assumed relative frequency with which observations from that class occur in a population.

### Classification Score

The naive Bayes score is the class posterior probability given the observation.


text:
# GED Calculator (TI-30 XS) Practice Test

Use your TI-30 XS to solve these questions. Every question includes an explanation and images on how to use the TI-30 XS.

Our lessons and practice tests are provided by Onsego. GED Testing Service recognizes Onsego as a trusted publisher that has developed curriculum materials that are 100% aligned with the GED test.

### The “All-in-One” GED Prep

Get Your Diploma in 2 Months.
It doesn’t matter when you left school.

1. Find the difference.

$$-83 - 17 + 87 =$$
A.
B.
C.

Question 1 of 15

2. Find the difference.

$$8695 + (-3) - (6290 - 4233)$$
A.
B.
C.

Question 2 of 15

3. Find the difference.

$$-71 - (435 + 124) + 132 =$$
A.
B.
C.
D.

Question 3 of 15

4. What number is $$22.4 \%$$ of $$125?$$
A.
B.
C.
D.

Question 4 of 15

5. What number is $$159\%$$ of $$185?$$
A.
B.
C.
D.

Question 5 of 15

6. Solve.

$$\frac{3}{4}-\frac{3}{7}$$
A.
B.
C.
D.

Question 6 of 15

7. Solve.

$$\frac{2}{7}+\frac{1}{4}$$
A.
B.
C.
D.

Question 7 of 15

8. Solve.

$$\frac{2}{9}-\frac{4}{5}$$
A.
B.
C.
D.

Question 8 of 15

9. What is $$\sqrt{121}$$
A.
B.
C.

Question 9 of 15

10. Compute $$\sqrt{289}$$.
A.
B.
C.

Question 10 of 15

11. Compute the exact value of the given expression.

$$\sqrt{3}^{2} + 4^{2}$$
A.
B.
C.

Question 11 of 15

12. Calculate.

$$14^{3}$$
A.
B.
C.
D.

Question 12 of 15

13. Calculate:
$$(-4)^{4}$$
A.
B.
C.
D.

Question 13 of 15

14. Evaluate the expression at the given value of $$x$$ and $$y$$.

$$-3x - 6y + 3$$,

at  $$x = 8$$,

$$y = 7$$
A.
B.
C.
D.

Question 14 of 15

15. Evaluate.

$$12x^{2} + \frac{1}{4} y - 6z$$

at  $$x = 2$$,

$$y = 8$$,

$$z = -7$$,

Tip. Make sure, you have input $$\frac{1}{4} y$$ correctly.
A.
B.
C.
D.

Question 15 of 15

Don’t forget to check our lessons on how to use the GED calculator.

Last Updated on June 12, 2022.

format: plain


text:
An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model

# An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model

Gulikers, L., Lelarge, M., Massoulié, L.
###### Abstract

We consider a Degree-Corrected Planted-Partition model: a random graph on nodes with two equal-sized clusters. The model parameters are two constants and an i.i.d. sequence of weights , with finite second moment . Vertices and are joined by an edge with probability when they are in the same class and with probability otherwise.

We prove that it is information-theoretically impossible to estimate the spins in a way positively correlated with the true community structure when .

A by-product of our proof is a precise coupling-result for local-neighbourhoods in Degree-Corrected Planted-Partition models, which could be of independent interest.

## 1 Introduction

It is well-known that many networks exhibit a community structure. Think about groups of friends, web pages discussing related topics, or people speaking the same language (for instance, the Belgium population could be roughly divided into people speaking either Flemish or French). Finding those communities helps us understand and exploit general networks.

Instead of looking directly at real networks, we experiment first with models for networks with communities. One of the most elementary models is the Planted-Partition Model (PPM) [14]: a random graph on vertices partitioned into two equal-sized clusters such that vertices within the same cluster are connected with probability and between the two communities with probability . Note that the PPM is a special case of the Stochastic Block Model (SBM). The question is now: given an instance of the PPM, can we retrieve the community-membership of its vertices?

Most real networks are sparse and a thorough analysis of the sparse regime in the PPM - i.e., and for some constants - will therefore lead to a better understanding of networks.

When the difference between and is small, the graph might not even contain enough information to distinguish between the two clusters. In [9] it was first conjectured that a detectability phase-transition exists in the PPM: detection would be possible if and only if . The negative-side of this conjecture has been confirmed in [25]. The positive side has been recently confirmed in [20] and [24] using sophisticated (but still running in polynomial time) algorithms designed for this particular problem.

In this paper we study an extension of the PPM: a Degree-Corrected Planted-Partition Model (DC-PPM), a special case of the Degree-Corrected Stochastic Block Model (DC-SBM) in [16]. Because, although the PPM is a useful model due to its analytical tractability, it fails to accurately describe networks with a wide variety in their degree-sequences (because nodes in the same cluster are stochastically indistinguishable). Indeed, real degree distributions follow often, but not always, a power-law [1]. Compare this to fitting a straight line on intrinsically curved data, which is doomed to miss important information.

The DC-PPM is defined as follows: It is a random graph on vertices partitioned into two asymptotically equal-sized clusters by giving each vertex a spin drawn uniformly from . The vertices have i.i.d. weights governed by some law with support in where are constants. We denote the second moment of the weights by . An edge is drawn between nodes and with probability when and have the same spin and with probability otherwise. The model parameters and are constant.

In the underlying paper we extend results in [25] to the degree-corrected setting. More specifically, we prove that when , it is information-theoretically impossible to estimate the spins in a way positively correlated with the true community structure.

In a follow-up paper [13], we show that above the threshold (i.e., ), reconstruction is possible based on the second eigenvector of the so-called non-backtracking matrix. This is an extension of the results in [3] for the ordinary Stochastic Block Model.

We remark that there is an interpretation of the threshold in terms of eigenvalues of the conditional expectation of . Indeed, if denotes the adjacency matrix and and are the vectors defined for by and , then

 E[A|ϕ1,…,ϕn]=a+bnψ1ψ∗1+a−bnψ2ψ∗2−a1ndiag{ϕ2u}.

So that, in probability,

 E[A|ϕ1,…,ϕn]ψ1=(a+b21nn∑u=1ϕ2u)ψ1+(a−b21nn∑u=1σuϕ2u)ψ2+O(1)→a+b2Φ(2)ψ1,

and

 E[A|ϕ1,…,ϕn]ψ2=(a−b21nn∑u=1ϕ2u)ψ2+(a+b21nn∑u=1σuϕ2u)ψ1+O(1)→a−b2Φ(2)ψ2,

by the law of large numbers. Now, the condition is equivalent to

### 1.1 Our results

It is a well-known fact that in the sparse graph, vertices are isolated whose type thus cannot be recovered by any algorithm. Therefore, the best we can ask for is that our reconstruction is positively correlated with the true partition:

###### Definition 1.1.

Let be an observation of the degree-corrected planted partition-model, with true communities . Further, let be a reconstruction of the communities, based on the observation , such that . Then, we say that is positively correlated with the true partition if there exists such that

 1nn∑u=11{σu=ˆσu}≥12+δ,

with high probability.

Our main result is as follows:

###### Theorem 1.2.

Let be an observation of the degree-corrected planted partition-model with . Then, no reconstruction based on is positively correlated with .

As mentioned above, this theorem is an extension of the result in [25]. Their strategy, that we shall follow, invokes a connection with the tree reconstruction problem (see for instance [23]): deducing the sign of the root based on all the spins at some distance from the root. Indeed, we shall see that the -neighbourhood of a vertex looks like the following random labelled tree, that we denote by :

We begin with a single particle, the root , having spin and weight (which we often take random). The root is replaced in generation by particles of spin and particles of spin . Further, the weights of those particles are i.i.d. distributed following law , the size-biased version of , defined for by

 ν∗(x)=1Φ(1)∫xϕminydν(y). (1.1)

For generation , a particle with spin and weight is replaced in the next generation by particles with the same spin and particles of the opposite sign. Again, the weights of the particles in generation follow in an i.i.d. fashion the law . The offspring-size of an individual is thus a Poisson-mixture.

### 1.2 General proof idea

We first note that reconstruction is senseless when , because in this regime there is no giant component111Indeed, the main result in [2] concerns the existence, size and uniqueness of the giant component. In particular, in the setting considered here, a giant component emerges if and only if . We shall henceforth assume a giant component to emerge.. Note further that already implies .

To prove that detection is not possible when and , we show in Theorem 4.2 that for uniformly chosen vertices and ,

 P(σu=+|σv,G)P→12, (1.2)

as . I.e., it is already impossible to decide the sign of two random vertices, which is an easier problem than reconstructing the group-membership of all vertices (made precise in Lemma 4.3). To establish (1.2), we condition on the boundary spins of an neighbourhood around , where tends to infinity: it should make reconstruction easier. But, as we shall see, long-range correlations in this model are weak (Lemma 4.1). Hence, we can leave out the conditioning on the spin of , so that we are precisely in the setting of a tree-reconstruction problem, see Section 2. In fact, we shall prove (Theorem 2.4) that reconstruction of the sign of the root in a tree based on the spins at depth (where ), is impossible when .

### 1.3 Outline and differences with ordinary Planted-Partition model

Due to the presence of weights, the offspring in the branching process is governed by a Poisson-mixture. Section 2 deals with these type of branching processes. The main theorem (i.e., Theorem 2.4) deals with a reconstruction problem on sequences of trees rather than a single random tree as in Theorem in [25].

In Section 3 we establish a coupling between the local neighbourhood and . This result is different from the coupling in [2], because we need the weights in the graph and their counterparts in the branching process to be exactly the same.

Finally, in Section 4 we show that long-range interactions are weak. The proof of Lemma 4.1 is based on an idea in the proof of Lemma in [25]. Note however that (besides the presence of weights) the statement of our Lemma 4.1 is slightly stronger than Lemma in [25], see below for details.

### 1.4 Background

Without the degree correction (i.e., ), the authors of [9] where the first to conjecture a phase-transition for the ordinary planted partition model based on ideas from statistical physics: Clustering positively correlated with the true spins is possible if and impossible if . They conjectured further that using the the so-called belief propagation algorithm would establish the positive part. In [17] ’spectral redemption conjecture’ was made: detection using the second eigenvalue of the so called non-backtracking matrix would also establish the positive part.

The work [6] showed that positively correlated results exist in the sparse case, however not applying all the way down to the threshold. The remainder of the positive part in was established [20] by using a matrix counting the number of self-avoiding paths in the graph. The work [24] establishes independently of [20] the positive part of the conjecture in [9]. Further, the authors of [24] show impossibility in [25]. In fact they show a bit more, namely that for reconstructions are never positively correlated. We shall here extend their results for the DC-PPM by relying on similar techniques.

Recovering the planted partition (without degree-corrections) often coincides with finding the minimum bisection in the same graph. That is, finding a partition of the graph such that the number of edges between separated components (the bisection width) is small. This problem is NP-hard [10].

Graph bisection on random graphs has been studied intensively. For instance, [4] studies the collection of labelled simple random graphs that have nodes, node-degree at least and bisection width . For these graphs the minimum bisection is much smaller than the average bisection. The main result is a polynomial-time algorithm based on the maxflow-mincut theorem, that finds exactly the minimum bisection for almost all graphs.

Another example is given in [10]. There, the authors consider the uniform distribution on the set of all graphs that have a small cut containing at most a fraction of the total number of edges for some fixed . Those authors show that, if in the planted partition model are fixed (for ), then the underlying community structure coincides with the minimum bisection and it can be retrieved in polynomial time. This result is improved in [15].

In [21] the case of non-constant and is analysed. A spectral algorithm is presented that recovers the communities with probability if . Here is a sufficiently large constant.

Positive results of spectral clustering in the DC-SBM have been obtained by various authors. The work [8] introduces a reconstruction algorithm based on the matrix that is obtained by dividing each element of the adjacency matrix by the geometric mean of its row and column degrees.

The extended planted-partition is studied in [7]. In that model, an edge is present between and with probability where , the average weight. The main result is a polynomial time algorithm that outputs a partitioning that differs from the planted clusters on no more that nodes. This recovery succeeds only under certain conditions: the minimum weight should be a fraction of the average weight and the degree of each vertex is .

The article [18] gives an algorithm based on the adjacency matrix of a graph together with performance guarantees. The average degree should be at least of order . However, since the spectrum of the adjacency matrix is dominated by the top eigenvalues [5], the algorithm does a poor job when the degree-sequence is very irregular.

The authors of the underlying paper propose in [12] an algorithm that recovers consistently the block-membership of all but a vanishing fraction of nodes, even when the lowest degree is of order . It outperforms algorithms based on the adjacency matrix in case of heterogeneous degree-sequences.

## 2 Broadcasting on the branching process

Here we repeat without changes the definition of a Markov broadcasting process on trees given in [25]. Let be an infinite tree with root . Given a number , define a random labelling . First, draw uniformly in . Then, conditionally independently given , take every child of and set with probability and otherwise. Continue this construction recursively to obtain a labelling for which every vertex, independently, has probability of having the same label as its parent.

Suppose that the labels at depth in the tree are known (here, ). The paper [11] gives precise conditions as to when reconstruction of the root label is feasible using the optimal reconstruction strategy (maximum likelihood), i.e., deciding according to the sign of . Interestingly, this is completely decided by the branching number of .

###### Definition 2.1.

The branching number of a tree , denoted by , is defined as follows:

• If is finite, then ;

• If is infinite, then where the infimum is taken over all cutsets .

Theorem in [11] reads tailored to our needs:

###### Theorem 2.2.

(Theorem in [11]) Consider the problem of reconstructing from the spins at the th level of . Define as the difference between the probability of correct and incorrect reconstruction given the information at level :

 Δm:=∣∣P(τρ=+|τ∂Tm)−P(τρ=−|τ∂Tm)∣∣.

If then .
If, however, then .

Note that in this theorem the tree is fixed, compared to the setting in this paper where the multi-type branching process defined in Section 1.1 is considered. But, it can be easily seen that the spins on a fixed instance of are distributed according to the above broadcasting process with error probability 222Indeed, instances of the tree when ignoring spins are generated according to a Galton-Watson process where the number of offspring of a particle is an independent copy of Poi , with governed by . We obtain the spins by giving particles, independently, the same spin as its parent with probability and the opposite sign with probability . Thus, a particle gives birth to particles of the same sign, and particles of the opposite sign. Those numbers are seen to be independent. . We thus need to calculate the branching number of a typical instance :

###### Proposition 2.3.

Assume that . Consider the multi-type branching process , where the root has spin drawn uniformly from and weight governed by . Then, given the event that the branching process does not go extinct, almost surely.

###### Proof.

Denote the multi-type branching process by . Assume w.l.o.g. that the root has children denoted as . Denote by the subtree of all particles with common ancestor . We observe that if and only if for all .

Now, conditional on the spin of the root, are i.i.d. copies of with weight governed by the biased law . The latter is a Galton-Watson process with offspring mean . Hence Proposition in [19] entails that a.s. ∎

Note that it can in fact be easily proved that almost surely.

We conclude with the main theorem of this section. Note that we assume that , so that the branching process does not die out with non-zero probability. Remark further that the theorem is a bit more precise than Theorem in [25] (which deals with unweighed Poisson trees), in the sense that we need to re-sample the tree for each . Indeed, in the coupling result Theorem 3.1 below we re-sample for each .

###### Theorem 2.4.

Assume that . Let be a collection of i.i.d. copies of . Denote for each tree its spins by . Further, let be an unbounded non-decreasing function. Assume that , then

 P(τnρ=+|TnR(n),τn∂TnR(n))P→12,

as .

###### Proof.

We begin by describing the above broadcasting process on random trees more precisely. By the triple we denote the underlying probability-space of the following stochastic process: Let be the branching process with root where we ignore all types on it (we denote the collection of its realizations by , and we let be a sigma-algebra on it). We define a new random labelling on every instance of by running the Markov broadcast process. I.e., is uniformly drawn from and each child has the same spin as its parent with probability .

Let, for each , be an independent copy of . Formally, the random variable is thus a mapping from to : it therefore makes sense to define the pull-back measure for by .

With this notation,

 E[∣∣∣P(τnρ=+|TnR(n),τn∂TnR(n))−12∣∣∣] =∫Ω′E[∣∣∣P(τnρ=+|TnR(n),τn∂TnR(n))−12∣∣∣∣∣∣Tn=T]dPT(T) =∫Ω′E[∣∣∣P(τρ=+|T=T,τ∂TR(n))−12∣∣∣]dPT(T).

Since Br almost surely, almost surely. Consequently,

 fn(T):=E[∣∣∣P(τρ=+|T=T,τ∂TR(n))−12∣∣∣]→0

for almost every realization of . Because , it is the immediate consequence of Lebesgue’s dominated convergence theorem that

 P(τnρ=+|TnR(n),τn∂TnR(n))→12,

in as .

Finally, it is a well-known fact that convergence in implies convergence in probability. ∎

## 3 Coupling of local neighbourhood

This section has as its objective to establish a coupling between the local neighbourhood of an arbitrary fixed vertex in the DC-PPM and . The main result is the following theorem, where we let , , and be random instances of , its spins and its weights, respectively.

###### Theorem 3.1.

Let , with . Let be a uniformly picked vertex in , where for each , is an instance of the DC-PPM. Let for each , be an independent copy of , then

 P((GR(n)(ρ),σGR,ϕGR)=(TnR(n),τnTR,ψnTR))=1−n−12log(4/e).

We defer its proof to the end of this section. It uses an alternative description of the branching process in Section 1.1.

### 3.1 Alternative description of branching process

We obtain an alternative description of the graph by considering a particle with spin and weight to be of type . We denote the law of by , i.e., for , Two distinct vertices and are then joined by an edge with probability , where is defined for by

 κ(x,y)=|xy|(1{xy>0}a+1{xy<0}b). (3.1)

Analogously, we obtain the following equivalent description of the branching process: We begin with a single particle of type governed by , giving birth to Poi children, where for , and ,

 λx(A)=∫Aκ(x,y)dμ(y). (3.2)

Conditional on the children have i.i.d. types governed by 333Note that if has law , then for any , . Hence, we can identify sign with the particle’s spin and with its independent weight., where for , and ,

 μ∗x(A)=λx(A)λx(S)=∫A(aa+b1xy>0+ba+b1xy<0)|y|dν(|y|)Φ(1). (3.3)

For generation , all particles give birth independently in the following way: A particle with type is replaced in the next generation by Poi children, again with i.i.d. types governed by .

In [2] it is shown that local neighbourhoods of the graph are described by the above branching process, if we ignore the types. (To be precise: the equivalent description used in [2] is that a particle of type gives birth to Poi children with type in , for any . Those numbers are independent for different sets and different particles.)

The coupling-technique in [2] uses a discretization of as an intermediate step, thereby losing some information: types in the tree deviate slightly from their counterparts in the graph. We shall therefore use another coupling method, presented below, so that the types in graph and branching process are exactly the same.

### 3.2 Coupling

We use the following exploration process: At time , choose a vertex uniformly in , where is an instance of the DC-PPM. Initially, it is the only active vertex: . All other vertices are neutral at start: . No vertex has been explored yet: . At each time we arbitrarily pick an active vertex in that has shortest distance to , and explore all its edges in : if for , then we set active in step , otherwise it remains neutral. At the end of step , we designate to be explorated. Thus,

 E(m+1)=E(m)∪{u},
 A(m+1)=(A(m)∖{u})∪(N(u)∩U(m)),

and,

 U(m+1)=U(m)∖N(u).

Our aim in this section is to show that the exploration process and the branching process are equal upto depth (defined in Theorem 3.1) with probability tending to one for large . We do this in two steps:

Firstly, we establish that the i.i.d. vertices in follow a law such that

 ∣∣∣∣μ(m)−μ∣∣∣∣TV=O(mn).

This is the content of the following:

###### Lemma 3.2.

Let be the vertices in , with types . Then, the vertices in are i.i.d. with law where

 dμ(m)(⋅)=g(⋅)dμ(⋅)∫Sg(z)dμ(z), (3.4)

with

 g(⋅)=m∏i=1(1−κ(xi,⋅)n). (3.5)

Further, in the regime , there exists such that for all :

 ∣∣∣∣μ(m)x1,…,xm−μ∣∣∣∣TV≤2κmaxmn,

if .

Secondly, if has type , then its neighbours in (i.e., those vertices that will be added to ) are i.i.d. with law , which is away from in total variation distance. Further, we can approximate the number of neighbours by with error :

###### Lemma 3.3.

Assume has type . Let be the number of neighbours has in . Then, the types of those neighbours are i.i.d. with law , where

 dμ∗(m)x(⋅)= κ(x,⋅)dμ(m)(⋅)∫Sκ(x,y)dμ(m)(y). (3.6)

Recall from Lemma 3.2: if then

 ∣∣∣∣μ∗(m)x−μ∗x∣∣∣∣TV≤4κ3maxκ2minmn. (3.7)

Further,

 ∣∣∣∣D−\emphPoi(λx(S))∣∣∣∣TV≤κmaxn−|U(m)|n+3κ2maxmn. (3.8)

To establish the desired coupling, let us give names to all good events:

 Ar+1={∀u∈∂Gr:Du=ˆDu},
 Br+1={∀u∈∂Gr,v∈{1,…,Du}:Uuv=ˆUuv},
 Cr={|∂Gs|≤g(s)=2sMslog(n) ∀s≤r},

where, for (we identify ),

• ;

and where, conditional that has type ,

• ;

• moreover, for :

• denotes the type of child of vertex ;

• is a random variable with law .

The types attached to siblings are independent conditional on their parents type.

With the above lemma’s established, the event

 Er=r⋂s=1{As∩Bs∩Cs}

happens indeed w.h.p.:

###### Lemma 3.4.

For any integer ,

 P(Er+1|Er)≥1−n3Clog(2κmax)−1−n−log(4/e),

for large enough .

The events and alone do not contain enough information to completely reconstruct the neighbourhood of : vertices in might be merged among each other, or it is possible that they share a child in . But, those events, are rare. Indeed, let be the event that no vertex in has more than one neighbour outside and that there are no edges in . Then, we have the following:

###### Lemma 3.5.

Let , then

 P(Kr|CR)≥1−n3Clog(2κmax)−1,

for large enough .

###### Proof of Lemma 3.2.

Consider vertex with type . We show first that, conditional on and , has law . To this end we shall calculate for ,

 P(Y≤y|v∉N(1,…,m),X1=x1,…,Xm=xm) (3.9)

since . Recall (3.5) and observe that

 g(⋅)=P(v∉N(1,…,m)|Y=⋅,X1=x1,…,Xm=xm).

Hence, the denominator in (3.9) is just

 P(v∉N(1,…,m)|X1=x1,…,Xm=xm)=∫Sg(z)dμ(z). (3.10)

Evaluating the numerator yields,

 P(Y≤y)P(v∉N(1,…,m)|Y≤y,X1=x1,…,Xm=xm) (3.11) =P(Y≤y)∫y−ϕming(z)dp(z)=∫y−ϕming(z)dμ(z),

where, we defined for , . By combining (3.10) and (3.11) we establish (3.4), i.e., has distribution .

To see that indeed approximates , observe that

 (1−κmaxn)m≤g(⋅)∫Sg(z)dμ(z)≤1(1−κmaxn)m.

We use Taylor’s theorem to appropriately bound both sides for large :

 (1−κmaxn)m=1−κmaxmn+O⎛⎝κ2max2(mn)2⎞⎠,

where and,

where . Consequently, there exists such that

 ∣∣∣∣μ(m)−μ∣∣∣∣TV ≤∫S∣∣ ∣∣g(y)∫Sg(z)dμ(z)−1∣∣ ∣∣dμ(y)≤2κmaxmn,

for all . ∎

###### Proof of Lemma 3.3.

Put and let denote the types of the neighbours of .

Let be an arbitrary measurable function. The first claim follows if we prove that

 E[e−∑Dj=1f(Yj)∣∣D=d]=(∫Se−f(y)dμ∗(m)x(y))d (3.12)

Now,

 E[e−∑Dj=1f(Yj)1D=d]

where, conditioning on means that . We have,

Hence,

 E[e−∑Dj=1f(Yj)∣∣D=d]=1(nmd)∑F⊂[nm],|F|=dE[e−∑j∈Ff(Yj)∣∣F].

Conditional on , the types are i.i.d., thus

 E[e−∑j∈Ff(Yj)∣∣F]=⎛⎜⎝∫Se−f(y)κ(x,y)ndμ(m)(y)∫Sκ(x,y)ndμ(m)(y)⎞⎟⎠d,

which combined with (3.6) gives (3.12), our first claim.

Further, an explicit calculation yields

 ∫S|dμ∗(m)x−dμ∗x|≤4κ3% maxκ2minmn,

establishing (3.7).

For the last claim, observe that Bin, where . Hence,

 ∣∣∣∣Bin(nm,p)−Poi(nmp)∣∣∣∣%TV≤nm∑i=1p2≤κ2maxn.

Standard bounds for Poisson random variables entail the existence of a constant such that Poi Poi. Consequently,

 1CPoi∣∣∣∣Poi(nmp)−Poi(λx(S))∣∣∣∣TV ≤|nm−n|p+∣∣∣∫Sκ(x,y)dμ(m)(y)−∫Sκ(x,y)dμ(y)∣∣∣ ≤κmax|nm−n|n+κmax∫S∣∣dμ(m)(y)−dμ(y)∣∣ ≤κmax|nm−n|n+2κ2maxmn.

Thus,

###### Proof of Lemma 3.4.

Write . We have

 P(Er+1|Er)≥P(Br+1|Er)−P(¬Ar+1|Er)−P(¬Cr+1|Er).

Now,

 P(Br+1|Er,nr) ≥1−nr∑u=1P(¬B(u)r+1∣∣u−1⋂v=1B(v)r+1,Er), (3.13)

where Denote the already explored vertices by (where ) and their types as . Conditional on those types, the vertices in are i.i.d. with distribution . Hence:

 P(B(u)r+1∣∣u−1⋂v=1B(v)r+1,Er,nr,X1,…,Xm)=P(B(u)r+1∣∣X1,…,Xm) (3.14) ≥P(B(u)r+1∣∣Du≤


text:
# 3.4 Addition of velocities  (Page 5/12)

 Page 5 / 12

## Making connections: relativity and einstein

Because Einstein was able to clearly define how measurements are made (some involve light) and because the speed of light is the same for all observers, the outcomes are spectacularly unexpected. Time varies with observer, energy is stored as increased mass, and more surprises await.

## Phet explorations: motion in 2d

Try the new "Ladybug Motion 2D" simulation for the latest updated version. Learn about position, velocity, and acceleration vectors. Move the ball with the mouse or let the simulation move the ball in four types of motion (2 types of linear, simple harmonic, circle).

## Summary

• Velocities in two dimensions are added using the same analytical vector techniques, which are rewritten as
${v}_{x}=v\phantom{\rule{0.25em}{0ex}}\text{cos}\phantom{\rule{0.25em}{0ex}}\theta$
${v}_{y}=v\phantom{\rule{0.25em}{0ex}}\text{sin}\phantom{\rule{0.25em}{0ex}}\theta$
$v=\sqrt{{v}_{x}^{2}+{v}_{y}^{2}}$
$\theta ={\text{tan}}^{-1}\left({v}_{y}/{v}_{x}\right).$
• Relative velocity is the velocity of an object as observed from a particular reference frame, and it varies dramatically with reference frame.
• Relativity is the study of how different observers measure the same phenomenon, particularly when the observers move relative to one another. Classical relativity is limited to situations where speed is less than about 1% of the speed of light (3000 km/s).

## Conceptual questions

What frame or frames of reference do you instinctively use when driving a car? When flying in a commercial jet airplane?

A basketball player dribbling down the court usually keeps his eyes fixed on the players around him. He is moving fast. Why doesn’t he need to keep his eyes on the ball?

If someone is riding in the back of a pickup truck and throws a softball straight backward, is it possible for the ball to fall straight down as viewed by a person standing at the side of the road? Under what condition would this occur? How would the motion of the ball appear to the person who threw it?

The hat of a jogger running at constant velocity falls off the back of his head. Draw a sketch showing the path of the hat in the jogger’s frame of reference. Draw its path as viewed by a stationary observer.

A clod of dirt falls from the bed of a moving truck. It strikes the ground directly below the end of the truck. What is the direction of its velocity relative to the truck just before it hits? Is this the same as the direction of its velocity relative to ground just before it hits? Explain your answers.

## Problems&Exercises

Bryan Allen pedaled a human-powered aircraft across the English Channel from the cliffs of Dover to Cap Gris-Nez on June 12, 1979. (a) He flew for 169 min at an average velocity of 3.53 m/s in a direction $\text{45º}$ south of east. What was his total displacement? (b) Allen encountered a headwind averaging 2.00 m/s almost precisely in the opposite direction of his motion relative to the Earth. What was his average velocity relative to the air? (c) What was his total displacement relative to the air mass?

(a) $\text{35}\text{.}8 km$ , $\text{45º}$ south of east

(b) $5\text{.}\text{53 m/s}$ , $\text{45º}$ south of east

(c) $\text{56}\text{.}1 km$ , $\text{45º}$ south of east

A seagull flies at a velocity of 9.00 m/s straight into the wind. (a) If it takes the bird 20.0 min to travel 6.00 km relative to the Earth, what is the velocity of the wind? (b) If the bird turns around and flies with the wind, how long will he take to return 6.00 km? (c) Discuss how the wind affects the total round-trip time compared to what it would be with no wind.

Preparation and Applications of Nanomaterial for Drug Delivery
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
I only see partial conversation and what's the question here!
what about nanotechnology for water purification
please someone correct me if I'm wrong but I think one can use nanoparticles, specially silver nanoparticles for water treatment.
Damian
yes that's correct
Professor
I think
Professor
what is the stm
is there industrial application of fullrenes. What is the method to prepare fullrene on large scale.?
Rafiq
industrial application...? mmm I think on the medical side as drug carrier, but you should go deeper on your research, I may be wrong
Damian
How we are making nano material?
what is a peer
What is meant by 'nano scale'?
What is STMs full form?
LITNING
scanning tunneling microscope
Sahil
how nano science is used for hydrophobicity
Santosh
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest. Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.? How this robot is carried to required site of body cell.? what will be the carrier material and how can be detected that correct delivery of drug is done Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
Anam
Any one who tell me about Preparation and application of Nanomaterial for drug Delivery
Hafiz
what is Nano technology ?
write examples of Nano molecule?
Bob
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
why we need to study biomolecules, molecular biology in nanotechnology?
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
why?
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
anyone know any internet site where one can find nanotechnology papers?
research.net
kanaga
sciencedirect big data base
Ernesto
Introduction about quantum dots in nanotechnology
hi
Loga
Got questions? Join the online conversation and get instant answers!


text:
# How do you solve log_3(27)?

Nov 29, 2015

${\log}_{3} \left(27\right) = 3$

#### Explanation:

Finding the value $x = {\log}_{3} \left(27\right)$
is equivalent to finding $x$ such that ${3}^{x} = 27$
(this is basic to the definition of $\log$)

${3}^{1} = 3$
${3}^{2} = 9$
${3}^{3} = 27$

$x = 3$


text:
# What are $S$ and $L$?

In a helium atom, the total spin of the electrons is 0, suggesting that the total spin quantum number S is the sum of the ms quantum numbers (1/2-1/2=0). However, many sources say that the total spin quantum number S is the sum of the s quantum numbers, so in helium S should be 1 (s is always 1/2 for electrons).

In much the same way, I've seen some sources say that L is the sum of the ml quantum numbers and others say that L is the sum of the l quantum numbers.

So, which is correct?

Both $$L$$ and $$S$$ are quantum angular momenta.

Angular momentum is different in quantum mechanics (QM). Almost everything is different in QM.

In QM, angular momentum is complete if you give two numbers: the "angular momentum" and its "third component" $$M$$. So you give the pairs $$|l,\ m_l\rangle$$ and $$|s, \ m_s\rangle$$

So, any angular momentum is defined with those two numbers. But those numbers behave very differently.

The third component is additive. You add $$m$$'s without problem:

Total $$m$$ = $$m_1+m_2$$

On the other hand, $$l$$'s behave very differently. When we add two angular momenta, the total angular momentum (let's call it $$J$$), is different: it can go from $$|L-S|$$ to $$L+S$$

And the thing is that both things are called "sum", that's the reason of the confusion.

When you add two angular momenta (vectors) $$\vec{L}+\vec{S}=\vec{J}$$ That's okay, but this is the same as saying

$$|l,\ m_l\rangle \ + \ |s,\ m_s\rangle \ = \ |j,\ m_j\rangle$$

And the total $$m$$ adds normally: $$m_j=m_l+m_s$$, okay.

But $$j$$ is different. $$j$$ can go from $$|l-s|$$ to $$|l+s|$$ in unit steps.

In all angular momenta, as you know, $$m$$ can go from $$-l$$ to $$+l$$. And also $$m_s$$ from $$-s$$ to $$+s$$; and $$m_j$$ from $$-j$$ to $$+j$$.

So, if you have $$s=½$$, you can have $$m_s=\pm ½$$

But if you add two spins, $$s_1+s_2$$, the resulting $$j$$ can be 0 or 1.

For $$j=0$$, $$m_j$$ can only be 0 as well. But for $$j=1$$, $$m$$ can have three values: $$m_j={-1,0,1}$$.

So, "summing two spins" can mean that total spin is "J=1" but "M=0".

• Brilliant, thank you very much. – Ali Chopping Jan 9 at 12:13
• while in general this is an excellent answer, may I object to the line $|l, m_l\rangle + |s, m_s⟩ = |j, m_j\rangle$? This makes it seem as if $l$ and $s$ are referring to the same part of Hilbert space, and that $|j, m_j\rangle$ is something like a superposition of them, while this is not correct. The correct formatting will be $|l, m_l \rangle \otimes |s, m_s\rangle = |j, m_j\rangle$ – yu-v Jan 9 at 13:53


text:
# Tag Info

0

Working with a queue automaton for me is intuitively equivalent to working with a circular tape. Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw_1Bw_2$. Now we can one by one eat a letter after $A$ and one after $B$. For the deterministic variant it suffices to put $B$ exactly in the middle of the ...

0

Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$. Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's ...

3

McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a ...

1

This can also be proved easily using Myhill-Nerode theorem. Myhill-Nerode Theorem: Given a language $L \subseteq \Sigma^*$, Suppose $$\forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^* ,L(xz) \neq L(yz))$$ where S is an infinite set. Then L is not a regular language. (Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.) For the ...

1

The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: divide $m$ by $c$, and increment $c$. The algorithm terminates when one of the following happens: $m = 1$, in which case you can declare success; or $m$ is not ...

1

This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ ...

0

A string is accepted by an NFA if there is a sequence of moves such that it can reach a final state at the end of the string. As you said, assume that for $w=0110$ after reading $011$ we are in a final state (called $q$) and there is no transition like $\delta(q,0)$, this is when we encounter a situation called dead configuration. At this point we can't just ...

0

You almost got it Right in the comments, so I will give you the last push along with one way to think about it. In the right automaton: the language of the automaton is simply $0\cdot L(q_1)$, where $L(q_1)$ is the set of words that can be accepted from $q_1$. Its not hard to see that a word $w$ is accepted from $q_1$ iff it $w$ is the empty word $\epsilon$,...

1

The Rule 110 cellular automaton is apparently Turing-complete. If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches. See also https://softwareengineering.stackexchange.com/q/230538/34181.

2

Here are the first few words accepted by the DFA on the right: $$0 \\ 00 \\ 000,010 \\ 0000,0010,0100,0110 \\ 00000,00010,00100,00110,01000,01010,01100,01110$$ The DFA on the left accepts a subset of these words. Here are the words it does not accept: $$010 \\ 0010,0100 \\ 00010,00100,01000,01110$$ Perhaps you can use these lists to obtain a guess on the ...

0

The following doesn't necessarily answer the question, but might be of interest. Suppose that $L$ is a regular language consisting entirely of palindromes, and suppose that $L$ is accepted by a DFA having $n$ states. According to the pumping lemma, every word $w \in L$ of length at least $n$ can be decomposed as $xyz$ such that $|xy| \leq n$, $y \neq \... 2 I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short). Let$\...

3

Consider a nondeterministic Büchi automaton $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, \alpha\rangle$. The acceptance condition of $\mathcal{A}$ is a subset of states $\alpha\subseteq Q$, and an infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots$ is accepting iff $r$ visits a state in $\alpha$ infinitely many times. ...

Top 50 recent answers are included


text:
# What triggers a nuclear decay?

I understand that the decay of a nucleus is a random event and one cannot predict exactly when it will happen for a particular nucleus. What I would like to know is what triggers this event to happen?

The surprising answer is that nothing triggers it. In quantum mechanics all we can talk about is the probabilities of various events happening: whether they actually happen in a given period is truly random. There is no secret mechanism which we could find which controls whether an event happens or not.

Well, there are, really, three-and-a-half possibilities:

• the first possibility is that there is no secret mechanism, things really are random as I said above;
• the second possibility is that there is some secret mechanism, but the rules of the game say that we could never observe such a mechanism, even in principle;
• the third possibility is that there's not really a mechanism, but somehow there's just a huge list saying what happens when for every event, which list we could also never discover, even in principle;
• the final half possibility are that the experiments which show that one of the preceding three possibilities must be true are incorrect.

I think most physicists think that the first possibility is true, but there are significant minorities who are unhappy with it in various ways. Well, perhaps everyone is unhappy with it, but there is a significant minority who are so unhappy with it that they devote a lot of effort into investigating other options. Einstein, famously, was one of this minority.

## Bell's theorem

The core thing here is a famous result called Bell's theorem. What Bell concluded was that

In a theory in which parameters are added to quantum mechanics to determine the results of individual measurements, without changing the statistical predictions, there must be a mechanism whereby the setting of one measuring device can influence the reading of another instrument, however remote. Moreover, the signal involved must propagate instantaneously, so that such a theory could not be Lorentz invariant.

What this means is that if we want to explain the predictions of quantum mechanics by what I've called a 'secret mechanism' above, and which physicists call a 'hidden variable', then this mechanism must allow the instantaneous transmission of information between objects, however far separated they are. He then says that 'such a theory could not be Lorentz invariant': how bad is that?

It's bad. What it means is that such a theory is not compatible with special relativity, a theory which has been extremely well tested. In particular it means that if we had access to this secret mechanism, then assuming all the tests we've done of special relativity are not just wrong, we could build a time machine. In particular we could build a time machine which will send information into our own past. And this isn't just some kind of thorectical 'if we could make a black hole we could do this' thing: we could actually build such a thing for a reasonable amount of money (I don't know how much, but let's say for less money than was spent on the Apollo programme). This is very bad, to put it mildly.

So if we aren't willing to accept that this leads to the four options above, which I'll present in a different order.

• Perhaps the experiments which show that the predictions of quantum mechanics are correct are wrong, and we're off the hook. These experiments are really hard to do without loopholes, but all of the experiments done so far have been compatible with what quantum mechanics predicts. I think it's a safe assumption that the predictions made by quantum mechanics are in fact correct.
• Perhaps there is a secret mechanism, but life is arranged so that it can never be observed, even in principle. That's a horrible option I think, and in particular if there is this secret mechanism which can never be observed why not just assume there isn't? Science has to do with things that can be observed (even if such observation is very hard and perhaps beyond our abilities for the forseeable future), not with things that can't, even in principle.
• Perhaps there isn't a mechanism but things still are not random: everything is just predetermined, and in particular the results of the experiments we do and the choices we make while doing those experiments is all predetermined, so the experiments are meaningless. This is called 'superdeterminism' and, again, it's kind of uninteresting: if it's true then we can't know it is because, well, everything we do is predetermined.
• Perhaps there isn't a mechanism and things really are random and all we can know is various probabilities.

The last of these is, I think, the standard view, and it's the view that gives rise to my initial statement: nothing triggers the decays, whether or not a decay happens is truly random and all we can know is the probability that it will happen in a given interval.

## Entanglement and randomness

Bell's theorem is usually understood to refer to a phenonemon in quantum mechanics called entanglement: this is where measurements on two physically separated objects are correlated, and it turns out that they are correlated in such a way that the awkward options above are the only valid explanations (indeed Bell's theorem itself is the bit of maths that shows that these are the only options).

The reason this matters for atomic decay is that the theory which controls atomic decay is the same: quantum mechanics. So although Bell's theorem deals with entanglement, the theory that predicts entanglement is also the theory that controls atomic decay: if there are hidden variables behind atomic decay which mean it's not random they will be the same hidden variables that Bell's theorem show have such awkward properties if they exist.

It's also the case, I think, that atomic decay should produce particles which are entangled and which therefore should, in principle, be amenable to using as candidates in tests of quantum mechanics. I am not an expert on this so this is somewhat speculative on my part, but in beta decay the results are an electron and an antineutrino (or a positron and a neutrino). Both of these have spin, and I presume that their spins must be entangled (or entangled with each other and the spin of the nucleus which decayed). So in principle you could use these things in tests of entanglement. This is very much in principle because neutrinos are absurdly hard to detect.

Although such an experiment would be extremely hard to do, it would rule out the possibility that there is somehow some completely other, hitherto unknown, theory which controls atomic decay and which does allow prediction of when it happens. I think there are a lot of other reasons why this possibility is implausible: quantum mechanics works superbly well for one thing and we see no trace of any other theory which might apply for another, but such an experiment would conclusively show that it is what governs decay.

Note that Einstein was dead by the time Bell published his theorem: we don't know what he would have said if he had known about it.

• Wouldn't there be another possibility where there is some trigger but we just haven't identified it yet? – Mike Aug 19 '19 at 23:02
• @Mike: that's the 'all the experiments which validate the predictions of QM are wrong' case. QM predicts, testably, that such a mechanism ('trigger') must agree with Bell's theorem. So yes, this is a possibility, and that possibility is that QM is wrong. – tfb Aug 20 '19 at 10:06
• Doesn't this go too far? Op just asked about randomness, but here the discussion veers into the fact that entangled quantum states exist. These things seem orthogonal. The randomness question would be valid in a universe governed by purely classical probabilities and local phenomena. The entanglement question arises because "probabilities" switch to complex-valued, aka "the wave function", which is really a lot more interesting than a real-valued probability distribution. – David Tonhofer Aug 20 '19 at 15:11
• @DavidTonhofer: that's a good question. I think I have a good answer to it, and I'm going to add it to the answer: if you want to check it in a few minutes & comment again if you think I'm wrong or confused? – tfb Aug 20 '19 at 15:30
• @IronGremlin: I don't understand what you're asking, but if it can be formulated as a question then it's probably better to ask it as such where people better at this than me will see it! – tfb Aug 21 '19 at 9:04

If you look at the actual equations governing quantum mechanics, there is no randomness at all. The nucleus starts out in a state where it hasn't decayed. Over time, it evolves into a mixture of the undecayed state and the decayed state. It's like Schrodinger's cat. Gradually the mixture shifts more and more toward decay.

If an observer watches the nucleus to see whether it's decayed yet, then the observer also becomes a mixture of a state in which they have seen it decay and a state in which they haven't. For practical reasons, it's not possible to observe wave interference effects between human-scale objects, so we can't detect interference between the different states of the observer.

Therefore each state of the observer is cut off from the others, and they can't detect each other, it seems to the observer, in that particular state, as if something random has happened. It's then natural for that observer to stop thinking about the other possibilities which, to them, might as well not exist. If they stop keeping track of those other possibilities, they are doing something called the Copenhagen interpretation of quantum mechanics. The Copenhagen interpretation is an optional add-on to quantum-mechanics.

• That should be "superposition", not "mixture", right? Because superposition is the complex-linear combination of two basis state vectors (both states at the same time for real!), but mixture is the real-valued classical probability mix of two state vectors (one or the other but we don't know which). – David Tonhofer Aug 20 '19 at 14:52
• @DavidTonhofer: Yes, I'm just writing in nontechnical language, because of my perception of the level of the OP's knowledge. – Ben Crowell Aug 25 '19 at 0:44
• Not wanting to get into interpretations of quantum mechanics but ... just found at the arxiv: Interpretations of quantum theory: A map of madness – David Tonhofer Aug 25 '19 at 17:30

I am surprised that no one has discussed vacuum fluctuations as the trigger for these spontaneous nuclear decays. This question is just the nuclear physics analog of this question: An explanation of the Spontaneous Emission which applies to atomic physics. That spontaneous decays in atomic physics are triggered by vacuum fluctuations of the E&M field is the essence of Wigner-Weisskopf Theory.

Unlike atomic physics spontaneous nuclear decays can involve the strong and weak interactions as well as E&M. Vacuum fluctuations occur for these interactions as well. Physical manifestations of vacuum fluctuations include the Casimir force and the Lamb shift among other phenomena. A strong hint that these fluctuations are the trigger for nuclear decays is the fact that some decay half-lives have been observed to undergo small changes when the decaying nucleus is subjected to an altered (or polarized) environmemnt (see the discussion on "Changing Decay Rates" here https://en.wikipedia.org/wiki/Radioactive_decay#Theoretical_basis_of_decay_phenomena )

It is true that many theoretical treatments of vacuum fluctuations are based on perturbative calculations. This leads some to question whether vacuum fluctuations are not just an artifact of an approximation scheme, hence lacking physical reality. The success of some nonperturbative treatments for certain toy QFT models argues against that view (see: https://ncatlab.org/nlab/show/non-perturbative+quantum+field+theory).

• But that just shifts the problem to "vacuum fluctuations" (whatever these are ... and they are "ontologically suspect" aren't they) – David Tonhofer Aug 25 '19 at 17:24
• @DavidTonhofer I will edit my answer to address your comment. – Lewis Miller Aug 26 '19 at 2:32
• I think vacuum fluctuations fall with the definition of the wavefunction for a system , and just are within the general quantum mechanical probability frame. Experiments showing effects on decays (again statistically, not per decay) actually show that different boundary conditions affect the probability for the reaction. – anna v Aug 26 '19 at 3:30
• The link in the last sentence does not mention the words "vacuum" or "fluctuations". – fqq Aug 28 '19 at 12:31

This is a simpler statement:

Take the probability curve for throwing a dice and coming up with six. If the dice is true, not deliberately weighted, there is a probability of $$1/6$$ and there is no way for the player to know when juggling the dice what the outcome would be. If the dice were weighted so that some numbers came up more often, again it is only statistically that this will be seen, not at the individual throw.

Quantum mechanical wave functions ($$Ψ$$) ,with the boundary conditions of the problem, in this case the decay of a nucleus, weight the statistical distribution of quantum mechanical observations according to $$Ψ^*Ψ$$ in an analogous fashion as with a weighted dice.

The argument on how the dice behavior can be in principle calculated exactly in classical mechanics when all factors are taken into account, including the way of the throw, does not hold by axiomatic definition in quantum mechanics. Some physicists are still trying to find underlying deterministic mathematics , for quantum mechanics, but at the moment not successfully .

In any case, even for classical probabilities it is not possible to give an exact prediction of a probable path. even though in principle it is there when all the boundary values are taken in, because of the complexity. That is why probabilities were invented.

There cannot be a "trigger" for 6 coming up, even for weighted dice. More so for quantu mechanical cases, axiomatically at the moment, but even if a deterministic underlying theory is ever established , no "trigger" can exist because of the complexity.

The short answer is that systems tend to minimise their energy over time. The electrons around an atom will spontaneously drop to the lowest possible energy orbitals. Carbon spontaneously combines with oxygen to form carbon dioxide. Radioactive nuclei lower their energy by decaying.

A ball on the crest of a hill will not spontaneously roll down the hill; it needs some impetus to get itself moving. As soon as you push it, it will quickly roll down, because the position "ball in the valley" has less energy than "ball on top of the hill". But you need to get it moving. With very small things, like nuclei, you don't even need to do that - the nucleus doesn't have a well-defined position or momentum; it's as if the rock in our example could spontaneously move a few inches to the side, or gain a bit of velocity. The rock wouldn't stay on top of the hill for very long.

• This seems like a somewhat misleading classical analogy. Randomness in quantum mechanics doesn't have anything to do with equilibrium, and the Schrodinger equation doesn't say anything about things going to lower energy levels. The Schrodinger equation is symmetric under time-reversal, and it describes absorption of energy on an equal footing with emission. – Ben Crowell Aug 19 '19 at 22:48
• This Answer simply begs the question. The OP asks what triggers the decay of a nucleus at one time and not another, and you offer the analogy of a stone that rolls down a hill-- because it spontaneously moved an inch from the peak and o began to roll. Well, then, what triggered that initial movement at one time and not another? – Beta Aug 19 '19 at 23:22
• @BenCrowell The classical analogy is also symmetric; and the reason it (almost never) happens in the opposite direction is essentially the same as with the quantum case - though obviously, it's a lot easier for a stable nuclei to absorb e.g. a photon and an antineutrino of just the right energy than for a rock to absorb all of the energy released as it was rolling down the hill; it would be so unlikely for a lock to spontaneously roll back uphill that we can't really expect it would ever happen once in the whole universe. – Luaan Aug 20 '19 at 6:58
• @Beta No, I contrast the classical macroscopic phenomenon with what actually happens on the level of e.g. individual nuclei. The crucial distinction is the uncertainty in position and momentum - a rock doesn't spontaneously start rolling down the hill, but if you scaled it small enough, it would (for a narrow enough peak, of course). Of course there's no real macroscopic analogue (though classical waves do share the uncertainty, it's not quite the same kind). – Luaan Aug 20 '19 at 7:01


text:
HomeSciencePhysicsAir Waveguide from “Donut” Laser Beams

# Air Waveguide from “Donut” Laser Beams

• Physics 16, 11

A waveguide sculpted in air with lasers transmits mild over a distance of almost 50 meters, which is 60 occasions farther than earlier air-waveguide schemes.

Conventional optical waveguides reminiscent of optical fibers and planar waveguides encompass a core surrounded by a cladding with a decrease index of refraction. Light is effectively confined within the core by whole inner reflection on the core-cladding boundary. Optical fibers can transport mild over 100s of kilometers, however there are purposes—reminiscent of high-power transmission and atmospheric monitoring—the place the usage of fibers turns into impractical. Sending mild instantly by means of air just isn’t an choice, as diffraction results trigger the beam to unfold out. A possible answer is to “sculpt” waveguides within the air with laser pulses that produce a low-density cladding round a central core of unperturbed air. Using a brand new methodology with donut-shaped beams, Andrew Goffin from the University of Maryland, College Park, and colleagues have created a 45-m-long waveguide in air [1], reaching 60 occasions farther than the report they beforehand established for an air waveguide. The achievement might allow supply of high-power laser pulses to distant targets, opening up a variety of purposes reminiscent of distant sensing, lightning management (see Research News: A Laser-Based “Lightning Rod”), and microwave guiding.

The precept of an air waveguide is to fireplace a femtosecond laser pulse that opens a short-lived channel within the air by means of which a subsequent “probe” pulse can cross [2]. The first pulse generates the mandatory refractive index distinction between the core and cladding by heating the air constituents (reminiscent of N2, O2, and noble gases). The heated air expands in such a means that the density of the cladding turns into decrease than that of the encircling air. The ensuing air waveguide can final a couple of milliseconds—sufficient time to ship the probe sign by means of it.

But one may marvel, why is the primary laser pulse in a position to propagate forward of the probe with out spreading out? The reply lies in a nonlinear course of, referred to as filamentation, that outcomes from the steadiness of two competing results in air: a self-focusing impact induced by so-called Kerr nonlinearity and a defocusing impact induced by the formation of a plasma created by the heart beat itself [3]. Filamentation can keep a laser subject narrowly confined over a distance a lot better than that allowed by diffraction underneath linear propagation circumstances. However, a laser filament can have a width no bigger than

$\sim$

200

$𝜇\text{m}$

and a peak depth no better than

$\sim$

1014 W/cm2, finally limiting the typical energy within the filament core. For this purpose, the filaments generated by femtosecond laser pulses are usually not an efficient means—by themselves—for delivering excessive energy. But when used to generate an air waveguide, the filaments can create a path for high-power mild beams.

Goffin and colleagues first demonstrated the precept of air waveguiding in 2014. In that earlier experiment, the workforce handed a crimson laser beam by means of a four-segment masks to create 4 laser filaments in a sq. sample. These filaments fashioned a “light fence” that confined mild inside its core. The researchers used this air waveguide to transmit a 110-mJ pulse of inexperienced mild over a

$\sim$

70-cm size in air (see Viewpoint: A Waveguide Made of Hot Air).

The workforce has now achieved a powerful extension of this earlier work. The comparatively quick size of the group’s first air waveguide was because of the restricted variety of filaments within the mild fence, which restricted the width of the waveguide and the power of the density distinction between core and cladding. To improve the variety of filaments, one may naively think about utilizing a masks with extra segments to seed a bigger variety of filaments. However, in follow, it’s tough to make sure that the segments produce beam lobes with equal power and regionally easy part fronts. As an alternate, the authors use a donut-shaped beam or, technically talking, a easy Laguerre-Gaussian LG01 mode. They generate this mode utilizing a spiral part plate that concentrates the laser mild into a hoop with a diameter of some millimeters (Fig. 1). The concentrated mild initiates random filamentation in a uniform distribution across the donut ring. Using a bigger beam robotically produces extra filaments—supplied that the native laser fluence stays fixed—which implies the ensuing cladding covers the entire waveguide circumference.

In a hallway subsequent to their laboratory, the authors demonstrated air waveguiding over a distance of 45 m. Their waveguide generator was a 300-fs laser pulse with a wavelength of 800 nm and whole power of 120 mJ. This pulse was imprinted with the LG01 donut mode, inflicting it to type roughly 30 filaments round a hoop with diameter of 5.6 mm. Through the ensuing waveguide, the researchers transmitted a 7-ns probe pulse with a wavelength of 532 nm and a complete power of 1 mJ. A detector recorded the quantity of transmitted mild at varied distances, displaying that the sunshine delivered was round 20% better with the waveguide than with out (Fig. 2). The researchers additionally confirmed that the air waveguide had a protracted lifetime of tens of milliseconds.

This waveguiding scheme, nonetheless, has a couple of drawbacks, together with a comparatively excessive propagation loss, a poor mode profile of the guided beam, and a excessive power consumption within the formation of the air waveguide. To enhance the scheme’s efficiency, researchers might want to develop extra subtle light-sculpture methods. If the preliminary donut beam could be made extra uniform, then the a number of filaments ought to type in a extra deterministic means, and this could result in air waveguides which might be extra steady and reproducible.

In the long run, the authors envisage air waveguides that may ship high-power mild over distances of a kilometer or extra. They estimate that reaching kilometer-scale transmission would require a high-energy (as much as 2 J) LG01 pulse supporting ring protection of ~40–80 filaments. Such air waveguiding opens the door to many sensible purposes requiring environment friendly laser-energy supply to distant places within the ambiance. One instance is detecting fuel pollution by thrilling them with UV mild carried by means of the ambiance by an air waveguide [4, 5]. The emitted mild from the excited pollution may then be analyzed spectroscopically. An analogous scheme may remotely detect radioactive supplies [6]. Another attainable utility—which was just lately demonstrated—is lightning safety by means of the technology of a plasma channel that might information lightning to the bottom.

## References

1. A. Goffin et al., “Optical guiding in 50-meter-scale air waveguides,” Phys. Rev. X 13, 011006 (2023).
2. N. Jhajj et al., “Demonstration of long-lived high-power optical waveguides in air,” Phys. Rev. X 4, 011027 (2014).
3. A. Couairon and A. Mysyrowicz, “Femtosecond filamentation in transparent media,” Phys. Rep. 441, 47 (2007).
4. J. Kasparian et al., “White-light filaments for atmospheric analysis,” Science 301, 61 (2003).
5. J. Yao et al., “High-brightness switchable multiwavelength remote laser in air,” Phys. Rev. A 84, 051802 (2011).
6. R. M. Schwartz et al., “Remote detection of radioactive material using mid-IR laser–driven electron avalanche,” Sci. Adv. 5, aav6804 (2019).

Ya Cheng acquired his BS diploma from Fudan University in 1993 and PhD diploma from the Shanghai Institute of Optics and Fine Mechanics in 1998. He is at the moment director of the State Key Laboratory of Precision Spectroscopy on the East China Normal University. His analysis focuses on ultrafast nonlinear optics and photonic integration based mostly on skinny movie lithium niobate. He is an Optica Fellow and Fellow of the Institute of Physics, UK.

## Related Articles

Geophysics

### A Laser-Based “Lightning Rod”

Experiments on a Swiss mountain reveal {that a} high-powered laser can affect the trajectory of lightning strikes—a step towards laser-based lightning safety. Read More »

RELATED ARTICLES


text:
# Convolution theorem

Short description: Theorem in mathematics

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms. More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.

## Functions of a continuous variable

Consider two functions $\displaystyle{ g(x) }$ and $\displaystyle{ h(x) }$ with Fourier transforms $\displaystyle{ G }$ and $\displaystyle{ H }$: \displaystyle{ \begin{align} G(f) &\triangleq \mathcal{F}\{g\}(f) = \int_{-\infty}^{\infty}g(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R}\\ H(f) &\triangleq \mathcal{F}\{h\}(f) = \int_{-\infty}^{\infty}h(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R} \end{align} } where $\displaystyle{ \mathcal{F} }$ denotes the Fourier transform operator. The transform may be normalized in other ways, in which case constant scaling factors (typically $\displaystyle{ 2\pi }$ or $\displaystyle{ \sqrt{2\pi} }$) will appear in the convolution theorem below. The convolution of $\displaystyle{ g }$ and $\displaystyle{ h }$ is defined by: $\displaystyle{ r(x) = \{g*h\}(x) \triangleq \int_{-\infty}^{\infty} g(\tau) h(x-\tau)\, d\tau = \int_{-\infty}^{\infty} g(x-\tau) h(\tau)\, d\tau. }$

In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol $\displaystyle{ \otimes }$ is sometimes used instead.

The convolution theorem states that:[1][2]:eq.8

$\displaystyle{ R(f) \triangleq \mathcal{F}\{r\}(f) = G(f) H(f). \quad f \in \mathbb{R} }$

(Eq.1a)

Applying the inverse Fourier transform $\displaystyle{ \mathcal{F}^{-1} }$, produces the corollary:[2]:eqs.7,10

Convolution theorem

$\displaystyle{ r(x) = \{g*h\}(x) = \mathcal{F}^{-1}\{G\cdot H\}, }$

(Eq.1b)

where $\displaystyle{ \cdot }$ denotes point-wise multiplication

The theorem also generally applies to multi-dimensional functions.

This theorem also holds for the Laplace transform, the two-sided Laplace transform and, when suitably modified, for the Mellin transform and Hartley transform (see Mellin inversion theorem). It can be extended to the Fourier transform of abstract harmonic analysis defined over locally compact abelian groups.

### Periodic convolution (Fourier series coefficients)

Consider $\displaystyle{ P }$-periodic functions $\displaystyle{ g_{_P} }$ and $\displaystyle{ h_{_P}, }$ which can be expressed as periodic summations: $\displaystyle{ g_{_P}(x)\ \triangleq \sum_{m=-\infty}^{\infty} g(x-mP) }$   and   $\displaystyle{ h_{_P}(x)\ \triangleq \sum_{m=-\infty}^{\infty} h(x-mP). }$

In practice the non-zero portion of components $\displaystyle{ g }$ and $\displaystyle{ h }$ are often limited to duration $\displaystyle{ P, }$ but nothing in the theorem requires that. The Fourier series coefficients are: \displaystyle{ \begin{align} G[k] &\triangleq \mathcal{F}\{g_{_P}\}[k] = \frac{1}{P} \int_P g_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z}; \quad \quad \scriptstyle \text{integration over any interval of length } P\\ H[k] &\triangleq \mathcal{F}\{h_{_P}\}[k] = \frac{1}{P} \int_P h_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z} \end{align} } where $\displaystyle{ \mathcal{F} }$ denotes the Fourier series integral.

• The pointwise product: $\displaystyle{ g_{_P}(x)\cdot h_{_P}(x) }$ is also $\displaystyle{ P }$-periodic, and its Fourier series coefficients are given by the discrete convolution of the $\displaystyle{ G }$ and $\displaystyle{ H }$ sequences: $\displaystyle{ \mathcal{F}\{g_{_P}\cdot h_{_P}\}[k] = \{G*H\}[k]. }$
• The convolution: \displaystyle{ \begin{align} \{g_{_P} * h\}(x)\ &\triangleq \int_{-\infty}^{\infty} g_{_P}(x-\tau)\cdot h(\tau)\ d\tau\\ &\equiv \int_P g_{_P}(x-\tau)\cdot h_{_P}(\tau)\ d\tau; \quad \quad \scriptstyle \text{integration over any interval of length } P \end{align} }is also $\displaystyle{ P }$-periodic,[upper-alpha 1] and is called a periodic convolution. The corresponding convolution theorem is:

$\displaystyle{ \mathcal{F}\{g_{_P} * h\}[k] =\ P\cdot G[k]\ H[k]. }$

(Eq.2)

## Functions of a discrete variable (sequences)

By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now $\displaystyle{ \mathcal{F} }$ denotes the discrete-time Fourier transform (DTFT) operator. Consider two sequences $\displaystyle{ g[n] }$ and $\displaystyle{ h[n] }$ with transforms $\displaystyle{ G }$ and $\displaystyle{ H }$: \displaystyle{ \begin{align} G(f) &\triangleq \mathcal{F}\{g\}(f) = \sum_{n=-\infty}^{\infty} g[n]\cdot e^{-i 2\pi f n}\;, \quad f \in \mathbb{R}\\ H(f) &\triangleq \mathcal{F}\{h\}(f) = \sum_{n=-\infty}^{\infty} h[n]\cdot e^{-i 2\pi f n}\;. \quad f \in \mathbb{R} \end{align} }

The § Discrete convolution of $\displaystyle{ g }$ and $\displaystyle{ h }$ is defined by: $\displaystyle{ r[n] \triangleq (g * h)[n] = \sum_{m=-\infty}^\infty g[m]\cdot h[n - m] = \sum_{m=-\infty}^\infty g[n-m]\cdot h[m]. }$

The convolution theorem for discrete sequences is:[3][4]:p.60 (2.169)

$\displaystyle{ R(f) = \mathcal{F}\{g * h\}(f) =\ G(f) H(f). }$

(Eq.3)

### Periodic convolution

$\displaystyle{ G(f) }$ and $\displaystyle{ H(f), }$ as defined above, are periodic, with a period of 1. Consider $\displaystyle{ N }$-periodic sequences $\displaystyle{ g_{_N} }$ and $\displaystyle{ h_{_N} }$: $\displaystyle{ g_{_N}[n]\ \triangleq \sum_{m=-\infty}^{\infty} g[n-mN] }$   and   $\displaystyle{ h_{_N}[n]\ \triangleq \sum_{m=-\infty}^{\infty} h[n-mN], \quad n \in \mathbb{Z}. }$

These functions occur as the result of sampling $\displaystyle{ G }$ and $\displaystyle{ H }$ at intervals of $\displaystyle{ 1/N }$ and performing an inverse discrete Fourier transform (DFT) on $\displaystyle{ N }$ samples (see § Sampling the DTFT). The discrete convolution: $\displaystyle{ \{g_{_N} * h\}[n]\ \triangleq \sum_{m=-\infty}^{\infty} g_{_N}[m]\cdot h[n-m] \equiv \sum_{m=0}^{N-1} g_{_N}[m]\cdot h_{_N}[n-m] }$

is also $\displaystyle{ N }$-periodic, and is called a periodic convolution. Redefining the $\displaystyle{ \mathcal{F} }$ operator as the $\displaystyle{ N }$-length DFT, the corresponding theorem is:[5][4]:p.548

$\displaystyle{ \mathcal{F}\{g_{_N} * h\}[k] =\ \underbrace{\mathcal{F}\{g_{_N}\}[k]}_{G(k/N)} \cdot \underbrace{\mathcal{F}\{h_{_N}\}[k]}_{H(k/N)}, \quad k \in \mathbb{Z}. }$

(Eq.4a)

And therefore:

$\displaystyle{ \{g_{_N} * h\}[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{g_{_N}\} \cdot \mathcal{F}\{h_{_N}\}\}. }$

(Eq.4b)

Under the right conditions, it is possible for this N-length sequence to contain a distortion-free segment of a $\displaystyle{ g*h }$ convolution. But when the non-zero portion of the $\displaystyle{ g(n) }$ or $\displaystyle{ h(n) }$ sequence is equal or longer than $\displaystyle{ N, }$ some distortion is inevitable.  Such is the case when the $\displaystyle{ H(k/N) }$ sequence is obtained by directly sampling the DTFT of the infinitely long § Discrete Hilbert transform impulse response.[upper-alpha 2]

For $\displaystyle{ g }$ and $\displaystyle{ h }$ sequences whose non-zero duration is less than or equal to $\displaystyle{ N, }$ a final simplification is:

Circular convolution

$\displaystyle{ \{g_{_N} * h\}[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{g\} \cdot \mathcal{F}\{h\}\}. }$

(Eq.4c)

This form is often used to efficiently implement numerical convolution by computer. (see § Fast convolution algorithms and § Example)

As a partial reciprocal, it has been shown [6] that any linear transform that turns convolution into pointwise product is the DFT (up to a permutation of coefficients).

## Convolution theorem for inverse Fourier transform

There is also a convolution theorem for the inverse Fourier transform: $\displaystyle{ \mathcal{F}\{g*h\} = \mathcal{F}\{g\} \cdot \mathcal{F}\{h\} }$ $\displaystyle{ \mathcal{F}\{g \cdot h\}= \mathcal{F}\{g\}*\mathcal{F}\{h\} }$ so that $\displaystyle{ g*h= \mathcal{F}^{-1}\left\{\mathcal{F}\{g\}\cdot\mathcal{F}\{h\}\right\} }$ $\displaystyle{ g \cdot h= \mathcal{F}^{-1}\left\{\mathcal{F}\{g\}*\mathcal{F}\{h\}\right\} }$

## Convolution theorem for tempered distributions

The convolution theorem extends to tempered distributions. Here, $\displaystyle{ g }$ is an arbitrary tempered distribution (e.g. the Dirac comb) $\displaystyle{ \mathcal{F}\{f*g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\} }$ $\displaystyle{ \mathcal{F}\{\alpha \cdot g\}= \mathcal{F}\{\alpha\}*\mathcal{F}\{g\} }$ but $\displaystyle{ f = F\{\alpha\} }$ must be "rapidly decreasing" towards $\displaystyle{ -\infty }$ and $\displaystyle{ +\infty }$ in order to guarantee the existence of both, convolution and multiplication product. Equivalently, if $\displaystyle{ \alpha = F^{-1}\{f\} }$ is a smooth "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product.[7][8][9]

In particular, every compactly supported tempered distribution, such as the Dirac Delta, is "rapidly decreasing". Equivalently, bandlimited functions, such as the function that is constantly $\displaystyle{ 1 }$ are smooth "slowly growing" ordinary functions. If, for example, $\displaystyle{ g\equiv\operatorname{III} }$ is the Dirac comb both equations yield the Poisson summation formula and if, furthermore, $\displaystyle{ f\equiv\delta }$ is the Dirac delta then $\displaystyle{ \alpha \equiv 1 }$ is constantly one and these equations yield the Dirac comb identity.

## Notes

1. Proof: \displaystyle{ \begin{align} \int_{-\infty}^\infty g_{_P}(x - \tau) \cdot h(\tau)\,d\tau &= \sum_{k=-\infty}^\infty \left[\int_{x_o+kP}^{x_o+(k+1)P} g_{_P}(x - \tau) \cdot h(\tau)\ d\tau\right] \quad x_0 \text{ is an arbitrary parameter}\\ &=\sum_{k=-\infty}^\infty \left[\int_{x_o}^{x_o+P} \underbrace{g_{_P}(x - \tau-kP)}_{g_{_P}(x - \tau), \text{ by periodicity}} \cdot h(\tau + kP)\ d\tau\right] \quad \text{substituting } \tau \rightarrow \tau+kP\\ &=\int_{x_o}^{x_o+P} g_{_P}(x - \tau) \cdot \underbrace{\left[\sum_{k=-\infty}^\infty h(\tau + kP)\right]}_{\triangleq \ h_{_P}(\tau)}\ d\tau \end{align} }
2. An example is the MATLAB function, hilbert(g,N).

## References

1. McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. p. 118 (3-102). ISBN 0-03-061703-0.
2. Weisstein, Eric W.. "Convolution Theorem".
3. Proakis, John G.; Manolakis, Dimitri G. (1996) (in en), Digital Signal Processing: Principles, Algorithms and Applications (3 ed.), New Jersey: Prentice-Hall International, p. 297, sAcfAQAAIAAJ, ISBN 9780133942897, Bibcode1996dspp.book.....P
4. Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). Discrete-time signal processing (2nd ed.). Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2.   Also available at https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf
5. Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing. Englewood Cliffs, NJ: Prentice-Hall, Inc.. p. 59 (2.163). ISBN 978-0139141010.
6. Amiot, Emmanuel (2016). Music through Fourier Space. Zürich: Springer. p. 8. ISBN 978-3-319-45581-5.
7. Horváth, John (1966). Topological Vector Spaces and Distributions. Reading, MA: Addison-Wesley Publishing Company.
8. Barros-Neto, José (1973). An Introduction to the Theory of Distributions. New York, NY: Dekker.
9. Petersen, Bent E. (1983). Introduction to the Fourier Transform and Pseudo-Differential Operators. Boston, MA: Pitman Publishing.

## Further reading

• Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis, Dover, ISBN 0-486-63331-4
• Li, Bing; Babu, G. Jogesh (2019), "Convolution Theorem and Asymptotic Efficiency", A Graduate Course on Statistical Inference, New York: Springer, pp. 295–327, ISBN 978-1-4939-9759-6
• Crutchfield, Steve (October 9, 2010), "The Joy of Convolution", Johns Hopkins University, retrieved November 19, 2010

## Additional resources

For a visual representation of the use of the convolution theorem in signal processing, see:

de:Faltung (Mathematik)#Faltungstheorem 2 fr:Produit de convolution


text:
# Math Help - Invertible Matrices

1. ## Invertible Matrices

So there is a preposition that says;
If AB is invertible, then A is invertible and B is invertible too.

I uploaded the proof that I made, however I think it's not enough.

The problem with my proof, in my opinion, is that I showed that B and A is invertible from one side (either from left or right), so I think that in order to show that they are invertible I have to show that they have inverses from both side and they are the same, am I mistaken?

I would appreciate if you can verify, and tell me if my proof is correct, however if it's not don't tell me what's the right proof, I want to work on it. Thank you!

2. ## Re: Invertible Matrices

seems to me you can just say

Because AB is given to be invertible

$$(AB)^{-1}=B^{-1}A^{-1}$$

and because A is given to be invertible

$$(AB)^{-1}A=B^{-1}A^{-1}A$$

$$B^{-1}=(AB)^{-1}A$$

3. ## Re: Invertible Matrices

You can simplify it a great deal:

If AB is invertible, there is a matrix C such that C(AB) = (AB)C = I.

By associativity, we have: (CA)B = I, and A(BC) = I.

You are correct in that you have only shown B is left-invertible, and A is right-invertible.

We have 4 cases to consider:

1) A is invertible, B is not,

2) B is invertible, A is not,

3) Neither are invertible,

4) Both are invertible.

Let's look at case (1):

We know there is a matrix C such that (AB)C = I. Multiplying by A-1, we get:

A-1[(AB)C] = A-1I = A-1.

(A-1A)(BC) = A-1

BC = A-1

(BC)A = A-1A = I

B(CA) = I, showing B is right-invertible, with the same right-inverse as left-inverse, that is: B is invertible, contradicting our assumption. So case 1 cannot occur.

I think you can easily do case (2).

For case (3) show that B singular implies AB singular, which is impossible. What's left?

4. ## Re: Invertible Matrices

This is my the new proof. The credit goes to Deveno.
Though I am curious , is it possible to improve my first proof and get to the conclusion that A and B is invertible?

5. ## Re: Invertible Matrices

There is a problem with your proof for case (3), can you see what it is? (Hint: suppose A was the 0-matrix...does it follow from D ≠ I that AD ≠ A?).

You could modify your original proof by using column reduction instead of row reduction, this would give you the inverses on "the other side".

6. ## Re: Invertible Matrices

Originally Posted by Deveno
There is a problem with your proof for case (3), can you see what it is? (Hint: suppose A was the 0-matrix...does it follow from D ≠ I that AD ≠ A?).
But that is the case when A is the zero matrix, and we know for sure that A can't be the zero matrix, otherwise AB wouldn't be invertible, am I mistaken?


text:
# How to bake multiple fluid simulations in one scene?

If we understood correctly, Blender does not allow more than one domain for fluid simulation in a given scene. This means that any inflow (fluid) object will be transformed into only one domain object as the final simulated fluid. That is, regardless to any material assigned to inflow (fluid) objects, ultimately the domain material will apply. This causes difficulties to experience mixing fluids as questioned here.

In our recent trial in the following figures in order to simulate two different types of fluid (i.e., different material, etc) we simulated each separately and baked. Now we question how we can use the resulting images to put the fluids together in one animation? We tried to composite but didn't get acceptable results. Is this the correct approach or is it possible to bake multiple simulations in a scene?

Note that before we end up with separate baking we played sometime with multiple scenes, different layers but no success in putting two fluids together!

Here we share our results based on the method explained {here} and {here}.

The idea is simple:

1) define domain, fluid, obstacle etc
2) assign unique folder for baking cache
3) bake the fluid one
4) remove domain and fluid associations

Repeat the above as many times you want (here in the following example we did it three times). Trick: Indeed, for the following example we just baked once. Then we copied domain+obstacle two times. Relocated them on the scene. Duplicated all the cache on the disk two times in two folders that later we assigned in the above algorithm :))

We also used offset frame just to make the fluids a little bit different in stage:)

Note: domains can overlap or whatever, but notice that the fluids do not interact each other but overlay.

• We accepted our answer however credits go to iKLsR and gandalf3 for their directive comments above. – Developer Jan 10 '14 at 1:25

If you want multiple fluid sims create the first sim and bake it having specified a directory to cache. Now remove the fluid domain modifier from the first cube. Create your second sim, specify a new cache directory and bake. Repeat, disabling each domain except the one you are baking. You can set parameters different for each sim. When you have all 4 sims baked, go back and re-enable the Domain status so all four domains exist and be sure to specify which directory they will read from. To start them at different times, adjust the offset. To delay 100 frames, set the offset to -100. The fluids won't interact, but you can have them all running at once, you just can't bake them all with more than one domain present.


text:
FAC¶

FAC is a parallel fast adaptive composite grid solver for finite volume, cell-centred discretizations of smooth diffusion coefficient problems. To be precise, it is a FACx algorithm since the patch solves consist of only relaxation sweeps. For details of the basic overall algorithms, see [McCo1989]. Algorithmic particularities include formation of non-Galerkin coarse-grid operators (i.e., coarse-grid operators underlying refinement patches are automatically generated) and non-stored linear/constant interpolation/restriction operators. Implementation particularities include a processor redistribution of the generated coarse-grid operators so that intra-level communication between adaptive mesh refinement (AMR) levels during the solve phase is kept to a minimum. This redistribution is hidden from the user.

The user input is essentially a linear system describing the composite operator, and the refinement factors between the AMR levels. To form this composite linear system, the AMR grid is described using semi-structured grid parts. Each AMR level grid corresponds to a separate part so that this level grid is simply a collection of boxes, all with the same refinement factor, i.e., it is a struct grid. However, several restrictions are imposed on the patch (box) refinements. First, a refinement box must cover all underlying coarse cells- i.e., refinement of a partial coarse cell is not permitted. Also, the refined/coarse indices must follow a mapping: with $$[r_1,r_2,r_3]$$ denoting the refinement factor and $$[a_1,a_2,a_3] \times [b_1,b_2,b_3]$$ denoting the coarse subbox to be refined, the mapping to the refined patch is

$[r_1*a_1,r_2*a_2,r_3*a_3] \times [r_1*b_1+ r_1-1, r_2*b_2+ r_2-1,r_3*b_3+ r_3-1].$

With the AMR grid constructed under these restrictions, the composite matrix can be formed. Since the AMR levels correspond to semi-structured grid parts, the composite matrix is a semi-structured matrix consisting of structured components within each part, and unstructured components describing the coarse-to-fine/fine-to-coarse connections. The structured and unstructured components can be set using stencils and the HYPRE_SStructGraphAddEntries routine, respectively. The matrix coefficients can be filled after setting these non-zero patterns. Between each pair of successive AMR levels, the coarse matrix underlying the refinement patch must be the identity and the corresponding rows of the rhs must be zero. These can performed using routines HYPRE_SStructFACZeroCFSten (to zero off the stencil values reaching from coarse boxes into refinement boxes), HYPRE_SStructFACZeroFCSten (to zero off the stencil values reaching from refinement boxes into coarse boxes), HYPRE_SStructFACZeroAMRMatrixData (to set the identity at coarse grid points underlying a refinement patch), and HYPRE_SStructFACZeroAMRVectorData (to zero off a vector at coarse grid points underlying a refinement patch). These routines can simplify the user’s matrix setup. For example, consider two successive AMR levels with the coarser level consisting of one box and the finer level consisting of a collection of boxes. Rather than distinguishly setting the stencil values and the identity in the appropriate locations, the user can set the stencil values on the whole coarse grid using the HYPRE_SStructMatrixSetBoxValues routine and then zero off the appropriate values using the above zeroing routines.

The coarse matrix underlying these patches are algebraically generated by operator-collapsing the refinement patch operator and the fine-to-coarse coefficients (this is why stencil values reaching out of a part must be zeroed). This matrix is re-distributed so that each processor has all of its coarse-grid operator.

To solve the coarsest AMR level, a PFMG V cycle is used. Note that a minimum of two AMR levels are needed for this solver.


text:
# RunsTest: Runs Test for Randomness In DescTools: Tools for Descriptive Statistics

## Description

Performs a test whether the elements of x are serially independent - say, whether they occur in a random order - by counting how many runs there are above and below a threshold. If y is supplied a two sample Wald-Wolfowitz-Test testing the equality of two distributions against general alternatives will be computed.

## Usage

 1 2 3 4 5 6 7 8 RunsTest(x, ...) ## Default S3 method: RunsTest(x, y = NULL, alternative = c("two.sided", "less", "greater"), exact = NULL, correct = TRUE, na.rm = FALSE, ...) ## S3 method for class 'formula' RunsTest(formula, data, subset, na.action, ...)

## Arguments

 x a dichotomous vector of data values or a (non-empty) numeric vector of data values. y an optional (non-empty) numeric vector of data values. formula a formula of the form lhs ~ rhs where lhs gives the data values and rhs the corresponding groups. data an optional matrix or data frame (or similar: see model.frame) containing the variables in the formula formula. By default the variables are taken from environment(formula). subset an optional vector specifying a subset of observations to be used. na.action a function which indicates what should happen when the data contain NAs. Defaults to getOption("na.action"). alternative a character string specifying the alternative hypothesis, must be one of "two.sided" (default), "less" or "greater". exact a logical indicating whether an exact p-value should be computed. By default exact values will be calculated for small vectors with a total length <= 30 and the normal approximation for longer ones. correct a logical indicating whether to apply continuity correction when computing the test statistic. Default is TRUE. Ignored if exact is set to TRUE. See details. na.rm defines if NAs should be omitted. Default is FALSE. ... further arguments to be passed to or from methods.

## Details

The runs test for randomness is used to test the hypothesis that a series of numbers is random. The 2-sample test is known as the Wald-Wolfowitz test.

For a categorical variable, the number of runs correspond to the number of times the category changes, that is, where x_i belongs to one category and x_(i+1) belongs to the other. The number of runs is the number of sign changes plus one.

For a numeric variable x containing more than two values, a run is a set of sequential values that are either all above or below a specified cutpoint, typically the median. This is not necessarily the best choice. If another threshold should be used use a code like: RunsTest(x > mean(x)).

The exact distribution of runs and the p-value based on it are described in the manual of SPSS "Exact tests" http://www.sussex.ac.uk/its/pdfs/SPSS_Exact_Tests_21.pdf.

The normal approximation of the runs test is calculated with the expected number of runs under the null

μ_r=\frac{2 n_0 n_1}{n_0 + n_1} + 1

and its variance

σ_r^2 = \frac{2 n_0 n_1 (2 n_0 n_1 - n_0 - n_1) }{(n_0 + n_1)^2 \cdot (n_0 + n_1 - 1)}

as

\hat{z}=\frac{r - μ_r + c}{σ_r}

where n_0, n_1 the number of values below/above the threshold and r the number of runs.

Setting the continuity correction correct = TRUE will yield the normal approximation as SAS (and SPSS if n < 50) does it, see http://support.sas.com/kb/33/092.html. The c is set to c = 0.5 if r < \frac{2 n_0 n_1}{n_0 + n_1} + 1 and to c = -0.5 if r > \frac{2 n_0 n_1}{n_0 + n_1} + 1.

Wald-Wolfowitz with Ties. Ideally there should be no ties in the data used for the Wald-Wolfowitz test. In practice there is no problem with ties within a group, but if ties occur between members of the different groups then there is no unique sequence of observations. For example the data sets A: 10,14,17,19,34 and B: 12,13,17,19,22 can give four possible sequences, with two possible values for r (7 or 9). The "solution" to this is to list every possible combination, and calculate the test statistic for each one. If all test statistics are significant at the chosen level, then one can reject the null hypothesis. If only some are significant, then Siegel (1956) suggests that the average of the P-values is taken. Help for finding all permutations of ties can be found at: https://stackoverflow.com/questions/47565066/all-possible-permutations-in-factor-variable-when-ties-exist-in-r

However this solutions seems quite coarse and in general, the test should not be used if there are more than one or two ties. We have better tests to distinguish between two samples!

## Value

A list with the following components.

 statistic z, the value of the standardized runs statistic, if not exact p-values are computed. parameter the number of runs, the total number of zeros (m) and ones (n) p.value the p-value for the test. data.name a character string giving the names of the data. alternative a character string describing the alternative hypothesis.

## Author(s)

Andri Signorell <[email protected]>, exact p-values by Detlew Labes <[email protected]>

## References

Wackerly, D., Mendenhall, W. Scheaffer, R. L. (1986) Mathematical Statistics with Applications, 3rd Ed., Duxbury Press, CA.

Wald, A. and Wolfowitz, J. (1940): On a test whether two samples are from the same population, Ann. Math Statist. 11, 147-162.

Siegel, S. (1956) Nonparametric Statistics for the Behavioural Sciences, McGraw-Hill Kogakusha, Tokyo.

Run Length Encoding rle
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 # x will be coerced to a dichotomous variable x <- c("S","S", "T", "S", "T","T","T", "S", "T") RunsTest(x) x <- c(13, 3, 14, 14, 1, 14, 3, 8, 14, 17, 9, 14, 13, 2, 16, 1, 3, 12, 13, 14) RunsTest(x) # this will be treated as RunsTest(x > median(x)) plot( (x < median(x)) - 0.5, type="s", ylim=c(-1,1) ) abline(h=0) set.seed(123) x <- sample(0:1, size=100, replace=TRUE) RunsTest(x) # As you would expect of values from a random number generator, the test fails to reject # the null hypothesis that the data are random. # SPSS example x <- c(31,23,36,43,51,44,12,26,43,75,2,3,15,18,78,24,13,27,86,61,13,7,6,8) RunsTest(x, exact=TRUE) # exact probability RunsTest(x, exact=FALSE) # normal approximation # SPSS example small dataset x <- c(1, 1, 1, 1, 0, 0, 0, 0, 1, 1) RunsTest(x) RunsTest(x, exact=FALSE) # if y is not NULL, the Wald-Wolfowitz-Test will be performed A <- c(35,44,39,50,48,29,60,75,49,66) B <- c(17,23,13,24,33,21,18,16,32) RunsTest(A, B, exact=TRUE) RunsTest(A, B, exact=FALSE)