text:
# Pareto distribution

34,190pages on
this wiki

 Probability density functionPareto probability density functions for various α (labeled "k") with xm = 1. The horizontal axis is the x  parameter. As α → ∞ the distribution approaches δ(x − xm) where δ is the Dirac delta function. Cumulative distribution functionPareto cumulative distribution functions for various α(labeled "k") with xm = 1. The horizontal axis is the x  parameter. Parameters $x_\mathrm{m}>0\,$ scale (real)$\alpha>0\,$ shape (real) Support $x \in [x_\mathrm{m}, +\infty)\!$ pdf $\frac{\alpha\,x_\mathrm{m}^\alpha}{x^{\alpha+1}}\text{ for }x\ge x_m\!$ cdf $1-\left(\frac{x_\mathrm{m}}{x}\right)^\alpha \text{ for } x \ge x_m\!$ Mean $\frac{\alpha\,x_\mathrm{m}}{\alpha-1}\text{ for }\alpha>1\,$ Median $x_\mathrm{m} \sqrt[\alpha]{2}$ Mode $x_\mathrm{m}\,$ Variance $\frac{x_\mathrm{m}^2\alpha}{(\alpha-1)^2(\alpha-2)}\text{ for }\alpha>2\,$ Skewness $\frac{2(1+\alpha)}{\alpha-3}\,\sqrt{\frac{\alpha-2}{\alpha}}\text{ for }\alpha>3\,$ Kurtosis $\frac{6(\alpha^3+\alpha^2-6\alpha-2)}{\alpha(\alpha-3)(\alpha-4)}\text{ for }\alpha>4\,$ Entropy $\ln\left(\frac{x_\mathrm{m}}{\alpha}\right) + \frac{1}{\alpha} + 1\!$ mgf $\alpha(-x_\mathrm{m}t)^\alpha\Gamma(-\alpha,-x_\mathrm{m}t)\text{ for }t<0\,$ Char. func. $\alpha(-ix_\mathrm{m}t)^\alpha\Gamma(-\alpha,-ix_\mathrm{m}t)\,$

The Pareto distribution, named after the Italian economist Vilfredo Pareto, is a power law probability distribution that coincides with social, scientific, and many other types of observable phenomena. Outside the field of economics it is sometimes referred to as the Bradford distribution.

## Definition

If X is a random variable with a Pareto (Type I) distribution,[1] then the probability that X is greater than some number x is given by

$\Pr(X>x) = \begin{cases} \left(\frac{x_\mathrm{m}}{x}\right)^\alpha & \text{for }x\ge x_\mathrm{m}, \\ 1 & \text{for } x < x_\mathrm{m}. \end{cases}$

where xm is the (necessarily positive) minimum possible value of X, and α is a positive parameter. The family of Pareto distributions is parameterized by two quantities, xm and α. When this distribution is used to model the distribution of wealth, then the parameter α is called the Pareto index.

## Properties

### Cumulative distribution function

From the definition, the cumulative distribution function of a Pareto random variable with parameters α and xm is

$F_X(x) = \begin{cases} 1-\left(\frac{x_\mathrm{m}}{x}\right)^\alpha & \text{for } x \ge x_\mathrm{m}, \\ 0 & \text{for }x < x_\mathrm{m}. \end{cases}$

### Graphical representation

When plotted on linear axes, the distribution assumes the familiar J-shaped curve which approaches each of the orthogonal axes asymptotically. All segments of the curve are self-similar (subject to appropriate scaling factors).

When plotted on logarithmic scales (both axes logarithmic), the distribution is represented by a straight line.

### Probability density function

It follows (by differentiation) that the probability density function is

$f_X(x)= \begin{cases} \alpha\,\dfrac{x_\mathrm{m}^\alpha}{x^{\alpha+1}} & \text{for }x > x_\mathrm{m}, \\[12pt] 0 & \text{for } x < x_\mathrm{m}. \end{cases}$

### Moments and characteristic function

$E(X)=\frac{\alpha x_\mathrm{m}}{\alpha-1} \,$
(if α ≤ 1, the expected value does not exist).
$\mathrm{Var}(X)=\left(\frac{x_\mathrm{m}}{\alpha-1}\right)^2 \frac{\alpha}{\alpha-2}.$
(If α ≤ 2, the variance does not exist.)
$\mu_n'=\frac{\alpha x_\mathrm{m}^n}{\alpha-n}, \,$
but the nth moment exists only for n < α.
$M\left(t,\alpha,x_\mathrm{m}\right) = E(e^{tX}) = \alpha(-x_\mathrm{m} t)^\alpha\Gamma(-\alpha,-x_\mathrm{m} t)\text{ and }M\left(0,\alpha,x_\mathrm{m}\right)=1.\,$
$\varphi(t;\alpha,x_\mathrm{m})=\alpha(-ix_\mathrm{m} t)^\alpha\Gamma(-\alpha,-ix_\mathrm{m} t),$
where Γ(ax) is the incomplete gamma function.

### Degenerate case

The Dirac delta function is a limiting case of the Pareto density:

$\lim_{\alpha\rightarrow \infty} f(x;\alpha,x_\mathrm{m})=\delta(x-x_\mathrm{m}). \,$

### Conditional distributions

The conditional probability distribution of a Pareto-distributed random variable, given the event that it is greater than or equal to a particular number x1 exceeding xm, is a Pareto distribution with the same Pareto index α but with minimum x1 instead of xm.

### A characterization theorem

Suppose Xi, i = 1, 2, 3, ... are independent identically distributed random variables whose probability distribution is supported on the interval [xm, ∞) for some xm > 0. Suppose that for all n, the two random variables min{ X1, ..., Xn } and (X1 + ... + Xn)/min{ X1, ..., Xn } are independent. Then the common distribution is a Pareto distribution.

## Applications

Pareto originally used this distribution to describe the allocation of wealth among individuals since it seemed to show rather well the way that a larger portion of the wealth of any society is owned by a smaller percentage of the people in that society. He also used it to describe distribution of income.[2] This idea is sometimes expressed more simply as the Pareto principle or the "80-20 rule" which says that 20% of the population controls 80% of the wealth.[3] However, the 80-20 rule corresponds to a particular value of α, and in fact, Pareto's data on British income taxes in his Cours d'économie politique indicates that about 30% of the population had about 70% of the income. The probability density function (PDF) graph at the beginning of this article shows that the "probability" or fraction of the population that owns a small amount of wealth per person is rather high, and then decreases steadily as wealth increases. This distribution is not limited to describing wealth or income, but to many situations in which an equilibrium is found in the distribution of the "small" to the "large". The following examples are sometimes seen as approximately Pareto-distributed:

• Sizes of sand particles [4]
• Sizes of meteorites
• Numbers of species per genus (There is subjectivity involved: The tendency to divide a genus into two or more increases with the number of species in it)[citation needed]
• Areas burnt in forest fires
• Severity of large casualty losses for certain lines of business such as general liability, commercial auto, and workers compensation.[7][8]
• In hydrology the Pareto distribution is applied to extreme events such as annually maximum one-day rainfalls and river discharges. The blue picture illustrates an example of fitting the Pareto distribution to ranked annually maximum one-day rainfalls showing also the 90% confidence belt based on the binomial distribution. The rainfall data are represented by plotting positions as part of the cumulative frequency analysis.

## Relation to other distributions

### Relation to the exponential distribution

The Pareto distribution is related to the exponential distribution as follows. If X is Pareto-distributed with minimum xm and index α, then

$Y = \log\left(\frac{X}{x_\mathrm{m}}\right).$

is exponentially distributed with intensity (rate parameter) α. Equivalently, if Y is exponentially distributed with intensity α, then

$x_\mathrm{m} e^Y \,$

is Pareto-distributed with minimum xm and index α.

This can be shown using the standard change of variable techniques:

$\Pr(Y

The last expression is the cumulative distribution function of an exponential distribution with intensity α.

### Relation to the log-normal distribution

Note that the Pareto distribution and log-normal distribution are alternative distributions for describing the same types of quantities. One of the connections between the two is that they are both the distributions of the exponential of random variables distributed according to other common distributions, respectively the exponential distribution and normal distribution. (Both of these latter two distributions are "basic" in the sense that the logarithms of their density functions are linear and quadratic, respectively, functions of the observed values.)[citation needed]

### Relation to the generalized Pareto distribution

The Pareto distribution is a special case of the generalized Pareto distribution, which is a family of distributions of similar form, but containing an extra parameter in such a way that the support of the distribution is either bounded below (at a variable point), or bounded both above and below (where both are variable), with the Lomax distribution as a special case. This family also contains both the unshifted and shifted exponential distributions.

### Relation to Zipf's law

Pareto distributions are continuous probability distributions. Zipf's law, also sometimes called the zeta distribution, may be thought of as a discrete counterpart of the Pareto distribution.

### Relation to the "Pareto principle"

The "80-20 law", according to which 20% of all people receive 80% of all income, and 20% of the most affluent 20% receive 80% of that 80%, and so on, holds precisely when the Pareto index is α = log45, approximately 1.161. Moreover, the following have been shown[9] to be mathematically equivalent:

• Income is distributed according to a Pareto distribution with index α > 1.
• There is some number 0 ≤ p ≤ 1/2 such that 100p% of all people receive 100(1 − p)% of all income, and similarly for every real (not necessarily integer) n > 0, 100pn% of all people receive 100(1 − p)n% of all income.

This does not apply only to income, but also to wealth, or to anything else that can be modeled by this distribution.

This excludes Pareto distributions in which 0 < α ≤ 1, which, as noted above, have infinite expected value, and so cannot reasonably model income distribution.

## Pareto, Lorenz, and Gini

The Lorenz curve is often used to characterize income and wealth distributions. For any distribution, the Lorenz curve L(F) is written in terms of the PDF ƒ or the CDF F as

$L(F)=\frac{\int_{x_\mathrm{m}}^{x(F)} xf(x)\,dx}{\int_{x_\mathrm{m}}^\infty xf(x)\,dx} =\frac{\int_0^F x(F')\,dF'}{\int_0^1 x(F')\,dF'}$

where x(F) is the inverse of the CDF. For the Pareto distribution,

$x(F)=\frac{x_\mathrm{m}}{(1-F)^{1/\alpha}}$

and the Lorenz curve is calculated to be

$L(F) = 1-(1-F)^{1-1/\alpha},\,$

where α must be greater than or equal to unity, since the denominator in the expression for L(F) is just the mean value of x. Examples of the Lorenz curve for a number of Pareto distributions are shown in the graph on the right.

The Gini coefficient is a measure of the deviation of the Lorenz curve from the equidistribution line which is a line connecting [0, 0] and [1, 1], which is shown in black (α = ∞) in the Lorenz plot on the right. Specifically, the Gini coefficient is twice the area between the Lorenz curve and the equidistribution line. The Gini coefficient for the Pareto distribution is then calculated to be

$G = 1-2\int_0^1L(F)\,dF = \frac{1}{2\alpha-1}$ (?? - Talk:Pareto distribution#Gini coeff)

(see Aaberge 2005).

## Parameter estimation

The likelihood function for the Pareto distribution parameters α and xm, given a sample x = (x1x2, ..., xn), is

$L(\alpha, x_\mathrm{m}) = \prod _{i=1}^n \alpha \frac {x_\mathrm{m}^\alpha} {x_i^{\alpha+1}} = \alpha^n x_\mathrm{m}^{n\alpha} \prod _{i=1}^n \frac 1 {x_i^{\alpha+1}}. \!$

Therefore, the logarithmic likelihood function is

$\ell(\alpha, x_\mathrm{m}) = n \ln \alpha + n\alpha \ln x_\mathrm{m} - (\alpha + 1) \sum _{i=1} ^n \ln x_i. \!$

It can be seen that $\ell(\alpha, x_\mathrm{m})$ is monotonically increasing with $x_\mathrm{m}$, that is, the greater the value of $x_\mathrm{m}$, the greater the value of the likelihood function. Hence, since $x \ge x_\mathrm{m}$, we conclude that

$\widehat x_\mathrm{m} = \min_i {x_i}.$

To find the estimator for α, we compute the corresponding partial derivative and determine where it is zero:

$\frac{\partial \ell}{\partial \alpha} = \frac{n}{\alpha} + n \ln x_\mathrm{m} - \sum _{i=1}^n \ln x_i = 0.$

Thus the maximum likelihood estimator for α is:

$\widehat \alpha = \frac{n}{\sum _i \left( \ln x_i - \ln \widehat x_\mathrm{m} \right)}.$

The expected statistical error is:

$\sigma = \frac {\widehat \alpha} {\sqrt n}.$[10]

## Graphical representation

The characteristic curved 'long tail' distribution when plotted on a linear scale, masks the underlying simplicity of the function when plotted on a log-log graph, which then takes the form of a straight line with negative gradient.[citation needed]

## Generating a random sample from Pareto distribution

Random samples can be generated using inverse transform sampling. Given a random variate U drawn from the uniform distribution on the unit interval (0, 1], the variate T given by

$T=\frac{x_\mathrm{m}}{U^{1/\alpha}}$

is Pareto-distributed.[citation needed] If U is uniformly distributed on [0, 1), it can be exchanged for (1 - U).

## Bounded Pareto distribution

 Probability density function Cumulative distribution function Parameters $L > 0 \,$ location (real) $H > L \,$ location (real) $\alpha > 0 \,$ shape (real) Support $L \leqslant x \leqslant H \,$ pdf $\frac{\alpha L^\alpha x^{-\alpha - 1}}{1-\left(\frac{L}{H}\right)^\alpha}$ cdf $\frac{1-L^\alpha x^{-\alpha}}{1-\left(\frac{L}{H}\right)^\alpha}$ Mean $\frac{L^\alpha}{1 - \left(\frac{L}{H}\right)^\alpha} \cdot \left(\frac{\alpha}{\alpha-1}\right) \cdot \left(\frac{1}{L^{\alpha-1}} - \frac{1}{H^{\alpha-1}}\right), \alpha\neq 1$ Median $L \left(1- \frac{1}{2}\left(1-\left(\frac{L}{H}\right)^\alpha\right)\right)^{-\frac{1}{\alpha}}$ Mode Variance $\frac{L^\alpha}{1 - \left(\frac{L}{H}\right)^\alpha} \cdot \left(\frac{\alpha}{\alpha-2}\right) \cdot \left(\frac{1}{L^{\alpha-2}} - \frac{1}{H^{\alpha-2}}\right), \alpha\neq 2$ Skewness Kurtosis Entropy mgf Char. func.

The bounded Pareto distribution or truncated Pareto distribution has three parameters α, L and H. As in the standard Pareto distribution α determines the shape. L denotes the minimal value, and H denotes the maximal value. (The Variance in the table on the right should be interpreted as 2nd Moment).

$\frac{\alpha L^\alpha x^{-\alpha - 1}}{1-\left(\frac{L}{H}\right)^\alpha}$

where L ≤ x ≤ H, and α > 0.

### Generating bounded Pareto random variables

If U is uniformly distributed on (0, 1), then

$\left(-\frac{U H^\alpha - U L^\alpha - H^\alpha}{H^\alpha L^\alpha}\right)^{-\frac{1}{\alpha}}$

is bounded Pareto-distributed.[citation needed]

## Symmetric Pareto distribution

The symmetric Pareto distribution can be defined by the probability density function:[11]

$f(x;\alpha,x_\mathrm{m}) = \begin{cases} (\alpha x_\mathrm{m}^\alpha/2) |x|^{-\alpha-1} & \text{for }|x|>x_\mathrm{m} \\ 0 & \text{otherwise}. \end{cases}$

It has a similar shape to a Pareto distribution for $x > x_\mathrm{m}$ while looking like an inverted Pareto distribution for $x < x_\mathrm{m}$[citation needed].

## Notes

1. See Arnold (1983).
2. Pareto, Vilfredo, Cours d’Économie Politique: Nouvelle édition par G.-H. Bousquet et G. Busino, Librairie Droz, Geneva, 1964, pages 299–345.
3. For a two-quantile population, where approximately 18% of the population owns 82% of the wealth, the Theil index takes the value 1.
4. 4.0 4.1 4.2 4.3 4.4 William J. Reed et al., “The Double Pareto-Lognormal Distribution – A New Parametric Model for Size Distributions”, Communications in Statistics : Theory and Methods 33(8), 1733-1753, 2004 p 18 et seq.
5. (2010-02-24)Understanding latent sector error and how to protect against them. 8th Usenix Conference on File and Storage Technologies (FAST 2010).
6. Cumfreq, a free computer program for cumulative frequency analysis.
7. Kleiber and Kotz (2003): page 94.
8. (1980). Survival probabilities based on Pareto claim distributions. ASTIN Bulletin 11: 61–71.
9. (2010). Pareto's Law. Mathematical Intelligencer 32 (3): 38–43.
10. M. E. J. Newman (2005). Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46 (5): 323–351.
11. Grabchak, M. & Samorodnitsky, D.. Do Financial Returns Have Finite or Infinite Variance? A Paradox and an Explanation.

## References

• Barry C. Arnold (1983). Pareto Distributions, International Co-operative Publishing House.
• Christian Kleiber and Samuel Kotz (2003). Statistical Size Distributions in Economics and Actuarial Sciences, Wiley.
• M. O. Lorenz (1905). Methods of measuring the concentration of wealth. Publications of the American Statistical Association 9 (70): 209–219.
• Pareto V (1965) "La Courbe de la Repartition de la Richesse" (Originally published in 1896). In: Busino G, editor. Oevres Completes de Vilfredo Pareto. Geneva: Librairie Droz. pp. 1–5.


text:
### Quagga

After having some interviews where I’ve been asked about routing on linux solutions, I’ve decided to playaround with Quagga. As always, you can find all the info already on the internet. And in my case Brian Kletter had all the necessary info to setup the environment. Here’s the link on how to setup a linux server with quagga software. And here the initial setup for quagga.

### Password recovery procedure on Cisco Catalyst 3500-XL

Just got a used Catalyst 3500-XL switch and don’t have credentials? Did you forget your auth credentials or you just want to have fun?

### How to create text files on Cisco routers

In case you will need it, here’s a thing that helped me out once. In case you want to append some config lines that you have stored in a file and if you can’t copy it through SFTP, you can make it locally. To do this you need to start tclsh and create the file puts [open "flash:filename" w+] {  now don’t press enter but just paste in your config lines and then } and ENTER. tclquit to exit tclsh. Now you’ll have your config snippet in flash:filename and you can use it to append to your config. Would be a good idea to check it with more flash:filename just to be sure that you have everything in place and no characters were left outside. As always, more info on Cisco’s webpage

### Cisco guest shell

So, it seems that finally Cisco decided to introduce a shell for their routers. I know this already exists for their FirePower plaform, but from my knowledge, they just made it available for routers.

format: plain


text:
## Elementary and Intermediate Algebra: Concepts & Applications (6th Edition)

$\text{Set Builder Notation: } \{x|x\lt-1\} \\\text{Interval Notation: } (-\infty,-1)$
The given graph shows all the numbers that are less than $-1.$ Hence, the given graph of inequality can be described in the following formats: \begin{array}{l}\require{cancel} \text{Set Builder Notation: } \{x|x\lt-1\} \\\text{Interval Notation: } (-\infty,-1) .\end{array}


text:
Latest Articles

## Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant,... (more)

## Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive Move-To-Local-Min (Mtlm) algorithm by Bartal et al. (SODA 1997). Like Mtlm, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of... (more)

## Faster Approximation Schemes for the Two-Dimensional Knapsack Problem

For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One example... (more)

## An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph

In this article, we consider the following problem. Given a directed graph G, output all walks of G... (more)

##### NEWS

The ACM Transactions on Algorithms (TALG) publishes original research of the highest quality dealing with algorithms that are inherently discrete and finite, and having mathematical content in a natural way, either in the objective or in the analysis.

#### SODA'18 Editorial

More Logarithmic-Factor Speedups for 3SUM, (median,+)-Convolution, and Some Geometric 3SUM-Hard...

We present an algorithm that solves the 3SUM problem for $n$ real numbers in $O((n^2/\log^2n) (\log\log n)^{O(1)})$ time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM\@. We also obtain the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

We consider integer programming problems in standard form $\max \{c^Tx : Ax = b, \, xe0, \, x $^n\}$where$A  $^{m ×n}$, $b $^m$and$c  $^n$. We show that such an integer program can be solved in time $(m Å )^{O(m)} Å \|b\|_ ^2$, where $$ is an upper bound on each absolute value of an entry in $A$. This improves upon the longstanding best bound of Papadimitriou (1981) of $(mÅ)^{O(m^2)}$, where in addition, the absolute values of the entries of $b$ also need to be bounded by $$. % and addresses an open problem raised by Fomin. Our result relies on a lemma of Steinitz that states that a set of vectors in $^m$ that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by $m$. We also use the Steinitz lemma to show that the $\ell_1$-distance of an optimal integer and fractional solution, %of the integer %program, also under the presence of upper bounds on the variables, is bounded by $m Å (2\,mÅ+1)^m$. Here $$ is again an upper bound on the absolute values of the entries of $A$. The novel strength of our bound is that it is independent of $n$. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

Faster Replacement Paths and Distance Sensitivity Oracles

Given a directed n-node graph G with integer edge weights in [-M,M], a source node s, a target node t, and an edge e, a replacement path for the triple (s,t,e) is a shortest s-t path in G avoiding e. In this paper we achieve the following main results: 1) We describe an algorithm with runtime $\tilde{O}(Mn^{\omega})$ that computes the lengths of all the replacement paths for a given source-target pair (s,t). Here $\omega<2.373$ is fast matrix multiplication exponent. For a comparison, the previous fastest algorithms have runtime $\tilde{O}(Mn^{1+2\omega/3})$ [Weimann,Yuster-FOCS'10] and $\tilde{O}(n^{2.5})$ in the unweighted case [Roditty,Zwick-ICALP'05]. 2) We describe an algorithm with runtime $\tilde{O}(M^{\frac{1}{4-\omega}}n^{2+\frac{1}{4-\omega}})$ that computes the lengths of all the replacement paths for a given source s. Our runtime reduces to $\tilde{O}(Mn^\omega)$ for positive weights, hence matching our mentioned result for the simpler case where also the target t is fixed. 3) We present a data structure (a.k.a. distance sensitivity oracle) that answers to queries of the form (s,t,e) with the length of the associated replacement path. For a given parameter $\alpha\in [0,1]$, our oracle has preprocessing time $\tilde{O}(Mn^{\omega+\frac{1}{2}}+Mn^{\omega+\alpha(4-\omega)})$ and query time $\tilde{O}(n^{1-\alpha})$. In particular, we achieve for the first time simultaneously subcubic preprocessing time and sublinear query time. For a comparison, the previous best oracle has $\tilde{O}(Mn^{\omega+1-\alpha})$ preprocessing time and (superlinear) $\tilde{O}(n^{1+\alpha})$ query time [Weimann,Yuster-FOCS'10]. All the mentioned results are randomized: a wrong distance is output with polynomially small probability in n.

Distributed Edge Coloring with Small Palettes

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree $\Delta$. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. We simplify the \emph{round elimination} technique of Brandt et al. and prove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$ time w.h.p. 2. We give a randomized edge coloring algorithm that can use palette sizes as small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for randomized approaches. 3. We develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-edge coloring algorithm for trees running in $O(\log\log n)$ time. 4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via augmenting paths.'' We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$.

A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs

Given a weighted planar bipartite graph G(A U B, E) where each edge has an integer edge cost, we give an O(n4/3 log2 n log(nC)) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best known planarity exploiting algorithm has a running time of O(n3/2log n) and is achieved by using planar separators (Lipton and Tarjan '80). Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan '89). For each scale, our algorithm first executes O(n1/3) iterations of Gabow and Tarjan's algorithm in O(n4/3) time leaving only O(n2/3) vertices unmatched. Next, it constructs a compressed residual graph H with O(n2/3) vertices and O(n) edges. This is achieved by using an r-division of the planar graph G with r=n2/3. For each partition of the r-division, there is an edge between two vertices of H if and only if they are connected by a directed path inside the partition. Using existing efficient shortest-path data structures, the remaining O(n2/3) vertices are matched by iteratively computing a minimum-cost augmenting path each taking O(n2/3 log2 n) time. Augmentation changes the residual graph, so the algorithm updates the compressed representation for each partition affected by the change in O(n2/3 log n) time. We bound the total number of affected partitions over all the augmenting paths by O(n2/3 log n). Therefore, the total time taken by the algorithm is O(n4/3log2 n log(nC)).

Scheduling When You Don't Know the Number of Machines

Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this paper, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. In order to evaluate algorithms in such an environment, we introduce the idea of an ±-robust algorithm, one which is guaranteed to return a schedule on any number m of machines that is within an ± factor of the optimal schedule on m machine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a 5/3-robust algorithm for scheduling on parallel machines to minimize makespan, and show a lower bound 4/3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.

Algorithms to Approximate Column-Sparse Packing Problems

Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go half the remaining distance" to optimal for a major integrality-gap conjecture of F\"uredi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

Randomized Memoryless Algorithms for the Weighted and the Generalized $k$-server Problems

The weighted $k$-server problem is a generalization of the $k$-server problem, wherein the cost of moving a server of weight $\beta_i$ through a distance $d$ is $\beta_i\cdot d$. On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its $k$ servers. In this paper, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted $k$-server problem on uniform metrics. We first prove that there is an $\alpha_k$-competitive memoryless algorithm for this problem, where $\alpha_k=\alpha_{k-1}^2+3\alpha_{k-1}+1$; $\alpha_1=1$. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than $\alpha_k$. Finally, we prove that the above bounds also hold for the generalized $k$-server problem on weighted uniform metrics.

#### Solving the Sigma-Tau Problem

Approximation Schemes for Low-Rank Binary Matrix Approximation Problems

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem generalizes a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are \bmfgfr, \bmfbr, and various versions of \textsc{Binary Clustering}. For example, for \bmfgfr problem, where for an $m\times n$ binary matrix $A$ and integer $r>0$, we seek for a binary matrix $B$ of \GF rank at most $r$ such that $\ell_0$ norm of matrix $\bfA-\bfB$ is minimum, our algorithm, for any $\epsilon>0$ in time $f(r,\epsilon)\cdot n\cdot m$, where $f$ is some computable function, outputs a $(1+\epsilon)$-approximate solution with probability at least $(1-\frac{1}{e})$. This is the first linear time approximation schemes for these problems. We also give (deterministic) PTASes for these problems running in time $n^{f(r)\frac{1}{\epsilon^2}\log \frac{1}{\epsilon}}$, where $f$ is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting in its own.

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

This paper presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{n})$ time and exchanges $\tilde{O}(m)$ messages (both with high probability), where $n$ is the number of nodes of the network, $D$ is the hop-diameter, and $m$ is the number of edges. This is the \emph{first} distributed MST algorithm that matches \emph{simultaneously} the time lower bound of $\tilde{\Omega}(D + \sqrt{n})$ [Elkin, SIAM J.\ Comput.\ 2006] and the message lower bound of $\Omega(m)$ [Kutten et al., J.\ ACM 2015], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both $\tilde{\Omega}(D + \sqrt{n})$ rounds and $\Omega(m)$ messages.

###### All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name


text:
1. What is a decentralized organization? 2. Describe three advantages of a decentralized organization? 3. Describe...

Question:

1. What is a decentralized organization? 2. Describe three advantages of a decentralized organization? 3. Describe three disadvantages of a decentralized organization? 4. Describe the each of the following: a. cost center b. profit center c. investment center. 5. Describe the term Return on Investment ("ROI"). 6. What is the formula to determine ROI? 7. Describe the term Residual Income. 8. Describe and provide the formula for the following Operating Performance Measures: a. Throughput (Manufacturing Cycle) Time b. Delivery Cycle Time c. Manufacturing Cycle Efficiency ("MCE") 9. Describe the Common Characteristics of Balance Scorecards. 10. How would you construct a balanced scorecard?

Similar Solved Questions

Write the rormal prababllity for ihe shaded reqion (Round = fout Cucima pljcus needed ) P(4<*<6)-P(35s*s6.5) = 0 B. Pr<xc7)=P(352*<75} = P(3sxT=PQ5_*{75) =graph andelm ils value Select the cortect choice below and flin Ine answer box wthin ydut choice_0 D: P(-<x<6)=P(45<x<5 5) =
Write the rormal prababllity for ihe shaded reqion (Round = fout Cucima pljcus needed ) P(4<*<6)-P(35s*s6.5) = 0 B. Pr<xc7)=P(352*<75} = P(3sxT=PQ5_*{75) = graph andelm ils value Select the cortect choice below and flin Ine answer box wthin ydut choice_ 0 D: P(-<x<6)=P(45<x<5...
Yogeeta halal & I 9/27/19 11:20 PM Test: Exam 1 This Question: 2 pts Submit Test...
Yogeeta halal & I 9/27/19 11:20 PM Test: Exam 1 This Question: 2 pts Submit Test 3 of 25 (5 complete This Test: 50 pts possible Here are boxplots of the points scored during the first 10 games of the season for both Alex and Sue a) Summarize the similarities and differences in their performance ...
Question 1 (15 marks) Vic Corporation refines petrol and sellsit through its own petrol station. On...
Question 1 (15 marks) Vic Corporation refines petrol and sellsit through its own petrol station. On the basis of market research, Vic Corporation determines that 60% of the overall petrol market consists of service-oriented customers," medium to high income individuals who are willing to pay a h...
The Dahlia Medical Center has 30 labor rooms, 19 combination labor and delivery rooms, and 55...
The Dahlia Medical Center has 30 labor rooms, 19 combination labor and delivery rooms, and 55 delivery rooms. All of these facilities operate around the clock. Time spent in labor rooms varies from hours to days, with an average of about a day. The average uncomplicated delivery...
1.52E19 photons/s 4.27E19 photons/s Question 11 5 pts A square planar loop of coiled wire has...
1.52E19 photons/s 4.27E19 photons/s Question 11 5 pts A square planar loop of coiled wire has a length of 0.25 m on a side and is rotated 60 times per second between the poles of a permanent magnet. The magnetic field between the poles is 0.75 T. If a peak voltage of 1 kV is generated in the coil, h...
What is the relationship between the following compounds? HCC Η CH3 H3C CH3 (a) identical compounds...
What is the relationship between the following compounds? HCC Η CH3 H3C CH3 (a) identical compounds (b) constitutional isomers (C) enantiomers (d) diastereomers...
Problem Solve the 3 following 6z inicial 'salue) , problem: 22 7
Problem Solve the 3 following 6z inicial 'salue) , problem: 2 2 7...
7 . (10 points)I2 ry + yz + 23 = 1. Use implicit differentiation to solve for Dz dy
7 . (10 points) I2 ry + yz + 23 = 1. Use implicit differentiation to solve for Dz dy...
Q2. Fig Q2 shows the block diagram of an unstable system with transfer function G(s) -...
Q2. Fig Q2 shows the block diagram of an unstable system with transfer function G(s) - under the control of a lead compensator (a) Using the Routh's stability criterion, determine the conditions on k and a so that the closed-loop system is stable, and sketch the region on the (k, a)- plane where...
Aucstion:Eolaernele5 dozdFhal sunjng & u7=Quinuiu *uFpuelel Iocilo [lilacuedAu4tUnt tenHELHLATHI1oua"o tore prI mnlce(Acundte Inuraalnat [r_nntulrul
Aucstion: Eola ernele 5 dozd Fhal sunjng & u7= Quinuiu *u Fpuelel Iocilo [lila cued Au4t Unt ten HELHLATHI 1oua"o tore prI mnlce (Acundte Inuraalnat [r_nn tulrul...
Assume that sample is used t0 estimate population mean Find the 99.5% confidence interval for sample of size 37 with mean of 54.7 and standard deviation of 21.5. Enter your answer as an open- interval (i.e- parentheses accurate to one decimal place (because the sample statistics are reported accurate t0 one decimal place).99.58 C.I.Answer should be obtained without any preliminary rounding_ However thc critical value may be rounded decimal places_
Assume that sample is used t0 estimate population mean Find the 99.5% confidence interval for sample of size 37 with mean of 54.7 and standard deviation of 21.5. Enter your answer as an open- interval (i.e- parentheses accurate to one decimal place (because the sample statistics are reported accurat...
Evaluate each expression.$|20-12|$
Evaluate each expression. $|20-12|$...
Question 5What is the solution to the following equation? Br +66 MzI532Enter onlyithe numericalivalue
Question 5 What is the solution to the following equation? Br +66 MzI532 Enter onlyithe numericalivalue...
An engineer is going to redesign an ejection seat for an airplane. The seat was designed for pilots weighing between 130 Ib and 191 Ib. The new population of pilots has normally distributed weights with a mean of 140 Ib and a standard deviation of 33.5 Ib. a. If a pilot is randomly selected, find the probability that his weight is between 130 Ib and 191 IbThe probability is approximately(Round to four decimal places as needed:)
An engineer is going to redesign an ejection seat for an airplane. The seat was designed for pilots weighing between 130 Ib and 191 Ib. The new population of pilots has normally distributed weights with a mean of 140 Ib and a standard deviation of 33.5 Ib. a. If a pilot is randomly selected, find th...
Per the and molecules _ construct models Use the molecular model sets medium length bonds: following instructlons: Use the Carbon black atom Chlorine green atom Iodine dark purple atom Bromine- dark blue atom Hydrogen white atom Molecule Moleculerelated? How are these two molecules = they the same? ECompare the two models_molecule on the left solution containing thee molecules; determine the direction following two direction; Can You = Consider the clockwise molecule on the ~polarized light in s
per the and molecules _ construct models Use the molecular model sets medium length bonds: following instructlons: Use the Carbon black atom Chlorine green atom Iodine dark purple atom Bromine- dark blue atom Hydrogen white atom Molecule Molecule related? How are these two molecules = they the same?...
Write MATLAB commands for y = sin2(4.12π/6)2 and give its numerical value.
Write MATLAB commands for y = sin2(4.12π/6)2 and give its numerical value....
Huang Automotive is presently operating at 75% of capacity. The company recently received an offer from...
Huang Automotive is presently operating at 75% of capacity. The company recently received an offer from a Korean truck manufacturer to purchase 21,000 units of a power steering system component for $197 per unit. Peter Wu, vice-president of sales, notes that although there will be an additional$2.7...
Problem Set IbProve thatV108 + 10V108 10 = 2Hint: note that '108 + 10613 : 10 and find a and b such that(bV3 =a)3 = 6v3 _ 10.Show your work:
Problem Set Ib Prove that V108 + 10 V108 10 = 2 Hint: note that '108 + 10 613 : 10 and find a and b such that (bV3 =a)3 = 6v3 _ 10. Show your work:...
Onion Cell Pictures are real microscope views of the tip of an onion root The root growing; The DerttWc imges Khich means M} ofthe cells are undergoing mitosis Label the phase indicated by the arrows and blanks: (You Lill the same phase more than once You illnot see all five phases in the sume picture: The cell may be in Interphasel)Onion Root Tip (40Ox)
Onion Cell Pictures are real microscope views of the tip of an onion root The root growing; The DerttWc imges Khich means M} ofthe cells are undergoing mitosis Label the phase indicated by the arrows and blanks: (You Lill the same phase more than once You illnot see all five phases in the sume pi...
A single gas molecule of inertia m is trapped in a box and travels back and...
A single gas molecule of inertia m is trapped in a box and travels back and forth with constant speedv between opposite walls A and B a distance lapart. At each collision with a wall, the molecule reverses direction without changing speed. 1) Write algebraic expressions for the magnitude of the chan...
2. Suppose that two oligopolistic retail chains are considering opening a new sales outlet in a...
2. Suppose that two oligopolistic retail chains are considering opening a new sales outlet in a particular town. The changes to each firm's profits, depending on the actions taken, are given in the following payoff matrix. If a chain does not open a new outlet, it eams no addition to profits. If...
1. BEFORE you start working on this problem, enter the following commands: set.seed (2) height =...
1. BEFORE you start working on this problem, enter the following commands: set.seed (2) height = 1:50 weight rbeta(50, 3, 7) + 10 Here we consider height explanatory and weight response. Compute the estimate of mean wight given by the regression line for height 25 (round the result to 3 decimals). A...
Suppose a $1.0 \mathrm{~m}$ solution of a solute is made using a solvent with a density of $1.15 \mathrm{~g} / \mathrm{mL}$. Will the molarity of this solution be numerically larger or smaller than $1.0 ?$ Justify your conclusion mathematically.
Suppose a $1.0 \mathrm{~m}$ solution of a solute is made using a solvent with a density of $1.15 \mathrm{~g} / \mathrm{mL}$. Will the molarity of this solution be numerically larger or smaller than $1.0 ?$ Justify your conclusion mathematically....
[~a Foints] Give bases fat rowla} colka) , DETAILS and nulllA}: 1 0/2 Submissions pasn1
[~a Foints] Give bases fat rowla} colka) , DETAILS and nulllA}: 1 0/2 Submissions pasn 1...
Give the definition of what it means for a function, f(x)f(x), to be increasing on the interval ]...
Give the definition of what it means for a function, f(x)f(x), to be increasing on the interval ]a,b[]a,b[. Give the definition of what it means for a function, f(x)f(x), to be decreasing on the interval ]a,b[]a,b[. Note that your answer for (3) should be different from (2)....
= = 5. Let tan(0) - and csc(0) V5. Draw a picture with the unit circle...
= = 5. Let tan(0) - and csc(0) V5. Draw a picture with the unit circle to illustrate 0. Then use it to answer the following questions. (a) What quadrant is in? = = (b) sin(0) (c) cos(0) (d) cot(0) = (e) sec(0) =...
Solve the initial value problem for the heat eqquation " Kuz with the boundary condlitions (0,4) = "_ (LO)+hu(L:() anc the initial coudlition &(-. 0) = Tx where h,Tz aud T; are psitive const;ts
Solve the initial value problem for the heat eqquation " Kuz with the boundary condlitions (0,4) = "_ (LO)+hu(L:() anc the initial coudlition &(-. 0) = Tx where h,Tz aud T; are psitive const;ts...
Geradlon_0ip 0i 0 NotallsThe lunctlon /s gaphed bolom Stato the vdues (hat fulfh Iho {ollowag raqulreanonts: Mcte o uch utd I"DNL . thero Itua uple atcrutu vuov; sopuratao thern wth Lomrnas Iy 0o fox 6 md60 fwhereundotined?Whcrc docs f Ihaye local minimums? Thia not dedmx ntege Vu () Wherc do81 , havt local maximum;?(v) hje the absolute (elobal) Minimum absolute Mniavmf in the interval [-1,2.5]What thc absolute (elobal) maximum f in thc Intcrval [-1,2.5]7 absolute tiaximutnAdd Wlork
Geradlon_ 0ip 0i 0 Notalls The lunctlon /s gaphed bolom Stato the vdues (hat fulfh Iho {ollowag raqulreanonts: Mcte o uch utd I"DNL . thero Itua uple atcrutu vuov; sopuratao thern wth Lomrnas Iy 0o fox 6 md60 f where undotined? Whcrc docs f Ihaye local minimums? Thia not dedmx ntege Vu () Wherc...
Evaluate these health care models: Managed Care - Competition Consumerism What model, or hybrid model, would...
Evaluate these health care models: Managed Care - Competition Consumerism What model, or hybrid model, would you recommend to maximize quality of care while controlling health care costs in the future? What would be components of a hybrid model? How could these models be used in ongoing developmen...
IC4uDAWoringuatr /4 DInsMalno tozbntoimallahtnlttsJRLoemmnleelnaAUan EAlmaA
IC4uDAWoring uatr /4 DIns Malno tozbntoimallahtnltts JRLo emmnleelnaAUan EAlmaA...
Nonuniform grids Use the indicated methods to solve the following problems with nonuniform grids. Approximating integrals The function $f$ is twice differentiable on $(-\infty, \infty) .$ Values of $f$ at various points on [0,20] are given in the table. a. Approximate $\int_{0}^{20} f(x) d x$ in three ways: using a left Riemann sum, a right Riemann sum, and the Trapezoid Rule. b. A scatterplot of the data in the table is provided in the figure. Use the scatterplot to illustrate each of the appro
Nonuniform grids Use the indicated methods to solve the following problems with nonuniform grids. Approximating integrals The function $f$ is twice differentiable on $(-\infty, \infty) .$ Values of $f$ at various points on [0,20] are given in the table. a. Approximate $\int_{0}^{20} f(x) d x$ in thr...
Calculate the formula mass of strontium chlorite. Sr(C1Oz)z' in atomic mass units (amu or 0).
Calculate the formula mass of strontium chlorite. Sr(C1Oz)z' in atomic mass units (amu or 0)....
Lilah and Juliet form a corporation (LJ Inc) Lilah contributes land ( a capital asset) with...
Lilah and Juliet form a corporation (LJ Inc) Lilah contributes land ( a capital asset) with a fair market value of $250,000 and a tax basis of S 50,000. The land is subject to a mortgage of$ 150,000 which is assumed by LJ Inc. Lilah receives 1,000 shares of LJ Incin the transaction Juliet contribu...
Problem 3-5 The accounts listed below appeared in the December 31 trial balance of the Savard Theater. Credit Equipment Accumulated Depreciation-Equipment Notes Payable Admissions Revenue Advertising Expense Salaries and Wages Expense Interest Expense $192,000$60,000 90,000 380,000 13,680 57,600 1,...


text:
# Thread: how to prove if a and b are recursively enumerable sets on N then so is

1. ## how to prove if a and b are recursively enumerable sets on N then so is

a intersection b ??

is it enough to state that since some thing is RE then its also Recursive ?

2. ## Re: how to prove if a and b are recursively enumerable sets on N then so is

A set $S \subseteq \mathbb{N}$ is r.e. iff there exists a turing machine ${M}_{S}$ such that $\forall x \in S$, ${M}_{S}(x)=1$ and that $\forall x \notin S$, ${M}_{S}(x)$ doesn't stop.

Let ${M}_{A}$ and ${M}_{B}$ be such turing machines for your r.e. sets A and B respectively. It is easy to construct turing machine ${M}_{C}$ such that ${M}_{C}(x)=1$ iff ${M}_{A}(x)={M}_{B}(x)=1$ and ${M}_{C}(x)$ doesn't stop otherwise ( ${M}_{C}$ just alternates between ${M}_{A}$ and ${M}_{B}$ and output 1 iff both of them output 1).

So by the above construction $C$ is r.e. and $C=A\cap B$.

---------------------------------------------------
A set $S$ is recursive iff both $S$ and $\mathbb{N}-S$ are r.e.. So in our previous argument you need the stronger condition: ${M}_{S}(x)=1$ $\forall x \in S$ and ${M}_{S}(x)=0$ $\forall x \notin S$.
Any recursive set is also r.e., but not vice versa.

3. ## Re: how to prove if a and b are recursively enumerable sets on N then so is

thanks.. much appreciated !!


text:
# American Institute of Mathematical Sciences

ISSN:
1078-0947

eISSN:
1553-5231

All Issues

## Discrete & Continuous Dynamical Systems - A

October 2009 , Volume 23 , Issue 4

A special issue on
Asymptotic Description of Natural Phenomena

Select all articles

Export/Reference:

2009, 23(4): i-ii doi: 10.3934/dcds.2009.23.4i +[Abstract](1204) +[PDF](35.1KB)
Abstract:
This special issue of Discrete and Continuous Dynamical Systems grows out of a focused session at the AIMS 6 meeting held in Poitiers, France, in 2006. The session struck its organizers, who were perhaps not unbiased, as very successful. As a consequence, when Shouchuan Hu approached us about editing a special issue based on the papers delivered in the session, we were enthusiastic at the prospect.
The focus of the session was asymptotic models of physical phenomena. This is a large subject, and one special session cannot hope to do it justice. Consequently, some focal point was required, and in the event, most of the lectures in the session were centered upon nonlinear wave equations arising in plasma physics and fluid mechanics. This is also the subject around which most of this special issue turns.

2009, 23(4): 1099-1139 doi: 10.3934/dcds.2009.23.1099 +[Abstract](1479) +[PDF](1519.6KB)
Abstract:
Laser sources nowadays deliver optical pulses reaching few cycles in duration and peak powers exceeding several terawatt (TW). When such pulses propagate in transparent media, they first self-focus in space, until they generate a tenuous plasma by photo-ionization. These pulses evolve as self-guided objects, resulting from successive equilibria between the Kerr focusing process, the defocusing action of the electron plasma and the chromatic dispersion of the medium. Discovered ten years ago, this self-channeling mechanism reveals a new physics, having direct applications in the long-distance propagation of TW beams in air, supercontinuum emission as well as pulse self-compression. This review presents the major progress in this field. Particular emphasis is laid to the derivation of the propagation equations, for single as well as coupled wave components. Physics is discussed from numerical simulations and explained by analytical arguments. Attention is also paid to the multifilamentation instability, which breaks up broad beams into small-scale cells. Several experimental data validate theoretical descriptions.
2009, 23(4): 1141-1168 doi: 10.3934/dcds.2009.23.1141 +[Abstract](1480) +[PDF](296.7KB)
Abstract:
Studied here is the large-time behavior and eventual periodicity of solutions of initial-boundary-value problems for the BBM equation and the KdV equation, with and without a Burgers-type dissipation appended. It is shown that the total energy of a solution of these problems grows at an algebraic rate which is in fact sharp for solutions of the associated linear equations. We also establish that solutions of the linear problems are eventually periodic if the boundary data are periodic.
2009, 23(4): 1169-1190 doi: 10.3934/dcds.2009.23.1169 +[Abstract](1389) +[PDF](1591.3KB)
Abstract:
We present here a highly efficient and accurate numerical scheme for initial and boundary value problems of a two-dimensional Boussinesq system which describes three-dimensional water waves over a moving and uneven bottom with surface pressure variation. The scheme is then used to study in details the waves generated from rectangular sources and the two-dimensional wave patterns.
2009, 23(4): 1191-1204 doi: 10.3934/dcds.2009.23.1191 +[Abstract](1894) +[PDF](1239.0KB)
Abstract:
We consider a Boussinesq system of BBM-BBM type in two space dimensions. This system approximates the three-dimensional Euler equations and consists of three coupled nonlinear dispersive wave equations that describe propagation of long surface waves of small amplitude in ideal fluids over a horizontal bottom. We show that the initial-boundary value problem for this system, posed on a bounded smooth plane domain with homogeneous Dirichlet or Neumann or reflective (mixed) boundary conditions, is locally well-posed in $H^1$. After making some remarks on the temporal interval of validity of these models, we discretize the system by a standard Galerkin-finite element method and present the results of some numerical experiments aimed at simulating two-dimensional surface wave flows in complex plane domains with a variety of initial and boundary conditions.
2009, 23(4): 1205-1240 doi: 10.3934/dcds.2009.23.1205 +[Abstract](1513) +[PDF](318.0KB)
Abstract:
The Benjamin-Ono equation is known as a model of internal long waves in stratified fluids or two-fluid systems. In this paper, we consider the validity of this type of modeling of a two-phase problem for capillary-gravity waves, which is a free boundary problem for the incompressible Euler equation with the irrotational condition. We show that the solutions of the free boundary problem split up into two waves and the shape of each wave is governed by the Benjamin-Ono equation in a slow time scale.
2009, 23(4): 1241-1252 doi: 10.3934/dcds.2009.23.1241 +[Abstract](2022) +[PDF](201.7KB)
Abstract:
The regularized long-wave or BBM equation

$u_{t}+u_{x}+u u_{x}-u_{x x t} = 0$

was derived as a model for the unidirectional propagation of long-crested, surface water waves. It arises in other contexts as well, and is generally understood as an alternative to the Korteweg-de Vries equation. Considered here is the initial-value problem wherein $u$ is specified everywhere at a given time $t = 0$, say, and inquiry is then made into its further development for $t>0$. It is proven that this initial-value problem is globally well posed in the $L^2$-based Sobolev class $H^s$ if $s \geq 0$. Moreover, the map that associates the relevant solution to given initial data is shown to be smooth. On the other hand, if $s < 0$, it is demonstrated that the correspondence between initial data and putative solutions cannot be even of class $C^2$. Hence, it is concluded that the BBM equation cannot be solved by iteration of a bounded mapping leading to a fixed point in $H^s$-based spaces for $s < 0$. One is thus led to surmise that the initial-value problem for the BBM equation is not even locally well posed in $H^s$ for negative values of $s$.

2009, 23(4): 1253-1275 doi: 10.3934/dcds.2009.23.1253 +[Abstract](1688) +[PDF](257.0KB)
Abstract:
In this essay, we study the initial-value problem

$u_t+u_x+g(u)_x+Lu_t=0, \qquad x\in\mathbb R,\quad t>0,$
$u(x,0)=u_0(x), \qquad x\in\mathbb R, (0.1)$

where $u=u(x,t)$ is a real-valued function, $L$ is a Fourier multiplier operator with real symbol $\alpha(\xi),$ say, and $g$ is a smooth, real-valued function of a real variable. Equations of this form arise as models of wave propagation in a variety of physical contexts. Here, fundamental issues of local and global well-posedness are established for $L_p$, $H^s$ and bore-like or kink-like initial data. In the special case where $\alpha(\xi)=|\xi|^{r}$ wherein $r>1$ and $g(u)=1/2u^2,$ (0.1) is globally well-posed in time if $s$ and $r$ satisfy a simple algebraic relation.

2009, 23(4): 1277-1294 doi: 10.3934/dcds.2009.23.1277 +[Abstract](1582) +[PDF](256.0KB)
Abstract:
We study the global well-posedness (GWP) and small data scattering of radial solutions of the semirelativistic Hartree type equations with nonlocal nonlinearity $F(u) = \lambda (|\cdot|^{-\gamma}$ * $|u|^2)u$, $\lambda \in \mathbb{R} \setminus \{0\}$, $0 < \gamma < n$, $n \ge 3$. We establish a weighted $L^2$ Strichartz estimate applicable to non-radial functions and some fractional integral estimates for radial functions.
2009, 23(4): 1295-1311 doi: 10.3934/dcds.2009.23.1295 +[Abstract](1548) +[PDF](220.8KB)
Abstract:
We prove the local-well posedness of the generalized Benjamin-Ono equations in $H^1(\T)$.
2009, 23(4): 1313-1325 doi: 10.3934/dcds.2009.23.1313 +[Abstract](1715) +[PDF](216.1KB)
Abstract:
We consider the Cauchy problem for the damped nonlinear Schrödinger equations, and prove some blowup and global existence results which depend on the size of the damping coefficient. We also discuss the $L^2$ concentration phenomenon of blowup solutions in the critical case.

2018  Impact Factor: 1.143


text:
# Which of the following salts does not contain water of crystallization?(A) Blue vitriol(B) Baking soda(C) Washing soda(D) Gypsum

Verified
185.1k+ views
Hint: The water that is stoichiometrically bound into a crystal when crystallized out of water is known as water(s) of crystallization or water(s) of hydration.

Complete step by step solution:
-In simpler words, the number of water molecules present in one formula unit of salt is known as the water of crystallization. Water being the common solvent to be found in crystals because of its polarity and smaller size hence may sometimes incorporate within the crystal lattice.
-Water of crystallization refers to the water that is found in the crystalline framework of a metal complex or a salt and is not bonded directly to the metal cation.
-The crystal salts which have water(s) of crystallization are known as hydrates.
-This crystal of water does not include contaminants and is easily affected by the heat.
-The chemical formula of blue vitriol which is copper sulphate pentahydrate is $CuS{{O}_{4}}.5{{H}_{2}}O$. It has 5 moles of water.
-The chemical formula of baking soda which is sodium bicarbonate is $NaHC{{O}_{3}}$. It does not have any water molecule incorporated in its crystal lattice.
-The chemical formula of Washing soda which is sodium carbonate monohydrate is $N{{a}_{2}}C{{O}_{3}}.{{H}_{2}}O$. It has one mole of water.
-The chemical formula of Gypsum which is sulphate dihydrate is $CaS{{O}_{4}}.2{{H}_{2}}O$. It has 2 moles of water.

So, the correct answer is option (B).

Note: The water molecules present in hydrated molecules are held by hydrogen bonding. Hydrogen bonding is a type of weak force that results in the formation of dipole-dipole interaction between the hydrogen atom and an electronegative atom that is strongly bonded to another electronegative atom. Since the water of crystallization in a crystal is much less intimately combined with the salt than the water of constitution, and therefore on heating, these water of crystallization are more easily expelled, often losing the crystalline properties.


text:
FEATool Multiphysics  v1.15.5 Finite Element Analysis Toolbox
Orthotropic Heat Conduction

This is an example of modeling anisotropic heat conduction in an orthotropic material where a heated solid bar suddenly is cooled by submerging it in a cool fluid. The material features different thermal conductivities in the x and y-directions which is accounted for by modifying the diffusion term in the heat transfer equation. Instead of solving the usual isotropic case

$\rho C_p\frac{\partial T}{\partial t} - k(\frac{\partial^2 T}{\partial x^2} + \frac{\partial^2 T}{\partial x^2}) = 0$

we will instead solve the following

$\rho C_p\frac{\partial T}{\partial t} - (k_x\frac{\partial^2 T}{\partial y^2} + k_y\frac{\partial^2 T}{\partial y^2}) = 0$

where $$k_x = 34.6147$$ and $$k_y = 6.23687\ W/mK$$ are the thermal conductivities in the different directions. Fully anisotropic cases can technically also be handled by introducting off-diagonal $$k_{x_i,x_j}\frac{\partial^2 T}{\partial x_i \partial x_j}$$ diffusion terms.

The following material and simulation parameters are given; initial temperature $$T_0 = 260\ °C$$, density $$\rho = 6407.4 \ kg/m^3$$, heat capacity $$C_p = 37.688\ J/kgK$$. Due to symmetry we only need to model a quarter domain of a 2D cross-section with dimensions 5.08 by 2.54 cm. Conductive heat flux boundary conditions are used on the external boundaries with a convection coefficient $$h = 1361.7\ W/m^2K$$ and surrounding temperature $$T_{inf} = 37.7778\ °C$$. The cooling process is simulated for 3 seconds after which the temperature is measured in the center core and corners, and compared to the reference values [1].

# Tutorial

This section describes how to set up and solve the orthotropic heat conduction example with the FEATool graphical user interface (GUI).

The model is available as an automated tutorial by selecting Model Examples and Tutorials... > Heat Transfer > Orthotropic Heat Conduction from the File menu. Or alternatively, follow the step-by-step instructions below.

1. To start a new model click the New Model toolbar button, or select New Model... from the File menu.
2. Select the Heat Transfer physics mode from the Select Physics drop-down menu.

3. Press OK to finish the physics mode selection.

Due to symmetry we only need to model a quarter of the domain, a 1 by 2 inch rectangle. Note that as FEATool does not specify a fixed unit system the dimensions are converted to SI units for convenience and to be consistent with the units used in the material parameters.

1. Select Rectangle from the Geometry menu.
2. Enter 2*2.54*1e-2 into the xmax edit field.
3. Enter 1*2.54*1e-2 into the ymax edit field.

4. Press OK to finish and close the dialog box.

5. Switch to Grid mode by clicking on the corresponding Mode Toolbar button.
6. Increase the grid density by pressing the Refine Toolbar button twice.

7. Switch to Equation mode by clicking on the corresponding Mode Toolbar button.
8. Enter 6407.4 into the Density edit field.
9. Enter 37.688 into the Heat capacity edit field.
10. Enter 260 into the Initial condition for T edit field.

To model the anisotropic diffusion coefficient edit the heat transfer equation and replace the original term k_ht*(Tx_x + Ty_y) with (34.6147*Tx_x + 6.23687*Ty_y).

1. Press the edit button.
2. Enter rho_ht*cp_ht*T' - (34.6147*Tx_x + 6.23687*Ty_y) + rho_ht*cp_ht*(u_ht*Tx_t + v_ht*Ty_t) = q_ht into the Equation for T edit field.

3. Press OK to finish and close the equation editing dialog box.
4. Then press OK to finish the equation and subdomain settings specification.

Boundary conditions are defined in Boundary Mode and describes how the model interacts with the external environment. Here the bottom and left sides are symmetry boundaries while the top and right are prescribed convective flux conditions.

1. Switch to Boundary mode by clicking on the corresponding Mode Toolbar button.
2. Select 1 and 4 in the Boundaries list box.
3. Select Thermal insulation/symmetry from the Heat Transfer drop-down menu.
4. Select 2 and 3 in the Boundaries list box.
5. Select Heat flux from the Heat Transfer drop-down menu.
6. Enter 1361.7 into the Heat transfer coefficient edit field.
7. Enter 37.7778 into the Bulk temperature edit field.

8. Press OK to finish the boundary condition specification.
9. Switch to Solve mode by clicking on the corresponding Mode Toolbar button.
10. Press the Settings Toolbar button.
11. Select Time-Dependent from the Solution and solver type drop-down menu.
12. Enter 3 into the Duration of time-dependent simulation (maximum time) edit field.

13. Press the Solve button.
14. Press the Plot Options Toolbar button.
15. Select the Contour Plot check box.
16. Enter 20 into the Number or specified vector of contour levels to plot edit field.
17. Press OK to plot and visualize the selected postprocessing options.

To evaluate the accuracy of the solution the temperature can be evaluated in the points (0,0), (2,1), (2,0), and (0,1) inches and compared with reference temperature values $$T_{ref}$$ = 237, 66.1, 137, and 94.4 degrees C respectively.

1. Select Point/Line Evaluation... from the Post menu.
2. Enter 0 0.0508 0.0508 0 into the Evaluation coordinates in x-direction edit field.
3. Enter 0 0.0254 0 0.0254 into the Evaluation coordinates in y-direction edit field.
4. Press the Apply button.

From the Evaluation Result field we can see that the computed temperature in the evaluation points is very close to the reference values.

1. Press the Cancel button to close the dialog box.

The orthotropic heat conduction heat transfer model has now been completed and can be saved as a binary (.fea) model file, or exported as a programmable MATLAB m-script text file, or GUI script (.fes) file.

# Reference

[1] P.J. Schneider, Conduction Heat Transfer, Addison-Wesley, 2nd Ed., Ex. 10-7, pp. 261, 1957.


text:
WR Card

The WR card is used to define a dielectric windscreen reference plane. Geometrically this surface is not part of the electromagnetic model and is used simply to determine the curvature factor between the two elements on the windscreen.

On the Solve/Run tab, in the Windscreen group, click the  Windscreen reference (WR) icon.

Note: The WR, WA and WD cards should be used together to create windscreen antenna models. These three cards respectively define the windscreen reference surface, the windscreen solution elements (antenna) and the windscreen layered media definition.

Parameters:

Windscreen name
The name of the windscreen.
Use as reference all surfaces with label
The start of the label range.
(optionally) up to label
[Optional] The end of the label range.
Note: The windscreen reference triangles are defined by label and since this plane also forms the zero reference with respect to the defined windscreen antenna elements and glass layers, they should all have their normals pointing in the same direction.


text:
# How do you place the inclusion symbols to make the statement 3*4+2/6=3 true?

$3 \cdot \left(4 + 2\right)$/$6$ or
3*((4+2)/6)


text:
# Suppose G is a finite abelian group with a nontrivial subgroup H contained in every subgroup of G. Show that G is cyclic. [duplicate]

The prompt is from Herstein's Topics in Algebra. The proof is to be done without using the structure theorem for finite abelian groups. I showed that $H$ was cyclic of order $p$ a prime and G was a $p$-group. I then set $|G| = p^n$ and proceeded by induction on n. The case $n=1$ is clear. Then, by induction every proper subgroup of $G$ is cyclic. By the Sylow theorems $G$ therefore contains an element $a$ of order $p^{n-1}$. We have $G = \langle a\rangle \langle b\rangle$, where $b$ is any element of $G$ not in $\langle a\rangle$ (here $\langle a\rangle$ denotes the subgroup generated by $a$). Quotient by $K$, the intersection of $\langle a\rangle$ and $\langle b\rangle$, to see that $G/K$ is isomorphic to $\Bbb{Z}_{p}^{2}$, since $G/K$ is the direct product of two nontrivial cyclic p-groups ($\langle a\rangle /K$ and $\langle b\rangle /K$) and by homomorphism every one of $G/K$'s subgroups is cyclic. Therefore taking the preimage of each of the cyclic subgroups of $G/K$, each of which is a distinct maximal proper subgroup of $G$, $G$ must have $p+1$ distinct subgroups of order $p^{n-1}$. Also, note that since $b$ was an arbitrary element not in $\langle a\rangle$ and $\langle a\rangle /K$ and $\langle b\rangle /K$ have the same number of elements, $\langle a\rangle$ contains every element of order less than $p^{n-1}$. Since $\langle a\rangle$ has a unique subgroup of order $p^m$ where $m<n-1$, $G$ has a unique cyclic subgroup of order $p^m$.

This is as far as I've got so far. Not really sure where to go from here. Any ideas? Let me know if you need more details.

## marked as duplicate by Nicky Hekster group-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 30 '16 at 12:26

• In what page of the Herstein book is? (to know what theorems can be used and which ones are very strong) – MonsieurGalois Aug 30 '16 at 6:33
• This is on page 108 of the second edition. Chapter 2, section 13. – Vik78 Aug 30 '16 at 6:34

(1) $H$ should be of prime order (otherwise it will have a proper subgroup $K$ and $H\nsubseteq K$).

(2) Let $|H|=p$. If $|G|$ is divisible by another prime $q$, then there will be a subgroup of order $q$ and $H$ can not be contained in it.

(3) Hence $|G|=p^k$ for some $k$, with condition that there is a subgroup $H$ of order $p$ contained in every subgroup.

(4) Let $H=\langle h\rangle$. If $k=1$ we are done. Let $k>1$. Then every proper subgroup of $G$ satisfies the hypothesis and so is cyclic by induction.

(5) Let $M$ be a maximal subgroup of $G$; it is cyclic by (4), say $M=\langle x\rangle$. Take $y\in G\setminus M$.

(6) Then consider the following situation in $G$: $$1 \leq \langle h\rangle \leq \cdots \leq \langle x^p\rangle \leq \langle x\rangle \leq G.$$ Since $[G: \langle x\rangle]=p$, so $y^p\in \langle x\rangle$.

(7) Suppose if possible $y^p$ is in $\langle x^p\rangle$. Then $y^p=x^{ip}$ for some $i$. Then consider $(yx^{-i})$. Its order is $1$ or $p$ or $p^2$ or ...

(8) Since $(yx^{-i})^p=1$ and $yx^{-i}\neq 1$ (o.w. $y\in \langle x\rangle$) hence order of $\langle yx^{-i}\rangle$ is $p$, and it should be equal to the subgroup $H=\langle h\rangle$ by hypothesis.

(9) Since $yx^{-1}\in H\leq \langle x\rangle$, hence $y\in \langle x\rangle=M$ contradiction. Thus assumption (that $y^p\in \langle x^p\rangle$) is wrong, hence $y^p$ is in $\langle x\rangle$ but not in $\langle x^p\rangle$.

(10) Then $|y^p|=|x|$ so $|y|=p.|x|=|G|$.

• Great proof! I was almost there. – Vik78 Aug 30 '16 at 18:54


text:
# Fixing free parameters

### Chapter 5: Vagueness

Sometimes our words themselves are imprecise, vague, and heavily dependent on context to fix their interpretations. Compositionality assumes semantic atoms with invariant meanings; context-dependent word interpretations pose a serious challenge to compositionality. Take the case of gradable adjectives: “expensive for a sweater” means something quite different from “expensive for a laptop.” What, then, do we make of the contribution from the word “expensive”? Semanticists settle on the least common denominator: a threshold semantics by which the adjective asserts that holders of the relevant property surpass some point on the relevant scale (i.e., expensive means something like “more expensive than some contextually-determined threshold on prices). Whereas semanticists punt on the mechanism by which context fixes these aspects of meaning, the RSA framework is well-suited to meet the challenge.

Lassiter & Goodman propose we parameterize the meaning function for sentences containing gradable adjectives so that their interpretations are underspecified (reft:lassitergoodman2013, reft:LassiterGoodman2015:Adjectival-vagu). This interpretation-fixing parameter, the gradable threshold value $$\theta$$ (i.e., a degree), is something that conversational participants can use their prior knowledge to actively reason about and set. As with the ambiguity-resolving variable in the previous chapter, $$\theta$$ gets lifted to the level of the pragmatic listener, who jointly infers the gradable threshold (e.g., the point at which elements of the relevant domain count as expensive) and the true state (e.g., the indicated element’s price).

The model depends crucially on our prior knowledge of the world state. Let’s start with a toy prior for the prices of books.

var book = {
"prices": [2, 6, 10, 14, 18, 22, 26, 30],
"probabilities": [1, 2, 3, 4, 4, 3, 2, 1]
};

var statePrior = function() {
return categorical(book.probabilities, book.prices);
};

Exercise: Visualize the statePrior.

Next, we create a prior for the degree threshold $$\theta$$. Since we’re talking about expensive books, $$\theta$$ will be the price cutoff to count as expensive. But we want to be able to use expensive to describe anything with a price, so we’ll set the thetaPrior to be uniform over the possible prices in our world.

var book = {
"prices": [2, 6, 10, 14, 18, 22, 26, 30],
"probabilities": [1, 2, 3, 4, 4, 3, 2, 1]
};

var statePrior = function() {
return categorical(book.probabilities, book.prices);
};

var thetaPrior = function() {
return uniformDraw(book.prices);
}

Exercise: Visualize the thetaPrior.

We introduce two possible utterances: saying that a book is expensive, or saying nothing at all (a “null utterance”). The semantics of the expensive utterance checks the relevant item’s price against the price cutoff. The “null utterance” represents the speaker’s choice to stay silent: silence is easier to produce than saying “expensive” and it is never (literally) false. (Whence, that rational speakers prefer silence over speech which is not informative; see below.) The model of the literal listener implemented here can be written as (where $$s$$ is general notation for the world state (here: price of a book), and $$\theta$$ is the threshold to be inferred later on):

$P_{L_0}(s \mid u, \theta) = P(s \mid [\![u]\!]^\theta)$
var book = {
"prices": [2, 6, 10, 14, 18, 22, 26, 30],
"probabilities": [1, 2, 3, 4, 4, 3, 2, 1]
};

var statePrior = function() {
return categorical(book.probabilities, book.prices);
};

var thetaPrior = function() {
return uniformDraw(book.prices);
};

var utterances = ["expensive", ""];
var cost = {
"expensive": 1,
"": 0
};
var utterancePrior = function() {
return uniformDraw(utterances);
};

var meaning = function(utterance, price, theta) {
utterance == "expensive" ? price >= theta : true;
};

var literalListener = cache(function(utterance, theta) {
return Infer({method: "enumerate"}, function() {
var price = statePrior();
condition(meaning(utterance, price, theta))
return price;
})
})

Exercise: Check $$L_0$$’s predictions for various price cutoffs.

We get a full RSA model once we add the pragmatic speaker $$L_1$$ and pragmatic listener $$L_1$$ models. The pragmatic speaker is assumed to have a fixed threshold $$\theta$$, the pragmatic listener hears the gradable adjective and jointly infers the relevant item price and cutoff to count as expensive.

$P_{S_1}(u \mid s, \theta) \propto \exp ( \alpha \ (\log P_{L_0}(s \mid u, \theta) - C(u)))$ $P_{L_1}( s, \theta \mid u) \propto P(s) \ P(\theta) \ P_{S_1}( u \mid s, \theta)$
var book = {
"prices": [2, 6, 10, 14, 18, 22, 26, 30],
"probabilities": [1, 2, 3, 4, 4, 3, 2, 1]
};

var statePrior = function() {
return categorical(book.probabilities, book.prices);
};

var thetaPrior = function() {
return uniformDraw(book.prices);
};

var alpha = 2; // optimality parameter

var utterances = ["expensive", ""];
var cost = {
"expensive": 1,
"": 0
};
var utterancePrior = function() {
return uniformDraw(utterances);
};

var meaning = function(utterance, price, theta) {
utterance == "expensive" ? price >= theta : true;
};

var literalListener = cache(function(utterance, theta) {
return Infer({method: "enumerate"}, function() {
var price = statePrior();
condition(meaning(utterance, price, theta))
return price;
});
});

var speaker = cache(function(price, theta) {
return Infer({method: "enumerate"}, function() {
var utterance = utterancePrior();
factor( alpha * (literalListener(utterance, theta).score(price)
- cost[utterance]));
return utterance;
});
});

var pragmaticListener = function(utterance) {
return Infer({method: "enumerate"}, function() {
var price = statePrior();
var theta = thetaPrior();
factor(speaker(price, theta).score(utterance));
return { price: price, theta: theta };
});
};

var expensiveBook = pragmaticListener("expensive");
viz.auto(marginalize(expensiveBook, "price"));
viz.auto(marginalize(expensiveBook, "theta"));

Exercises:

1. What happens when you make the "expensive" utterance more costly? Why?
2. Try altering the statePrior and see what happens to $$L_1$$’s inference.

For a better model, rather than assuming prior knowledge (e.g., knowledge about domain-specific prices), we can measure it, then feed these measurements into the model as facts about the world. Doing so allows the model to make actual predictions about the behavior we expect to observe from listeners. Here, we draw on data measuring prior knowledge that was gathered by Lassiter & Goodman (unpublished work).

///fold:
// "price" refers to the midpoint of the bin that participants marked a slider for
// "probability" refers to the average of participants' responses, after normalizing responses for each person for each item
var coffee = {
"prices": [2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126, 130, 134, 138, 142, 146, 150, 154, 158, 162, 166, 170, 174, 178, 182, 186, 190, 194, 198, 202, 206, 210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262, 266, 270],
"probabilities": [0.00394425443541116, 0.00566290387321734, 0.00825676850536135, 0.0128170636252316, 0.016825062585583, 0.0252551834871954, 0.028468923991368, 0.0287662881619652, 0.0282906782393822, 0.0298574213919862, 0.0289804109562303, 0.0294934077950995, 0.0282267499972963, 0.027150810280172, 0.0263590035097067, 0.0281826763029633, 0.0279055635543465, 0.0278411275661919, 0.0278729305091271, 0.0260779123427457, 0.025504052957576, 0.0244726498427457, 0.0245886104865853, 0.0244622094919612, 0.0245026711395991, 0.0215246465554349, 0.018590665797836, 0.0178546907780941, 0.0171993717256383, 0.0162494284404094, 0.0160224797974072, 0.0153063570140879, 0.0146233597944038, 0.0137848051705444, 0.0143326737593802, 0.0134490255028661, 0.0135790032064503, 0.0138226943563312, 0.0131925119561275, 0.0126370445876965, 0.0106890591752964, 0.0106020628239155, 0.0101185949533398, 0.00911819843666944, 0.0106104999317876, 0.0109322919246626, 0.0107129834142186, 0.00837168284710854, 0.0080750721559225, 0.00804082264332751, 0.0067313619453682, 0.00627460791368519, 0.00589113687110393, 0.00540523790626922, 0.00552727879179031, 0.00550309276614945, 0.00523220007943591, 0.00511881990396121, 0.00512531318796172, 0.00518250532794681, 0.00363644079549071, 0.00358121922955672, 0.00340485508432679, 0.00300204070158435, 0.00285900767263514, 0.00307193123371249, 0.00265238954722026, 0.00259519926379722]
};
"prices": [3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, 105, 111, 117, 123, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285, 291, 297, 303, 309, 315, 321, 327],
"probabilities": [0.0100932350462178, 0.0170242011533158, 0.0239368832461044, 0.0287274552724317, 0.0335581038692007, 0.0340978261675896, 0.0343161232972866, 0.0360390185911639, 0.036657423324831, 0.0363628055611882, 0.0363696076759004, 0.0349562074307856, 0.034074002420704, 0.0319526478383908, 0.0310094760253021, 0.0310633591664631, 0.0306213012447122, 0.0267011137913525, 0.0258670033914898, 0.0258502350122376, 0.025023519418377, 0.023483875551852, 0.0220028560428636, 0.0214970268323533, 0.0208370797134518, 0.0179036695749784, 0.0171528323730662, 0.0146789727474624, 0.0151970966046565, 0.0144002087359724, 0.0133747582315602, 0.0123806405169515, 0.0120269613954518, 0.0114214380586013, 0.0119920388378585, 0.011383038780713, 0.0113361342839428, 0.0109751373856222, 0.00862772988748631, 0.00849834370871022, 0.00929436665963529, 0.00977137935316548, 0.00855300304060609, 0.00704341088484788, 0.00760242506144268, 0.0066676293070587, 0.00664151547908964, 0.00631842654192989, 0.00633866335810551, 0.00617281009506307, 0.00588389192288987, 0.00480853638779448, 0.00438645078845164, 0.00381072308793509, 0.00323537982338538]
};
var laptop = {
"prices": [25, 75, 125, 175, 225, 275, 325, 375, 425, 475, 525, 575, 625, 675, 725, 775, 825, 875, 925, 975, 1025, 1075, 1125, 1175, 1225, 1275, 1325, 1375, 1425, 1475, 1525, 1575, 1625, 1675, 1725, 1775, 1825, 1875, 1925, 1975, 2025, 2075, 2125, 2175, 2225, 2275, 2325, 2375, 2425, 2475],
"probabilities": [0.00143805356403561, 0.00271785465081783, 0.00606278580557322, 0.00969025393738191, 0.0148967448541453, 0.0198125393878057, 0.0241329166751748, 0.0295996079491818, 0.0330742235328304, 0.0361264464785417, 0.0401533300800443, 0.0409948060761354, 0.0413284234227614, 0.0403647740154393, 0.0401794950623575, 0.0389208352425967, 0.0381211282626673, 0.0380271843819898, 0.0337130710333348, 0.0320869893997556, 0.0303954589742173, 0.0290371975286599, 0.026737673556754, 0.0259385656770147, 0.0246868317621353, 0.0229019589247208, 0.0214921049215865, 0.0206506505418053, 0.0194727089077923, 0.0192606778139999, 0.016502461425033, 0.015779852769427, 0.014573698680051, 0.0141934767007475, 0.0128416097234241, 0.0124983882714321, 0.011580082968956, 0.0111057181921517, 0.0107390517842162, 0.0097877804629936, 0.00869628232285698, 0.00796157687645315, 0.00781439122831209, 0.0074127159955819, 0.00686298004874477, 0.00667898701991275, 0.00628316286073362, 0.00606433685126466, 0.00552579230999036, 0.00508236108646155]
};
var sweater = {
"prices": [1.5, 4.5, 7.5, 10.5, 13.5, 16.5, 19.5, 22.5, 25.5, 28.5, 31.5, 34.5, 37.5, 40.5, 43.5, 46.5, 49.5, 52.5, 55.5, 58.5, 61.5, 64.5, 67.5, 70.5, 73.5, 76.5, 79.5, 82.5, 85.5, 88.5, 91.5, 94.5, 97.5, 100.5, 103.5, 106.5, 109.5, 112.5, 115.5, 118.5, 121.5, 124.5, 127.5, 130.5, 133.5, 136.5, 139.5, 142.5, 145.5, 148.5, 151.5, 154.5, 157.5, 160.5, 163.5, 166.5, 169.5, 172.5, 175.5, 178.5, 181.5, 184.5, 187.5, 190.5, 193.5, 196.5, 199.5, 202.5, 205.5, 208.5, 211.5, 214.5, 217.5, 220.5, 223.5, 226.5, 229.5, 232.5, 235.5, 238.5],
"probabilities": [0.00482838499944466, 0.00832934578733181, 0.0112952500492109, 0.0173774790108894, 0.0232006658974883, 0.0258422772579257, 0.0278986695293033, 0.0295289411585088, 0.0306833716679902, 0.0318318597751272, 0.0337834568516467, 0.0339921053872795, 0.0344439315108449, 0.033934432265521, 0.032462878943956, 0.031189466255733, 0.0308771801297135, 0.028870440122745, 0.0268081450723193, 0.0255858806436071, 0.0251329374896422, 0.0228478370318916, 0.0204321414255458, 0.0198885290723185, 0.018227461808914, 0.0175834655975716, 0.0162564776853142, 0.0157731201439098, 0.0152929182194243, 0.0150019091787104, 0.0149289099733278, 0.0141896849640091, 0.0139276040018639, 0.0134566451556076, 0.0121362548659773, 0.0108558348756676, 0.010613387912742, 0.010091436302254, 0.0098485635160309, 0.00934441306894098, 0.0085581357559821, 0.00679765980394746, 0.00693786098620408, 0.00696322949112243, 0.0070065216834756, 0.00642780104088309, 0.0064321559380608, 0.00656481702666307, 0.0062031359060876, 0.00687959185242292, 0.00510183619524203, 0.00519749642756681, 0.00498195289503402, 0.00463848039694862, 0.00446827225938831, 0.00434243838506282, 0.00454705086043589, 0.0045914966088052, 0.00451510979961212, 0.00443992782954235, 0.00329590488378491, 0.00349426470729333, 0.00329078051712042, 0.00323849270094039, 0.00302968185434419, 0.00294213735024183, 0.00335510797297302, 0.00328341117067163, 0.00329874147186505, 0.00306305447627786, 0.00262071902879654, 0.00274925007756808, 0.00246374710845232, 0.00262910011008071, 0.00248819809733968, 0.00211124548886266, 0.00204178897873852, 0.00208550762922333, 0.00204890779502054, 0.00228129283166782]
};
var watch = {
"prices": [25, 75, 125, 175, 225, 275, 325, 375, 425, 475, 525, 575, 625, 675, 725, 775, 825, 875, 925, 975, 1025, 1075, 1125, 1175, 1225, 1275, 1325, 1375, 1425, 1475, 1525, 1575, 1625, 1675, 1725, 1775, 1825, 1875, 1925, 1975, 2025, 2075, 2125, 2175, 2225, 2275, 2325, 2375, 2425, 2475, 2525, 2575, 2625, 2675, 2725, 2775, 2825, 2875, 2925, 2975],
"probabilities": [0.040844560268751, 0.0587099798246933, 0.0656194599591356, 0.0667642412698035, 0.0615953803048016, 0.0510809063784378, 0.0467203673419258, 0.0446735950187136, 0.040047421916613, 0.0350583957334483, 0.0297508215717606, 0.0256829651118227, 0.024135920250668, 0.0228891907259206, 0.021706684520276, 0.0186449440066946, 0.0187249266247728, 0.0179250744798993, 0.0173698811746238, 0.0165581725818319, 0.0160745066032247, 0.0127927305129066, 0.0113730680265067, 0.0109485307623827, 0.00923468422650943, 0.00899007751887508, 0.00880520147998275, 0.00838023585866885, 0.00841052411004918, 0.00828830635037619, 0.00834008093757411, 0.00750681534099784, 0.00724072133740109, 0.00717291664158004, 0.00682823777708754, 0.00646995193940331, 0.00697139732982518, 0.00711846547272734, 0.00698781312802354, 0.00732316558583701, 0.00594973158122097, 0.00557461443747403, 0.00541637601910211, 0.00518850469148531, 0.00572025848989677, 0.0051443557601358, 0.00510282169734075, 0.00493720252580643, 0.00560198932991028, 0.00519158715054485, 0.00473398797752786, 0.00540907722833213, 0.00494653421540979, 0.00495500420164643, 0.00494083025189895, 0.00481566268206312, 0.00442965937328148, 0.00441189688100535, 0.00415116538135834, 0.00361842012002631]
};
var data = {
"coffee maker": coffee,
"laptop": laptop,
"sweater": sweater,
"watch": watch
};

var statePrior_lookup = function(item) {
var prices = data[item].prices;
var probabilities = data[item].probabilities;
return function() {
return categorical(probabilities, prices);
};
};

var thetaPrior_lookup = function(item) {
var thetas = data[item].prices;
return function() {
return uniformDraw(thetas);
};
};
///

var alpha = 2; // optimality parameter

var utterances = ["expensive", ""];
var cost = {
"expensive": 1,
"": 0
};
var utterancePrior = function() {
return uniformDraw(utterances);
};

var meaning = function(utterance, price, theta) {
utterance == "expensive" ? price >= theta : true;
};

var literalListener = cache(function(utterance, theta, item) {
var statePrior = statePrior_lookup(item);
return Infer({method: "enumerate"}, function() {
var price = statePrior();
condition(meaning(utterance, price, theta));
return price;
});
});

var speaker = cache(function(price, theta, item) {
return Infer({method: "enumerate"}, function() {
var utterance = utterancePrior();
factor( alpha * (literalListener(utterance, theta, item).score(price)
- cost[utterance]));
return utterance;
});
});

var pragmaticListener = function(utterance, item) {
// first identify the relevant priors
var statePrior = statePrior_lookup(item);
var thetaPrior = thetaPrior_lookup(item);
// then run inference
return Infer({method: "enumerate"},
function() {
var price = statePrior();
var theta = thetaPrior();
factor( speaker(price, theta, item).score(utterance) );
return { price: price, theta: theta };
});
};

var expensiveWatch = pragmaticListener("expensive", "watch");
print("the listener's posterior over watch prices:")
viz.density(marginalize(expensiveWatch, "price"));
print("the listener's posterior over watch price thresholds:")
viz.density(marginalize(expensiveWatch, "theta"));

var expensiveSweater= pragmaticListener("expensive", "sweater");
print("the listener's posterior over sweater prices:")
viz.density(marginalize(expensiveSweater, "price"));
print("the listener's posterior over sweater price thresholds:")
viz.density(marginalize(expensiveSweater, "theta"));

Exercises:

1. Visualize the various state priors.
2. Check $$L_1$$’s behavior for coffee makers and headphones and laptops.
3. Add an $$S_2$$ layer to the model and check its predictions.

#### Application 2: Inferring the comparison class

Implicit in the adjectives model from reft:lassitergoodman2013 is an awareness of the relevant comparison class: expensive for a watch vs. for a sweater. But what if we don’t know what the relevant comparison class is? Take the adjective tall: if I tell you John is a basketball player and he is tall, you probably infer that the comparison class is the superordinate category of all people. Similarly, if I tell you that John is a gymnast and tall, you probably infer that he is short compared to all people. But if I tell you that John is a soccer player and tall/short, you might instead infer that John is tall/short just for the subordinate category of soccer players. In an attempt to formalize the reasoning that goes into this inference, Tessler et al. (2017) augment the basic adjectives model to include uncertainty about the relevant comparison class: superordinate (e.g., compared to all people) or subordinate (e.g., compared to gymnasts or soccer players or basketball players).

This reasoning depends crucially on our prior knowledge about the relevant categories. To model this knowledge, we’ll need to intelligently simulate various categories: the heights of all people, the heights of gymnasts, the heights of soccer players, and the heights of basketball players.

// helper function
var exp = function(x){return Math.exp(x)}

// for discretization
var binParam = 5;

// information about the superordinate category prior
// e.g., the height distribution for all people
var superordinate = {mu: 0, sigma: 1};

// calculate the range in pre-defined steps;
// these values correspond to possible heights
var stateVals = _.range(superordinate.mu - 3 * superordinate.sigma,
superordinate.mu + 3 * superordinate.sigma,
superordinate.sigma/binParam)

// for each possible height, calculate its probability of occurrence
var stateProbs = cache(function(stateParams){
return map(function(s){
exp(Gaussian(stateParams).score(s))
}, stateVals)
});

// generate a statePrior using the possible heights and their probabilities
var generateStatePrior = cache(function(stateParams) {
return Infer({
model: function(){
return categorical({vs: stateVals, ps: stateProbs(stateParams)})
}
})
});

// information about the subordinate category priors
var subParams = {
low: {mu: -1, sigma: 0.5}, // gymnast heights
middle: {mu: 0, sigma: 0.5}, // soccer player heights
high: {mu: 1, sigma: 0.5} // basketball player heights
}

display("hypothetical height prior for all people")
viz.density(generateStatePrior(superordinate))
display("hypothetical height prior for gymnasts")
viz.density(generateStatePrior(subParams["low"]))
display("hypothetical height prior for soccer players")
viz.density(generateStatePrior(subParams["middle"]))
display("hypothetical height prior for basketball players")
viz.density(generateStatePrior(subParams["high"]))

Exercise: Try altering the subParams to generate different subordinate category priors.

We can add these state priors to the basic adjectives model, together with a lifted variable concerning the comparison class. Now, the pragmatic listener $$L_1$$ is told the relevant subordinate category (e.g., John is a basketball player) and hears the utterance with the scalar adjective (i.e., John is tall). On the basis of this information, $$L_1$$ jointly infers the state (i.e., John’s height) and the relevant comparison class the speaker intended (e.g., tall for all people vs. tall for a basketball player).

///fold:
// helper function
var exp = function(x){return Math.exp(x)}

// for discretization
var binParam = 3;

// information about the superordinate category prior
// e.g., the height distribution for all people
var superordinate_params = {mu: 0, sigma: 1};

// calculate the range in pre-defined steps;
// these values correspond to possible heights
var stateVals = _.range(superordinate_params.mu - 3 * superordinate_params.sigma,
superordinate_params.mu + 3 * superordinate_params.sigma,
superordinate_params.sigma/binParam)

// for each possible height, calculate its probability of occurrence
var stateProbs = cache(function(stateParams){
return map(function(s){
exp(Gaussian(stateParams).score(s))
}, stateVals)
});

// generate a statePrior using the possible heights and their probabilities
var generateStatePrior = cache(function(stateParams) {
return Infer({
model: function(){
return categorical({vs: stateVals, ps: stateProbs(stateParams)})
}
})
});

// generate the uniform threshold prior
var thresholdBins ={
positive: map(function(x){
return  x - (1/(binParam*2));
}, sort(stateVals)),
negative: map(function(x){
return  x + (1/(binParam*2));
}, sort(stateVals))
};

var thresholdPrior = cache(function(form){
return Infer({
model: function() { return uniformDraw(thresholdBins[form]) }
});
});
///

// information about the superordinate category priors
var subParams = {
gymnasts: {mu: -1, sigma: 0.5}, // gymnast heights
soccerPlayers: {mu: 0, sigma: 0.5}, // soccer player heights
}

// possible utterances can be either positive (tall) or negative (short) or a null utterance
var utterances = ["tall", "short", "silence"]

// meaning function for utterances
var meaning = function(utterance, state, thresholds) {
utterance == "tall" ? state > thresholds.tall :
utterance == "short" ? state < thresholds.short :
true
}

// assume a uniform prior over comparison classes
var classPrior = Infer({
model: function(){return uniformDraw(["subordinate", "superordinate"])}
});

// set speaker optimality
var alpha = 5;

var literalListener = cache(
function(utterance, thresholds, comparisonClass) {
Infer({model: function(){
var StatePrior = generateStatePrior(comparisonClass)
var state = sample(StatePrior);
var m = meaning(utterance, state, thresholds);
condition(m);
return state;
}})
}, 10000 // limit cache size
)

var speaker1 = cache(
function(state, thresholds, comparisonClass) {
Infer({model: function(){
var utterance = uniformDraw(utterances);
var L0 = literalListener(utterance, thresholds, comparisonClass);
factor( alpha * L0.score(state) );
return utterance;
}})
}, 10000 // limit cache size
)

var pragmaticListener = cache(function(utterance, subordinate_params) {
Infer({model: function(){

var statePrior = generateStatePrior(subordinate_params);
var state = sample(statePrior);
var thresholds = {
tall: sample(thresholdPrior("positive")),
short: sample(thresholdPrior("negative"))
}

// uncertainty about the comparison class (superordinate vs. subordinate)
var c = sample(classPrior)
var comparisonClass = c == "subordinate" ? subordinate_params : superordinate_params

var S1 = speaker1(state, thresholds, comparisonClass);
observe(S1, utterance);

return { comparisonClass: c, state : state }
}})
}, 10000 // limit cache size
)

// the possible experiment conditions:
// you hear that someone is a member of a subordinate category
// then you are told that they are tall/short;
// the task is to figure out the implicit comparison class
var exptConditions = [
{utt: "tall", sub: "soccerPlayers"},
{utt: "short", sub: "soccerPlayers"},
{utt: "tall",  sub: "gymnasts"},
{utt: "short", sub: "gymnasts"}
];

// generate structure predictions by mapping through the experiment conditions
var L1predictions = map(function(stim){
var L1posterior = pragmaticListener(stim.utt, subParams[stim.sub])
return {
utterance: stim.utt,
"P(superordinate comparison class)": exp(marginalize(L1posterior, "comparisonClass").score("superordinate")),
"subordinate category": stim.sub,
model: "L1"
}
}, exptConditions)


text:
### Overview

Batch methods, such as limited memory BFGS, which use the full training set to compute the next update to parameters at each iteration tend to converge very well to local optima. They are also straight forward to get working provided a good off the shelf implementation (e.g. minFunc) because they have very few hyper-parameters to tune. However, often in practice computing the cost and gradient for the entire training set can be very slow and sometimes intractable on a single machine if the dataset is too big to fit in main memory. Another issue with batch optimization methods is that they don’t give an easy way to incorporate new data in an ‘online’ setting. Stochastic Gradient Descent (SGD) addresses both of these issues by following the negative gradient of the objective after seeing only a single or a few training examples. The use of SGD In the neural network setting is motivated by the high cost of running back propagation over the full training set. SGD can overcome this cost and still lead to fast convergence.

The standard gradient descent algorithm updates the parameters \theta of the objective J(\theta) as,

\theta = \theta - \alpha \nabla_\theta E[J(\theta)]

where the expectation in the above equation is approximated by evaluating the cost and gradient over the full training set. Stochastic Gradient Descent (SGD) simply does away with the expectation in the update and computes the gradient of the parameters using only a single or a few training examples. The new update is given by,

\theta = \theta - \alpha \nabla_\theta J(\theta; x^{(i)},y^{(i)})

with a pair (x^{(i)},y^{(i)}) from the training set.

Generally each parameter update in SGD is computed w.r.t a few training examples or a minibatch as opposed to a single example. The reason for this is twofold: first this reduces the variance in the parameter update and can lead to more stable convergence, second this allows the computation to take advantage of highly optimized matrix operations that should be used in a well vectorized computation of the cost and gradient. A typical minibatch size is 256, although the optimal size of the minibatch can vary for different applications and architectures.

In SGD the learning rate \alpha is typically much smaller than a corresponding learning rate in batch gradient descent because there is much more variance in the update. Choosing the proper learning rate and schedule (i.e. changing the value of the learning rate as learning progresses) can be fairly difficult. One standard method that works well in practice is to use a small enough constant learning rate that gives stable convergence in the initial epoch (full pass through the training set) or two of training and then halve the value of the learning rate as convergence slows down. An even better approach is to evaluate a held out set after each epoch and anneal the learning rate when the change in objective between epochs is below a small threshold. This tends to give good convergence to a local optima. Another commonly used schedule is to anneal the learning rate at each iteration t as \frac{a}{b+t} where a and b dictate the initial learning rate and when the annealing begins respectively. More sophisticated methods include using a backtracking line search to find the optimal update.

One final but important point regarding SGD is the order in which we present the data to the algorithm. If the data is given in some meaningful order, this can bias the gradient and lead to poor convergence. Generally a good method to avoid this is to randomly shuffle the data prior to each epoch of training.

#### Momentum

If the objective has the form of a long shallow ravine leading to the optimum and steep walls on the sides, standard SGD will tend to oscillate across the narrow ravine since the negative gradient will point down one of the steep sides rather than along the ravine towards the optimum. The objectives of deep architectures have this form near local optima and thus standard SGD can lead to very slow convergence particularly after the initial steep gains. Momentum is one method for pushing the objective more quickly along the shallow ravine. The momentum update is given by,

\begin{align} v &= \gamma v+ \alpha \nabla_{\theta} J(\theta; x^{(i)},y^{(i)}) \\ \theta &= \theta - v \end{align}

In the above equation v is the current velocity vector which is of the same dimension as the parameter vector \theta. The learning rate \alpha is as described above, although when using momentum \alpha may need to be smaller since the magnitude of the gradient will be larger. Finally \gamma \in (0,1] determines for how many iterations the previous gradients are incorporated into the current update. Generally \gamma is set to 0.5 until the initial learning stabilizes and then is increased to 0.9 or higher.