text:
Optimal query complexity for estimating the trace of a matrix

# Optimal query complexity for estimating the trace of a matrix

Karl Wimmer Duquesne University Most of the work is done when the author is visiting the Simons Institute for the Theory of Computing, University of California-Berkeley. Supported in part by NSF grant CCF-1117079.    Yi Wu Purdue UniversityMost of the work is done when the author is visiting the Simons Institute for the Theory of Computing, University of California-Berkeley.    Peng Zhang Purdue University
###### Abstract

Given an implicit matrix with oracle access for any , we study the query complexity of randomized algorithms for estimating the trace of the matrix. This problem has many applications in quantum physics, machine learning, and pattern matching. Two metrics are commonly used for evaluating the estimators: i) variance; ii) a high probability multiplicative-approximation guarantee. Almost all the known estimators are of the form for being i.i.d. for some special distribution.

Our main results are summarized as follows:

1. We give an exact characterization of the minimum variance unbiased estimator in the broad class of linear nonadaptive estimators (which subsumes all the existing known estimators).

2. We also consider the query complexity lower bounds for any (possibly nonlinear and adaptive) estimators:

1. We show that any estimator requires queries to have a guarantee of variance at most .

2. We show that any estimator requires queries to achieve a -multiplicative approximation guarantee with probability at least .

Both above lower bounds are asymptotically tight.

As a corollary, we also resolve a conjecture in the seminal work of Avron and Toledo (Journal of the ACM 2011) regarding the sample complexity of the Gaussian Estimator.

## 1 Introduction

Given an matrix , we study the problem of estimating its trace

 trace(A)=n∑i=1Aii

with a randomized algorithm that can query for any . The goal is to minimize the number of queries used to achieve certain type of accuracy guarantee, such as the variance of the estimate or a multiplicative approximation (which holds with high probability). Finding an estimator that achieves such an accuracy guarantee with few queries has several applications. For example, this problem is well studied in the subject of lattice quantum chromodynamics, since such queries are physically feasible and can be used to efficiently estimate the trace of a function of a large matrix . Such an estimator can also be used as a building block for many other applications including solving least-squares problems [Hut89], computing the number of triangles in a graph [Avr10, Tso08], and string pattern matching [ACD01, AGW13].

This problem has been well studied in the literature. All of the previously analyzed estimators are of the form for ; nearly all take to be independent and identically distributed (i.i.d.) from some well designed distribution. For example, in [Hut89], the author just takes each query to be a random vector whose entries are i.i.d. Rademacher random variables (i.e., each coordinate is a uniformly random sample from ); we call this the Rademacher estimator. There are also several other alternative distributions on , such as drawing each query from a multivariate normal distribution [SR97], we call this the Gaussian estimator. Here, the coordinates of each vectors are i.i.d. Gaussian random variables. The work of [IE04] considers the case where only one query is allowed, but that query can be a unit vector in . Other estimators occur in [DS93, Wan94]. Recent work by [AT11], the authors propose several new estimators such as the unit vector estimator, normalized Rayleigh-quotient trace estimator, and the mixed unit vector estimator. One estimator that does not use i.i.d. queries is due to [RKA13]; in that work, the authors propose querying random standard basis vectors without replacement.

To characterize the performance of an estimator, perhaps the most natural metric is the variance of the estimator. It is known that the Gaussian estimator has variance and the random Rademacher vector estimator has variance , where is the Frobenius norm. In recent work by Avron and Toledo [AT11], it is suggested that the notion of a multiplicative approximation guarantee might be a better success metric of an estimator than the variance. Formally, we say an estimator is an -estimator if it outputs an estimate in the interval with probability at least . It should be noted that some assumptions on the matrices need to be made to have a valid -estimator, as it is impossible to achieve any multiplicative approximation when the matrix could have a trace of . A natural choice is to assume that comes from the class of symmetric positive semidefinite (SPD) matrices. For a SPD matrix, the authors in [AT11] prove that the Gaussian estimator with queries to the oracle is an -estimator. It was recently shown in [RKA13] that the random Rademacher vector estimator is also an -estimator with the same sample complexity.

An open problem asked in [AT11] is the following: does the Gaussian estimator require in order to be an -estimator? The authors showed that this number of queries suffices and conjectured that their analysis of the Gaussian estimator is tight with supporting evidence from empirical experiments. The paper gives some intuition on how to show an lower bound. The authors suggested that the difficulty of turning this argument into a formal proof is that “current bounds [on the cumulative distribution function] are too complex to provide a useful lower bound”. Regarding lower bounds for trace estimators, we note the related work of [LNW14], which considers the problem of sketching the nuclear norms of using bilinear sketches (which can be viewed as nonadaptive queries of the form ). The problem is similar to estimating trace when the underlying matrix is positive semidefinite.

All of the above mentioned estimators (with one exception in [RKA13]) use independent identically distributed queries from some special distributions, and the output is a linear combination of the query results. On the other hand, when viewing an estimator as a randomized algorithm, we can choose any distribution over the queries, and the output can be any (possibly randomized) function of the results of the queries. Given the success of the previously mentioned estimators, it is natural to ask whether these extensions are helpful. For example, can we get a significantly better estimator with a non i.i.d. distribution? Can we do better with adaptive queries? Can we do better with a nonlinear combination of the query results?

In this paper, we make progress on answering above questions and understanding the optimal query complexity for randomized trace estimators. Below is an informal summary of our results.

1. Among all the linear nonadaptive trace estimators (which subsumes all the existing trace estimators), we prove that the “random orthogonal vector” estimator is the minimum variance estimator. The distribution on the queries is not i.i.d., and we are unable to find an occurrence of this estimator in the literature regarding trace estimators.

2. We also prove two asymptotically optimal lower bounds for any (possibly adaptive and possibly nonlinear) estimator.

1. We show that every trace estimator requires queries to have a guarantee that the variance of the estimator is at most .

2. We show that every -estimator requires queries.

As a simple corollary, our result also confirms the above mentioned conjecture in [AT11] (as well as the tightness of the analysis of the Rademacher estimator in [RKA13]). Notice our result is a much stronger statement: the original conjectured lower bound is only for an estimator that returns a linear combination of i.i.d. Gaussian queries; we prove the lower bound holds for any estimator. Our lower bound also suggests that adaptiveness as well as nonlinearity will not help asymptotically as all these lower bounds are matched by the nonadaptive Gaussian estimator. On the other hand, our upper bound suggests that the exact minimum variance estimator might not use i.i.d. queries.

### 1.1 Problem Definitions

###### Definition 1 (estimator for the trace)

A trace estimator is a randomized algorithm that, given query access to an oracle for an unknown matrix , makes a sequence of queries to the oracle and receives . The output of the estimator is a real number determined by the queries and the answers to the queries.

###### Definition 2 (nonadaptive linear unbiased trace estimator)

We say a trace estimator is nonadaptive if the distribution of is not dependent on . A trace estimator is linear if we sample from a distribution over queries as well as their weights: , and , and output . In addition, a linear trace estimator is unbiased if

 E\/w1,w2,…,wn,x1,x2,…,xn[n∑i=1wifA(xi)]=trace(A)

Without loss of generality, we can assume that all the queries in a linear estimator are of unit length, where the actual lengths of the queries are absorbed by the weights.

The most natural measure of quality of an estimator is its variance. There is a large body of work on the existence of and finding a minimum variance unbiased estimator. Such an estimator has a strong guarantee; it is the estimator for which the variance is minimized for all possible values of the parameter to estimate. In general, finding such an estimator is quite difficult. It is easy to see that the variance depends on the scale of the matrix. To normalize, we assume that the Frobenius norm of the matrix is fixed.

###### Definition 3

We define the variance of a trace estimator as the worst case of variance over all matrices with Frobenius norm . To be specific, given a matrix  let us define , then

 Var(h)=sup∥A∥2F=1Var(A,h).

If the variance of an estimator is at most , we say that is a -variance estimator.

Given an unbiased estimator class, the minimum variance unbiased estimator has the minimum variance among all the (unbiased) estimators in the class.

Another natural accuracy guarantee for a trace estimator is the notion of -estimator that is introduced in [AT11].

###### Definition 4 ((ϵ,δ)-estimator)

A trace estimator is said to be an -estimator of the trace if, for every matrix , we have that with probability at least .

We stress that both Definitions 3 and 4 involve worst case estimates over the choice of the matrix, and the randomness only comes from the internal randomness of the estimator.

### 1.2 Main Results

Our main results are as follows:

###### Theorem 1.1

Among all linear nonadaptive unbiased trace estimators, the minimum variance unbiased estimator that makes queries is achieved by sampling random orthogonal unit vectors (see Definition 5) and outputting .

###### Theorem 1.2

Any trace estimator with variance requires queries.

###### Theorem 1.3

Any -estimator for the trace requires queries, even if the unknown matrix is known to be positive semidefinite.

The bounds in Theorem 1.2 and 1.3 are tight: both bounds can be asymptotically matched by the Gaussian estimator and the uniform Rademacher vector estimator.

### 1.3 Proof Techniques Overview

All of our results crucially use a powerful yet simple trick, which we call symmetrization. The heart of this trick lies in the fact that the trace of a matrix is unchanged under similarity transformations; for every and orthogonal . If we have a nonadaptive estimator with query distribution and an orthogonal matrix , using the queries distributed as should not be too different in terms of worst-case behavior. (We have to be more careful with adaptive estimators, which we discuss in Section 3.) Thus, applying symmetrization to a nonadaptive estimator yields a nonadaptive estimator where it draws queries as in the original estimator, but transforms the queries using a random orthogonal transformation. This “symmetrizes” the estimator. We prove that the performance of the estimator never decreases when symmetrization is applied, so we can exclusively consider symmetrized estimators.

In order to characterize the minimum variance linear nonadaptive unbiased estimator, we notice that after the symmetrization, the distribution over queries for any such estimator is defined by a distribution over the pairwise angles of the queries. We then show that the queries should be taken to be orthogonal with certainty in order to minimize variance.

As for the lower bounds for adaptive and nonlinear estimators, the symmetrization also plays an important role. Consider the problem of proving a query lower bound for -approximation: the most common approach of proving such a lower bound is to use Yao’s minimax principle. To apply this principle, we would need to construct two distributions of matrices such that the distributions cannot be distinguished after making a number of queries, even though the traces of the matrices are very different in the two distributions. There are several technical difficulties in applying the minimax principle directly here. First of all, the query space is , so it is unclear whether one can assert that there exists a sufficiently generalized minimax principle to handle this case. Second, even if one can apply a suitable version of minimax principle, we do not have general techniques of analyzing the distribution of adaptive queries, especially when the queries involve real numbers and thus the algorithm might have infinitely many branches.

We overcome the above two barriers and avoid using a minimax principle entirely by applying symmetrization. One nice property of the symmetrization process is that a symmetrized estimator outputs the same distribution of results on all matrices with the same diagonalization. In the proof we carefully construct two distributions of matrices with the same diagonalization in each distribution, while the traces are different for different distributions. Each distribution is simply the “orbit” of a single diagonal matrix ; the support consists of all matrices similar to . Using the symmetrization, it suffices to show that we can not distinguish these two distributions of matrices by adaptive queries, as it is equivalent to distinguish two diagonal matrices for symmetrized trace estimators. The argument for achieving a lower bound for adaptive estimators is more subtle; we show that due to the structure of symmetrized estimators, we define a stronger query model such that adaptive estimators behave the same as the nonadaptive estimators while we achieve the same lower bound, even with the stronger query model.

### 1.4 Organization

In section 2, we define the mathematical tools that are needed in our analysis. In section 3, we introduce the idea of symmetrization. We prove Theorem 1.1 in section 4. In section 5, we prove Theorem 1.2. In section 6, we prove Theorem 1.3.

## 2 Preliminaries

###### Definition 5 (random Gaussian matrix and random orthogonal matrix)
• We call a vector a random Gaussian vector if each coordinate is sampled independently from .

• We call an matrix a random Gaussian matrix if its entries are sampled independently from .

• We call an matrix a random orthogonal matrix if it is drawn from the distribution whose probability measure is the Haar measure on the group of orthogonal matrices; specifically, it is the unique probability measure that is invariant under orthogonal transformations.

• We call vectors random orthogonal unit vectors if they are chosen as row vectors of a random orthogonal matrix.

We note that one way to generate a random orthogonal matrix is to generate a random Gaussian matrix and perform Gram-Schmidt orthonormalization on its rows.

###### Definition 6 (total variation distance)

Let be two distributions with density functions over a domain . The total variation distance between and is defined as .

###### Proposition 1

Suppose we are given one sample on either distribution or defined on the same sample space, and we are asked to distinguish which distribution the sample came from. The success probability of any algorithm is at most .

###### Definition 7 (KL-divergence)

Let be two distributions with density functions over a domain . The Kullback-Leibler divergence of from is defined as .

We know the following relationship between Kullback-Leibler divergence and total variation distance, which is also known as Pinsker’s Inequality.

###### Theorem 2.1

Suppose the KL-divergence between distributions is , and total variation distance is , then

 2dTV(P,Q)2≤dKL(P,Q)

To bound the total variation distance of the distributions we consider, we compute the KL-divergence and apply Pinsker’s Inequality. For example, the KL-divergence between two multivariate Gaussian distributions is well known; we will only use the following special case for multivariate Gaussian distributions with mean and covariance matrices and .

###### Theorem 2.2

Given two -dimensional Gaussian distributions and we have that

 dKL(N0,N1)=12(trace(Σ−11Σ0)−n−lndet(Σ0)det(Σ1))

## 3 Symmetrization of an estimator

In this section, we introduce the idea of symmetrization of an estimator which is a crucial element of all our remaining proofs. We first define the rotation of an estimator, which we will denote for an orthogonal matrix . Intuitively, the construction of is such that emulates the behavior of on a rotated version of the matrix . More specifically, makes queries in the following way:

• Letting be a random variable whose distribution is the same as the first query of , the distribution of the first query of is the same as the random variable .

• Given queries made by so far with responses , the distribution of the th query of has the same distribution as , where is distributed the same as the th query that makes, given queries with responses .

In the case that is a nonadaptive estimator, the queries of are just , where is a set of queries from the distribution of queries that makes.

###### Lemma 1

For any estimator and orthogonal matrix ,

• .

• is an -approximation estimator if and only if is also an -estimator.

###### Proof

We know that given a matrix , the behavior of is the same as on estimating . On the other hand, we know that and . Therefore, the variance of on is the same as the variance of on . Now suppose is an -estimator. We know that the approximation guarantee of on is the same as on . Therefore, we know that with probability at least , the estimator ’s output is within

 ((1−ϵ)trace(UTAU),(1+ϵ)trace(UTAU))=((1−ϵ)trace(A),(1+ϵ)trace(A)).
###### Definition 8 (averaging estimators over a distribution)

Suppose we have a collection of estimators , for any probability distribution on , we define as the following estimator:

1. Randomly sample an estimator .

2. Output according to the estimation of .

###### Lemma 2

Averaging a collection of estimators cannot increase variance or weaken an -guarantee. Specifically:

• If all the estimators are unbiased and have variance at most , then ’s variance is also at most .

• If all the estimators in are -estimators, then is also an -estimator.

###### Proof

For the first, we apply the law of total variance conditioned on the draw of :

 Var[hH,P]=E\/h∼P[Var[h]]+Varh∼P[E\/[h]]

The second term above is , since all estimators in are unbiased. Since for every , as well.

For the second claim, assuming that

 Pr\/[h(A)∈((1−ϵ)trace(A),(1+ϵ)trace(A))]≥1−δ

for each , we have

 Pr\/[hH,P(A)∈((1−ϵ)trace(A),(1+ϵ)trace(A))]≥
 infh∈HPr\/[h(A)∈((1−ϵ)trace(A),(1+ϵ)trace(A))]≥1−δ.
###### Definition 9 (Symmetrization of a trace estimator)

Given an estimator , we define the symmetrization of to be the estimator where we

1. sample a random orthogonal matrix (see definition 5), and

2. use to estimate the trace.

We say an estimator is symmetric if it is equivalent to the symmetrization of some estimator.

By Lemma 1 and Lemma 2, we know that ’s variance as well as its -approximation is always no worse than . Therefore, without loss of generality, we can always assume that the optimal estimator is symmetric.

One nice property of the symmetric estimator is that it has the same performance on all matrices with the same diagonalization.

###### Lemma 3

Given a symmetrized estimator , its variance and approximation guarantee is the same for any matrix and for any orthogonal matrix .

###### Proof

Given any matrix , we know that the variance of is and the variance of on the matrix is . We know that and are identically distributed; therefore, has the same estimation variance on and .

Similarly, for the approximation guarantee, suppose is an -estimator, which means that

 E\/U1[Pr\/(h(UT1AU1)∈((1−ϵ)trace(A),(1+ϵ)trace(A)))]≥1−δ.

We know that for the matrix , has the same distribution as . Therefore,

 E\/U1[Pr\/(h(UT1AU1)∈((1−ϵ)trace(A),(1+ϵ)trace(A)))]=E\/U1[Pr\/(h(UT1A′U1)∈((1−ϵ)trace(A′),(1+ϵ)trace(A′)))]

## 4 Optimal Linear Nonadaptive Estimator

Without loss of generality, we can assume that the optimal estimator is symmetric. For a symmetric nonadaptive estimator, we can think of as generated by the following process.

• Sample a configuration from some distribution . For each configuration , there is a corresponding weight vector .

• Generate by drawing random unit vectors conditioned on the angle between being for all . (This can be done efficiently.)

• Output .

The proof of Theorem 1.1 consists of two steps. First we will show that we can set all of the angles (deterministically) to be without increasing the variance, so we can assume that the queries are orthogonal. In the second step, we will then show that the optimal way of assigning weight is to (deterministically) set each weight to be .

We first prove that we can replace the queries by random orthogonal unit vectors without increasing the variance.

###### Lemma 4

Let be randomly orthogonal unit vectors. We have that

 Var(k∑i=1wθifA(yi))≤Var(k∑i=1wθifA(xi)) (1)
###### Proof

It is easy to see that the marginal distribution on each is the same as the marginal distribution on . Therefore, we have that

 E\/θ,y1,…,yk[k∑i=1wθifA(yi)]=E\/x1,…,xk,θ[k∑i=1wθifA(xi)]=trace(A)

This implies that is also an unbiased estimator.

Since both estimators have the same expectation, in order to show (1), it suffices to prove that

 E\/θ,x1,…,xn⎡⎣(k∑i=1wθifA(xi))2⎤⎦≥E\/θ,y1,…,yn⎡⎣(k∑i=1wθifA(yi))2⎤⎦ (2)

By the process of generating , we know that the marginal distribution of is independent of and equal to the marginal distribution of . If we expand the left hand side of (2), we have that

 E\/θ,x1,…,xn⎡⎣(k∑i=1wθifA(xi))2⎤⎦ = k∑i=1E\/θ[(wθi)2]E\/xi[fA(xi)2]+2∑1≤i

If we expand the right hand side of (2) we have that

 E\/θ,y1,…,yn[(k∑i=1wθifA(yi)2)] = k∑i=1E\/θ[(wθi)2]E\/yi[fA(yi)2]+2∑1≤i

Therefore, in order to prove (2), it suffices to prove that for any and , we have

 E\/θ,xi,xj[wθiwθjfA(xi)fA(xj)]≥E\/θ[wθiwθj]E\/yi,yj[fA(yi)fA(yj)] (3)

To compare and , we note that the marginal distribution on the pair is equivalent to drawing from the following process:

1. Draw .

2. Set and .

It is easy to check that the joint distribution on and has the same distribution as two random unit vectors with angle .

Therefore,

 E\/θ,xi,xj[wθiwθjfA(xi)fA(xj)] (4) = E\/θ,yi,yj[wθiwθjyTiAyi(cosθij⋅yi+sinθij⋅yj)TA(cosθij⋅yi+sinθij⋅yj)] = E\/θ[wθiwθjcos2θij]E\/yi[yTiAyi⋅yTiAyi]+E\/θ[wθiwθjsin2θij]E\/yi,yj[yTiAyiyTjAyj] + E\/θ[wθiwθjsinθijcosθij]E\/yi,yj[yTiAyiyTiAyj+yTiAyiyTjAyi]

In order to simplify the above expression, we first claim that

 E\/yi,yj[yTiAyiyTiAyj+yTiAyiyTjAyi]=0.

To see this, note that is a random unit vector orthogonal to . Conditioned on any fixed realization of , the distribution on is symmetric about ; has the same distribution as .

In addition, using Cauchy-Schwarz and the fact that and have the same distribution, we have that

 E\/yi[(yTiAyi)2]=√E\/yi[(yTiAyi)2]E\/yj[(yTjAyj)2]≥E\/yi,yj[yTjAyj⋅yTiAyi].

Therefore, we have that

 (???) ≥ E\/θ[wθiwθjcos2θ]E\/yi,yj[yTjAyj⋅yTiAyi]+E\/θ[wθiwθjsin2θ]E\/yi,yj[yTiAyiyTjAyj] = E\/θ[wθiwθj]⋅E\/yi,yj[yTjAyj⋅yTiAyi]

which proves (3), completing the proof of Lemma 4.

Now that we can assume that the queries are mutually orthogonal, we can view this as an estimator with randomized weights for . Below we will use the random variable to denote as is independent from .

###### Lemma 5

Let be random orthogonal unit vectors. Then the estimator has minimum variance when .

###### Proof

First we must have to make the estimator unbiased, since . Also,

 E\/⎡⎣(k∑i=1wi)2⎤⎦=E\/[k∑i=1w2i]+2⋅E\/⎡⎣∑1≤i

Minimizing the variance is equivalent to minimizing

 E\/w,y⎡⎣(k∑i=1wifA(yi))2⎤⎦ = k∑i=1E\/[fA(yi)2]E\/[w2i]+2⋅∑1≤i

Equality holds for , completing the proof.

Combining Lemma 4 and Lemma 5, the minimum variance linear nonadaptive unbiased estimator making queries is , where is a collection of random orthogonal unit vectors. This completes the proof of Theorem 1.1.

## 5 Every δ-variance estimator requires Ω(1/δ)-queries

###### Theorem 5.1

Any estimator with variance requires queries.

The main idea to show such a lower bound is to reduce the problem from getting a -variance estimator to an easier problem of distinguishing two distributions. Here, the unknown matrix is drawn from either distribution or distribution , and our goal is to determine, with high probability, which distribution the sample came from. Importantly, the trace of every matrix in the support of is far from the trace of every matrix in the support of .

For the problem here, we define and as follows, with parameter precisely specified later :

1. A draw from distribution is the matrix , where are two random orthogonal unit vectors.

2. A draw from distribution is the matrix , where are two random orthogonal unit vectors, for

 C=√(1+2ϵ)2+(2−ϵ)2=√5(1+ϵ2)

It is easy to check that we have . It will be more convenient to write as that

 A2=1√5(1+ϵ2)((1+2ϵ)uuT+(2−ϵ)vvT)=1√5((1+ϵ1)uuT+(2−ϵ2)vvT)

where we have set and . We will also write . For the rest of the proof, we do not explicitly write as an expression of . Instead, our proof only requires that and . It is straightforward to verify that .

The proof of Theorem 5.1 consists of the following two lemmas.

###### Lemma 6

Suppose there is an -variance estimator that makes queries. Then we can distinguish from with probability at least using queries.

###### Lemma 7

Any algorithm that can distinguish from with probability at least requires at least queries.

Combining Lemma 7 and Lemma 6, we have that for any estimator with variance , we need at least queries.

###### Proof

(Proof of Lemma 6). Without loss of generality, let us assume that our estimator is symmetric. By assumption, we have for . The randomness comes from the distribution of as well as the estimator . We use the fact that a symmetric estimator has the same variance on any matrix with the same diagonalization.

Consider the following algorithm for distinguishing and : it uses to first get an estimation on the trace of the unknown matrix . Since every matrix in the support of has trace while every matrix in the support of has trace , the algorithm will output that comes from the distribution if , and otherwise. Below we will show the accuracy of the above algorithm is at least .

We know that is a random variable satisfying , where the randomness is only over the internal randomness of . By Chebyshev’s inequality, we have . Thus, with probability at least , if is drawn from , then , so the algorithm succeeds. Similarly, with probability at least , if is drawn from , then , so the algorithm succeeds in this case as well.

###### Proof

(Proof of Lemma 7) First let us define a general problem.

###### Definition 10 (distinguishing rank 2 matrices)

We are given a matrix that is from one of the following two classes of distributions.

1. Distribution : for and for to be two uniformly random orthogonal unit vectors.

2. Distribution : for and for to be two uniformly random orthogonal unit vectors.

It is easy to see that our goal is to understand the sample complexity of distinguishing from .

Recall that . We will prove the testing problem of distinguishing from requires even with stronger queries. We define a strong query to be a query that, instead of returning , returns and . The vectors and are vectors used to construct from a draw of or in Definition 10. It suffices to show that we need at least strong queries to distinguish from .

One interpretation of the information given by a strong query is that it gives us the projection of on the query point . After making queries , we have the projection of both on


text:
# Embedding a linearly ordered free monoid into a linearly ordered group

A linearly ordered (shortly, l.o.) monoid is a triple $\mathbb M = (M, \cdot, \le)$ for which $(M, \cdot)$ is a (multiplicatively written) monoid and $\le$ is a total order on $M$ such that $xy < xz$ and $yx < zx$ for all $x,y,z \in M$ with $y < z$. In particular, $\mathbb M$ is called an l.o. group if $(M, \cdot)$ is, well, a group, and an l.o. free monoid if $(M, \cdot)$ is the free monoid on an alphabet $X$.

What is known about the following question?

(Q) Let $\mathbb M = (M, \cdot, \le)$ be a linearly ordered free monoid. Does there always exist an embedding of $\mathbb M$ into a linearly ordered group? In more plain words: do there always exist a linearly ordered group $\mathbb G = (G, \cdot, \le)$ and a (monoid) monomorphism $f: (M, \cdot) \to (G, \cdot)$ such that $f(x) < f(y)$ for all $x,y \in M$ with $x < y$?

The answer is affirmative in the case when $\le$ is the lexicographic order induced on $M$ by any well-ordering of the underlying alphabet (this can be proved, e.g., by the "Magnus trick").

But what about the rest? Any reference?

• Any reference for what you call "Magnus trick"? Apr 9, 2014 at 16:01
• As for free groups on finite alphabets, see Section 5 in: D. M. Kim and D. Rolfsen, An Ordering for Groups of Pure Braids and Fibre-type Hyperplane Arrangements, Canad. J. Math. 55 (2002), 822-838 (and the references therein). I don't know if the proof of the general statement: "All free groups are linearly orderable" by the same method (which is as simple or difficult, it is up to you, as the finite case), is explicitly written down somewhere. Does anybody know? Apr 9, 2014 at 17:03
• For the record: An alternative proof that any free group (and hence any free monoid) is linearly orderable can be found in K. Iwasawa, On linearly ordered groups, J. Math. Soc. Japan 1 (1948), 1-9. Yet, Iwasawa's approach doesn't help much with the OP (as far as I can tell). Apr 9, 2014 at 17:37

I suspect this is false, although I don't have a proof. The Thompson group $F$ is generated by $A, B$, which are piecewise-linear homeomorphisms of the interval which change slope at dyadic points, and piecewise have slopes in $2^\mathbb{Z}$. As described in Theorem 4.6 of Cannon-Floyd-Parry, the submonoid generated by $A,B$ is free. The group is linearly ordered (called bi-ordered in the literature), and the spaces of bi-orderings has been classified. I suspect that some of these bi-orderings, when restricted to the submonoid generated by $A, B$, do not extend to the free group generated by $A, B$. I would try one of the 8 isolated bi-orderings of the Thompson group, and see if it can be extended to the free group generated by $A,B$. If it can't, then one can detect this in a ball of finite-radius in the free group.

It suffices to show this for l.o. free monoids on finite alphabets, as follows from the Compactness Theorem in logic - which can be found in any text on First Order Logic. [This principle can be applied to a range of similar problems.]

Indeed, let $\mathbb M = (M, \cdot, \le)$ be a linearly ordered free monoid on the alphabet $X$, and consider the first-order language $\mathcal{L} = (\circ, \preceq, \{x_m|m \in M\})$ consisting of a binary function symbol $\circ$ to represent multiplication, a binary relation symbol $\preceq$ representing ordering, plus an individual constant symbol $x_m$ for each element $m$ of the set $M$.

Then let $T$ be the $\mathcal{L}$-theory having the following axioms:

1. the usual axioms for linearly ordered groups, expressed using $\circ$ and $\preceq$
2. $x_m \ne x_n$ for all $m, n\in M$ with $m\ne n$ [these axioms ensure that $M$ naturally injects as a subset of any model of $T$ via the interpretation of the $x_m$ constants]
3. $x_m \preceq x_n$ for all $m, n\in M$ with $m\le n$ [these make this injection an embedding of l.o. sets]
4. $x_m \circ x_n = x_{m\cdot n}$ for all $m, n\in M$ [which make the embedding a monoid homomorphism].

So any model $\mathbb G = (G, \cdot, \le, \{g_m|m \in M\})$ of $T$ will provide a desired l.o. group, with $m\mapsto g_m$ (being the interpretation of the constant $x_m$ in $\mathbb G$) giving the desired embedding $\mathbb M\to \mathbb G$. And conversely.

By the Compactness Theorem, the theory $T$ admits a model iff every finite subset $\Delta$ of the axioms of $T$ does. Now only finitely many symbols $x_m$ can occur in sentences belonging to such a $\Delta$, and the finitely many elements $m\in M$ so involved can be expressed as words in a finite subalphabet $Y\subseteq X$. This $Y$ generates a l.o. free submonoid $\mathbb S$ of $\mathbb M$ that contains all the $m\in M$ for which $x_m$ figures in statements occurring in $\Delta$. And so any l.o. group that "extends" $\mathbb S$ (in the sense of the OP) will be a model of $\Delta$.

Hence it is enough to consider free l.o. monoids on finite alphabets.

[Incidentally, by the same token, if all finitely generated free groups are linearly orderable, so are all free groups.]

format: plain


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 The Bulletin of Irkutsk State University. Series Mathematics: Year: Volume: Issue: Page: Find

 The Bulletin of Irkutsk State University. Series Mathematics, 2019, Volume 29, Pages 68–85 (Mi iigum385)

Algebraic and logical methods in computer science and artificial intelligence

The completeness criterion for closure operator with the equality predicate branching on the set of multioperations on two-element set

V. I. Panteleev, L. V. Riabets

Irkutsk State University, Irkutsk, Russian Federation

Abstract: Multioperations are operations from a finite set A to set of all subsets of A. The usual composition operator leads to a continuum of closed sets. Therefore, the research of closure operators, which contain composition and other operations becomes necessary. In the paper, the closure of multioperations that can be obtained using the operations of adding dummy variables, identifying variables, composition operator, and operator with the equality predicate branching is studied. We obtain eleven precomplete closed classes of multioperations of rank 2 and prove the completeness criterion. The diagram of inclusions for one of the precomplete class is presented.

Keywords: closure, equality predicate, multioperation, closed set, composition, completeness criterion.

DOI: https://doi.org/10.26516/1997-7670.2019.29.68

Full text: PDF file (446 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.716
MSC: 03B50, 08A99
Language:

Citation: V. I. Panteleev, L. V. Riabets, “The completeness criterion for closure operator with the equality predicate branching on the set of multioperations on two-element set”, The Bulletin of Irkutsk State University. Series Mathematics, 29 (2019), 68–85

Citation in format AMSBIB
\Bibitem{PanRya19} \by V.~I.~Panteleev, L.~V.~Riabets \paper The completeness criterion for closure operator with the equality predicate branching on the set of multioperations on two-element set \jour The Bulletin of Irkutsk State University. Series Mathematics \yr 2019 \vol 29 \pages 68--85 \mathnet{http://mi.mathnet.ru/iigum385} \crossref{https://doi.org/10.26516/1997-7670.2019.29.68} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000486448100007}


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

Exercise 2.4.9. Let $A$ be a matrix representing a system of $m$ equations in $n$ unknowns, and assume that the only solution to $Ax = 0$ is 0. What is the rank of $A$? Explain your answer.

Answer: $Ax$ is a linear combination of the columns of $A$ with the coefficients being the entries of $x$, namely $x_1, x_2, \dotsc, x_n$. If the only time when $Ax = 0$ is when $x$ itself is zero (i.e., the coefficients $x_1, \dotsc, x_n$ are all zero) then all the columns of $A$ are linearly independent. Since the rank $r$ of $A$ is the same as the number of linearly independent columns of $A$ we then have $r = n$.

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

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

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


text:
# wall - brick or block count

Not Reviewed
"brick/block count" =
Tags:
Rating
ID
KurtHeckman.wall - brick or block count
UUID
e6d06f9c-da27-11e2-8e97-bc764e04d25f

The Brick or Block Wall calculator computes the number of standard U.S. bricks or blocks are needed for a wall.  To calculate the brick/block count using European brick and block sizes, CLICK HERE.                    MASONRY WALL

INSTRUCTIONS:   Choose units and enter the following:

• (l) Length of the wall
• (h) Height of the wall
• (bs) Brick or Block Size.  Choose a standard brick or block size via the pull-down menu.
• (M) Choose whether to add margin to the count estimate (see Note1).

Brick or Block in a Wall:  The calculator returns the number of brick or block needed for the wall.

Note1: Choosing to add margin (M) assumes that partial bricks or blocks remaining in a given row are discarded..  Other wise, the algorithm assumes all fractional bricks and blocks are used.  The default is YES, because it is better to have a few too many bricks or blocks on the site than waist time waiting for more to come.

# Definition

This equation calculates the number of brick or block needed for a wall based on the dimensions of the wall and the size of the brick or block.  This calculation is for a block wall or brick fascia wall which implies that wall is one unit (brick or block) deep.   The user identifies the height and length of the wall and chooses the brick or block from the pull down list. vCalc will then calculate the number of selected brick or block needed for the wall.  The graphic shows a straight wall.  However, the length can be provided for a circular or other-wised curved or serpentine wall, and the calculation should be accurate.

To do this, vCalc calculates the area of a wall and then uses the standard dimensions of bricks or blocks to determine how many bricks or blocks are needed for the construction of the wall.  This is an ESTIMATION, and actual number of bricks or blocks needed may vary based on the thickness of the mortar joints and other factors.  Nonetheless, this formula does take into account a nominal mortar joint.  The ADD MARGIN option is a more conservative method.  While one ideally would like to precisely pre-order and purchase the exact amount, it is better to have a small excess of materials that can be returned after the job, than to halt construction in order to acquire additional materials.  This latter case is both frustrating and costly.

Brick and block unit sizes include: brick(standard), brick(paver), block(4x16), block(4x18), block(5x18), block(8x8), block(8x12), block(8x16), block(8x18), block(8x24).  These are chosen because they are the most commonly used.  Brick and block unit sizes includes the most commonly used brick and block sizes in the United States.  For a calculator that allows you to enter any brick or block size and a mortar joint, CLICK HERE.

# Use

Brick and block walls are used in many applications, ancient to modern.  They can be found in homes, building, and gardens.  They can also be seen in general landscaping as retention walls.


text:
# $f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$

Where:

1. $n,k$ are natural numbers and $k\le n$.
2. $t$ is taken over all integers between $0$ and $k$ such that $t$ is equivalent to $a$ modulo a prime $p$.
3. $x$ is a natural number between $0$ and $n$.

So the function is determined by the parameters $n,k,p,a$. I'm particularly interested in the case $p=3$ and $a=0$ (but also $a=1$ is relevant).

My main question is - is there a way to characterize (instead of simply computing) for which values of $x$ (given $n,k,p,a$) the values of $f(x)$ will be odd numbers?

The first step seems to be answering the question of when ${\alpha \choose \beta}$ is odd and when it is even. This question was asked here and received a beautiful solution; however, I fail to see a way in which to apply that solution to "my" function.

-
Perhaps Lucas's theorem [en.wikipedia.org/wiki/Lucas%27_theorem] helps. – Blackbird Jul 14 at 11:33


text:
# How to physically make sense of these generalized measurements?

In Quantum Mechanics one often by postulate has that the system is described by a Hilbert space $\mathscr{H}$ and observables are described by hermitian operators $A\in \mathfrak{A}(\mathscr{H})$ on the corresponding algebra. The possible values to be measured are the ones in the spectrum $\sigma(A)$ and we work with generalized eigenstates, so that for each $a\in \sigma(A)$ we have $|a\rangle$ the state with definite value for $A$ equal to $a$, which we assume normalized conveniently.

We can thus define projectors

$$\pi_a =|a\rangle\langle a|,$$

and we have:

$$\int_{\sigma(A)}\pi_a da=\int_{\sigma(A)}|a\rangle\langle a|da=\mathbf{1}$$

and they are also orthogonal, in the sense that $$\pi_a\pi_b=\delta_{ab}|a\rangle \langle b|.$$

Now, in the paper A Mini-Introduction To Information Theory by Witten, he turns this around. Working in the discrete and finite case for simplicity, he actually says that if we pick any collection $\pi_a$ of hermitian operators satisfying:

$$\sum_{a=1}^k \pi_a=\mathbf{1},\quad \pi_a^2=\pi_a,\quad \pi_a \pi_{a'}=0, \ a\neq a'$$

they determine a projective measurement.

Now, these are just abstract mathematical operators. How do they correspond to physical measurement?

I mean, take position. We know how to measure position. One puts detectors around, and when a particle is detected somewhere position has been measured. The same goes for momentum, energy, and so all.

In these cases, we have a physical measurement in mind, we create one abstract operator out of it. And when we say "after a measurement in position yielding $x$ the state is $|x\rangle$" we know what we are saying physically.

This is the opposite. We pick abstract operators first and want them to correspond to measurement.

So how to physically understand such a measurement, when it seems like a purely mathematicaly abstract concept? How does one actually "measure" what corresponds to $\pi_a$?

• The direction from a given experiment to the related operator is far from trivial. But here, if you ask for the other way around, I think we are lost. Of course, on a formal level, one can consider all self-adjoint operators as describing "some" ideal measurement, but how to actually build it may be impossible to find out. – Luke Jul 11 '18 at 9:43

A Hermitian operator $\pi$ satisfying $\pi^2 = 1$ is still an orthogonal projector, so this is not too exotic. The reason why Witten writes it this way is that it allows, for example, to measure:

Is my particle inside the interval $[0,1]$ or outside of it?

In that case $k=2$, $\pi_1 = \int_0^1 |x \rangle \langle x |\, \mathrm dx$ and $\pi_2 = 1 - \pi_1$.

Now, you were asking "given some projectors satisfying the conditions, what observable are we actually measuring"? Well, you have to find a Hermitian operator so that sums of its eigenspaces correspond to the projectors. That still leaves open the question what physical quantity actually corresponds to the Hermitian operator, but that question is also open in the postulates you are familiar with ;)

Finally note that "generalized measurement" usually means something more general than what you quoted. We want to describe also weak measurements and more. For that, there is the framework of generalized measurements where the $\pi$ are not required to be projectors (neither hermitianity nor idempotence is required), only that $\sum \pi^\ast \pi = 1$.

Note that if the projection operators $\pi_{\alpha}$ in question satisfy the postulates above that constitute the definition of an orthogonal projective measurement according to Witten, it is easy to prove that the operators $\pi^{'}_{\alpha}=U\pi_{\alpha}U^{\dagger}$ also constitute a projective measurement. Thus those properties alone do not define a particular set of observables on which we perform measurements, but rather the entirety of operators that perform a projection on a particular orthogonal basis (operators of the form $| \alpha\rangle\langle\alpha|$ with the states $|\alpha \rangle$ belonging to an orthonormal basis).

Witten references in his paper the E type of generalized measurement with the property $\sum_{s}E^{\dagger}_s E_{s}=1$ and now this equation is satisfied by any operators of the form $\pi_{\alpha\beta}=|\alpha\rangle\langle\beta|$, where now the states $|\alpha \rangle$ have to be part of a complete basis but no longer orthonormal or even orthogonal.

What would conclude this proof nicely, is a proof that these are the only types of operators that satisfy the above relations, but I couldn't think of a quick way to prove it.


text:
# Probability of Largest Sample Observation

Let $X_1, X_2, X_3$ be three random variable following a normal distribution $N(6,4)$. What is the probability that the largest observation exceeds 8? Hint: $Y = \max(X_1, X_2, X_3)$.

Here is what I tried:

$P(Y\leq y) = P(X_i\leq y)$ for $i=1,2,3$. Then $$P(Y\leq y) = P(X_1 \leq y)*P(X_2 \leq y) * P(X_3 \leq y).$$ To get $P(X_ i \leq y)$, I use the $P(X > 8) = 1 - P(X < 8) = 1 - 0.841 = 0.159$. Then I plug in $0.159$ to the previous equation: $P(X_1 \leq y) * P(X_2 \leq y) *P(X_3 \leq y)$, so that $(0.159)(0.159)(0.159) = 0.0040$.

However, my teacher said this is wrong.

-
You should try to tell us what you've tried so far and where you get stuck. (In other words, we're not going to simply do your homework for you.) –  Patrick Coulombe Mar 23 at 6:38
what I did was: Pr(Y< or = y) = Pr(Xi< or = y, i=1,2,3). Then Pr(Y< or = y) = Pr(X1< or =y)xPr(X2< or =y)xPr(X3< or =y). To get the Pr(Xi< or = y), I use the Pr(x>8)=1-Pr(x<8)=1-0.841=0.159. Then I plug-in 0.159 to the previous equation: Pr(X1< or =y)xPr(X2< or =y)xPr(X3< or =y), so that (0.159)(0.159)(0.159) = 0.0040. My teacher said it it wrong. :( –  user42404 Mar 23 at 7:37
Wow, thanks for the edited version. –  user42404 Mar 23 at 8:01

There is just a small mistake in the development provided in the question. The mistake comes from the fact that $$P(Y > y) \neq P(X_1 > y) \cdot P(X_2 > y) \cdot P(X_3 > y) .$$ Here is a way to solve the problem. Since $P(Y > y) = 1 - P(Y \leq y)$, and assuming the mutual independence of $X_1, X_2, X_3$ \begin{align*} P(Y \leq y) &= P\left\{\max(X_1, X_2, X_3) \leq y \right\} \\ &= P(X_1 \leq y) \cdot P(X_2 \leq y) \cdot P(X_3 \leq y) \\ &= P(X_1 \leq y)^3, \end{align*} then the requested probability is $P(Y > y) = 1 - P(X_1 \leq y)^3$.

The numerical result is $P(Y > 8) = 1 - P(X_1 \leq 8)^3 = 1 - 0.8413^3 \approx 0.4044$

-
I assumed that $X_i \sim N(6, 4)$ meant ${\rm var}(X_i) = 4$ and used pnorm(8, 6, 2) in R. –  QuantIbex Mar 23 at 10:19
Thanks! It took me days and still can't figure it out what to do about it. Anyways, again thanks. –  user42404 Mar 23 at 11:06

I got to the following, please let me know if there is anything wrong.

Assume that $\mu=6$ and $\sigma=4$, then we have $P(X_i \geq 8)= 0.3085$ for an arbitrary $i$, i.e. $i=1,2,3$. Thus the probability that we get a number higher than 8 from an observation drawn from a sample $X_{i}$ is $0.3085$, so the probability that there is at least one observation from our sample $X_{i}$ that is larger than $8$ is equal to $P(K\geq1)=1-P(K=0)$, where $K$ is equal to the number of observations larger than 8, thus $P(K\geq1)=1-{{3}\choose{0}}\cdot 0.6915^3$, which is about $0.66934$. Well, this holds for an arbitrary $i$.

Now we would like to know what the probability is that one of these samples have an observation higher than 8. The probability that one sample has an observation higher than 8 is equal to $0.66934$. This can be done with a binomial distribution, so $P(L\geq 1)$, where $L$ stands for the number of $X_{i}$'s that have an observation larger than 8. $P(L\geq 1)=1-P(L=0)$. I get a probability of about 0.97.

Not sure whether I have made a mistake, hopefully it is helpful.

-
Thanks for your help. Actually the answer is 0.405, I just don't know how to arrive to such answer. It seems just a simple normal distribution problem to me, but the Y=max(X1, X2, X3) makes life complicated. How did you get to the P(Xi≥8)=0.3085? –  user42404 Mar 23 at 8:59


text:
# Three Of A Kind Poker

Veröffentlicht

Reviewed by:
Rating:
5
On 16.03.2020

### Summary:

Einen Video Slots Bonus ohne Einzahlung in Anspruch nimmt.

There are 10 different hands ranks in Texas Hold'em – from a Royal Flush to a Straight to a lousy High Card. Here's a comprehensive list of all. Der bestmögliche Straight Flush ist der Royal Flush aus As, König, Dame, Bube und 10 in derselben Farbe. Dieses Blatt ist unschlagbar. Four of a Kind: Vier. Three of a Kind am Pokertisch, was ist das eigentlich? Wir erklären die Pokerbegriffe im Großen Online Poker Glossar.

## Three of a Kind - Poker Glossar

There are 10 different hands ranks in Texas Hold'em – from a Royal Flush to a Straight to a lousy High Card. Here's a comprehensive list of all. Je höher der Straight Flush, desto besser. Four of a kind – eine weitere Hand, mit der man nur schwer verliert! Wenn du vier Karten mit demselben Wert hast, zum. Three of a Kind am Pokertisch, was ist das eigentlich? Wir erklären die Pokerbegriffe im Großen Online Poker Glossar.

## Three Of A Kind Poker {dialog-heading} Video

Insane Poker Hand - Straight vs Flush vs Quads

Category Commons Outline. Main page Freezell Kostenlos Current events Random article About Wikipedia Contact us Donate. The best Two Pair Hand is made up of Aces and Kings, with a Queen kicker fifth card. Three of a Kind can also beat another Three of a Kind hand with a lower ranking. Poker: PokerStars Poker Real Money UK NZ Canada Canadien India Mobile iPhone Android Paypal Hands Odds Casinos Gambling. Question feed. Three Champions League Гјbertragung Mittwoch represent the strongest Three of a Kind poker hand. Since both players have the same rank of three of a kind Track Greyhound the above Wetter Heute Ulm, the winner will be determined by the Singapore Casino Hotel. Rolled Up in Schnaps Roulette - Poker Terms. If it becomes clear that the other players in the hand have very little, then you have some room to maneuver where you can exercise a little bit of bullying. The denomination of the cards also determines the rank of the combination. Viewed 96 times. If we have top trips, we might find Haunstetter Hof Augsburg up against the full-house made with a pocket-pair. Online GamblingAustralia GamblingCanada GamblingUK GamblingNZ Gambling UK Sports BettingAustralia Sports BettingCanada Sports BettingDeutsche SportwettenIreland Sports BettingNew Zealand Sports BettingSouth Africa Sports BettingBetStars. This is the Der5 that I don't quite understand. Although it Werder Gegen Chelsea not one of the best winning poker hands, Three of a Kind can definitely get you the pot in some situations.

It is under a Straight and above Two Pairs. The hand can also be ranked based on the denomination of the three matching cards in case two or more players have Three of a Kind in the same round.

Three Aces represent the strongest Three of a Kind poker hand. There are some definitions involving Three of a Kind in Texas Hold'em.

If the combination is made with a pocket pair and one community card, it is called a "set". If the player only uses one hole card and two community cards , the hand is known as "trips".

This is the perfect instance where you will want to start a hand on the front foot. An early raise will ensure you do your best to eliminate any low value cards that could form a stronger combination later in the hand.

If it becomes clear that the other players in the hand have very little, then you have some room to maneuver where you can exercise a little bit of bullying.

Be careful though! We calculated the poker hand odds and probability of getting Three of a Kind while playing Texas Hold'em. These figures are based on having five available cards — your two hole cards and three community cards.

The odds of being dealt Three of a Kind on the flop is only the tip of the iceberg. To view a wider range of odds and probabilities of being dealt different hands then check out our very own poker odds calculator.

A Three of a Kind hand in poker refers to a combination of five cards where three of them have the same denomination, also known as rank.

The remaining two cards are of different ranks. A hand of A-J is Three of a Kind. A Straight beats Three of a Kind and of course, so do the higher-ranking poker hands , such as Flush, Full House, Four of a Kind, and Straight Flush.

Three of a Kind can beat Two Pairs, One Pair, or a High Card. Three of a Kind can also beat another Three of a Kind hand with a lower ranking. Both players technically hold three of a kind Tens with an Ace kicker.

This leaves us room to incorporate a second kicker as the tie-breaker. Hand 1 is trip Tens with Ace Queen kickers while hand 2 is trip Tens with Ace King kickers.

Hand 2 hence wins the pot since the second kicker is stronger. Trips is where we only use one of our hole-cards when formulating the three-of-a-kind component of the hand.

A set is where we formulate our three of a kind using a pocket pair in the hole. If we have top trips, we might find ourselves up against the full-house made with a pocket-pair.

In many cases, sets are strong enough for us to be happy about committing postflop when playing in bb cash games. There are exceptions however, especially on board textures where straights and flushes are possible.

Trips needs to be treated with a little more caution, and whether we commit the stacks or not will usually be dependent on whether we have a decent kicker.

Caution is especially advised with bottom and middle set, since they often get novice PLO players into a lot of difficult. These hands are often not strong enough to stack off with for bb, especially assuming no relevant redraws.

Top Menu. How to play. Download Now. Category Menu. What is Three of a kind in Poker? Three of a Kind is made when we hold three cards of identical rank.

This leaves room for two kickers in regular poker variants that use 5-card hands. Three of a Kind beats two-pair but loses to a straight.

Ciao Winter Bash ! Featured on Meta. New Feature: Table Support.

### Solche einarmigen Banditen genauso funktionieren, dass Three Of A Kind Poker absolut Three Of A Kind Poker echtes Geld gewinnen kann. - Navigationsmenü

Anleitung Ein- und Auszahlungen Spielregeln Mobile Poker Hilfe. On this page you will find the solution to Poker slang for three of a kind crossword clue crossword clue. This clue was last seen on December 24 on New York Times’s Crossword. If you have any other question or need extra help, please feel free to contact us or use the search box/calendar for any clue. Probability of getting 3 of a kind in a 5 card poker hand using combinations. Ask Question Asked 2 months ago. Active 2 after you chose the $3$ numbers, you must also choose which of the three is the one in the 3-of-a-kind. There are $\dbinom31=3$ choices for that. Incidentally: 3\binom {13}3 =\frac {3\times13!}{10!3!} = 13 \times \frac. Three-of-a-kind is made by holding three of the same-ranking card in a five-card hand. An example of a three-of-a-kind hand would be: The above hand qualifies as three-of-a-kind aces. Note that if the latter two cards are paired (like A ♥ A♠ A♣ 2♣ 2 ♥), the hand qualifies as a full house. Three of a Kind is made when we hold three cards of identical rank. The strength of our three of a kind is determined by it’s rank value where Aces are high. This leaves room for two kickers in regular poker variants that use 5-card hands. Three of a Kind beats two-pair but loses to a straight. Please find below all Poker slang for three of a kind crossword clue answers and solutions for the daily New York Times Crossword Puzzle. Since you have landed on our site then most probably you are looking for the solution of Poker slang for three of a kind. Three cards of the same number or face value ("trips"). Live Events 1 Home Strategy Poker Terms Three of a Kind. Three of a Kind. Three cards of the same number or face value ("trips"). What does Three of a Kind look like? A♠, A♣, A♦, J♥, 4♣. Q♥, Q♦, Q♠, A♦, 8♦. 9♣, 9♠, 9♥, K♥, 7♣. 2♦, 2♣, 2♠, J♥, 10♠. Der bestmögliche Straight Flush ist der Royal Flush aus As, König, Dame, Bube und 10 in derselben Farbe. Dieses Blatt ist unschlagbar. Four of a Kind: Vier. Ein Royal Flush, wie z. B. A♧ K♧ Q♧ J♧ 10♧, ist ein Straight Flush mit dem Ass als höchster Karte, somit also der höchste. Da Asse vom Rang her höher sind als Buben, gewinnt im genannten Beispiel Spieler 1. Pokerhände Royal Flush Straight Flush 4 of a Kind Full House Flush. Three of a Kind. Drilling. Pokerseiten. Spiele Poker auf bWin Poker. bWin Poker bietet Dir € unabhängig vom Einzahlungsbetrag. Download. Bewertung. Dann wird die Anzahl der Kombinationen, die Tv.Dfb Straight Flush bilden würden, wodurch eine ranghöhere Hand entstehen würde abgezogen. August Da das Blatt vier gleichfarbige Karten enthält, werden drei ignoriert und es entsteht ein Ein-Karten-Blatt, das nur Filmon Bbc1 der Drei besteht.

#### 2 Gedanken zu „Three Of A Kind Poker“

1. Samushakar sagt:

Ich denke, dass Sie nicht recht sind. Es ich kann beweisen. Schreiben Sie mir in PM, wir werden umgehen.

2. Zulushicage sagt:

Es ist die einfach bemerkenswerte Antwort


text:
# Vapor Pressure Lowering

The vapor pressure of a solvent in a solution is always lower than the vapor pressure of the pure solvent. The vapor pressure lowering is directly proportional to the mole fraction of the solute.

$P_{solvent} = X_{solvent} P^o_{solvent}$

or

$\Delta P = X_{solute} P^o_{solvent}$

where Psolvent  is the vapor pressure of the solvent on the solution, $$X_{solvent}$$ and $$X_{solute}$$ is the mole fraction of the solvent or solute, respectively. (Xsolvent + Xsolute = 1). Posolvent is the vapor pressure of the pure solvent, and $$\Delta P$$ is amplitude of the vapor pressure lowering .

Exercise

At 25oC the vapor pressure of pure benzene is 93.9 torr. When a non-volatile solvent is dissolved in benzene, the vapor pressure of benzene is lowered to 91.5 torr. What is the concentration of the solute and the solvent, expressed in mole fraction?

Vapor pressure lowering $$\Delta P= 2.4\; torr$$ with $$X_{solute} = 0.026$$.


text:
•

• <tt id="a6oys"></tt>
• Paul's Online Notes
Home / Calculus II / Parametric Equations and Polar Coordinates / Arc Length with Polar Coordinates
Show General Notice Show Mobile Notice Show All Notes Hide All Notes
General Notice

I apologize for the outage on the site yesterday and today. Lamar University is in Beaumont Texas and Hurricane Laura came through here and caused a brief power outage at Lamar. Things should be up and running at this point and (hopefully) will stay that way, at least until the next hurricane comes through here which seems to happen about once every 10-15 years. Note that I wouldn't be too suprised if there are brief outages over the next couple of days as they work to get everything back up and running properly. I apologize for the inconvienence.

Paul
August 27, 2020

Mobile Notice
You appear to be on a device with a "narrow" screen width (i.e. you are probably on a mobile phone). Due to the nature of the mathematics on this site it is best views in landscape mode. If your device is not in landscape mode many of the equations will run off the side of your device (should be able to scroll to see them) and some of the menu items will be cut off due to the narrow screen width.

### Section 3-9 : Arc Length with Polar Coordinates

We now need to move into the Calculus II applications of integrals and how we do them in terms of polar coordinates. In this section we’ll look at the arc length of the curve given by,

$r = f\left( \theta \right)\hspace{0.5in}\alpha \le \theta \le \beta$

where we also assume that the curve is traced out exactly once. Just as we did with the tangent lines in polar coordinates we’ll first write the curve in terms of a set of parametric equations,

\begin{align*}x & = r\cos \theta & \hspace{0.75in} y & = r\sin \theta \\ & = f\left( \theta \right)\cos \theta & \hspace{0.75in} & = f\left( \theta \right)\sin \theta \end{align*}

and we can now use the parametric formula for finding the arc length.

We’ll need the following derivatives for these computations.

\begin{align*}\frac{{dx}}{{d\theta }} & = f'\left( \theta \right)\cos \theta - f\left( \theta \right)\sin \theta & \hspace{0.75in}\frac{{dy}}{{d\theta }} & = f'\left( \theta \right)\sin \theta + f\left( \theta \right)\cos \theta \\ & = \frac{{dr}}{{d\theta }}\cos \theta - r\sin \theta & \hspace{0.75in}& = \frac{{dr}}{{d\theta }}\sin \theta + r\cos \theta \end{align*}

We’ll need the following for our $$ds$$.

\begin{align*}{\left( {\frac{{dx}}{{d\theta }}} \right)^2} + {\left( {\frac{{dy}}{{d\theta }}} \right)^2} & = {\left( {\frac{{dr}}{{d\theta }}\cos \theta - r\sin \theta } \right)^2} + {\left( {\frac{{dr}}{{d\theta }}\sin \theta + r\cos \theta } \right)^2}\\ & = {\left( {\frac{{dr}}{{d\theta }}} \right)^2}{\cos ^2}\theta - 2r\frac{{dr}}{{d\theta }}\cos \theta \sin \theta + {r^2}{\sin ^2}\theta \\ & \hspace{0.75in} + {\left( {\frac{{dr}}{{d\theta }}} \right)^2}{\sin ^2}\theta + 2r\frac{{dr}}{{d\theta }}\cos \theta \sin \theta + {r^2}{\cos ^2}\theta \\ & = {\left( {\frac{{dr}}{{d\theta }}} \right)^2}\left( {{{\cos }^2}\theta + {{\sin }^2}\theta } \right) + {r^2}\left( {{{\cos }^2}\theta + {{\sin }^2}\theta } \right)\\ & = {r^2} + {\left( {\frac{{dr}}{{d\theta }}} \right)^2}\end{align*}

The arc length formula for polar coordinates is then,

$L = \int{{ds}}$

where,

$ds = \sqrt {{r^2} + {{\left( {\frac{{dr}}{{d\theta }}} \right)}^2}} \,d\theta$

Let’s work a quick example of this.

Example 1 Determine the length of $$r = \theta$$ $$0 \le \theta \le 1$$.
Show Solution

Okay, let’s just jump straight into the formula since this is a fairly simple function.

$L = \int_{{\,0}}^{{\,1}}{{\sqrt {{\theta ^2} + 1} \,d\theta }}$

We’ll need to use a trig substitution here.

$\theta = \tan x\hspace{0.5in}d\theta = {\sec ^2}x\,dx$ \begin{align*}\theta & = 0\hspace{0.5in}0 = \tan x\hspace{0.5in}x = 0\\ \theta & = 1\hspace{0.5in}1 = \tan x\hspace{0.5in}x = \frac{\pi }{4}\end{align*} $\sqrt {{\theta ^2} + 1} = \sqrt {{{\tan }^2}x + 1} = \sqrt {{{\sec }^2}x} = \left| {\sec x} \right| = \sec x$

The arc length is then,

\begin{align*}L * = \int_{{\,0}}^{{\,1}}{{\sqrt {{\theta ^2} + 1} \,d\theta }}\\ & = \int_{{\,0}}^{{\,\frac{\pi }{4}}}{{{{\sec }^3}x\,dx}}\\ & = \left. {\frac{1}{2}\left( {\sec x\tan x + \ln \left| {\sec x + \tan x} \right|} \right)} \right|_0^{\frac{\pi }{4}}\\ & = \frac{1}{2}\left( {\sqrt 2 + \ln \left( {1 + \sqrt 2 } \right)} \right)\end{align*}

Just as an aside before we leave this chapter. The polar equation $$r = \theta$$ is the equation of a spiral. Here is a quick sketch of $$r = \theta$$ for $$0 \le \theta \le 4\pi$$.

亚洲欧美中文日韩视频 - 视频 - 在线观看 - 影视资讯 - av网 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>


text:
## Elementary Statistics: A Step-by-Step Approach with Formula Card 9th Edition

b. $r^{2}$
The coefficient of determination is $r^{2}$


text:
• ## C6X Series Jaw Crusher

C6X Jaw Crusher is new equipment used for crushing hard or abrasiveness stones. It is possess of detachable frame without welding structure, double wedge adjusting device, elastic limit damping device and integrated motor seat, which will make C6X Series Jaw Crusher popular in the market.

• ## HPT Hydraulic Cone Crusher

HPT Series High-Efficiency Hydraulic Cone Crusher combines crushing stroke with crushing chamber perfectly, which makes capacity improved and efficiency increased. Besides, hydraulic lubrication control system helps bearing of hydraulic cone crusher get double protection.

• ## VSI6X Series Vertical Crusher

Based on more than 30 years of experiences, VSI6X Series Vertical Shaft Impact Crusher carrying many patents amazes the market greatly. This machine is possess of four openings impeller, special sealing structure and sealed cartridge bearing structure, which makes production convenient and efficient.

# measures to control illegal mining

### How to control illegal mining GhanaWeb

Jul 06, 2014· How to control illegal mining then it is probably time to try other measures to bring to an end to this unfortunate situation. The fast rate at which illegal mining is causing harm to theHow To Control Illegal Mining Modern Ghana,How To Control Illegal Mining. By Bruce Misbahu Bulmuo (illegal mining) to our sources of food and water. If interventions used in the past to address this problem has proved futile, then it is probably time to try other measures to bring to an end to this unfortunate situation.Illegal mining: the problem and possible solutions,May 24, 2016· Illegal mining is particularly prevalent where there has been a failure to take adequate measures to close a mine. However, illegal mining also occurs in unused mines for which closure measures have been taken. Illegal miners will go to great lengths to circumvent efforts to prevent access to unused mines, such as using dynamite to blast

### Illegal mining: Control influx of non-indigenes, says

Dec 26, 2020· Illegal mining: Control influx of non-indigenes, says monarch. Published December 27, 2020 December 27, 2020. Kindly Share This Story. Owa-Obokun of measures to control illegal mining,How To Control Illegal Mining Modern Ghana. Jul 05, 2014 How To Control Illegal Mining. If interventions used in the past to address this problem has proved futile, then it is probably time to try other measures to bring to an end to this unfortunate situation. A greater majority of people engaged in illegal mining are the youth.Steps Taken to Curb Illegal Mining and Theft in Various,Such steps include: (i) Rat holes created by illegal mining are being dozed off and filled up with stone and debris wherever possible. (ii) Concrete walls have been erected on the mouth of the abandoned mines to prevent access and illegal activities in these areas.

### How to stop illegal sand mining iPleaders

Sand is a mineral as defined under Section 3 (e) of Mines and Minerals Development and Regulation Act, 1957 (MMDR Act). This act empowers government and state to make any laws to prevent illegal mining. Sand mining is a practice that is used to extract sand, mainly through open pit.measures to control illegal mining,How To Control Illegal Mining Modern Ghana. How To Control Illegal Mining. If interventions used in the past to address this problem has proved futile, then it is probably time to try other measures to bring to an end to this unfortunate situation. A greater majority of people engaged in illegal mining Galamsey menace: Causes, effects and solutions,May 17, 2017· The high incidence of "galamsey" or illegal mining in recent times, have been on several discussions and heated debates for some time now and has perplexed the

### Steps Taken to Curb Illegal Mining and Theft in Various

Suitable steps are being taken to curb Illegal mining of coal. Such steps include: (i) Rat holes created by illegal mining are being dozed off and filled up with stone and debris wherever possible. (ii) Concrete walls have been erected on the mouth of the abandoned mines to prevent access and illegal Illegal mining: the problem and possible solutions,May 24, 2016· Illegal mining is particularly prevalent where there has been a failure to take adequate measures to close a mine. However, illegal mining also occurs in unused mines for which closure measures have been taken. Illegal miners will go to great lengths to circumvent efforts to prevent access to unused mines, such as using dynamite to blast(DOC) PREVENTION OF ILLEGAL MINING ACTIVITIES FOR,The Issues of mining are in the wake because of the increasing demands for mineral products and diminishing nature of such minerals in the Europe. This had become an opportunity for developing countries in Africa which have mineral deposits comes

### How to stop illegal sand mining iPleaders

Sand mining is a practice that is used to extract sand, mainly through open pit. This demand is exalting at alarming rates a result of ever increasing building construction projects and other infrastructural development. In the view of high demand there is illegal means for sand extraction.Illegal mining: Control influx of non-indigenes, says,Dec 26, 2020· Illegal mining: Control influx of non-indigenes, says monarch. Published December 27, 2020 December 27, 2020. Kindly Share This Story. Owa-Obokun of Mining health and safety: 7 common risks to protect,Mar 06, 2020· Even though measures to prevent black lung have been legally enforced for many years now, new cases still occur among coal miners. Mining companies need to develop a dust control plan, and supervisors should ensure that dust control systems are working properly for every production shift.

### National and international policies to control illegal

violating the law (e.g., timber mining, tax evasion, harvesting protected species or in unauthorized areas) exceed the costs of non-compliance. In large part, the policy options that are listed in the report consist of measures that reduce the economic rewards from illegal behavior, either by increasing the rewards of compliance, or byMP govt to control illegal sand mining, new policy to come,Aug 30, 2019· Up Next. MP govt to control illegal sand mining, new policy to come in two months, says CM Kamal Nath; State govt will take up the cause of people left out in the NRC list: Assam CMLAND DEGRADATION DUE TO MINING AND ITS REMEDIAL ,Land Degradation due to Mining in India and its Mitigation Measures Dr H. B. Sahu Department of Mining Engineering National Institute of Technology Rourkela 769 008, India [email protected] Er. S. Dash State Pollution Control Board Orissa Bhubaneswar 751 012, India [email protected] Abstract- The impact of mining activities on


text:
SERVING THE QUANTITATIVE FINANCE COMMUNITY

Cuchulainn
Topic Author
Posts: 61518
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Simple Compounding, why?

Take a 1-period (length dt) approximation to exp(-r dt), i.e. the popular1 / (1 + r dt)Questions:1. Why this? Is there a financial reasoning or is it just numerical convenience?2. If we had a more accurate and more stable approximation, is that 'financially acceptable'?3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Simple Compounding, why?

Isn't it just historical path dependency? Given principal, rate, and time (P, r, dt), the simplest formula for interest to be paid on an account is P*r*dt which is then added to P. When I was little, we got monthly compounding of simple interest and we were darn glad of it, too! Then, in school, we learned that the exponential form was almost magical mathematical formula that results from getting interest-on-the-interest-on-the-interest-on-the-... and it seemed almost sneaky or subversive. P.S. I'd avoid division and more complicated maths!

Cuchulainn
Topic Author
Posts: 61518
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Simple Compounding, why?

No.Both forms are simple rational functions. So, what is the compelling rationale (e.g. convention, QED), then fair enough. BTW these rational functions are in a yield curve fitting routine. For zero coupon bond.
Last edited by Cuchulainn on December 9th, 2013, 11:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Simple Compounding, why?

QuoteOriginally posted by: CuchulainnBoth forms are simple rational functions. So, what is the compelling rationale (e.g. convention, QED), then fair enough.I'm not joking about division. Moreover, the simpler method can be done on a four-function calculator (no stack or memory) and the other cannot. In a pre-computer, pre-numerate environment, only addition and multiplication were possible (and even the multiplication might be handled by an interest rate table).That's not to say a better approximation won't be appreciated. It's just a rational explanation for why rational functions weren't acceptable historically.What about Taylor series? I think we have a plain English explanation of it somewhere here.

DavidJN
Posts: 1746
Joined: July 14th, 2002, 3:00 am

### Simple Compounding, why?

The simple (i.e. non-compounded) method is not an approximation, it is an economically equivalent convention that is used in the marketplace for many financial instruments with maturities under one year. You would not use the same numerical value for the interest rate in both equations. Changing your notation ever so slightly, denote rs the simple rate and rc the continuous compound rate.1/(1 + rs dt) = exp(-rc dt)If you know one of the two rates you can solve for the other. Different numerical rates using different mathematical conventions that yield the same discount factor. Equivalent transforms.Few, if any financial contracts use continuous compounding, they instead either use simple compounding or discrete compounding (e.g. semi-annual). Continuous compounding is a theorist's way of looking at things, a mathematical and maybe even programming convenience at times.

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Simple Compounding, why?

QuoteOriginally posted by: Cuchulainn3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)not much$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt) / (1 + r\,dt)\approx 1 - 2r\,dt$

Cuchulainn
Topic Author
Posts: 61518
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Simple Compounding, why?

QuoteOriginally posted by: ppauperQuoteOriginally posted by: Cuchulainn3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)not much$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt) / (1 + r\,dt)\approx 1 - 2r\,dt$Both forms are special cases of Pade(p,q) rational approximants, P(0,1) O(dt^2) and P(1,1) O(dt^3), respectively. (for PDE/FDM they correspond to fully implicit and Crank Nicolson, respectively, well established).PadeP(1,1) is more accurate and robust than P(0,1) which is nice but if simple compounding is agreed on financially then the results that P(1,1) produces will be more accurate and at the same time "wrong"? (?). A different value will be calibrated for the SDE.This goes back to the remarks of DavidJN concerning the numerical Vs programming Vs financial interpretation of this formula. // I put it in Student because #questions > #answers (speaking for myself)
Last edited by Cuchulainn on December 10th, 2013, 11:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

DavidJN
Posts: 1746
Joined: July 14th, 2002, 3:00 am

### Simple Compounding, why?

You are over thinking this to a staggaring degree. I repeat, this is not an approximation, just a transformed way (i.e. a particular convention out of many) of getting to the same present value factor.I also repeat that the exp(-r dt) form (i.e. continuously compound interest rate) is not something found in actual financial contracts but rather in textbooks. There is nothing stopping you from using that form (or any other form) of computing present values so long as you adjust the rate accordingly.

cemil
Posts: 221
Joined: September 16th, 2005, 7:44 am

### Simple Compounding, why?

QuoteOriginally posted by: CuchulainnTake a 1-period (length dt) approximation to exp(-r dt), i.e. the popular1 / (1 + r dt)Questions:1. Why this? Is there a financial reasoning or is it just numerical convenience?2. If we had a more accurate and more stable approximation, is that 'financially acceptable'?3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)Imagine you have 1euro with rd (discrete rate) for dt period, so at time dt you will have 1x(1+rd dt)Imagine you have 1euro with rc (continuous rate) for dt period, so at time dt you will have 1xexp(rc dt)If we suppose we have the same money at the date dt, we can write 1x(1+rd dt)=1xexp(rc dt)<=> exp(-rc dt)= 1/(1+rd dt)So it isn't an approximation.

Cuchulainn
Topic Author
Posts: 61518
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Simple Compounding, why?

Clear. Thanks all.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Simple Compounding, why?

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ppauperQuoteOriginally posted by: Cuchulainn3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)not much$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt) / (1 + r\,dt)\approx 1 - 2r\,dt$Both forms are special cases of Pade(p,q) rational approximants, P(0,1) O(dt^2) and P(1,1) O(dt^3), respectively. (for PDE/FDM they correspond to fully implicit and Crank Nicolson, respectively, well established).PadeP(1,1) is more accurate and robust than P(0,1) which is nice but if simple compounding is agreed on financially then the results that P(1,1) produces will be more accurate and at the same time "wrong"? (?). A different value will be calibrated for the SDE.This goes back to the remarks of DavidJN concerning the numerical Vs programming Vs financial interpretation of this formula. // I put it in Student because #questions > #answers (speaking for myself) you might want to put a factor of 1/2 in one....$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt/2) / (1 + r\,dt2)\approx 1 - r\,dt$$(1 -\alpha r\,dt) / (1 + (1-\alpha) r\,dt)\approx 1 - r\,dt$
Last edited by ppauper on December 10th, 2013, 11:00 pm, edited 1 time in total.

AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

### Simple Compounding, why?

I *guess* (like T4A) that it is historical, in German "Zins" and "Zehent"may even have common roots - may be you dig in Etymology and Bible texts:https://de.wikipedia.org/wiki/Zinsverbo ... stamentYou may find that "Zins für Speise" (~ in the middle of the screen) can notmean rates, it means payment for something (here: food for a 'brother').So I guess it started from simple rules.And they still exists in laws: for example the german law "BGB" uses it (andforbids compounding) for some kinds of debts. So I would say, it is the other way round: compounding naturally leads toto 'exponential' growth, using exp or similar (when it became 'handy' for the folks in Finance).
Last edited by AVt on December 10th, 2013, 11:00 pm, edited 1 time in total.

Cuchulainn
Topic Author
Posts: 61518
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Simple Compounding, why?

QuoteOriginally posted by: ppauperQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ppauperQuoteOriginally posted by: Cuchulainn3. What do you think of this approximation to exp(-r dt)?(1 - r dt) / (1 + r dt)not much$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt) / (1 + r\,dt)\approx 1 - 2r\,dt$Both forms are special cases of Pade(p,q) rational approximants, P(0,1) O(dt^2) and P(1,1) O(dt^3), respectively. (for PDE/FDM they correspond to fully implicit and Crank Nicolson, respectively, well established).P(1,1) is more accurate and robust than P(0,1) which is nice but if simple compounding is agreed on financially then the results that P(1,1) produces will be more accurate and at the same time "wrong"? (?). A different value will be calibrated for the SDE.This goes back to the remarks of DavidJN concerning the numerical Vs programming Vs financial interpretation of this formula. // I put it in Student because #questions > #answers (speaking for myself) you might want to put a factor of 1/2 in one....$exp(-r\,dt))\approx 1 - r\,dt$$(1 - r\,dt/2) / (1 + r\,dt/2)\approx 1 - r\,dt$ // edit DD$(1 -\alpha r\,dt) / (1 + (1-\alpha) r\,dt)\approx 1 - r\,dt$You are correct. I wrote it down too fast. In fact, exp(- z) is handily written as (2 - z)/(2 + z)// I put a '/' into your formulaVarga's classic book "Matrix Iterative Analysis" has a nice table for Pade(p,q) page 266.
Last edited by Cuchulainn on December 11th, 2013, 11:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget


text:
# Utils¶

## Version¶

### printinfo – Tools to print date, time, and version information¶

Print or return date, time, and package version information in any environment (Jupyter notebook, IPython console, Python console, QT console), either as html-table (notebook) or as plain text (anywhere).

This script is an adapted version of empymod.printversions (https://empymod.github.io), which itself was heavily inspired by

Always shown are the OS, number of CPU(s), numpy, scipy, SimPEG, cython, properties, vectormath, discretize, pymatsolver, sys.version, and time/date.

Additionally shown are, if they can be imported, IPython, matplotlib, and ipywidgets. It also shows MKL information, if available.

All modules provided in add_pckg are also shown. They have to be imported before versions is called.

SimPEG.Utils.printinfo.versions(mode='print', add_pckg=None, ncol=4)

Return date, time, and version information.

Print or return date, time, and package version information in any environment (Jupyter notebook, IPython console, Python console, QT console), either as html-table (notebook) or as plain text (anywhere).

This script is an adapted version of empymod.printversions, (https://empymod.github.io) which itself was heavily inspired by

This is a wrapper for versions_html and versions_text.

Parameters

mode : string, optional; {<’print’>, ‘HTML’, ‘Pretty’, ‘plain’, ‘html’}
Defaults to ‘print’:
• ‘print’: Prints text-version to stdout, nothing returned.
• ‘HTML’: Returns html-version as IPython.display.HTML(html).
• ‘html’: Returns html-version as plain text.
• ‘Pretty’: Returns text-version as IPython.display.Pretty(text).
• ‘plain’: Returns text-version as plain text.

‘HTML’ and ‘Pretty’ require IPython.

Package or list of packages to add to output information (must be imported beforehand).
ncol : int, optional
Number of package-columns in html table; only has effect if mode='HTML' or mode='html'. Defaults to 3.

Returns

Depending on mode (HTML-instance; plain text; html as plain text; or nothing, only printing to stdout).

Examples

>>> import pytest
>>> import dateutil
>>> from SimPEG import versions
>>> versions()                 # Default values
>>> versions('plain', pytest)  # Provide additional package
>>> versions('HTML', [pytest, dateutil], ncol=5)  # HTML

SimPEG.Utils.printinfo.versions_html(add_pckg=None, ncol=4)

HTML version.

See versions for details.

SimPEG.Utils.printinfo.versions_text(add_pckg=None)

Plain-text version.

See versions for details.

## Matrix Utilities¶

SimPEG.Utils.matutils.avExtrap(**kwargs)
SimPEG.Utils.matutils.cartesian2spherical(m)

Convert from cartesian to spherical

SimPEG.Utils.matutils.coterminal(theta)

Compute coterminal angle so that [-pi < theta < pi]

SimPEG.Utils.matutils.diagEst(matFun, n, k=None, approach='Probing')

Estimate the diagonal of a matrix, A. Note that the matrix may be a function which returns A times a vector.

Three different approaches have been implemented:

1. Probing: cyclic permutations of vectors with 1’s and 0’s (default)
2. Ones: random +/- 1 entries
3. Random: random vectors
Parameters: matFun (callable) – takes a (numpy.ndarray) and multiplies it by a matrix to estimate the diagonal n (int) – size of the vector that should be used to compute matFun(v) k (int) – number of vectors to be used to estimate the diagonal approach (str) – approach to be used for getting vectors numpy.ndarray est_diag(A)
SimPEG.Utils.matutils.dip_azimuth2cartesian(dip, azm_N)

Function converting degree angles for dip and azimuth from north to a 3-components in cartesian coordinates.

INPUT dip : Value or vector of dip from horizontal in DEGREE azm_N : Value or vector of azimuth from north in DEGREE

OUTPUT M : [n-by-3] Array of xyz components of a unit vector in cartesian

Created on Dec, 20th 2015

@author: dominiquef

SimPEG.Utils.matutils.spherical2cartesian(m)

Convert from spherical to cartesian

SimPEG.Utils.matutils.uniqueRows(M)

## Solver Utilities¶

class SimPEG.Utils.SolverUtils.Solver(A, **kwargs)
clean()
class SimPEG.Utils.SolverUtils.SolverBiCG(A, **kwargs)
clean()
class SimPEG.Utils.SolverUtils.SolverCG(A, **kwargs)
clean()
class SimPEG.Utils.SolverUtils.SolverDiag(A)

docstring for SolverDiag

clean()
class SimPEG.Utils.SolverUtils.SolverLU(A, **kwargs)
clean()
SimPEG.Utils.SolverUtils.SolverWrapD(fun, factorize=True, checkAccuracy=True, accuracyTol=1e-06, name=None)

Wraps a direct Solver.

import scipy.sparse as sp
Solver   = SolverUtils.SolverWrapD(sp.linalg.spsolve, factorize=False)
SolverLU = SolverUtils.SolverWrapD(sp.linalg.splu, factorize=True)

SimPEG.Utils.SolverUtils.SolverWrapI(fun, checkAccuracy=True, accuracyTol=1e-05, name=None)

Wraps an iterative Solver.

import scipy.sparse as sp
SolverCG = SolverUtils.SolverWrapI(sp.linalg.cg)

## Model Builder Utilities¶

SimPEG.Utils.ModelBuilder.PolygonInd(mesh, pts)

Finde a volxel indices included in mpolygon (2D) or polyhedra (3D) uniformly distributed model.

Parameters: shape (tuple) – shape of the model. seed (int) – pick which model to produce, prints the seed if you don’t choose. anisotropy (numpy.ndarray) – this is the (3 x n) blurring kernel that is used. its (int) – number of smoothing iterations bounds (list) – bounds on the model, len(list) == 2 numpy.ndarray M, the model
SimPEG.Utils.ModelBuilder.addBlock(gridCC, modelCC, p0, p1, blockProp)

Add a block to an exsisting cell centered model, modelCC

Parameters: BlockProp float blockProp: gridCC (numpy.ndarray) – mesh.gridCC is the cell centered grid modelCC (numpy.ndarray) – cell centered model p0 (numpy.ndarray) – bottom, southwest corner of block p1 (numpy.ndarray) – top, northeast corner of block property to assign to the model model with block
SimPEG.Utils.ModelBuilder.defineBlock(ccMesh, p0, p1, vals=None)

Build a block with the conductivity specified by condVal. Returns an array. vals[0] conductivity of the block vals[1] conductivity of the ground

SimPEG.Utils.ModelBuilder.defineElipse(ccMesh, center=None, anisotropy=None, slope=10.0, theta=0.0)
SimPEG.Utils.ModelBuilder.defineTwoLayers(ccMesh, depth, vals=None)

Define a two layered model. Depth of the first layer must be specified. CondVals vector with the conductivity values of the layers. Eg:

Convention to number the layers:

<----------------------------|------------------------------------>
0                          depth                                 zf
1st layer                       2nd layer

SimPEG.Utils.ModelBuilder.getIndicesBlock(p0, p1, ccMesh)

Creates a vector containing the block indices in the cell centers mesh. Returns a tuple

The block is defined by the points

p0, describe the position of the left upper front corner, and

p1, describe the position of the right bottom back corner.

ccMesh represents the cell-centered mesh

The points p0 and p1 must live in the the same dimensional space as the mesh.

SimPEG.Utils.ModelBuilder.getIndicesSphere(center, radius, ccMesh)

Creates a vector containing the sphere indices in the cell centers mesh. Returns a tuple

The sphere is defined by the points

p0, describe the position of the center of the cell

r, describe the radius of the sphere.

ccMesh represents the cell-centered mesh

The points p0 must live in the the same dimensional space as the mesh.

SimPEG.Utils.ModelBuilder.layeredModel(ccMesh, layerTops, layerValues)

Define a layered model from layerTops (z-positive up)

Parameters: ccMesh (numpy.ndarray) – cell-centered mesh layerTops (numpy.ndarray) – z-locations of the tops of each layer layerValue (numpy.ndarray) – values of the property to assign for each layer (starting at the top) numpy.ndarray M, layered model on the mesh
SimPEG.Utils.ModelBuilder.randomModel(shape, seed=None, anisotropy=None, its=100, bounds=None)

Create a random model by convolving a kernel with a uniformly distributed model.

Parameters: shape (tuple) – shape of the model. seed (int) – pick which model to produce, prints the seed if you don’t choose. anisotropy (numpy.ndarray) – this is the (3 x n) blurring kernel that is used. its (int) – number of smoothing iterations bounds (list) – bounds on the model, len(list) == 2 numpy.ndarray M, the model
SimPEG.Utils.ModelBuilder.scalarConductivity(ccMesh, pFunction)

Define the distribution conductivity in the mesh according to the analytical expression given in pFunction

## Interpolation Utilities¶

discretize.utils.interputils.interpmat(locs, x, y=None, z=None)[source]

Local interpolation computed for each receiver point in turn

Parameters: loc (numpy.ndarray) – Location of points to interpolate to x (numpy.ndarray) – Tensor of 1st dimension of grid. y (numpy.ndarray) – Tensor of 2nd dimension of grid. None by default. z (numpy.ndarray) – Tensor of 3rd dimension of grid. None by default. scipy.sparse.csr_matrix Interpolation matrix

## Counter Utilities¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class MyClass(object): def __init__(self, url): self.counter = Counter() @count def MyMethod(self): pass @timeIt def MySecondMethod(self): pass c = MyClass('blah') for i in range(100): c.MyMethod() for i in range(300): c.MySecondMethod() c.counter.summary()
 1 2 3 4 5 Counters: MyClass.MyMethod : 100 Times: mean sum MyClass.MySecondMethod : 1.70e-06, 5.10e-04, 300x

### The API¶

class SimPEG.Utils.CounterUtils.Counter

Counter allows anything that calls it to record iterations and timings in a simple way.

Also has plotting functions that allow quick recalls of data.

If you want to use this, import count or timeIt and use them as decorators on class methods.

class MyClass(object):
def __init__(self, url):
self.counter = Counter()

@count
def MyMethod(self):
pass

@timeIt
def MySecondMethod(self):
pass

c = MyClass('blah')
for i in range(100): c.MyMethod()
for i in range(300): c.MySecondMethod()
c.counter.summary()

count(prop)

Increases the count of the property.

countTic(prop)

Times a property call, this is the init call.

countToc(prop)

Times a property call, this is the end call.

summary()

Provides a text summary of the current counters and timers.

SimPEG.Utils.CounterUtils.count(f)
SimPEG.Utils.CounterUtils.timeIt(f)


text:
# Resolve the force F2 into components acting along the u and v axes and determine

Resolve the force F2 into components acting along the u and v axes and determine the magnitudes of the components.

You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Neelam Wainwright
Jeffrey Jordon

By sine rule:

$\frac{{F}_{u}}{\mathrm{sin}{45}^{\circ }}=\frac{{F}_{v}}{\mathrm{sin}{30}^{\circ }}=\frac{{F}_{z}}{\mathrm{sin}{75}^{\circ }}$

$⇒{F}_{u}=\frac{{F}_{z}}{\mathrm{sin}{75}^{\circ }}×\mathrm{sin}{75}^{\circ }$

and ${F}_{v}=\frac{{F}_{z}}{\mathrm{sin}{75}^{\circ }}×\mathrm{sin}{30}^{\circ }=\frac{6}{\mathrm{sin}{75}^{\circ }}×\mathrm{sin}{30}^{\circ }$


text:
•  Entire Site   People   Research   Publications   News & Media   Events
 Search for in KeywordAuthorTitleAbstract in KeywordAuthorTitleAbstract in KeywordAuthorTitleAbstract in KeywordAuthorTitleAbstract Date Range

Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara
tech. report CMU-RI-TR-12-35, Robotics Institute, Carnegie Mellon University, December, 2012

 Download Adobe portable document format (pdf) (186KB) Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

 Abstract In this paper, we present provably-good distributed task allocation (assignment) algorithms for a heterogeneous multi-robot system where the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Our problem is motivated by applications where multiple robots with heterogeneous capabilities have to work together to accomplish tasks. Thus, for our purposes, a task group is a {\em compound task} composed of more than one atomic tasks where one robot is required for each atomic task. Since robots have limited battery life, we assume that the number of (atomic) tasks that a robot can do within a mission has an upper bound. Furthermore, each robot has a constraint on the number of tasks it can do from each group (this models the fact that multiple robots may be needed to simultaneously perform the atomic tasks that make up the compound task). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize the total payoff (or minimize the total cost) of all the robots. In general, existing (centralized or distributed) algorithms for task allocation either assume that (atomic) tasks are independent, or do not provide performance guarantee for the situation where task constraints exist. We show that our problem can be solved in polynomial time by a centralized algorithm by reducing it to a minimum cost network flow problem. We then present a decentralized algorithm (that extends the auction algorithm of Bertsekas for linear assignment problems~\cite{Bertsekas88}) to provide an almost optimal solution. We prove that our solution is within a factor of $O(n_t\epsilon)$ of the optimal solution, where $n_t$ is the total number of tasks and $\epsilon$ is a parameter that we choose (the guarantees are the same as that of the original auction algorithm for unconstrained tasks). The decentralized algorithm assumes a shared memory model of computation that may be unrealistic for many multi-robot deployments. Therefore, we show that by using a maximum consensus algorithm along with our algorithm, we can design a totally distributed algorithm for task allocation with group constraints. The key aspect of our distributed algorithm is that the overall objective is (nearly) maximized by {\em each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task)}. Our algorithm is polynomial in the number of tasks as well as the number of robots.

 Keywords Multi-robot assignment, Task allocation, Auction algorithm, Distributed algorithm

 Notes Sponsor: AFOSR MURI grant FA95500810356 and ONR grant N000140910680.

 Text Reference Lingzhi Luo, Nilanjan Chakraborty, and Katia Sycara, "A Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks," tech. report CMU-RI-TR-12-35, Robotics Institute, Carnegie Mellon University, December, 2012

 BibTeX Reference @techreport{Luo_2012_7378,    author = "Lingzhi Luo and Nilanjan Chakraborty and Katia Sycara",    title = "A Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks",    booktitle = "",    institution = "Robotics Institute",    month = "December",    year = "2012",    number= "CMU-RI-TR-12-35",    address= "Pittsburgh, PA", }