text:
Optimal pebbling number of the square grid

# Optimal pebbling number of the square grid

Ervin Győri gyori.ervin@renyi.mta.hu Gyula Y. Katona kiskat@cs.bme.hu László F. Papp lazsa@cs.bme.hu
###### Abstract

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph was investigated in several papers [1, 12, 9]. In this paper, we present a new method using some recent ideas to give a lower bound on . We apply this technique to prove that . Our method also gives a new proof for .

## 1 Introduction

Graph pebbling is a game on graphs. It was suggested by Saks and Lagarias to solve a number theoretic problem, which was done by Chung [2]. The main framework is the following: A distribution of pebbles is placed on the vertices of a simple graph. A pebbling move removes two pebbles from a vertex and places one pebble on an adjacent vertex. The goal is to reach any specified vertex by a sequence of pebbling moves. This may be viewed as a transportation problem on a graph where the cost of a move is one pebble. We begin with some notation needed to state our results.

Let be a simple graph. We denote the vertex and edge set of by and , respectively. A pebble distribution is a function from to the nonnegative integers. We say that has pebbles placed at the vertex under the distribution . We say that a vertex is occupied if and unoccupied otherwise. The size of a pebbling distribution , denoted , is the total number of pebbles placed on the vertices of .

Let be a vertex with at least two pebbles under , and let be a neighbor of . A pebbling move from to consists of removing two pebbles from and adding one pebble to . That is, a pebbling move yields a new pebbling distribution with and . We say that a vertex is -reachable under the distribution if we can obtain, after a sequence of pebbling moves, a distribution with at least pebbles on . If we say simply that is reachable under . More generally, a set of vertices is -reachable under the distribution if, after a sequence of pebbling moves, we can obtain a distribution with at least a total of pebbles on the vertices in .

A pebble distribution on is solvable if all vertices of are reachable under . A pebble distribution on is optimal if it is solvable and its size is minimal among all of the solvable distributions of . Note that optimal distributions are usually not unique.

The optimal pebbling number of , denoted by , is the size of an optimal pebble distribution. In general, the decision problem for this graph parameter is NP-complete [6].

We denote with and the path and cycle on vertices, respectively. The Cartesian product of graphs and is defined in the following way: and if and only if and or and .

Let and be vertices of graph . denotes the distance between and , namely the number of edges contained in the shortest path between and . The distance neighborhood of contains the vertices whose distance from is exactly . We denote this set with .

The optimal pebbling number is known for several graphs including paths, cycles [1, 3, 4], caterpillars [8] and -ary trees [11]. The optimal pebbling number of grids has also been investigated. Exact values were proved for [1] and [12]. The question for bigger grids is still open. The best known upper bound for the square grid can be found in [9]. Diagonal induced subgraphs of the square grid was studied in [10].

Instead of the square grid on the plane it is easier to work with the square grid on the torus. As the plane grid is a subgraph of this, any lower bound on the torus grid will also give a lower bound on the plane grid as well. It is well known that the torus grid is a vertex transitive graph, i.e. given any two vertices and of , there is some automorphism such that . Some of our statements will be stated for all vertex transitive graphs.

In this paper we present a new method giving a lower bound on the optimal pebbling number. We obtain as a lower bound for the optimal pebbling number of the square grid, which is better than the previously known bounds.

In Section 2 we show that the concept of excess — introduced in [12] — can be used to improve the fractional lower bound on the optimal pebbling number. The higher the total excess, the better the obtained bound on the optimal pebbling number is. The problem is that this method is not standalone, because excess can be zero and zero excess does not give us any improvement. Therefore the main objective of the rest of the paper is to give a lower bound on the excess using some other pebbling tools.

In Section 3 we study the concept of cooperation. Cooperation is the phenomenon which makes pebbling hard. We show there, that if cooperation can be bounded from above, then we can state a lower bound on the optimal pebbling number. We invent the tool called cooperation excess, which is a mixture of cooperation and excess. In this section we state and prove several small claims which will be required later to prove Lemma 4. This lemma is the essence of our work. It shows that if the total excess is small, then there is not much cooperation and if cooperation is huge, then the total excess is also large. Therefore in each case one of our two lower bounds works well.

Unfortunately, the proof of Lemma 4 is quite complicated. The third part of Section 3 and the whole Section 4 contain the parts of this proof. In Section 5 we show a general method which can be used to give a lower bound on the optimal pebbling number. This method relies on Lemma 4. Using this method we show that . We also present a new proof for .

## 2 Improving the fractional lower bound

The optimal pebbling number problem can be formulated as the following integer programming problem [13]:

 P(vi)+∑x∈N(vi)(pi(x,vi)−2pi(vi,x))≥1
 P(vj)+∑x∈N(vj)(pi(x,vj)−2pi(vj,x))≥0
 P(vi)≥0 integer
 pi(v,w)≥0 integer
 min∑v∈V(G)P(v)

Its fractional relaxation can be solved efficiently, and its solution is called the fractional optimal pebbling number, which gives a lower bound on the optimal pebbling number. Originally it was defined in a bit different way, but this is an equivalent definition. You can find the details of fractional pebbling in [13].

Notice that some vertices must be -reachable in a solvable distribution if there is an unoccupied vertex. Optimal distributions usually contain many unoccupied and several -reachable vertices. However, in some sense, , , or more reachability wastes the effect of pebbles. Also -reachability induces larger waste than -reachability. In order to measure this waste we use the notion called excess, which was introduced in [12].

Definition:  Let be the greatest integer such that is -reachable under . The excess of under is if is reachable and zero otherwise. It is denoted by .

We are interested in the total amount of waste, therefore we define the notation of total excess of , which is .

Definition:  An effect of a pebble placed at is the following: .

Herscovici et al. proved that the fractional optimal pebbling number of a vertex-transitive graph is , therefore it is a lower bound on the optimal pebbling number. The corollary of the next theorem improves this bound.

###### Theorem

If is a solvable distribution on , then

 ∑v∈V(G)ef(v)P(v)≥|V(G)|+TE(P).

###### Proof

It is clear that if a vertex is -reachable under , then it is mandatory that
. Summing these inequalities for all the vertices,

 ∑u∈V(G)∑v∈V(G)(12)d(v,u)P(v)≥∑u∈V(G)Reach(P,u).

Exchange the summations on the left side and use the fact that is solvable on the right side,

 ∑v∈V(G)∑u∈V(G)(12)d(v,u)P(v)≥∑u∈V(G)(1+Exc(P,u)).

Group the elements of the second sum according to the distance neighborhoods,

 ∑v∈V(G)diam(G)∑i=0(12)i|Ni(v)|P(v)≥|V(G)|+TE(P).

###### Corollary

If be a solvable distribution on a vertex-transitive graph , then

 |P|≥|V(G)|+TE(P)ef(v).

Naturally, this bound is useless without a proper estimate of total excess. To say something useful about it we look at the optimal pebbling problem from a different angle.

## 3 Cooperation between distributions

In this section we talk about cooperation, which makes pebbling hard.

### 3.1 Pebbling cooperation

Definition:  Let and be pebble distributions on graph . Now is the unique pebble distribution on which satisfies . and are disjoint when no vertex has pebbles under both distributions.

Definition:  The coverage of a distribution is the set of vertices which are reachable under . We denote the size of this set with .

A natural idea to find small solvable distributions is finding a distribution with small size and huge coverage and make it solvable by placing some more pebbles.

In the rest of the section we assume that we add disjoint distributions and together. We would like to establish an upper bound using on . Similarly, we are interested in some relation between and .

Definition:  A cooperation vertex is neither reachable under nor , but it is reachable under . We denote the number of such vertices with . A double covered vertex is reachable under both and , we denote the size of their set with .

The following claim is a trivial consequence of the definitions.

###### Claim

.

Definition:  We say that a distribution is a unit, if only one vertex has pebbles under .

Units are the building blocks of pebble distributions in the following sense: Any distribution can be written as , where is a unit having pebbles at . Units have two main advantages over other distributions. Their coverage and total excess can be easily calculated:

###### Claim
 Cov(U)=⌊log2(P(u))⌋∑i=0|Ni(u)|,
 TE(U)=⌊log2(P(u))⌋∑i=0|Ni(u)|(⌊P(u)2i⌋−1).

### 3.2 Combining cooperation and excess

We would like to distinguish the sources of excess. Does it come from or or does it arise from the “cooperation of and ”?

Definition:  The unit excess of , denoted by , is , where is a unit on containing exactly pebbles and all of them are placed at .

Definition:  The cooperation excess of a vertex is . If it is positive, then we say that has cooperation excess.

Similarly, the cooperation excess between and is the total excess of minus the total excesses of and . Denote this with .

We have mentioned previously, that we can split any pebbling distribution into disjoint unit distributions. If we get unit distributions, then the application of Claim 3.1 and the definition of cooperation excess gives the following results.

###### Claim

Let be a pebbling distribution on and let be a disjoint decomposition of to unit distributions. Denote the elements of with . Now

 TE(P)=t∑i=1TE(Ui)+t∑i=1CE(i−1∑k=1Uk,Ui), (1)
 Cov(P)=t∑i=1Cov(Ui)+t∑i=1(Coop(i−1∑k=1Uk,Ui)−DC(i−1∑k=1Uk,Ui)). (2)

Both and can be calculated easily. The “effect” of cooperation is calculated in the other, more complicated term. Lemma 4 is going to establish a connection between those quantities in a fruitful way.

### 3.3 Connection between cooperation and excess

Now let us consider an arbitrary graph , and let be the maximum degree of . In the rest of the section we assume that is a unit having pebbles only at vertex and its size is not zero. Now we state some basic claims about the recently defined objects.

###### Claim

Each cooperation vertex has a neighbor that has cooperation excess.

###### Proof

A cooperation vertex is not reachable under or . Therefore none of its neighbors is -reachable under these distributions. On the other hand, is reachable under , hence there is a neighbor of which is -reachable under this distribution. This means that has cooperation excess.

Definition:  If a vertex is not a cooperation vertex and it does not have cooperation excess, then we call it cooperation free.

This name is a somewhat misleading, because these vertices can participate in cooperation in a sophisticated way. For an example see Figure 1.

Definition:  A vertex is utilized by a pebbling sequence if there is a move in the sequence which removes or adds a pebble to the vertex. Let be the minimal number of cooperation vertices which are utilized by a pebbling sequence which satisfies that . If is not 2-reachable under , then we say that .

###### Claim

If there is an available pebbling move which removes a pebble from a cooperation vertex , then either two neighbors of , say and , have cooperation excess at least 1 and and or a neighbor has cooperation excess at least 3, and .

###### Proof

The condition implies that can obtain two pebbles by some pebbling moves under . Consider a pebbling sequence which does this by utilizing cooperation vertices. Either moves the two pebbles to from two different neighbors and , or it can move both pebbles from the same neighbor . None of the neighbors are -reachable under or , but , and has to be , and reachable under , respectively. This means that and have cooperation excess at least 1 and the cooperation excess of is at least 3. Furthermore, moves two pebbles to and or to , then it moves them to with some more moves. This shows that .

###### Claim

If the cooperation excess of a vertex is at least 3 and one of its neighbors, say , is a cooperation vertex, then there is a vertex that is adjacent to and .

###### Proof

does not have two pebbles under , otherwise can not be a cooperation vertex. obtains pebbles from its neighbors, so one of them, say , can get two pebbles by utilizing at most cooperation vertices. If is a cooperation vertex then a pebbling sequence resulting in two pebbles at utilizes more cooperation vertices than the sequence which does not make the final move from to .

###### Claim

If a vertex has cooperation excess, then it has a neighbor which has cooperation excess or reachable under or .

###### Proof

gets a pebble under , so a neighbor is -reachable under . If is not 2-reachable under of , then it has cooperation excess.

###### Remark 1

In fact, a stronger property holds. If a vertex gains an extra pebble by cooperation, then it can happen in two ways: A neighbor gained extra pebbles and it passes one of them. Or there are two or more neighbors of such that each of them can give some pebbles to , but these moves somehow blocks each other. The advantage of the cooperation is that some previously blocked moves can be done simultaneously. This is the way how cooperation free vertices can “help cooperation”.

### 3.4 Trajectories

Here we introduce a visualization of pebbling sequences, which is slightly different from the signature digraph used in several pebbling papers (i.e. in [6]).

Definition:  The trajectory of a pebbling sequence , denoted by , is a digraph on the vertices of without parallel edges, where is a directed edge if and only if a pebbling move is contained in the sequence.

Definition:  The size of a pebbling sequence is the total number of moves contained in it. We say that is a minimal pebbling sequence with property if its size is minimal among all pebbling sequences having property .

In the next proof, we need a lemma which is frequently used to solve pebbling problems. It is called No-Cycle Lemma and proved in several papers [5, 6, 7]. We state this lemma in the language of this paper.

###### Lemma (No-Cycle [7])

Let be a pebbling distribution on graph , and be an executable pebbling sequence. There is a subsequence whose trajectory does not contain directed cycles and for each vertex .

This implies the following corollary:

###### Corollary

If is a minimal pebbling sequence which moves pebbles to a vertex , then its trajectory is acyclic.

###### Claim

If has cooperation excess under , where , then is double covered.

###### Proof

The No-Cycle lemma yields that we can move maximum number of pebbles to without removing a pebble from . We can move pebbles to , which means that we move here a pebble of while we keep the pebbles of , so is double covered.

The following definition will be crucial in the proof.

Definition:  We say that a path is a coopexcess path, if each inner vertex of the path has cooperation excess.

###### Lemma

Let be a vertex which is not double covered but it has cooperation excess. There is a coopexcess path between and a double covered vertex or there are at least two cooperation free vertices such that each of them is connected to by a coopexcess path. If is not 2-reachable under both and , then these paths does not contain a vertex whose value is higher than .

###### Proof

Consider a pebbling sequence moving pebbles to utilizing cooperation vertices. Consider some path in the trajectory of connecting to . We can assume that the only sink in the trajectory path is . A cooperation vertex without cooperation excess can not be the tail of an arc which is contained in the trajectory, therefore each vertex in the trajectory is either cooperation free or it has cooperation excess.

If there is a path between and which is contained in the trajectory such that all vertices of this path have cooperation excess, then according to Claim 3.4 is double covered and this path is a coopexcess path. Otherwise, all of the paths which are contained in the trajectory contain cooperation free vertices.

In each such path let denote the cooperation free vertex which is the closest vertex to . If exist, then we have found 2 cooperation free vertices such that each of them is connected to by a coopexcess path.

In the remaining case there is only one such . Either it is a cut vertex in the trajectory or . Let be the set of vertices which are included in the trajectory. We divide to three sets , and in the following way:

We remove from the trajectory obtaining some components, then we place a vertex of to if is in the component containing , similarly we place to if it is in the component containing and place the remaining vertices to . Now we add to all of these sets. Let be the pebbling sequence containing all moves of which acts only on the vertices of . We define and similarly. The sources of the latter two sequences are only and vertices having pebbles under .

If is reachable under , then is empty ( is not double covered) and . We can replace with a pebbling sequence which does not use any pebbles of and . Therefore is an executable pebbling sequence and . must use a pebble of to do this, otherwise is executable under which is a contradiction. The trajectory of is connected, therefore there is a vertex which is double covered, furthermore each vertex in this trajectory is connected by a coopexcess path to , so we are done.

If is not reachable under , then . Thus, there is a minimal pebbling sequence which is executable under and . Clearly is not executable or . Both cases require that removes a pebble from a vertex contained in .

Let be the set of vertices from which removes a pebble. is executable under so these vertices are -reachable under . Consider the trajectory of . If any vertex from is connected in the trajectory with a vertex contained in without pass-through , then each vertex in such a connecting path is 2-reachable under , therefore it is cooperation free or has cooperation excess. So there is either an other cooperation free vertex connected by a coopexcess path to , or there is a coopexcess path between and which is connected to by a path in the trajectory of which does not contain , so that path has to contain a double covered or a cooperation free vertex, which is not .

The remaining case when separates all elements of from in the trajectory of .

Let be a maximal subset of which is executable without using the pebbles placed at , and let be the remaining subsequence. is not executable under or . Therefore moves more pebbles to than , but is executable under , thus , therefore has cooperation excess.

To prove the second claim, consider the paths we have found. If they were part of the trajectory of , therefore all of them are 2-reachable under , so their value can not be higher than . Otherwise, the path consists of vertices from the trajectory of and some others whose value is zero, since they are 2-reachable under .

The following claim is a trivial consequence of the definitions.

###### Claim

If contains at least two pebbles and it is double covered, then one of its neighbors is also double covered.

In the rest of the section we assume, that contains at least two pebbles, i. e. . Therefore we can use the previous claim.

###### Lemma

Assume that contains at least two pebbles. Then each double covered vertex is connected by a coopexcess path to an other double covered vertex or a cooperation free vertex. Furthermore each vertex of this coopexcess path is -reachable under .

###### Proof

The previous claim handles the case when is , since the neighbor is connected to . So assume that .

Since is double covered, it is reachable from , so it is connected to by a path, whose vertices are -reachable under . Therefore these vertices can not be cooperation vertices. If there is a vertex on this path which does not have cooperation excess, then the vertex closest to satisfies the conditions of the second type. Otherwise, has cooperation excess which means that it is double covered.

We are getting closer to establish a connection between the number of cooperation vertices and cooperation excess.

Definition:  We call a subset of a -block, if

1. each pair of vertices in is connected by a coopexcess path,

2. it contains a vertex having cooperation excess

and it is maximal with these properties.

Notice that the intersection of two -blocks can not contain a vertex having cooperation excess.

###### Lemma

Each -block either

1. contains at least two double covered vertices, or

2. contains one double covered vertex and one cooperation free vertex, or

3. contains at least two cooperation free vertices.

###### Proof

Consider an arbitrary element of which having cooperation excess. If the -block does not have a double covered vertex, then Lemma 3.4 guarantees that two cooperation free vertices are connected to by a coopexcess path, which means that they are contained in , so (5) is satisfied.

Otherwise contains a double covered vertex. According to lemma 3.4, either there is an other double covered vertex in , or a cooperation free vertex. Thus either (3) or (4) is satisfied.

Later we generalize the notion of -blocks, so that we keep the properties of 3.4. The following statement will be useful for this.

###### Lemma

If a vertex having cooperation excess is adjacent to a cooperation vertex such that , then there are vertices and , such that each of them is either double covered or cooperation free and they are connected to by coopexcess paths containing only vertices whose values are smaller than .

###### Proof

has a cooperation vertex neighbor, therefore is not 2-reachable under or . According to Lemma 3.4 there is a double covered vertex or there are two cooperation free vertices who are connected to by a coopexcess path containing only vertices whose values at most . In the latter case we are done. Since the double covered vertex is connected to an other double covered or cooperation free by a coopexcess path containing vertices whose M value is zero, according to Lemma 3.4. The concatenation of these two coopexcess paths fulfills criteria.

## 4 Connection between total cooperation excess, number of cooperation vertices and maximum degree

In this section we prove a crucial lemma. Unfortunately, the proof requires quite a lot of effort, including many small claims.

###### Lemma

Let be an arbitrary pebbling distribution on and be a unit having at least two pebbles, such that does not contain a pebble at . Now we have

 Coop(P,U)−DC(P,U)≤(Δ−2)CE(P,U).

This lemma gives a connection between the total cooperation, the total number of double covered vertices and total cooperation excess. The proof would be relatively easy if the effect of a pebble would appear close to the location of the pebble. The example on Figure 2. shows, that unfortunately this is not always true.

Another difficulty arises from the fact that a cooperation vertex can have cooperation excess. For such an example see Figure 3. To prove Lemma 4 we get rid of such vertices one by one.

So to prove the lemma we will change the graph in several steps. In the new graph it will be easier to isolate these effects.

We introduce a sequence of auxiliary graphs , whose vertices are vectors of four coordinates. The first and fourth coordinate is always an integer, while the other coordinates are binary. We denote the vertices of these graphs with underlined letters and the th coordinate of vertex with . We encode the parameters of the investigated pebbling problem in the auxiliary graph and in the coordinates in the following way:

is isomorphic to . The first coordinate of each vertex is the amount of the cooperation excess of the corresponding vertex. The second coordinate is 1 iff the corresponding vertex is a cooperation vertex. The third coordinate is 1 when the vertex is double covered. Finally, the last coordinate is , i.e. the minimum number of cooperation vertices have to be utilized by a pebbling sequence to obtain 2 pebbles at . So is representation of the original configuration, the labels give the values of the various quantities that we are interested in.

The other graphs in the sequence will be obtained from by applying certain operations recursively, until we finally obtain with some useful properties. It is important to note that although the labels of are obtained from the pebbling distribution on , this will not be true any more for the other auxiliary graphs. We are not trying to change the graph and the pebbling distribution and then obtain the new labels from these. We just apply the transformation on the abstract, labeled graphs.

Now we translate the properties of the pebbling distribution to properties of .

Definition:  We call a path in an -path, if each inner vertex of satisfies . We say that is an -block iff

1. there is a vertex such that ,

2. if , then there is an -path which connects them, and

and is maximal to these properties.

Note that the concept of -path and -block are generalizations of coopexcess path and -block, respectively. In this language, the statement of Lemma 4 can be formulated as:

 ∑a––∈Aa2−∑a––∈Aa3≤∑a––∈Aa1(Δ−2)

We state four properties of which will be inherited to later auxiliary graphs. The significant properties are the first and the last. The other two are technical ones which will help the proof of inheritance stated in Claim 4.

###### Claim

The following statements hold for :

1. If then one of the following two cases hold:

1. there exist a which is adjacent to , and , or

2. there are vertices and such that they are neighbors of , and are both positive, and .

2. If and has a neighbor such that , then there is a , which is adjacent to and .

3. Let be a vertex whose first and second coordinates are both positive. If is a neighbor of such that and , then there are vertices and such that each of them is connected to by -paths containing only vertices having their fourth coordinate smaller than , and their third coordinate is either or the first and second coordinates of them are .

4. Each -block contains either

1. two vertices with third coordinate , or

2. two vertices with first and second coordinates , or

3. one vertex with third coordinate and one vertex with first and second coordinates .

This claim is equivalent to the following, previously proven, statements with the new notation: Claim 3.3 (8), Claim 3.3 (9), Lemma 3.4 (10) and Lemma 3.4 (11).

We will obtain from by applying one of two transformations. Then we repeat this until it is possible to apply at least one of the transformations. Both transformations will preserve , , the fourth coordinate of each vertex and , the maximum degree in the graph. The objective of the transformations is to replace vertices satisfying (i.e. it has cooperation excess and it is a cooperation vertex) with (one ore more) vertices satisfying . From this point, we call these vertices saturated vertices. Both transformations will increase the number of vertices in the auxiliary graph.

Let be a vertex where such that its fourth coordinate is maximal among these vertices. By Claim 4 (8) there are two cases.

Case 1: If has a neighbor such that and , then we apply the following transformation to :

Transformation 1

• Choose a neighbor of such that its fourth coordinate is minimal among all neighbors of .

• Let be the set of ’s neighbors without where the product of the first and the second coordinate is positive.

• Delete and add three vertices , and , such that and . , and . Connect with , and .

• Delete each element of and add two vertices and and set the coordinates as: , , , , and . We connect to and to and to each original neighbor of .

• We connect the neighbors of which are not included in to .

• Set .

• If , then add an extra vertex and connect it only with . Set its vector to .

In other words this transformation replaces each saturated neighbor of (excluding a chosen ) with two vertices such that one of them is a leaf with zero first coordinate and the other one is act as the original vertex, but its second coordinate is zero. To handle the increased degree of , we triple it. Also, if is saturated then we add the additional vertex. Note that this can be done when . If we have to handle this case in a slightly different way.

Case 2: If has two neighbors such that their first coordinates are positive and their fourth coordinates are strictly less than , then we apply the second transformation:

Transformation 2

• We choose neighbors and whose fourth coordinate is minimal among all neighbors and .

• We delete and add vertices and . We set the coordinates of these vectors as: , , , , and .

• We connect only with . In contrast, we connect with all neighbors of except .

Both transformation can be seen on Figure 4.

###### Claim

Both transformations preserve , and if .

###### Claim

Both transformations decrease the number of saturated vertices.

###### Claim

If the statements of Claim 4 hold for an auxiliary graph, then they hold for the new one obtained by applying one of the above defined transformations.

###### Proof

We say that a vertex is created by the th transformation if is a vertex of and is a vertex of . In this situation we say that is a descendant of . A vertex is involved in a transformation if either it is created by that or its vector is changed by it.

Notice that the transformations keep the fourth coordinates of the vertices and if two vertices are descendants of the same vertex, then their fourth coordinates are the same.

(8): If is a saturated vertex in , then it is not created by the th transformation and it was saturated in also. If none of its neighbors were involved in the last transformation, then the property is clearly holds. Therefore assume the opposite. Assume that had a neighbor in , such that and in .

If is contained in also, then the th transformation did not change . In that case and are adjacent in and we are done.

Otherwise the th transformation created some descendants of .

If it was transformation 1 then a descendant of is connected to and either its first coordinate equals or it is . In the first case we are done and the latter can happen if and only if acted as in that transformation. However, this is not possible, because this would mean that acted as but by (9) and the choice of in Transformation 1, therefore which is a contradiction.

The remaining case is that two descendants of are created by Transformation 2. Since can not be or in Transformation 2, therefore it is adjacent to in and the first coordinate of this vertex equals .

Now assume that there are neighbors and in such that their fourth coordinates are smaller than and . We may assume that , otherwise we obtain the previous case. Therefore neither nor can act as in Transformation .

If is contained in , then it is still adjacent to . If is replaced with some descendants by the th transformation, then one of its descendants keep its first coordinate and that one is connected to . Like in the previous case it cannot happen that and in Transformation 1 or and in Transformation 2. We can state the same for .

(9): If is contained in then in also. Therefore according to (9) there is a which is adjacent to and . Either or one of its descendants is adjacent to in , therefore we are done.

Otherwise is a descendant of a vertex . has a neighbor whose fourth coordinate is at most . There are several cases:

First case: in Transformation , where . If we remove from the neighborhood of and add we obtains the neighborhood of . Therefore has a neighbor whose fourth coordinate is not bigger.

Second case: in Transformation . had the smallest fourth coordinate among the neighbors of , thus and and are adjacent in .

Third case: in Transformation . Since and according to (9).

(10): Transformation 1 keeps the -paths, because it keeps connectivity and the first coordinate becomes zero only at leaves. Transformation 2 destroys some -paths but all of them contain the saturated vertex which was handled by the transformation and whose fourth coordinate was at least .

(11): Transformation 1 does not split an -block, furthermore it keeps the number of vertices whose third coordinate is one and whose first and second coordinate are both zero in each -block.

Transformation 2 either does not split an -block and keeps the investigated quantities, or it splits an -block to two -blocks. But (10) guarantees that both blocks contain enough vertices whose third coordinate is one or both first and second coordinates are zero.

###### Claim

If Claim 4 holds for and there is a saturated vertex, then at least one of the two transformations can be applied to .

The first proposition of Claim 4 guarantees it.

###### Corollary

There is an , such that there is no saturated vertex in , furthermore , .

###### Lemma

If does not contain any saturated vertices and Claim 4 holds, then for each -block

 ∑a––∈Ba2−∑a––∈Ba3≤∑a––∈Ba1(Δ−2).

Definition:  Let be an -block in an auxiliary graph. We say that a vertex of is inner vertex if its first coordinate is positive, otherwise it is called a boundary vertex.

###### Claim

Consider an -block of an auxiliary graph . Let the number of the boundary and the number of inner vertices denoted by and , respectively. If holds for each then is satisfied.

###### Proof

Proof by induction: The base case is an -block with one inner vertex. This -block is the closed neighborhood of the only inner vertex, therefore the number of boundary vertices is at most . Now we assume that for any the inequality is true. Let . We take a spanning tree of the inner vertices and consider a leaf vertex . If we set to zero, then becomes a boundary vertex and at most boundary vertices, which are neighbors of , are dropped from the -block. The number of inner vertices is decreased by one, and the number of boundary vertices is decreased by at most . Using the induction hypothesis the proof is completed.

Proof of Lemma 4: Consider an -block and a boundary vertex of . Either or . Thus we have: where is the number of vertices in whose first two coordinates are zero. It is also clear that . Combining these observations and the previous claim:

 ∑a––∈Ba2+N(B)=b≤(Δ−2)i+2≤(Δ−2)∑a––∈Ba1+2.

Claim 4 implies that Claim 4 (11) holds for . This guarantees that . Therefore

 ∑a––∈Ba2+N(B)≤(Δ−2)∑a––∈Ba1+∑a––∈Ba3+N(B),
 ∑a––∈Ba2−∑a––∈Ba3≤(Δ−2)∑a––∈Ba1.

Proof of Lemma 4: We distinguish three cases depending on .

Case 1:

Let be the auxiliary graph which we obtained from by applying transformations until it does not contain any more saturated vertices. The last lemma holds for each -block, therefore:

 ∑B⎛⎝∑a––∈Ba2−∑a––∈Ba3⎞⎠≤∑B(Δ−2)∑a––∈Ba1.

Only boundary vertices can be included in multiple blocks, and the first and second coordinate of a boundary vertex is zero, thus:

 ∑a––∈Aka2−∑a––∈Aka3≤∑B⎛⎝∑a––∈Ba2−∑a––∈Ba3⎞⎠≤∑B(Δ−2)∑a––∈Ba1=(Δ−2)∑a––∈Aka1.

Using Claim 4 we obtain

 ∑a––∈A0a2−∑a––∈A0a3≤(Δ−2)∑a––∈A0a1.

Case 2:

If the graph consists of multiple connected components we may restrict our attention to the component containing the unit. Let be the number of double covered vertices. We first verify the lemma in the case . In this case the graph consists of a matching and isolated vertices. Thus, we must have , and we must show that . If the unit, , is isolated the result is trivial suppose the unit is in an edge . If , then . If , the . Suppose that and set . We have and

This completes the proof in the case. If then we may assume that the graph is a path or a cycle. In this case we have so we must show . However, it is easy to see that in a path or a cycle every cooperation vertex is adjacent to a double covered vertex and, moreover, that double covered vertex is on the path between the cooperation vertex and (possibly itself). It follows that there are at least as many double covered vertices as cooperation vertices, as desired.

Case 3:

We remind the reader that the problem with the case is that it is not possible to add in transformation 1.

is needed when is saturated in . In that case Transformation 1 handles and substitutes it with unsaturated descendants. If the degree of any of the descendants of is smaller than , then we can make adjacent to this vertex and the problem is eliminated. Otherwise has three neighbors: , and . The one whose fourth coordinate is minimal among them is , also and both and are saturated vertices.

Now we make one of ’s descendants saturated. We have to make sure that (8) holds for this saturated descendant therefore we have to make a few new transformations.

Case 1: (8) a) holds for


text:
Decide if a specific Turing machine halts on a specific string

Can you always decide if a specific Turing machine accepts a specific string?

If this is true, intuitively, it seams it would be implied that HALT could be decided, which is obviously not true. Otherwise what is the difference?

$$L_{HP-M'-x} = \begin{cases} 1 & \text{M' halts on x} \\ 0 & \text{otherwise} \end{cases}$$
The reason this language is decidable is because, given any $M'$ and $x$, this language must be either $\{1\}$ or $\{0\}$. In particular, this MUST be a finite language, and ALL finite languages are decidable.

format: plain


text:
filters.csf¶

The Cloth Simulation Filter (CSF) classifies ground points based on the approach outlined in [Zhang2016].

Default Embedded Stage

This stage is enabled by default

Example¶

The sample pipeline below uses CSF to segment ground and non-ground returns, using default options, and writing only the ground returns to the output file.

[
"input.las",
{
"type":"filters.csf"
},
{
"type":"filters.range",
"limits":"Classification[2:2]"
},
"output.laz"
]

Options¶

resolution

Cloth resolution. [Default: 1.0]

ignore

A range of values of a dimension to ignore.

returns

Return types to include in output. Valid values are “first”, “last”, “intermediate” and “only”. [Default: “last, only”]

threshold

Classification threshold. [Default: 0.5]

smooth

Perform slope post-processing? [Default: true]

step

Time step. [Default: 0.65]

rigidness

Rigidness. [Default: 3]

iterations

Maximum number of iterations. [Default: 500]

where

An expression that limits points passed to a filter. Points that don’t pass the expression skip the stage but are available to subsequent stages in a pipeline. [Default: no filtering]

where_merge

A strategy for merging points skipped by a ‘where’ option when running in standard mode. If true, the skipped points are added to the first point view returned by the skipped filter. If false, skipped points are placed in their own point view. If auto, skipped points are merged into the returned point view provided that only one point view is returned and it has the same point count as it did when the filter was run. [Default: auto]


text:
## Solving a Vector Differential Equation With Initial Conditions

We can solve vector differential equations by writing separate differential equations for each component. Solve these differential equations, then add them with the appropriate coordinate vectors to the give the answer to the question.
Example: solve the equation
$\frac{d^2 \mathbf{r}}{dt^2}+9 \mathbf{r}=2t \mathbf{j}$
with the initial conditions - where
$t=0$
,
$\mathbf{v}=2 \mathbf{i}$
m/s,
$\mathbf{r}= \mathbf{j}$
m
With
$\mathbf{r}= x \mathbf{i} + y \mathbf{j}$
, the equations of the components are
$\frac{d^2x}{dt^2}+9x=0$
(1_
$\frac{d^2y}{dt^2}+9y=2t$
(2)
(1) has solution
$x=Acos 3t+Bsin3t$
.
(2) has complementary solution
$y_c=Ccos 3t+Dsin3t$
.
We can find a particular solution
$y_p$
to (2) by assuming
$y_p=E+Ft$
and substituting into (2).
Differentiating twice gives zero, hence
$0+9*(E+Ft)=2t \rightarrow E=0, \; F=\frac{2}{9}\rightarrow y_p=\frac{2}{9}t$
.
Hence
$y=y_c+y_p=Ccos 3t+Dsin3t+ \frac{2}{9}t$
. Then
$\mathbf{r} =(Acos 3t+Bsin3t)+ \mathbf{i}+ (Ccos 3t+Dsin3t+ \frac{2}{9}t) \mathbf{j}$
.
Now use the initial conditions.
$\mathbf{v}=(-3A sin3t+3Bcost) \mathbf{i} + (-3Csin3t+3Dcos3t + \frac{2}{9}) \mathbf{j}$

$\mathbf{v}(0)=0 \mathbf{i}+ 2 \mathbf{j} =(3B) \mathbf{i} + (3D + \frac{2}{9}) \mathbf{j} \rightarrow B=0, \; D=\frac{2-2/9}{3}=\frac{16}{27}$

$\mathbf{r}(0)= \mathbf{i}+0 \mathbf{j}= (A) \mathbf{i}+ (C) \mathbf{j} \rightarrow A=1, \; C=0$
.
Then
$\mathbf{r} =Acos 3t \mathbf{i}+ ( \frac{16}{27} sin 3t+ \frac{2}{9}t) \mathbf{j}$
.


text:
Purchase

• System Options

Base System

This compact, stainless-steel countertop system includes a dual-hose and diverter valve which allows you to select filtered or unfiltered water. It serves as a terrific blend

of portability and countertop convenience.

NOTE: The Aquamini cannot be

converted for below sink use.

The Aquamini has not been tested, and make no claims

for the reduction of contaminants of health concern.

• Specifications

SKU

Housing Composition

Rubber Items

Inlet

Outlet

Approximate Capacity

Approx. Flow Rate

Water Pressure

Housing Dimensions

Particulate Retention Size

Housing Warranty

AQUAMINI1

Stainless Steel

Silicone

1/8" NPT

1/8" NPT

250 Gallons

0.5 gpm @ 60 psi

100 psi max/30 psi min

6" h x 5" w

Sub Micron

• Replacement Filter

Aquamini Replacement Filter

This solid carbon block filter is used

with the Aquamini filter unit.

Filter Capacity: 250 gallons

Purchase

• Documents

Multipure Products

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Multipure Community

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Product Services

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Multipure Services

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


text:
Invertible Matrix Theorem

## Invertible Matrix Theorem

Let $A$ be a square $n \times n$ matrix. Then the following statements are equivalent. That is, for a given $A$, the statements are either all true or all false.

1. $A$ is an invertible matrix.
2. $A$ is row equivalent to the $n \times n$ identity matrix.
3. $A$ has $n$ pivot position.
4. The equation $A \vec{x} = \vec{0}$ has only the trivial solution.
5. The columns of $A$ form a linearly independent set.
6. The linear transformation $\vec{x}$ to $A \vec{x}$ is one-to-one.
7. The equation $A \vec{x} = \vec{b}$ has at least one solution for each $\vec{b}$ in $\mathbb{R}^{n}$.
8. The columns of $A$ span $\mathbb{R}^{n}$.
9. The linear transformation $\vec{x}$ to $A \vec{x}$ maps $\mathbb{R}^{n}$ onto $\mathbb{R}^{n}$.
10. There is an $n \times n$ matrix $C$ such that $CA = I$.
11. There is an $n \times n$ matrix $D$ such that $AD = I$.
12. $A^{T}$ is an invertible matrix.
13. The columns of $A$ form a basis of $\mathbb{R}^{n}$.
14. $\mathrm{Col} \ A = \mathbb{R}^{n}$.
15. $\mathrm{dim} \ \mathrm{Col} \ A = n$.
16. $\mathrm{rank} \ A = n$.
17. $\mathrm{Nul} \ A = \left \{ \vec{0} \right \}$.
18. $\mathrm{dim} \ \mathrm{Nul} \ A = 0$.
19. The number $0$ is not an eigenvalue of $A$.
20. The determinant of $A$ is not zero; $\mathrm{det} \ A \neq 0$.
page revision: 2, last edited: 29 Apr 2015 00:20


text:
## anonymous 4 years ago Given that sin(x)=1/5 and sin(y)= 5/6, where x and y are acute angles, determine the exact value of sin (X + y)

1. Mertsj

$\sin (x+y)=sinxcosy+cosxsiny$

2. Mertsj

$\sin (x+y)=(\frac{1}{5})(\frac{\sqrt{11}}{6})+(\frac{2\sqrt{6}}{5})(\frac{5}{6})$

3. Mertsj

$\sin(x+y)=\frac{\sqrt{11}}{30}+\frac{10\sqrt{6}}{30}=\frac{\sqrt{11}+10\sqrt{6}}{30}$

4. anonymous

Thank you very much kind sir :)


text:
## College Physics (4th Edition)

The sign of $v_x$ is $~-~$
The object is moving in the $~-x~$ direction so the sign of $v_x$ is $~-~$


text:
Constant in the Poincare inequality for curl square integrable vector fields - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:07:18Z http://mathoverflow.net/feeds/question/106881 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106881/constant-in-the-poincare-inequality-for-curl-square-integrable-vector-fields Constant in the Poincare inequality for curl square integrable vector fields Shuhao Cao 2012-09-11T03:38:17Z 2012-09-11T03:38:17Z
$\newcommand{\v}[1]{\boldsymbol{#1}}$For an $u\in H^1(\Omega) = W^{1,2}(\Omega)$ where $\Omega$ is Lipschitz, we have

$${\|u - \frac{1}{\Omega} \int_{\Omega} u\|}_{L^2}\leq C {\|\nabla u \|}$$

and the Poincare constant is basically a multiple of diameter of the domain.

However in $\mathbb{R}^3$, the only similar result for $\mathbf{curl}$-square integrable vector fields $\v{u}$ would be:

$${\|\v{u} - \frac{1}{\Omega} \int_{\Omega} \v{u}\|}_{L^2} \leq {\|\mathbf{curl} \ \v{u}\|}$$

if $\v{u}$ is divergence free.

If not, suppose $\v{u}$'s divergence is not well-defined, then we could have:

$${\|\v{u} - \frac{1}{\Omega} \int_{\Omega} \v{u}\|}_{L^2(\Omega)} \leq C_1 \left(\|\v{u}\|_{L^2(\Omega)}^2+{\|\mathbf{curl} \ \v{u}\|}^2 \right)^{1/2}$$

Since we could still do Helmholtz decomposition $\v{u} = \v{w}+\nabla p$, qualitatively speaking, locally in the a compact subdomain $K\subset \Omega$, if the $\v{u}$ is more irrotational(that gradient field $\nabla p$ is dominant), then $C_1$ is closed to $1$, if the $\v{u}$ is more weakly-solenoidal($\v{w}$ is dominant), then the $C_1$ is more closed to $\sqrt{1+d^2}$.

I am curious if we could decompose the domain $\Omega$ into different parts, such that we estimate the Poincare constant locally and then put together to get a sharper bound?


text:
geerky42 Two blocks (with masses 20.5 kg and 68 kg) are connected by a string as shown. The pulley is frictionless and of negligible mass. The coeﬃcient of kinetic friction between block and machine is 0.257. Find the change in the kinetic energy of the block on the incline as it moves a distance of 15.4 m up the incline if the system starts from rest. one year ago one year ago

1. geerky42

2. geerky42

first, I have to set up equation for sum of force, find net force, then multiply it by the distance, right?

3. ndwelsh

reported abusive - CHEATING !!!!

4. geerky42

How is that cheat? I'm looking for a way to solve this problem.

5. geerky42

And my way doesn't work.

6. ndwelsh

So, report that problem as something you didn't solve

7. ndwelsh

everything else is on the side. Understood?

8. ndwelsh

are you learning physics or building problem solving skills?

9. geerky42

I just need help, I can't figure out how solve this problem... Thats why I am here... Isn't it what Openstudy is for?

10. geerky42

Both...?

11. ndwelsh

you can't cheat, this has to be stopped. Ask this question out of your knowledge of theory.

12. Yahoo!

hey @greeky42 he is just trolling just ignore him

13. ndwelsh

speak to me directly, like this: Aren't you trolling now?

14. ndwelsh

that's concern #1

15. ndwelsh

do not assume for me. Is that clear?

16. geerky42

And my theory is apparently wrong, and I don't know why. And it's isn't cheating. You are obviously trolling, just like Yahoo! said.

17. Yahoo!

$W = \Delta K.E$

18. Yahoo!

intial K.E is 0 brcoz the body was at rest..)

19. ndwelsh

It's not *YOUR* theory, it's your knowledge.

20. ndwelsh

so, it's knowledge which is wrong, theory is always there.

21. geerky42

@Yahoo! And $W = x \sum F$ right?

22. geerky42

My knowledge* Better, knowledge nazi?

23. Callisto

Sorry to interrupt. I think it's better to stop the discussion on cheating here. And also, it's okay to seek help for your homework, as long as you're looking for a way to learn how to do it, not just copying others work. @ndwelsh I think we'd better have a private talk.

24. ndwelsh

what is fun about substituting numbers to formulas? Aren't you striving for better degree? What are you supposed to learn? Physics, elementary principles of expressions and variables?

25. ndwelsh

@Callisto - who am I talking to now?

26. Yahoo!

nw ur job is to Find Work done..By the Body on incline

27. ndwelsh

Whatever you are trying to achieve in the future will unfold improperly. MARK MY WORDS NOW, bunch of puppets

28. Yahoo!

$W=F.S.\cos \theta$

29. geerky42

@ndwelsh Like, you think I take physics for absolutely no reason? Sure... And you are here, trolling and claiming everyone is cheating... I think your life has been unfolded improperly.

30. Yahoo!

Or another way to approach this is find accl

31. ndwelsh

Hold on there horse, don't you say "trolling" regarding my name any more? It's your stupid cheating Wikipedia type of philosophy that explains your inadequacy better than my life.

32. ndwelsh

answer now, what's wrong about using reference books better than theory books?

33. ndwelsh

Apparently I'm more knowledgable in this topic than you are

34. geerky42

Yet, I don't need you, fortunately. There are knowledgable beings who are wise enough not to troll in this site and are willing to help others. What about you? Answer now. What do you do with your life? Trolling? Well, that's pathetically sad. Beside you are wasting your time.

35. geerky42

@Yahoo! How can I find acceleration? its seems that there is not enough information.

36. ndwelsh

discussing my life at this point seems to be more off the topic. --- THAT'S FOR ADMINS TO TAKE NOTE don't you SPIT THAT POISON IN MY FACE, fraking DOLL?

37. ndwelsh

JUST GET THAT, CHEATER - BECOME PUNISHED FOR THAT IN FUTURE

38. geerky42

@ndwelsh Delight me.


text:
# NCERT Solutions For Class 10 Maths Chapter 14

## NCERT Solutions Class 10 Maths Statistics Types of statistics

### Ncert Solutions For Class 10 Maths Chapter 14 PDF Free Download

NCERT solutions class 10 maths chapter 14 statistics is one of the most important topics in Class 10 mathematics syllabus. Students must practice this chapter well to prepare maths more effectively. The class 10 maths chapter 14 statistics NCERT solutions is provided here to help students understand the concepts of the chapter in details. Students must practice the NCERT Solutions for class 10 maths chapter 14 thoroughly to score good marks in their class 10 board examination. Check the class 10 maths NCERT Solutions for chapter 14 pdf given below.

The topics covered in the chapter is given below

 Section Number Topic 14.1 Introduction 14.2 Mean of Grouped Data 14.3 Mode of Grouped Data 14.4 Median of Grouped Data 14.5 Graphical Representation of Cumulative Frequency Distribution 14.6 Summary

### NCERT Solutions Class 10 Maths Chapter 14 Exercises

Exercise – 1

Question 1:

A group of pupil has conducted a survey as a as the part of their college program, They collected examined data’s of plants from 20 houses and nearby areas. Find the mean of the collected plants from the given houses.

 No. of Plants Taken from 20 houses 0-2 2-4 4-6 6-8 8-10 10-12 12-14 Given number of houses 2 1 5 1 2 6 3

Name the method you use for finding the mean and why?

Solution:

 Class Interval fi xi fi xi 0-2 2 1 1 2-4 1 3 6 4-6 5 5 5 6-8 1 7 35 8-10 2 9 54 10-12 6 11 22 12-14 3 13 40 Sum fi=20 Sum fixi=163

Mean can be calculated as follows:

$\bar{x}= \frac{\Sigma f_{i}x_{i}}{\Sigma f_{i}}=\frac{163}{20}=8.15$

In this issues the $f_{i} and x_{i}$ are small so the direct method is given to solve the problem.

Question2:

The distributed wages is given for 50 workers working in the factory.

 Daily wages given to workers (in Rs) 100-120 120-140 140-160 160-180 180-200 Number of wage workers in factory 14 12 6 8 10

Find the mean of workers of daily wages given by the workers.

Solution:

In this case, value of xi is quite large and hence we should select the assumed mean method.

 Class given Interval fi xi di = xi – a fi di 100-120 14 110 -40 -480 120-140 12 130 -20 -280 140-160 6 150 0 0 160-180 8 170 20 120 180-200 10 190 40 400 Sum fi=50 Sum fi di = -240

Now, mean of deviations of daily wagesis calculated as follows:

$\bar{d}=\frac{\sum f_{i}d_{i}}{\sum f_{i}}=\frac{-240}{50}$

x = d + a = 150+(-4.8)= 145.20

Question 3:

This distribution shows that the money daily pocket given to students in the given area. The mean pocket money is Rs. 18. Find the f which is the missing frequency.

 Daily money allowance (in Rs) 11-13 13-15 15-17 17-19 19-21 21-23 23-25 Number of children 7 6 9 13 f 5 4

Solution:

 Class interval fi xi fixi 11-13 7 12 84 13-15 6 14 84 15-17 13 16 144 17-19 9 18 234 19-21 f 20 20f 21-23 4 22 110 23-25 5 24 96 Sum fi=44+f Sum fixi= 752+20f

We have;

$\bar{x}= \frac{\Sigma f_{i}x_{i}}{\Sigma f_{i}}$ $18= \frac{752+20f}{44+ f_{i}}$

18(44+18f) = 752+20f

792+18f = 752+20f

2f = 40

Missing frequency f= 20

Question4:

The number of 30 women were checked by one doctor and the distributed the heartbeat of them in following distribution table. Find the mean of heart beats of the given per minute for these thirty women, by choosing a suitable following method.

 Heartbeat per minute in given number 65-68 68-71 71-74 74-77 77-80 80-83 83-86 Number of 30 women 2 3 4 7 8 2 4

Solution:

 Class Interval fi xi di = xi – a fi di 65-68 2 66.5 -9 -18 68-71 3 69.5 -6 -24 71-74 4 72.5 -3 -9 74-77 7 75.5 0 0 77-80 8 78.5 3 21 80-83 2 81.5 6 24 83-86 4 84.5 9 18 Sum fi= 30 Sum fi di = 12

Now, mean can be calculated as follows:

$\bar{d}=\frac{\sum f_{i}d_{i}}{\sum f_{i}}=\frac{12}{30}=0.4$ $\bar{x}=\bar{d}+a=0.4+75.5=75.9$

Question 5:

The oranges were packed and were sold by the fruit seller in a  market. The numbers of oranges are arranged in different boxes by the fruit seller. Through the number of oranges the number of oranges are distributed in following manner.

 No.of oranges 50-52 53-55 56-58 89-61 62-64 No. of boxes 15 110 135 115 25

In the distributed pattern the number of oranges. Find the mean. Choose the method to find the mean:

Solution:

 Class interval fi xi di=x-a fi di 50-52 110 54 -6 90 53-55 15 51 -3 -330 56-58 135 60 0 0 59-61 25 57 3 345 62-64 115 63 6 150 Sum fi= 400 Sum fi di=75

Mean can be calculated as follows:

$\bar{d}=\frac{\Sigma f_{i}d_{i}}{\Sigma f_{i}}=\frac{75}{400}=0.1875$ $\bar{x}=\bar{d}+a=0.1875+57=57.1875$

In this case, there are wide variations in $f_{i}$ and hence assumed mean method is used.

Question 6:

The following distribution shows the food expenditure of the given households from the locality:

 Daily food expenditure (in Rs) 50-100 100-150 150-200 200-250 250-300 Number of given households 4 5 12 2 2

Find the mean daily expenditure on food by a suitable method.

Solution:

 Class Interval fi xi di= xi – a ui = di/h fiui 50-100 4 125 -100 -2 -8 100-150 5 175 -50 -1 -5 150-200 12 225 0 0 0 200-250 2 275 50 1 2 250-300 2 325 100 2 4 Sum fi = 25 Sum fiui = -7

Mean can be calculated as follows:

$\bar{x}=a+\frac{\sum f_{i}u_{i}}{\sum f_{i}}\times h$ $=225+\frac{-7}{25}\times 50 =225$

Question 7:

To find concentration in sulphur dioxide (in parts per million, i.e. ppm),The parts of data are collected by different areas from cities are given in distributed table:

 Concentration in SO2 (in ppm) Frequency of F 0.00-0.04 4 0.04-0.08 9 0.08-0.12 9 0.12-0.16 2 0.16-0.20 4 0.20-0.24 2

Give the mean of the sulphur dioxide collected from the given cities.

Solution:

 Class Interval fi xi fixi 0.00-0.04 9 0.02 0.08 0.04-0.08 4 0.06 0.54 0.08-0.12 9 0.10 0.90 0.12-0.16 2 0.14 0.28 0.16-0.20 2 0.18 0.72 0.20-0.24 4 0.22 0.44 Sum fi=30 Sum fixi=2.96

Mean can be calculated as follows:

$\bar{x}=\frac{\Sigma f_{i}x_{i}}{\Sigma f_{i}}=\frac{2.96}{30}=0.099 ppm$

Question 8:

The absentee record of 40 students is handled by the teacher for one complete term. Find the mean of absent days of the given students:

 Number of following days 0-6 6-10 10-14 14-20 20-28 28-38 38-40 Number of following students 10 11 4 7 3 4 1

Solution:

 Class Interval fi xi fixi 0-6 11 3 33 6-10 10 8 80 10-14 4 12 84 14-20 7 17 68 20-28 3 24 96 28-38 4 33 99 38-40 1 39 39 Sum fi = 40 Sum fixi= 499

Mean can be calculated as follows:

$\bar{x}=\frac{\sum f_{i}x_{i}}{\sum f_{i}}$= $\frac{499}{40}$=12.4

Question 9:

The data of the literacy digit from the 35 cities is given in the following table. Find the mean of the 35 literacy cities.

 Literacy rate from 35cities (in %) 40-45 50-55 60-65 70-75 80-85 Cities in values 10 3 8 11 3

Solution:

 Class Interval fi xi di=xi-a ui=di/h fiui 40-45 10 50 -20 -2 -6 50-55 3 60 -10 -1 -10 60-65 8 70 0 0 0 70-75 11 80 10 1 8 80-85 3 90 20 2 6 Sum fi=35 Sum fiui= -2

Mean can be calculated as follows:

$\bar{x}=a+\frac{\Sigma f_{i}u_{i}}{\Sigma f_{i}}\times h$ $= 70+\frac{-2}{35}\times 10=69.42$

EXERCISE – 2

Question 1:

The age of patients admitted in a hospitals are given in the following table for a complete year.

 Age (in years) 5-15 15-25 25-35 35-45 45-55 55-65 Number of patients 6 11 21 23 14 5

Calculate the mode and mean of the data above. Compare and interpret the two measures of central tendency.

Solution:

Modal class = 35-45, length = 35, height = 10, $a_{1} = 23, a_{0} = 21\, and\, a_{3} = 14$

Therefore, Mode = $l +\frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}}\times h$

= $35+\left ( \frac{23-21}{2\times 23-21-14} \right )\times 10$

= $35+\frac{2}{11}\times 10=36.8$

Calculating Mean

 CLASS INTERVAL ai zi aizi 5-15 6 10 60 15-25 11 20 220 25-35 21 30 630 35-45 21 30 920 45-55 14 50 700 55-65 5 60 300 Sum ai = 80 Sum aizi= 2830

$\bar{p}=\frac{\sum a_{i}x_{i}}{\sum a_{i}}=\frac{2830}{80}=35.37$

$\ therefore$The mode of data displays that the maximum number of patients is in the age group of 26.8, whereasthe average age of all the patients is 35.37.

Question 2:

The data given below provides the information for the observed lifetime (in hours) of 225 electrical components:

 Lifetime ( in hours) 0 – 20 20 – 40 40 – 60 60 – 80 80 – 100 100  – 120 Frequency 10 35 52 61 38 29

Find the modal lifetimes of the components.

Solution:

Modal class =  60-80, l = 60,$a_{1} = 61, a_{0} = 52, a_{2} = 38$ and h = 20

$Mode = l + \left ( \frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}} \right )\times h$

$= 60 + \left ( \frac{61 – 52}{2 \times 61 – 52 – 38 } \right ) \times 20$

$= 60 + \frac{9}{32} \times 20 = 65.62$

Question 3:

The total monthly household expenses of 200 families of a town are given in the following table. Calculate the modal monthly expenses of the families.  Also, calculate the mean monthly expenses.

 Expenses Number of families 1000 – 1500 24 1500 – 2000 40 2000 – 2500 33 2500 – 3000 28 3000 – 3500 30 3500 – 4000 22 4000 – 4500 16 4500 – 5000 7

Solution:

Modal class = 1500-2000, l = 1500,$a_{1} = 40, a_{0} = 24, a_{2} = 33$ and h = 500

$Mode = l + \left ( \frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}} \right )\times h$

$= 1500 + \left ( \frac{40 – 24}{2 \times 40 – 24 – 33} \right ) \times 500$

$= 1500 + \left ( \frac{16}{23} \right ) \times 500 = 1847.82$

Calculation of mean:

 Class Interval ai zi di =zi – b ui= di/h aiui 1000 – 1500 24 1250 -1500 -3 -72 1500 – 2000 40 1750 -1000 -2 -80 2000 – 2500 33 2250 -500 -1 -33 2500 – 3000 28 2750 0 0 0 3000 – 3500 30 3250 500 1 30 3500 – 4000 22 3750 1000 2 44 4000 – 4500 16 4250 1500 3 48 4500 – 5000 7 4750 2000 4 28 ai = 200 aiui = -35

$\bar{p}=\frac{\sum a_{i}x_{i}}{\sum a{i}}\times h$ $= 2750 – \frac{35}{200} \times 500$

= 2750 – 87.5 = 2662.50

Question 4:

The state – wise teacher- student ratio in a college in India are given in the following table. Calculate the mean and mode of the given data. Interpret the two measures.

 Number of students per teacher Number of states/UT 15 – 20 3 20 – 25 8 25 – 30 9 30 – 35 10 35 – 40 3 40 – 45 0 45 – 50 0 50 – 55 2

Solution:

Modal class = 30-35, l = 30, $a_{1} = 10, a_{0} = 9, a_{2} = 3$ and h = 5

$Mode = l +\left ( \frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}} \right )\times h$

$= 30 – \left ( \frac{20 – 9}{2 \times 10 – 9 – 3 } \right ) \times 5$

$= 30 – \frac{1}{8} \times 5 = 30.625$

Calculating mean:

 Number of students per teacher ai zi di= zi –b ui = ui/h aiui 15 – 20 3 17.5 -15 -3 -9 20 – 25 8 22.5 -10 -2 -16 25 – 30 9 27.5 -5 -1 -9 30 – 35 10 32.5 0 0 0 35 – 40 3 37.5 5 1 3 40 – 45 0 42.5 10 2 0 45 – 50 0 47.5 15 3 0 50 – 55 2 52.5 20 4 8 Sum ai = 35 sum aiui= -23

$\bar{p}=\frac{\sum a_{i}x_{i}}{\sum a_{i}}\times h$

$= 30.5 – \frac{23}{35}\times 5$

$= 30.5 – \frac{23}{7} = 29.22$

Therefore, from the mode we know that the maximum number of states has 30 – 35 students per teacher, and from the mean we know that the average ratio of students per teacher is 29.22

Question 5:

Provided table shows the total runs scored by some of the top batsman of the world in one-day cricket matches.

 Runs Scored Number of Batsman 3000 – 4000 4 4000 – 5000 18 5000 – 6000 9 6000 – 7000 7 7000 – 8000 6 8000 – 9000 3 9000 – 10000 1 10000 – 11000 1

Calculate the mode of the given information.

Solution:

Modal class = 4000-5000, l = 4000, $a_{1} = 18, a_{0} = 4, a_{2} = 9$ and h = 1000

$Mode = l + \left ( \frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}} \right )\times h$ $= 4000 + \left ( \frac{18 – 4}{2 \times 18 – 4 -9} \right )\times 1000$ $= 4000 + \left ( \frac{14}{23} \right )\times 1000 = 4608.70$

Question 6:

A complete observation of the number of cars on the roads for 100 periods of 3 minutes are summarized in the following table. Calculate the mode of the data.

 Number of cars 0 – 10 10 – 20 20 – 30 30 – 40 40 – 50 50 – 60 60 – 70 70 – 80 Frequency 7 14 13 12 20 11 15 8

Solution:

Modal class = 40 – 50, l = 40, $a_{1} = 20, a_{0} = 12, a_{2} = 11$ and h = 10

$Mode = l + \left ( \frac{a_{1}-a_{0}}{2a_{1}-a_{0}-a_{2}} \right )\times h$

$= 40 + \left ( \frac{20 – 12}{2 \times 20 – 12 – 11} \right )\times 10$

$= 40 + \left ( \frac{8}{17} \right )\times 10 = 44.70$

Exercise 3

Question 1:

The following frequency distribution gives the monthly consumption of an electricity of 68 consumers in a locality. Find the median, mean and mode of the data and compare them.

 Monthly consumption(in units) No. of customers 65-85 4 85-105 5 105-125 13 125-145 20 145-165 14 165-185 8 185-205 4

Solution:

 Class Interval Frequency Cumulative frequency 65-85 4 4 85-105 5 9 105-125 13 22 125-145 20 42 145-165 14 56 165-185 8 64 185-205 4 68 N=68

Where, n = 68 and hence $\frac{n}{2}=34$

Hence, the median class is 125-145 with cumulative frequency = 42

Where, l = 125, n = 68, cf = 22, f = 20, h = 20

Median is calculated as follows:

Median=$l+\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$

=$125+\left ( \frac{34-22}{20} \right )X20$

=125+12=137

Mode = Modal class = 125-145, $f_{1} = 20, f_{0} = 13, f_{2} = 14$ & h = 20

Mode=$l+\left ( \frac{f_{1}-f_{0}}{2Xf_{1}-f_{0}-f_{2}} \right )Xh$

=$125+\left ( \frac{20-13}{2X20-13-14} \right )X20$

=$125+\frac{7}{13}X20$

=125+10.77

=135.77

Calculate the Mean:

 Class Interval fi xi di=xi-a ui=di/h fiui 65-85 4 75 -60 -3 -12 85-105 5 95 -40 -2 -10 105-125 13 115 -20 -1 -13 125-145 20 135 0 0 0 145-165 14 155 20 1 14 165-185 8 175 40 2 16 185-205 4 195 60 3 12 Sum fi= 68 Sum fiui = 7

$\bar{x}=a+\frac{\sum f_{i}u_{i}}{\sum f_{i}}X h$ $=135+\frac{7}{68}X20$

=137.05

Mean, median and mode are more/less equal in this distribution.

Question 2:

If the median of a distribution given below is 28.5 then, find the value of an x &y.

 Class Interval Frequency 0-10 5 10-20 x 20-30 20 30-40 15 40-50 y 50-60 5 Total 60

Solution:

n = 60

Where,$\frac{n}{2}$ = 30

Median class is 20 – 30 with a cumulative frequency = 25 + x

Lower limit of median class = 20, cf = 5 + x , f = 20 & h = 10

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$

Or,28.5=20+$\left ( \frac{30-5-x}{20} \right )X10$

Or,$\frac{25-x}{2}$

Or,   25-x=17

Or,    x= 25 – 17   =8

Now, from cumulative frequency, we can identify the value of x + y as follows:

60=5+20+15+5+x+y

Or, 45+x+y=60

Or, x + y=60-45=15

Hence, y = 15 – x= 15 – 8 = 7

Hence, x = 8  &  y = 7

Question 3:

The Life insurance agent found the following data for the distribution of ages of 100 policy holders. Calculate the median age, if policies are given only to the  persons whose age is 18 years onwards but less than the 60 years.

 Age(in years) Number of policy holder Below 20 2 Below 25 6 Below 30 24 Below 35 45 Below 40 78 Below 45 89 Below 50 92 Below 55 98 Below 60 100

Solution:

 Class interval Frequency Cumulative frequency 15-20 2 2 20-25 4 6 25-30 18 24 30-35 21 45 35-40 33 78 40-45 11 89 45-50 3 92 50-55 6 98 55-60 2 100

Where, n = 100 and $\frac{n}{2}$ = 50

Median class = 35-45

Then, l = 35, cf = 45, f = 33 & h = 5

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$ $=35+\left ( \frac{50-45}{33} \right )X5$ $=35+\left ( \frac{25}{33} \right )$

=35.75

Question 4:

The lengths of 40 leaves in a plant are measured correctly to the nearest millimetre, and the data obtained is represented as in the following table:

 Length(in mm) Number of leaves 118-126 3 127-135 5 136-144 9 145-153 12 154-162 5 163-171 4 172-180 2

Find the median length of leaves.

Solution:

 Class Interval Frequency Cumulative frequency 117.5-126.5 3 3 126.5-135.5 5 8 135.5-144.5 9 17 144.5-153.5 12 29 153.5-162.5 5 34 162.5-171.5 4 38 171.5-180.5 2 40

Where, n = 40 and $\frac{n}{2}$ = 20

Median class = 144.5-153.5

then, l = 144.5, cf = 17, f = 12 & h = 9

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$ $=144.5+\left ( \frac{20-17}{12} \right )X9$ $=144.5+\left ( \frac{9}{4} \right )$

=146.75

Question 5:

The following table gives the distribution of a life time of 400 neon lamps.

 Lifetime(in hours) Number of lamps 1500-2000 14 2000-2500 56 2500-3000 60 3000-3500 86 3500-4000 74 4000-4500 62 4500-5000 48

Find the median lifetime of a lamp.

Solution:

 Class Interval Frequency Cumulative 1500-2000 14 14 2000-2500 56 70 2500-3000 60 130 3000-3500 86 216 3500-4000 74 290 4000-4500 62 352 4500-5000 48 400

Where, n = 400 &$\frac{n}{2}$ = 200

Median class = 3000 – 3500

Therefore, l = 3000, cf = 130, f = 86 & h = 500

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$ $=3000+\left ( \frac{200-130}{86} \right )X500$

=3000+406.97

=3406.97

Question 6:

In this 100 surnames were randomly picked up from a local telephone directory and the frequency distribution of the number of letters in English alphabets in the surnames was obtained as follows:

 Number of letters 1-4 4-7 7-10 10-13 13-16 16-19 Number of surnames 6 30 40 16 4 4

Determine the number of median letters in the surnames. Find the number of mean letters in the surnames and also, find the size of modal in the surnames.

Solution: To Calculate median:

 Class Interval Frequency Cumulative Frequency 1-4 6 6 4-7 30 36 7-10 40 76 10-13 16 92 13-16 4 96 16-19 4 100

Where, n = 100 &$\frac{n}{2}$ = 50

Median class = 7-10

Therefore, l = 7, cf = 36, f = 40 & h = 3

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$ $=7+\left ( \frac{50-36}{40} \right )X3$ $=7+\left ( \frac{14}{40} \right )X3$

=8.05

Calculate the Mode:

Modal class = 7-10,

Where, l = 7, f1 = 40, f0 = 30, f2 = 16 & h = 3

Mode=$l+\left ( \frac{f_{1}-f_{0}}{2Xf_{1}-f_{0}-f_{2}} \right )Xh$

=$7+\left ( \frac{40-30}{2X40-30-16} \right )X3$

=$7+\frac{10}{34}X3$

=7.88

Calculate the Mean:

 Class Interval fi xi fixi 1-4 6 2.5 15 4-7 30 5.5 165 7-10 40 8.5 340 10-13 16 11.5 184 13-16 4 14.5 51 16-19 4 17.5 70 Sum fi = 100 Sum fixi = 825

$\bar{x}=a+\frac{\sum f_{i}u_{i}}{\sum f_{i}}X h$ $=\frac{825}{100}$

=8.25

Q7. The distributions of below gives a weight of 30 students of a class. Find the median weight of a students.

 Weight(in kg) 40-45 45-50 50-55 55-60 60-65 65-70 70-75 Number of students 2 3 8 6 6 3 2

Solution:

 Class Interval Frequency Cumulative frequency 40-45 2 2 45-50 3 5 50-55 8 13 55-60 6 19 60-65 6 25 65-70 3 28 70-75 2 30

Where, n = 30 and $\frac{n}{2}$= 15

median class = 55-60

therefore, l = 55, cf = 13, f = 6 & h = 5

Median=l+$\left ( \frac{\frac{n}{2}-cf}{f} \right )Xh$ $=55+\left ( \frac{15-13}{6} \right )X5$ $=55+\left ( \frac{5}{3} \right )$

=56.67

Question 7:

The distribution shows the pocket money of students in an area. The mean pocket money is Rs 18. Find the missing frequency f.

 Daily pocket allowance (in Rs) 11-13 13-15 15-17 17-19 19-21 21-23 23-25 Number of children 07 06 09 013 F 05 04

Solution:

 Class interval fi xi fixi 11-13 07 012 84 13-15 06 014 84 15-17 09 016 144 17-19 013 018 234 19-21 f 020 20f 21-23 05 022 110 23-25 04 024 96 Sum fi = 44+f Sum fixi = 752+20f

We have,

Mean pocket money, $x_{i}$ = 18(given)

Hence substituting for fixi,

18(44+f) = 752 + 20f

Or, 792 + 18f = 752 + 20f

Or, 2f = 40

$\rightarrow f=20$

The modern world is highly data-oriented and it becomes necessary to know to represent data in a meaningful way. The branch of mathematics which deals with the representation of data in a meaningful way is known as statistics. Let us look at a few examples of how statistics is useful in our daily life

• The data that you see in the weather forecast section of the news is due to the goodwill of statistics.
• The selection of a player in any sport is mostly made based on the player’s statistical performance report.

In this chapter, students are introduced to histograms, graphical representations of data in the form of bar charts, cumulative frequency tables and frequency polygons. Students will be introduced to the three measures of central tendency. The three measures of central tendency are mean, median and mode.

Byju’s is India’s largest k-12 learning app with top-notch teachers from across the nation with excellent teaching skills. Find notes, question papers for various other subjects like Mathematics, Biology, Chemistry and many competitive exams as well. Enjoy learning with great experience. Stay tuned to know more about NCERT Solutions and preparation tips. To know more about NCERT solutions you can register to BYJU’s or download our app for simple and interesting content.


text:
# A block moving on the floor and hitting the walls

Do we have to keep this is mind for the second collision as well?

Why not :). But after calculating the second reflection angle, you may get negative value of angle. Thus the behaviour of the second collision is quite different from the first one. Just think of it in the physics sense and give an explanation of how the block should reflect after the second collision

1 симпатия

I have got this equation for reflection angle from second collision. I have taken beta as the refle tion angle from wall 2.

this equation is essentially the same as what i did under wrong assumption that the speed doesn’t change. use my another tip Help in this question - #36 от пользователя Alisher

1 симпатия

I am not able to get the answer.

when expressing the conservation of momentum along the wall, you have to write

\mu \int Ndt = mv_0(\cos37-v_\tau) = \mu\cdot 2mv_0\sin37 \Rightarrow \\ v_\tau = v_0(\cos37 - 2\mu\sin37).

here I denote \beta in the way I drew above, i.e. \tan\beta=v_\tau/v_0\sin37 = \cot44.82 - 2\mu_1, so \beta = 44.82\degree. Also,

v_1 =\sqrt{(v_0\sin37)^2+v_\tau^2}=\frac{v_0\sin37}{\cos\beta}= 8.48 \space \text{m/s}.

Then I use the same thing to calculate second reflection angle (remember it’s with respect to the normal line!):

\gamma = \arctan(\cot44.82 - 2\mu_2) = -26.26\degree.

Well, the \gamma<0 thing does not sound very physical; the result implies that the block has changed its direction. But the main catch is that friction force \mu N occurs only when relative movement occurs, so apparently during this infinitesimally short interval of time, the block has stopped moving relative to the second wall. Thus, the real reflection angle is 0, i.e. perpendicular to the second wall. Therefore, we get

v_2 = v_1\sin44.82 = 5.98\space\text{m/s}.
3 симпатии

Oh my god… finally I understand the whole problem… Thanks a lot!

1 симпатия

One more doubt, why did you take the sin component of V1 in the last part?

because modulus of perpendicular component of the velocity is conserved, and 44.8° is counted from the wall’s face, so i used sine

1 симпатия

Ohh, and one more thing, in the first line you used cos37 - V(parallel to first wall) is this correct ? How ?

yes, because v_\tau and v_0\cos37 are in the same direction, but the friction slows down this velocity component

1 симпатия

But you have taken out V0, and inside bracket you are still having v (parallel) ? How is this correct?

I think costheta should also have V0 written beside it…

1 симпатия

ah, i see. there should be v_\tau/v_0, but it doesn’t change the solution

1 симпатия

Is this correct??

yeah, this is what i meant

1 симпатия

Ok. Thank you!


text:
If the sum of n terms of an A.P. be 3n2 + n and its common difference is 6,
Question:

If the sum of $n$ terms of an A.P. be $3 n^{2}+n$ and its common difference is 6 , then its first term is

(a) 2

(b) 3

(c) 1

(d) 4

Solution:

In the given problem, the sum of n terms of an A.P. is given by the expression,

$S_{n}=3 n^{2}+n$

Here, we can find the first term by substitutingas sum of first term of the A.P. will be the same as the first term. So we get,

$S_{n}=3 n^{2}+n$

$S_{1}=3(1)^{2}+(1)$

$=3+1$

$=4$

Therefore, the first term of this A.P is $a=4$. So, the correct option is (d).


text:
# Why haven't we seen the big bang?

The Andromeda galaxy is 2,538,000 light years away, so if we view Andromeda from a telescope, we see Andromeda how it was 2,538,000 years ago. Now the diameter of the visible universe is 92 billion light years so if we say that we are at the center so the radius is 46 billion light years. So, if we see the farthest we can from our point, that will be 46 billion light years, so it means that we have seen the universe how it was 46 billion years ago, so why can't we say that universe was born 46 billion years ago?

And if still someone argues that 13.8 billion years ago universe was born then we should have seen the universe of how it was even before the singularity.

And if my logic of 49 billion years seems right then the thing we say that universe was born 13.8 billion years ago should be wrong, shouldn't it?

Hoping for a excellent answer with excellent explanation! :)

There are two parts to your question. First, why can we see things "46 billion light years away" if the Universe is only about 13.8 billion years old? Because the Universe is expanding. How far does a photon travel in 13.8 billion years in an expanding Universe? It depends on the rate of expansion. I'll give a simplified example to illustrate the point:

Imagine a Universe that is 10 billion years old. Its expansion history is simple. It started out with size $R$, which remained constant for 5 billion years, then the size suddenly doubled to $2R$, and remained constant for another 5 billion years. So, after 10 billion years, how far is the photon from its starting point? Well, it travels 5 billion light years in the first 5 billion years. When the size of the Universe doubles, so does the space between it and its point of origin, so just after the doubling it is 10 billion light years from where it started. Then in the next 5 billion years it travels another 5 billion light years, ending 15 billion light years from where it started. Notice that the constant speed of light from special relativity comes through intact here - the photon ends 15 billion light years from where it started after 10 billion years, but always moves at speed $c$ and only "travelled" 10 billion light years. Obviously a sudden doubling of size is not realistic, but the same idea applies to a more gradual, smooth expansion. Note that the expansion does not necessarily need to be "faster than light" (whatever that means). Any expansion at all will mean that the photon will be further from its starting point than expected in a static Universe when it arrives.

Second part to your question: why can't we see the Big Bang? Because a photon cannot reach us directly from the Big Bang. On a sunny day, I can see the Sun clearly because most of its photons that I observe leave the solar surface and travel along unimpeded to reach me. If it's cloudy, there's still sunlight - solar photons are reaching me - but I can't see the Sun directly because the photons are scattered along the way by the clouds. The early Universe was "cloudy" - it was full of an ionized plasma that scattered photons very frequently. As the Universe expanded and the plasma cooled, it eventually became transparent to the photons and the "Big Bang photons" have been travelling more or less without scattering ever since. This "surface of last scattering" is visible as the cosmic microwave background, and is the closest we'll get to seeing the Big Bang (except perhaps we could observe neutrinos or gravity waves from beyond the CMB because they are not scattered as strongly in the early Universe).

• Kyle in your second paragraph you said that light travels 15 billion light years in 10 years, but i didn't get that and you said its because of relativity but there are many things in relativity and excatly what part of relativity are you talking about? Please edit your answer and explain me better of what you are talking about in second paragraph. Hope you give a better answer. :) Apr 23, 2015 at 17:18
• @Bhavesh hopefully that's clearer? Apr 23, 2015 at 17:21
• @Bhavesh Simply put, imagine A and B are two points that are 5 billion light years apart. A photon travels from A to B in 5 billion years. But then the universe suddenly expands to twice it's size, the distance between A and B is now measured to be 10 billion light years. The light travelled from A to B (which we measure as 10 billion light years apart), taking only 5 billion years to do so. Apr 23, 2015 at 18:03
• @Bhavesh The light only traveled 10 billion light years, but the point where the light originated is 15 billion light years away by the time the light from it has traveled that far. The intervening space expanded, making the distance larger.
– Kyle
Apr 23, 2015 at 18:04
• @Bhavesh that's the idea, yes. The "sudden" doubling in size is not realistic, it is more gradual throughout the travel of the photon, but it's the same idea. The space already passed is growing behind the photon (of course so is the space ahead). Apr 24, 2015 at 2:27


text:
Address 2127 Holly Ln, Solvang, CA 93463 (805) 691-1397

# monte carlo standard error wiki Los Olivos, California

Env. Taking averages of derivative payoffs at points in a low-discrepancy sequence is often more efficient than taking averages of payoffs at random points. National Center for Health Statistics (24). P. (2004-12-01). "Population Monte Carlo".

On average, the approximation improves as more grains are dropped. Savvides, Cyprus Development Bank - Project Financing Division. "Risk Analysis in Investment Appraisal". External links A detailed discussion of measurements and the propagation of uncertainty explaining the benefits of using error propagation formulas and Monte Carlo simulations instead of simple significance arithmetic Uncertainties and A similar approach is used in calculating value at risk.[18][19] Monte Carlo Methods are used for personal financial planning.[20][21] For instance, by simulating the overall market, the chances of a 401(k)

Application to Non Linear Filtering Problems". This approach is accurate in a wide variety of settings, has reasonable computation requirements, and produces reasonably narrow intervals.[citation needed] Example applications This section includes a list of references, related reading Given the measured variables with uncertainties, I ± σI and V ± σV, and neglecting their possible correlation, the uncertainty in the computed quantity, σR is σ R ≈ σ V If the error estimate is larger than the required accuracy the integration volume is divided into sub-volumes and the procedure is recursively applied to sub-volumes.

Annals of Statistics, 9, 130. ^ Wu, C.F.J. (1986). "Jackknife, bootstrap and other resampling methods in regression analysis (with discussions)". ISBN 0-471-71575-1 Good, P. (2005) Introduction to Statistics Through Resampling Methods and Microsoft Office Excel. Johnson, S. T.; Dodd, R.

As a result, we need to use a distribution that takes into account that spread of possible σ's. New York: Marcel-Dekker Good, Phillip I. (2005) Permutation, Parametric and Bootstrap Tests of Hypotheses, 3rd ed., Springer ISBN 0-387-98898-X Good, P (2002). "Extensions of the concept of exchangeability and their applications". See also Accuracy and precision Bootstrap aggregating Empirical likelihood Imputation (statistics) Reliability (statistics) Reproducibility References ^ Efron, B.; Tibshirani, R. (1993). Numerical Solution of Stochastic Differential Equations.

This expression is only approximate, in fact E  [ σ ^ ] = σ ⋅ ( 1 + 1 16 n 2 + 3 16 n 3 + O ( Retrieved 2010-09-24. ^ John Norstad (February 2, 2005). "Financial Planning Using Random Walks" (PDF). ISBN 0-387-94527-X. Weinzierl, Introduction to Monte Carlo methods, W.H.

doi:10.1088/0031-9155/55/17/021. qfinance.com. The expected value of the sample variance is[5] E [ s 2 ] = σ 2 [ 1 − 2 n − 1 ∑ k = 1 n − 1 ( Percentile Bootstrap.

This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the a priori distribution is available. Monte Carlo methods were first introduced to finance in 1964 by David B. It may be defined by the absolute error Δx. Gaussian process regression bootstrap When data are temporally correlated, straightforward bootstrapping destroys the inherent correlations.

Zamora and D. New York: John Wiley & Sons. For example, the 68% confidence limits for a one-dimensional variable belonging to a normal distribution are ± one standard deviation from the value, that is, there is approximately a 68% probability P.; Brereton, T.; Taimre, T.; Botev, Z.

Acta Numerica. 7. The extent of this bias depends on the nature of the function. Approximate Tests of Correlation in Time-Series. There is often considerable interest in whether the sampling distribution can be approximated by an asymptotic distribution, which corresponds to the limiting case either as the number of random samples of

Contents 1 History 2 Approach 3 Discussion 3.1 Advantages 3.2 Disadvantages 3.3 Recommendations 4 Types of bootstrap scheme 4.1 Case resampling 4.1.1 Estimating the distribution of sample mean 4.1.2 Regression 4.2 Simulation and Optimization in Finance: Modeling with MATLAB, @Risk, or VBA. Experimental results. It is often applied to stochastic filters such as the Kalman filter or particle filter that forms the heart of the SLAM (simultaneous localization and mapping) algorithm.

Journal of Mixed Methods Research. 7 (1): 79–95. In the paper, Halton, Sobol, and Faure sequences for quasi-Monte Carlo are compared with the standard Monte Carlo method using pseudorandom sequences. This approximate formula is for moderate to large sample sizes; the reference gives the exact formulas for any sample size, and can be applied to heavily autocorrelated time series like Wall Retrieved 2010-09-24. ^ Carlos Blanco, Josh Gray & Marc Hazzard. "Alternative Valuation Methods for Swaptions: The Devil is in the Details" (PDF).

doi:10.1214/aos/1176350142. ^ Mammen, E. (Mar 1993). "Bootstrap and wild bootstrap for high dimensional linear models".


text:
# Variety of algebras

The notion of "variety of algebras" is fundamental to the foundations of the branch of mathematics known as universal algebra and also plays an important role in group theory.

## Definition

### Equational definition

A variety of algebras is defined as the collection of all algebras of a particular signature and satisfying a particular collection (not necessarily finite) of identities. Below, the terms signature and identity are explained.

Signature refers to a function from a fixed set (that we may call the operator domain) to $\mathbb{N}_0$ (the set of nonnegative integers). The elements of the operator domain are the "operators" and the signature sends each operator to a nonnegative integer that is its "arity." An algebra of a given signature is defined to be a set equipped with operations as follows: for each operator in the operator domain, there is a $n$-ary operation from the set to itself where $n$ equals the arity of the operator.

For instance, a signature where the image of the operator domain is (in order) $(2,1,3,2)$ means that the algebras of that signature are sets $S$ equipped with (labeled) operations $S \times S \to S, S \to S, S \times S \times S \to S, S \times S \to S$. Note that which operation is what matters, so for instance, the roles of the two binary operations here are not interchangeable.

Note that operators of arity zero are constant functions.

Identity refers to an equality of two formal expressions where both expressions are constructed using the operators in the operator domain, respecting arity. An algebra is said to satisfy the identity if that identity holds for all choices of elements in the algebra. For instance, associativity is an identity. Explicitly, for a binary operation $*$, associativity states that $(a * b) * c = a * (b * c)$. A magma (set with a binary operation) "satisfies associativity" if this holds for all $a,b,c$ in the set, in which case it is called a semigroup.

Identities can connect two or more operations. For instance, $a * (b + c) = (a * b) + (a * c)$ is an identity connecting two binary operations, $*$ and $+$.

### HSP definition

A variety of algebras is defined as a collection of all algebras of a particular signature that is closed under taking homomorphisms, subalgebras, and arbitrary direct products.

### Equivalence of definitions

Further information: Birkhoff-von Neumann theorem

## Particular cases

Algebraic structure that forms a variety of algebras Signature (operators and their arities) Identities Variety information page
magma (set with a binary operation) one operator $*$ of arity 2 none --
semigroup (set with an associative binary operation) one operator $*$ of arity 2 $(a * b) * c = a * (b * c)$ (associativity) --
monoid (set with an associative binary operation having a neutral element) two operators:
$*$ (multiplication) of arity 2
$e$ (identity element or neutral element) of arity 0
$(a * b) * c = a * (b * c)$ (associativity)
$a * e = a$
$e * a = a$
--
group (set with an associative binary operation having a neutral element and with an inverse map) three operators: $*$ (multiplication) of arity 2
$e$ (identity element or neutral element) of arity 0
$()^{-1}$ (inverse map) of arity 1
$(a * b) * c = a * (b * c)$ (associativity)
$a * e = a$
$e * a = a$
$a * a^{-1} = e$
$a^{-1} * a = e$
variety of groups
Lie ring the operators for a group, plus the Lie bracket $[ \ , \ ]$ of arity 2 all the identities for an abelian group, plus the bilinearity, alternation, and Jacobi identity variety of Lie rings