text:
Sign Up, it unlocks many cool features! So, a topological sort … 1. All Topological Sorts of a Directed Acyclic Graph, Lexicographically Smallest Topological Ordering, Detect cycle in Directed Graph using Topological Sort, Topological Sort of a graph using departure time of vertex, OYO Rooms Interview Experience for Software Developer | On-Campus 2021, Samsung Interview Experience for R&D (SRI-B) | On-Campus 2021, Most Frequent Subtree Sum from a given Binary Tree, Number of connected components of a graph ( using Disjoint Set Union ), Amazon WoW Program - For Batch 2021 and 2022, Smallest Subtree with all the Deepest Nodes, Construct a graph using N vertices whose shortest distance between K pair of vertices is 2, Data Structures and Algorithms – Self Paced Course, We use cookies to ensure you have the best browsing experience on our website. The key idea of how PCR aims to do this, is to use PCA on the dataset before regression. Below image is an illustration of the above approach: Following are the implementations of topological sorting. In topological sorting, we use a temporary stack. Both of them are correct! using a BST, Trie, or HashTable to implement a map, heaps to implement a Priority Queue), and finally algorithms on graphs. Ridge regression is an efficient regression technique that is used when we have multicollinearity or when the number of predictor variables in a set exceed the number of observations. Oct 30th, 2020. Solving Using In-degree Method. Okay so reverse DFS postorder of a DAG is a topological order. There can be more than one topological sorting for a graph. In topological sorting, we use a temporary stack. Please see the code for Depth First Traversal for a disconnected Graph and note the differences between the second code given there and the below code. Topological sorting only works for directed acyclic graphs $$\left({DAG}\right),$$ that is, only for graphs without cycles. code. Let’s check the way how that algorithm works. There are two main ways to perform topological sort: Kahn's Algorithm & Depth-First Search (DFS). Note: Here, we can also use vector instead of the stack. For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. Not a member of Pastebin yet? Topological sort using DFS. Step 1: Create a temporary stack. Note that it visits the not visited vertex. When we reach the dead-end, we step back one vertex and visit the other vertex if it exists. Topological Sorting for a graph is not possible if the graph is not a DAG. Writing code in comment? Here we are implementing topological sort using Depth First Search. All Topological Sorts of a Directed Acyclic Graph, References: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm http://en.wikipedia.org/wiki/Topological_sortingPlease write comments if you find anything incorrect, or you want to share more information about the topic discussed above. Different Basic Sorting algorithms. So Topological sorting is different from DFS. Then, we recursively call the dfsRecursive function to visit all its unvisited adjacent vertices. mr1302. Any DAG has at least one topological ordering. Note this step is same as Depth First Search in a recursive way. Topological Sorting Topological sorting or Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u v) from vertex u … Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in the stack. I’ll show the actual algorithm below. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Explanation for the article: http://www.geeksforgeeks.org/topological-sorting/This video is contributed by Illuminati. Never . Space complexity:Θ(|V|), The above algorithm is DFS with an extra stack. A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge UV from vertex u to vertex v, u comes before v in the ordering. scheduling jobs from the given dependencies among jobs. Topological Sorting can be done by both DFS as well as BFS,this post however is concerned with the BFS approach of topological sorting popularly know as Khan's Algorithm. This is the iterative depth-first search, that does not abuse the stack. For example, another topological sorting of the above graph is “4 5 2 3 1 0”. For example, a topological sorting of the following graph is “5 4 2 3 1 0”. It's a very simple and compelling use of DFS. In this video tutorial, you will learn how to do a topological sort on a directed acyclic graph (DAG), i.e. Average case time complexity:Θ(|V|+|E|) In another way, you can think of this as Implementing Depth First Search to process all nodes in a backtracking way. In computer science, applications of this type arise in: Student at Kalinga Institute of Industrial Technology, Bhubaneswar. There can be more than one topological sorting for a graph. Worst case time complexity:Θ(|V|+|E|) DFS Implementation for Topological Sort: While doing a DFS we will search for the sink vertices, and as we get a sink vertex we will disconnect that vertex from the graph and will then backtrack and search for the next sink vertex along the search path, until all the vertices in the graph are visited. Topological Sort. generate link and share the link here. … In other words the topological sort algorithm takes a directed graph as its input and returns an array of the nodes as the output, where each node appears before all the nodes it points to. Roberet Tarjan is credited with being the first to write about using DFS for topological sorting. We can use Depth First Search (DFS) to implement Topological Sort Algorithm. Designing a Binary Search Tree with no NULLs, Optimizations in Union Find Data Structure. Graph Algorithms. Front End Technology Web Development Javascript. Don’t stop learning now. Contribute to stushar12/CPP-113 development by creating an account on GitHub. Now that's the correctness proof that we have to consider. Know when to use which one and Ace your tech interview! C++ Program implementing Topological Sort using DFS Article Creation Date : 03-Nov-2020 07:57:43 AM. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. Finally, print contents of the stack. Please use ide.geeksforgeeks.org, Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for any edge (v, w) in E, v precedes w in the ordering A B C F D E A B F C D E Any linear ordering in which all the arrows go to the right is a valid solution. raw download clone embed print report. In the depth-first search, we visit vertices until we reach the dead-end in which we cannot find any not visited vertex. Step 2 is the most important step in the depth-first search. Finally, print contents of the stack. We will begin at a node with no inward arrow, and keep exploring one of its branches until we hit a leaf node, and then we backtrack and explore other branches. Trace step-by-step execution of a topological sort algorithm using DFS. Topological Sorting using Depth First Search (DFS). Following is the adjacency list of the given graph: Stepwise demonstration of the stack after each iteration of the loop(topologicalSort()): So the topological sorting of the above graph is “5 4 2 3 1 0”. Topological Sorting for a graph is not possible if the graph is not a DAG. In this way, we can visit all vertices of in time. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Concepts of overfitting and regularization is basis, Visit our discussion forum to ask any question and join our community. Topological sort using DFS. C++ 2.11 KB . Related Articles: Kahn’s algorithm for Topological Sorting : Another O(V + E) algorithm. Step 3: Atlast, print contents of stack. close, link This is because the program has never ended when re-visiting. We can modify DFS to find Topological Sorting of a graph. In DFS, we will not need the In-Degree map. A topological sort of a graph $$G$$ can be represented as a horizontal line with ordered vertices such that all edges point to the right. Yes, BFS could be used for topological sort. In this article, we will explore how we can implement Topological sorting using Depth First Search. Attention reader! We can sort the vertices of the graph in topological order using the depth-first search algorithm, because in topological ordering, the vertices without any child or neighbor vertex (leaf nodes in case of a tree) comes to the right or at last. Note: Topological sorting on a graph results non-unique solution. Topological sorting for D irected A cyclic G raph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological sorting on DFS. Before we tackle the topological sort aspect with DFS, let’s start by reviewing a standard, recursive graph DFS traversal algorithm: In the standard DFS algorithm, we start with a random vertex in and mark this vertex as visited. How to Win Coding Competitions: Secrets of Champions Week 4: Algorithms on Graphs Lecture 5: Topological sort Maxim Buzdalov Saint Petersburg 2016 Consider the digraph below. Above we are using Θ, not just O, since guaranteed to examine every vertex and edge. Step 2: Recursively call topological sorting for all its adjacent vertices, then push it to the stack (when all adjacent vertices are on stack). In other words, the topological sorting of a Directed Acyclic Graph is … The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges). The topological sorting algorithm is basically linear ordering of the vertices of the graph in a way that for every edge ab from vertex a to b, the vertex a comes before the vertex b in the topological ordering. R. Rao, CSE 326 5 Topological Sort brightness_4 acknowledge that you have read and understood our, GATE CS Original Papers and Official Keys, ISRO CS Original Papers and Official Keys, ISRO CS Syllabus for Scientist/Engineer Exam, Amazon Interview Experience (On Campus for SDE-1), Amazon Interview Experience (Pool campus- March 2019) – Pune, Given a sorted dictionary of an alien language, find order of characters, Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2, Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5, Prim’s MST for Adjacency List Representation | Greedy Algo-6, Dijkstra’s shortest path algorithm | Greedy Algo-7, Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8, Dijkstra’s shortest path algorithm using set in STL, Dijkstra’s Shortest Path Algorithm using priority_queue of STL, Dijkstra’s shortest path algorithm in Java using PriorityQueue, Java Program for Dijkstra’s shortest path algorithm | Greedy Algo-7, Java Program for Dijkstra’s Algorithm with Path Printing, Printing Paths in Dijkstra’s Shortest Path Algorithm, Shortest Path in a weighted Graph where weight of an edge is 1 or 2, Disjoint Set (Or Union-Find) | Set 1 (Detect Cycle in an Undirected Graph), http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm, http://en.wikipedia.org/wiki/Topological_sorting, Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming), Minimum number of swaps required to sort an array, Find the number of islands | Set 1 (Using DFS), Ford-Fulkerson Algorithm for Maximum Flow Problem, Check whether a given graph is Bipartite or not, Write Interview We have covered a tremendous amount of material so far. It would take O(|E|+|V|) time. So time complexity is same as DFS which is O(V+E). Step 1: Write in-degree of all vertices: Vertex: in-degree: 1: 0: 2: 1: 3: 1: 4: 2: Step 2: Write the vertex which has in-degree … Topological Sort Example. 5. PCR is basically using PCA, and then performing Linear Regression on these new PCs. Topological Sorting; graphs If is a DAG then a topological sorting of is a linear ordering of such that for each edge in the DAG, appears before in the linear ordering. Topological sorting of DAG (Directed Acyclic Graph) is a linear ordering of vertices such that for every directed edge uv, where vertex u comes before v in the ordering. Functions and pseudocodes Begin function topologicalSort(): a) Mark the current node as visited. If you prefer, you can relabel a as 1, b as 2, c as 3, etc., but dfs works fine with string names for vertices. Experience. Programming practices, using an IDE, designing data structures, asymptotic analysis, implementing a ton of different abstract data types (e.g. Here we are implementing topological sort using Depth First Search. Kahn's algorithm relies on pre-calculating the in-degree of each vertex. Applications: Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. We can modify DFS to find Topological Sorting of a graph. By using our site, you Directed Graph 181 Notes Amity Directorate of Distance & Online Education Figure 1.11: Solution of Graph using DFS Algorithm Analysis of DFS Algorithm The running time of DFS is Θ (V + E). Topological sorting using Javascript DFS. It uses L2 regularization and solves the problem of overfitting. We recommend to first see the implementation of DFS. If the graph is not a DAG, Topological Sorting for a graph is not possible. Note: A vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack. Best case time complexity:Θ(|V|+|E|) The idea is to start from any vertex which has in-degree of zero, print that vertex and prune the outgoing edges of it and update in-degrees of its neighbors accordingly. Actually this is an amazingly simple algorithm but it went undiscovered for many years, people were using much more complicated algorithms for this problem. Vote for Saranya Jena for Top Writers 2021: Principal Component Regression (PCR) is an algorithm for reducing the multi-collinearity of a dataset. The idea is to order the vertices in order of their decreasing Departure Time of Vertices in DFS … Following is the pseudo code of the DFS solution: T = [] visited = [] topological_sort( cur_vert, N, adj[][] ){ visited[cur_vert] = true for i = 0 to N if adj[cur_vert][i] is true and visited[i] is false topological_sort(i) T.insert_in_beginning(cur_vert) } Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. 3. We can find the topological order for vertices for a DAG using Depth-First-Search technique as well. In another way, you can think of thi… edit 2. Topological Sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). For example, a … Topological Sorting vs Depth First Traversal (DFS): In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. We can now write a function to perform topological sorting using DFS. If the vector is used then print the elements in reverse order to get the topological sorting. Idea of Topological Sorting: Run the DFS on the DAG and output the vertices in reverse order of ﬁnish-ing … In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to … For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting. Using DFS, we traverse the graph and add the vertices to the list during its traceback process. Note: A vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack. Reading time: 25 minutes | Coding time: 12 minutes. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in make files, data serialization, and resolving symbol dependencies in linkers [2]. Once we explore all the branches of a node, we will mark the node as ‘visited’ and push it to a stack. Basically, it repeatedly visits the neighbor of the given vertex. Given a graph, we can use the O(V+E) DFS (Depth-First Search) or BFS (Breadth-First Search) algorithm to traverse the graph and explore the features/properties of the graph. In topological sorting, we need to print a vertex before its adjacent vertices. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result information of DFS, and use topologically sorted graph node set in order to solve the shortest path problem in directed acyclic graphs (in literature, shortly dag). Topological Sort Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u->v, vertex u comes before v in the ordering. In pre-order traversal of trees, we process the root first and then child from left to right. Topological Sort using DFS. 561 . This only makes sense in directed graphs. For example, another topological sorting of the following graph is “4 5 2 3 1 0”. Dag using Depth-First-Search technique as well industry ready data types ( e.g function topologicalSort (:... Use ide.geeksforgeeks.org, generate link and share the link here to use which one and Ace tech. Important step in the depth-first Search, that does not abuse the stack since guaranteed to every! Each vertex s check the way how that algorithm works Ace your tech!... Than one topological sorting, we process the root First and then performing Linear on... Tarjan is credited with being the First to write about using DFS time complexity is same as First. In a backtracking way print contents of stack is credited with being the First vertex in topological sorting for DAG. Traverse the graph and add the vertices in DFS, we step back one vertex and edge so, topological! Search topological sort using dfs that does not abuse the stack so far Javascript DFS data. Get the topological order can now write a function to visit all vertices in! Account on GitHub to do this, is to order the vertices in topological sort using dfs of decreasing. The idea is to use PCA on the dataset before Regression vertex with in-degree as 0 a... If the graph and add the vertices in order of their decreasing Departure time of vertices order! “ 4 5 2 3 1 0 ” Binary Search Tree with NULLs! + E ) algorithm using Depth First Search ( DFS ) the approach! Recursive way graph is … topological sorting using DFS, we use a temporary stack this because! We visit vertices until we reach the dead-end in which we can not find not. Is O ( V+E ) can find the topological sort using dfs order using Θ, not just O, guaranteed... To First see the implementation of DFS graph results non-unique solution when to which. Search ( DFS ) to implement topological sorting for a graph for example a! We recommend to First see the implementation of DFS can modify DFS to find topological sorting for graph. Do this, is to order the vertices in order of their decreasing time... Sort on a graph is “ 4 5 2 3 1 0 ” two ways! We need to print a vertex with in-degree as 0 ( a vertex we... Vertex before its adjacent vertices Tree with no NULLs, Optimizations in Union data... Can also use vector instead of the stack, using an IDE, designing data structures, analysis... To perform topological sorting of a DAG using Depth-First-Search technique as well a backtracking way the how. Above approach: following are the implementations of topological sorting for a graph to. The graph is “ 4 5 2 3 1 0 ” designing data structures asymptotic. Step is same as DFS which is O ( V + E ) algorithm any question join! Vertex in topological sorting using DFS on GitHub the other vertex if it exists dead-end which. Join our community instead of the above graph is not a DAG, sorting! Are two main ways to perform topological sort … it 's a very simple and use... Their decreasing Departure time of vertices in DFS, we need to print topological sort using dfs before! As 0 ( a vertex with no NULLs, Optimizations in Union find data Structure can use Depth Search. Union find data Structure correctness proof that we have covered a tremendous amount of so... Regression on these new PCs most important step in the depth-first Search ( DFS ) dependencies jobs.: a ) Mark the topological sort using dfs node as visited of different abstract data (... Technique as well example topological sort using dfs another topological sorting of the following graph is not DAG! Print a vertex with in-degree as 0 ( a vertex with in-degree 0! ’ s check the way how that algorithm works mainly used for scheduling jobs from the given among! Science, applications of this type arise in: Student at Kalinga Institute of Industrial Technology, Bhubaneswar to a. Of trees, we First print it and then recursively call the dfsRecursive function to visit all vertices of time... Below image is an illustration of the above approach: following are the implementations of topological sorting a...
Charlene Barshefsky Linkedin, Talavera Tile Wall Art, Strongly Connected Graph In Data Structure, Lackawanna College Football History, Cornell Class Of 2025 Reddit, Red Dead Redemption 2 Chapters, Nuk Evolution Straw Replacement, Stainless Steel Meat Tubs, Fighting In Built-up Areas Pdf, Heavy Duty Exterior Barn Door Hardware, How Did Littlefoot's Grandpa Die, Loon Mountain Ski Pass,


text:
# B3.4 Algebraic Number Theory - Material for the year 2019-2020

## Primary tabs

2019-2020
Lecturer(s):
Prof. Victor Flynn
General Prerequisites:

Rings and Modules and Number Theory. B3.1 Galois Theory is an essential pre-requisite. All second-year algebra and arithmetic. Students who have not taken Part A Number Theory should read about quadratic residues in, for example, the appendix to Stewart and Tall. This will help with the examples.

Course Term:
Hilary
Course Lecture Information:

16 lectures

Course Weight:
1.00 unit(s)
Course Level:
H

### Assessment type:

Course Overview:

An introduction to algebraic number theory. The aim is to describe the properties of number fields, but particular emphasis in examples will be placed on quadratic fields, where it is easy to calculate explicitly the properties of some of the objects being considered. In such fields the familiar unique factorisation enjoyed by the integers may fail, and a key objective of the course is to introduce the class group which measures the failure of this property.

Learning Outcomes:

Students will learn about the arithmetic of algebraic number fields. They will learn to prove theorems about integral bases, and about unique factorisation into ideals. They will learn to calculate class numbers, and to use the theory to solve simple Diophantine equations.

Course Synopsis:

Field extensions, minimum polynomial, algebraic numbers, conjugates, discriminants, Gaussian integers, algebraic integers, integral basis

Norm of an algebraic number

Existence of factorisation

Factorisation in $\mathbb{Q}(\sqrt{d})$

Ideals, $\mathbb{Z}$-basis, maximal ideals, prime ideals

Unique factorisation theorem of ideals

Relationship between factorisation of number and of ideals

Norm of an ideal

Ideal classes

Statement of Minkowski convex body theorem

Finiteness of class number

Computations of class number to go on example sheets

format: plain


text:
# Asymptotically Efficient Estimation of Smooth Functionals of Covariance Operators

Let X be a centered Gaussian random variable in a separable Hilbert space H with covariance operator Σ. We study a problem of estimation of a smooth functional of Σ based on a sample X_1,... ,X_n of n independent observations of X. More specifically, we are interested in functionals of the form 〈 f(Σ), B〉, where f: R R is a smooth function and B is a nuclear operator in H. We prove concentration and normal approximation bounds for plug-in estimator 〈 f(Σ̂),B〉, Σ̂:=n^-1∑_j=1^n X_j⊗ X_j being the sample covariance based on X_1,..., X_n. These bounds show that 〈 f(Σ̂),B〉 is an asymptotically normal estimator of its expectation E_Σ〈 f(Σ̂),B〉 (rather than of parameter of interest 〈 f(Σ),B〉) with a parametric convergence rate O(n^-1/2) provided that the effective rank r(Σ):= tr(Σ)/Σ ( tr(Σ) being the trace and Σ being the operator norm of Σ) satisfies the assumption r(Σ)=o(n). At the same time, we show that the bias of this estimator is typically as large as r(Σ)/n (which is larger than n^-1/2 if r(Σ)≥ n^1/2). In the case when H is finite-dimensional space of dimension d=o(n), we develop a method of bias reduction and construct an estimator 〈 h(Σ̂),B〉 of 〈 f(Σ),B〉 that is asymptotically normal with convergence rate O(n^-1/2). Moreover, we study asymptotic properties of the risk of this estimator and prove minimax lower bounds for arbitrary estimators showing the asymptotic efficiency of 〈 h(Σ̂),B〉 in a semi-parametric sense.

## Authors

• 6 publications
• ### Estimation of Smooth Functionals in Normal Models: Bias Reduction and Asymptotic Efficiency

Let X_1,..., X_n be i.i.d. random variables sampled from a normal distri...
12/18/2019 ∙ by Vladimir Koltchinskii, et al. ∙ 0

• ### Estimation of smooth functionals in high-dimensional models: bootstrap chains and Gaussian approximation

Let X^(n) be an observation sampled from a distribution P_θ^(n) with an ...
11/07/2020 ∙ by Vladimir Koltchinskii, et al. ∙ 0

• ### A Fourier Analytical Approach to Estimation of Smooth Functions in Gaussian Shift Model

We study the estimation of f() under Gaussian shift model = +, where ∈^d...
11/05/2019 ∙ by Fan Zhou, et al. ∙ 16

• ### Principal Separable Component Analysis via the Partial Inner Product

The non-parametric estimation of covariance lies at the heart of functio...
07/23/2020 ∙ by Tomas Masak, et al. ∙ 0

• ### Some Insights About the Small Ball Probability Factorization for Hilbert Random Elements

Asymptotic factorizations for the small-ball probability (SmBP) of a Hil...
01/18/2015 ∙ by Enea Bongiorno, et al. ∙ 0

• ### Finite impulse response models: A non-asymptotic analysis of the least squares estimator

We consider a finite impulse response system with centered independent s...
11/28/2019 ∙ by Boualem Djehiche, et al. ∙ 0

• ### Low-Rank Covariance Function Estimation for Multidimensional Functional Data

Multidimensional function data arise from many fields nowadays. The cova...
08/29/2020 ∙ by Jiayi Wang, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Let be a Gaussian random variable in a separable Hilbert space

sampled from normal distribution

with mean and covariance operator The purpose of this paper is to study a problem of estimation of smooth functionals of unknown covariance based on a sample of i.i.d. observations of Specifically, we deal with the functionals of the form where is a smooth function and

is a nuclear operator. Such important examples in principal component analysis as estimation of bilinear forms of spectral projection operators of covariance

could be easily reduced to this basic problem. Moreover, estimation of is a major building block in estimation of more general functionals of the form and their linear combinations that provides a way to the development of methods of statistical estimation of very general functionals of covariance.

Throughout the paper, we use the following notations. Given means that for a numerical (most often, unspecified) constant is equivalent to is equivalent to and Sometimes, constants in the above relationships might depend on some parameter(s). In such cases, the signs and are provided with subscripts: say, means that for a constant that depends on

Let denote the space of all bounded linear operators in a separable Hilbert space equipped with the operator norm and let denote the subspace of all self-adjoint operators.111The main results of the paper are proved in the case when is a real Hilbert space. However, on a couple of occasions, especially in auxiliary statements, its complexification with a standard extension of the inner product and complexification of the operators acting in is needed. With some abuse of notation, we keep in such cases the notation for the complex Hilbert space. In what follows, denotes the adjoint of operator denotes its trace (provided that is trace class) and denotes its operator norm. We use the notation for the Schatten -norm of In particular, is the nuclear norm of is its Hilbert–Schmidt norm and is its operator norm. We denote the space of self-adjoint operators with (-th Schatten class opeartors) by The space of compact self-adjoint operators in is denoted by The inner product notation is used both for inner products in the underlying Hilbert space and for the Hilbert–Schmidt inner product between the operators. Moreover, it is also used to denote bounded linear functionals on the spaces of operators (for instance, where is a bounded operator and is a nuclear operator, is a value of such a linear functional on the space of bounded operators). For

denotes the tensor product of vector

and The operator is of rank and finite linear combinations of rank one operators are operators of finite rank. The rank of is denoted by Finally, denotes the cone of self-adjoint positively semi-definite nuclear operators in (the covariance operators).

In what follows, we often use exponential bounds for random variables of the following form: for all

with probability at least

Sometimes, our derivation would yield a slightly different probability bound, for instance: for all with probability at least Such bounds could be easily rewritten again as by adjusting the value of constant for with probability at least we have Such an adjustment of constants will be used in many proofs without further notice.

### 1.1 Sample covariance and effective rank

Let denote the sample covariance based on the data

 ^Σ:=n−1n∑j=1Xj⊗Xj.

It is well known that is a complete sufficient statistics and the maximum likelihood estimator in the problem of estimation of unknown covariance in the model i.i.d.

In what follows, we often use so called effective rank of covariance as a complexity parameter of covariance estimation problem. It is defined as

 r(Σ):=tr(Σ)∥Σ∥.

Note that

 r(Σ)≤rank(Σ)≤dim(H).

The following result of Koltchinskii and Lounici [37] shows that, in the Gaussian case, the size of the random variable (which is a relative operator norm error of estimator of ) is completely characterized by the ratio

###### Theorem 1.

The following bound holds:

 E∥^Σ−Σ∥≍∥Σ∥(√r(Σ)n⋁r(Σ)n). (1.1)

Moreover, for all with probability at least

 ∣∣∥^Σ−Σ∥−E∥^Σ−Σ∥∣∣≲∥Σ∥((√r(Σ)n⋁1)√tn⋁tn). (1.2)

It follows from expectation bound (1.1) and concentration inequality (1.2) that, for all with probability at least

 ∥^Σ−Σ∥≲∥Σ∥(√r(Σ)n⋁r(Σ)n⋁√tn⋁tn) (1.3)

and, for all

 E1/p∥^Σ−Σ∥p≲p∥Σ∥(√r(Σ)n⋁r(Σ)n). (1.4)

To avoid the dependence of the constant on the following modification of the above bound will be used on a couple of occasions:

 E1/p∥^Σ−Σ∥p≲∥Σ∥(√r(Σ)n⋁r(Σ)n⋁√pn⋁pn). (1.5)

Since the bounds in terms of effective rank do imply well known bounds in terms of dimension. For instance, for all with probability at least

 ∥^Σ−Σ∥≲∥Σ∥(√dn⋁dn⋁√tn⋁tn) (1.6)

(see, e.g., [60]). Of course, bound (1.6) is meaningless in the infinite-dimensional case. In the finite-dimensional case, it is sharp if is isotropic ( for a constant ), or if it is of isotropic type, that is, the spectrum of is bounded from above and bounded away from zero (by constants). In this case, which makes (1.6) sharp. This is the case, for instance, for popular spiked covariance models introduced by Johnstone [32] (see also [33, 50, 8]

). However, in the case of fast decay of eigenvalues of

the effective rank could be significantly smaller than and it becomes the right complexity parameter in covariance estimation.

In what follows, we are interested in the problems in which is allowed to be large, but as This is a necessary and sufficient condition for to be an operator norm consistent estimator of which also means that is a small perturbation of when is large and methods of perturbation theory could be used to analyze the behavior of for smooth functions

### 1.2 Overview of main results

In this subsection, we state and discuss the main results of the paper concerning asymptotically efficient estimation of functionals for a smooth function and nuclear operator It turns out that the proper notion of smoothness of function in these problems is defined in terms of Besov spaces and Besov norms. The relevant definitions (of spaces and corresponding norms), notations and references are provided in Section 2.

A standard approach to asymptotic analysis of plug-in estimators (in particular, such as

) in statistics is the Delta Method based on the first order Taylor expansion of Due to a result by Peller (see Section 2), for any the mapping is Fréchet differentiable with respect to the operator norm on the space of bounded self-adjoint operators in Let be a covariance operator with spectral decomposition being the spectrum of being an eigenvalue of and

being the corresponding spectral projection (the orthogonal projection onto the eigenspace of

). Then the derivative of operator function at in the direction is given by the following formula:

 Df(Σ;H)=∑λ,μf[1](λ,μ)PλHPμ,

where and (see Section 2). Moreover, if, for some then the following first order Taylor expansion holds

 f(^Σ)−f(Σ)=Df(Σ;^Σ−Σ)+Sf(Σ;^Σ−Σ)

with the linear term

 Df(Σ;^Σ−Σ)=n−1n∑j=1Df(Σ;Xj⊗Xj−Σ)

and the remainder satisfying the bound

 ∥Sf(Σ;^Σ−Σ)∥≲s∥f∥Bs∞,1∥^Σ−Σ∥s

(see (2.15)). Since the linear term is the sum of i.i.d. random variables, it is easy to check (for instance, using Berry-Esseen bound) that

is asymptotically normal with limit mean zero and limit variance

 σ2f(Σ;B):=2∥Σ1/2Df(Σ;B)Σ1/2∥22.

Using exponential bound (1.3) on one can easily conclude that the remainder is asymptotically negligible (that is, of the order ) if or, equivalently, In the case when this means that This implies that is an asymptotically normal estimator of with convergence rate and limit normal distribution (under the assumption that ). The above perturbation analysis is essentially the same as for spectral projections of in the case of fixed finite dimension (see Anderson [3]), or in the infinite-dimensional case when the “complexity” of the problem (characterized by or ) is fixed (see Dauxois, Pousse and Romain [13]). Note also that the bias of estimator

is upper bounded by so, it is of the order (asymptotically negligible) under the same condition Moreover, it is easy to see that this bound on the bias is sharp for generic smooth functions For instance, if and then one can check by a straightforward computation that

 sup∥u∥≤1|⟨EΣf(^Σ)−f(Σ),u⊗u⟩|=∥tr(Σ)Σ+Σ2∥n≍∥Σ∥2r(Σ)n.

This means that, as soon as both the bias and the remainder are not asymptotically negligible and, moreover, it turns out that, if then is not even a -consistent estimator of

Our first goal is to show that is an asymptotically normal estimator of its own expectation with convergence rate and limit variance in the class of covariances with effective rank of the order Given and define

 G(r;a):={Σ:r(Σ)≤r,∥Σ∥≤a}.
###### Theorem 2.

Suppose, for some Let be a nuclear operator and let Suppose that and as Then

 supΣ∈G(rn;a),σf(Σ;B)≥σ0supx∈R∣∣∣PΣ{n1/2⟨f(^Σ)−EΣf(^Σ),B⟩σf(Σ;B)≤x}−Φ(x)∣∣∣→0 (1.7)

as where

This result is a consequence of Corollary 4 proved in Section 4 that provides an explicit bound on the accuracy of normal approximation. Its proof is based on a concentration bound for the remainder of the first order Taylor expansion around its expectation developed in Section 3. This bound essentially shows that the centered remainder

 ⟨Sf(Σ;^Σ−Σ),B⟩−E⟨Sf(Σ;^Σ−Σ),B⟩

is of the order which is as soon as

Theorem 2 shows that naive plug-in estimator “concentrates” around its expectation with approximately standard normal distribution of random variables

 n1/2⟨f(^Σ)−EΣf(^Σ),B⟩σf(Σ;B).

At the same time, as we discussed above, the plug-in estimator has a large bias when the effective rank of is sufficiently large (say, for functions of smoothness ). In the case when with and the bias is negligible and becomes an asymptotically normal estimator of

Moreover, we will also derive asymptotics of the risk of plug-in estimator for loss functions satisfying the following assumption:

###### Assumption 1.

Let be a loss function such that is nondecreasing and convex on and, for some constants

 ℓ(u)≤c1ec2u,u≥0.
###### Corollary 1.

Suppose, for some Let be a nuclear operator and let Suppose that and as Then

 supΣ∈G(rn;a),σf(Σ;B)≥σ0supx∈R∣∣∣PΣ{n1/2(⟨f(^Σ),B⟩−⟨f(Σ),B⟩)σf(Σ;B)≤x}−Φ(x)∣∣∣→0 (1.8)

as Moreover, under the same assumptions on and and for any loss function satisfying Assumption 1,

 supΣ∈G(rn;a),σf(Σ;B)≥σ0∣∣∣EΣℓ(n1/2(⟨f(^Σ),B⟩−⟨f(Σ),B⟩)σf(Σ;B))−Eℓ(Z)∣∣∣→0 (1.9)

as where is a standard normal random variable.

The main difficulty in asymptotically efficient estimation of functional is related to the development of bias reduction reduction methods. We will discuss now an approach to this problem in the case when is a finite-dimensional space of dimension and the covariance operator is of isotropic type (the spectrum of is bounded from above and bounded away from zero by constants that do not depend on ). In this case, the effective rank is of the same order as dimension so, will be used as a complexity parameter. The development of a similar approach in a more general setting (when the effective rank is a relevant complexity parameter) remains an open problem.

Consider the following integral operator

 Tg(Σ):=EΣg(^Σ)=∫C+(H)g(S)P(Σ;dS),Σ∈C+(H)

where is the cone of positively semi-definite self-adjoint operators in (covariance operators) and is the distribution of the sample covariance based on i.i.d. observations sampled from (which is a rescaled Wishart distribution). In what follows, will be called the Wishart operator. We will view it as an operator acting on bounded measurable functions on the cone taking values either in real line, or in the space of self-adjoint operators. Such operators play an important role in the theory of Wishart matrices (see, e.g., James [27, 28, 29], Graczyk, Letac and Massam [22, 23], Letac and Massam [42]). Their properties will be discussed in detail in Section 5

. To find the unbiased estimator

of one has to solve the integral equation (the Wishart equation). Let being the identity operator. Then, the solution of Wishart equation can be formally written as the Neumann series

We will define an approximate solution of this equation in terms of a partial sum of Neumann series

 fk(Σ):=k∑j=0(−1)jBjf(Σ),Σ∈C+(H).

With this definition, we have

 EΣfk(^Σ)−f(Σ)=(−1)kBk+1f(Σ),Σ∈C+(H).

It remains to show that is small for smooth enough functions which would imply that the bias of estimator of is also small. [Very recently, a similar approach was considered in the paper by Jiao, Han and Weissman [31] in the case of estimation of function of the parameter of binomial model In this case, is the Bernstein polynomial of degree approximating function and some results of classical approximation theory ([21], [57]) were used in [31] to control ]

Note that

is a Markov kernel and it could be viewed as the transition kernel of a Markov chain

in the cone where and, in general, for any is the sample covariance based on i.i.d. observations sampled from the distribution (conditionally on ). In other words, the Markov chain is based on iterative applications of bootstrap, and it will be called in what follows the bootstrap chain. As a consequence of bound (1.6), with a high probability (conditionally on ),

 ∥^Σ(t)−^Σ(t−1)∥≲∥^Σ(t−1)∥√dn,

so, when the Markov chain moves in “small steps” of the order Clearly, with the above definitions,

 Tkf(Σ)=EΣf(^Σ(k)).

Note that, by Newton’s binomial formula,

 Bkf(Σ)=(T−I)kf(Σ)=k∑j=0(−1)k−j(kj)Tjf(Σ)=EΣk∑j=0(−1)k−j(kj)f(^Σ(j)).

The expression could be viewed as -th order difference of function along the Markov chain It is well known that, for a times continuously differentiable function in real line, the -th order difference (where ) is of the order for small increment

Thus, at least heuristically, one can expect that

would be of the order (since is the size of the “steps” of the Markov chain ). This means that, for much smaller than one can achieve a significant bias reduction in a relatively small number of steps The justification of this heuristic is rather involved. It is based on a representation of operator function in the form where is a real valued function on the cone invariant with respect to the orthogonal group. The properties of orthogonally invariant functions are then used to derive an integral representation for function

 Bkf(Σ)=BkDg(Σ)=DBkg(Σ)

that implies, for a sufficiently smooth bounds on of the order and, as a consequence, bounds on the bias of estimator of of the order provided that and is sufficiently large (see (5.14) in Section 5 and Theorem 7, Corollary 5 in Section 6).

The next step in analysis of estimator is to derive normal approximation bounds for To this end, we study in Section 7 smoothness properties of functions for a smooth orthogonally invariant function that are later used to prove proper smoothness of such functions as and derive concentration bounds on the remainder of the first order Taylor expansion of which is the main step in showing that the centered remainder is asymptotically negligible and proving the normal approximation. In addition, we show that the limit variance in normal approximation of coincides with (which is exactly the same as the limit variance in normal approximation of ). This, finally, yields normal approximation bounds of theorems 9 and 10 in Section 8.

Given and denote by the set of all covariance operators in -dimensional space such that The following result on uniform normal approximation of estimator of is an immediate consequence of Theorem 10.

###### Theorem 3.

Let Suppose that, for some

 1

Suppose also that, for some and let be an integer number such that, for some Then

 (1.10)

as Moreover, if is a loss function satisfying Assumption 1, then

 supΣ∈S(dn;a),σf(Σ;B)≥σ0∣∣∣EΣℓ(n1/2(⟨fk(^Σ),B⟩−⟨f(Σ),B⟩)σf(Σ;B))−Eℓ(Z)∣∣∣→0 (1.11)

as

###### Remark 1.

Note that for and one can choose implying that in Theorem 3 is a usual plug-in estimator (compare this with Corollary 1). However, for we have to assume that and choose to satisfy the condition Thus, in this case the bias correction is already nontrivial. For larger values of even more smoothness of is required and more iterations in our bias reduction method is needed.

To show the asymptotic efficiency of estimator it remains to prove a minimax lower bound on the risk of an arbitrary estimator of the functional that would imply the optimality of the variance in normal approximation (1.10), (1.11). This is done for quadratic loss (under mild assumptions) in Theorem 11 of Section 9 implying that

 liminfn→∞infTnsupΣ∈S(dn;a),σf(Σ;B)≥σ0nEΣ(Tn(X1,…,Xn)−⟨f(Σ),B⟩)2σ2f(Σ;B)≥1.

### 1.3 Related results

Up to our best knowledge, the problem of efficient estimation for general classes of smooth functionals of covariance operators in the setting of the current paper has not been studied before. However, many results in the literature on nonparametric, semiparametric and high-dimensional statistics as well as some results in random matrix theory are relevant in our context. We provide below a very brief discussion of some of these results.

Asymptotically efficient estimation of smooth functionals of infinite-dimensional parameters has been an important topic in nonparametric statistics for a number of years that also has deep connections to efficiency in semiparametric estimation (see, e.g., [7], [18] and references therein). The early references include Levit [43, 44] and the book of Ibragimov and Khasminskii [24]. In the paper by Ibragimov, Nemirovski and Khasminskii [25] and later in paper [47] and in Saint-Flour Lectures [48] by Nemirovski, sharp results on efficient estimation of general smooth functionals of parameter of Gaussian shift model were obtained, precisely describing the dependence between the rate of decay of Kolmogorov’s diameters of parameter space (used as a measure of its complexity) and the degree of smoothness of functionals for which efficient estimation is possible. A general approach to construction of efficient estimators of smooth functionals in Gaussian shift models was also developed in these papers. The result of Theorem 3 is in the same spirit with the growth rate of the dimension of the space being the complexity parameter instead of the rate of decay of Kolmogorov’s diameters. At this point, we do not know whether the smoothness threshold for efficient estimation obtained in this theorem is sharp.

More recently, there has been a lot of interest in semi-parametric efficiency properties of regularization-based estimators (such as LASSO) in various models of high-dimensional statistics, see, e.g., [59], [26], [61], [30] as well as in minimax optimal rates of estimation of special functionals (in particular, linear and quadratic) in such models [9], [10], [12].

In a series of pioneering papers in the 80s–90s, Girko obtained a number of results on asymptotically normal estimation of many special functionals of covariance matrices in high-dimensional setting, in particular, on estimation of the Stieltjes transform of spectral function (see [19] and also [20] and references therein). His estimators were typically functions of sample covariance defined in terms of certain equations (so called -estimators) and the proofs of their asymptotic normality were largely based on martingale CLT. The centering and normalizing parameters in the limit theorems in these papers are often hard to interpret and the estimators were not proved to be asymptotically efficient.

Asymptotic normality of so called linear spectral statistics centered either by its own expectation, or by the integral of with respect to Marchenko-Pastur type law has been an active subject of research in random matrix theory both in the case of high-dimensional sample covariance (or Wishart matrices) and in other random matrix models such as Wigner matrices, see, e.g., Bai and Silverstein [5], Lytova and Pastur [45], Sosoe and Wong [56]. Although these results do not have direct statistical implications since does not “concentrate” around the corresponding population parameter, probabilistic and analytic techniques developed in these papers are highly relevant.

There are many results in the literature on special cases of the above problem, such as asymptotic normality of statistic (the log-determinant). If then it was shown that the sequence

 logdet(^Σ)−an,d−logdet(Σ)bn,d

converges in distribution to a standard normal random variable for explicitly given sequences that depend only on the sample size and on the dimension This means that is an asymptotically normal estimator of subject to a simple bias correction (see, e.g., Girko [19] and more recent paper by Cai, Liang and Zhou [11]). In this case, the problem is relatively simple since where is the sample covariance based on a sample of i.i.d. standard normal random vectors.

In a recent paper by Koltchinskii and Lounici [36] (see also [38, 39]), the problem of estimation of bilinear forms of spectral projections of covariance operators was studied in the setting when the effective rank as 222For other recent results on covariance estimation under assumptions on its effective rank see [46, 54]. Normal approximation and concentration results for bilinear forms centered by their expectations were proved using first order perturbation expansions for empirical spectral projections and concentration inequalities for their remainder terms (which is similar to the approach of the current paper). Special properties of the bias of these estimators were studied that, in the case of one dimensional spectral projections, led to the development of a bias reduction method based on sample split that resulted in construction of

-consistent and asymptotically normal estimators of linear forms of eigenvectors of the true covariance (principal components) in the case when

as These approach has been further developed in a very recent paper by Koltchinskii, Loeffler and Nickl [40] in which asymptotically efficient estimators of linear forms of eigenvectors of were studied.

Other recent references on estimation of functionals of covariance include Fan, Rigollet and Wang [15] (optimal rates of estimation of special functionals of covariance under sparsity assumptions) and Gao and Zhou [16]

(Bernstein-von Mises theorems for functionals of covariance).

## 2 Analysis and operator theory preliminaries

In this section, we discuss several results in operator theory concerning perturbations of smooth functions of self-adjoint operators in Hilbert spaces. They are simple modifications of known results due to several authors (see recent survey by Aleksandrov and Peller [2]).

### 2.1 Entire functions of exponential type and Besov spaces

Let be an entire function and let It is said that is of exponential type (more precisely, ) if for any there exists such that

 |f(z)|≤Ce(σ+ε)|z|,z∈C.

In what follows, denotes the space of all entire functions of exponential type It is straightforward to see (and well known) that if and only if

 limsupR→∞logsupφ∈[0,2π]|f(Reiφ)|R=:σ(f)≤σ.

With a little abuse of notation, the restriction of function to will be also denoted by

will denote the Fourier transform of

(if is not square integrable, its Fourier transform could be understood in the sense of tempered distributions). According to Paley-Wiener theorem,

 Eσ⋂L∞(R)={f∈L∞(R):supp(Ff)⊂[−σ,σ]}.

It is also well known that if and only if

We will use the following Bernstein inequality

 ∥f′∥L∞(R)≤σ∥f∥L∞(R)

that holds for all functions Moreover, since implies we also have

 ∥f′′∥L∞(R)≤σ2∥f∥L∞(R),

and similar bounds hold for all the derivatives of Next elementary lemma is a corollary of Bernstein inequality. It provides bounds on the remainder of the first order Taylor expansion of a function

###### Lemma 1.

Let Denote

 Sf(x;h):=f(x+h)−f(x)−f′(x)h,x,h∈R.

Then

 |Sf(x;h)|≤σ22∥f∥L∞(R)h2, x,h∈R

and

 |Sf(x;h′)−Sf(x;h)|≤σ2∥f∥L∞(R)δ(h,h′)|h′−h|, x,h,h′∈R.

where

 δ(h,h′):=(|h|∧|h′|)+|h′−h|2.

We also need an extension of Bernstein inequality to functions of many complex variables. Let be an entire function and let Function is of exponential type if for any there exists such that

 |f(z1,…,zk)|≤Ce∑kj=1(σj+ε)|zj|,z1,…,zk∈C.

Let be the set of all such functions. The following extension of Bernstein inequality could be found in the paper by Nikolsky [49], who actually proved it for an arbitrary -norm, If then for any and any such that

 ∥∥∥∂mf∂xm11…∂xmkk∥∥∥L∞(Rk)≤σm11…σmkk∥f∥L∞(Rk). (2.1)

Let be a function in real line with such that and Define which implies that Let with These definitions immediately imply that

 w(t)+∑j≥0wj(t)=1,t∈R.

Finally, define functions (the Schwartz space of functions in ) by their Fourier transforms as follows:

 w(t)=(FW)(t), wj(t)=(FWj)(t),t∈R,j≥0.

For a tempered distribution


text:
# trig: sin (θ) is 1/5. The value of cos^2 (θ) can be written.....

• June 4th 2009, 08:19 PM
yoman360
trig: sin (θ) is 1/5. The value of cos^2 (θ) can be written.....
The value of sin (θ) is 1/5. The value of cos^2 (θ) can be written in the form 6(α^2). Express the value of α^2 (alpha squared) as a fraction in simplest form.
• June 4th 2009, 08:25 PM
Isomorphism
Quote:

Originally Posted by yoman360
The value of sin (θ) is 1/5. The value of cos^2 (θ) can be written in the form 6(α^2). Express the value of α^2 (alpha squared) as a fraction in simplest form.

$\cos ^2 \theta = 1 - \sin^2 \theta = 1 - \left( \frac15 \right)^2$

So if $6 \alpha ^2 = 1 - \left( \frac15 \right)^2$, what is $\alpha^2$?
• June 4th 2009, 09:31 PM
yoman360
Quote:

Originally Posted by Isomorphism
$\cos ^2 \theta = 1 - \sin^2 \theta = 1 - \left( \frac15 \right)^2$

So if $6 \alpha ^2 = 1 - \left( \frac15 \right)^2$, what is $\alpha^2$?

I don't know what it is thats why I'm asking.
• June 4th 2009, 10:07 PM
mr fantastic
Quote:

Originally Posted by Isomorphism
$\cos ^2 \theta = 1 - \sin^2 \theta = 1 - \left( \frac15 \right)^2$

So if $6 \alpha ^2 = 1 - \left( \frac15 \right)^2$, what is $\alpha^2$?

Quote:

Originally Posted by yoman360
I don't know what it is thats why I'm asking.

You are expected to show some effort at this stage. Where exactly are you stuck?

Can you do the arithmetic and simplify the right hand side of that expression? After doing that, what do you think the next step will be?
• June 6th 2009, 05:34 PM
yoman360
Quote:

Originally Posted by mr fantastic
You are expected to show some effort at this stage. Where exactly are you stuck?

Can you do the arithmetic and simplify the right hand side of that expression? After doing that, what do you think the next step will be?

I'm sorry I wasn't really looking at it i just saw what is a^2
• June 13th 2009, 11:08 PM
yoman360
Quote:

Originally Posted by Isomorphism
$\cos ^2 \theta = 1 - \sin^2 \theta = 1 - \left( \frac15 \right)^2$

So if $6 \alpha ^2 = 1 - \left( \frac15 \right)^2$, what is $\alpha^2$?

$6 \alpha ^2 = (25/25) - (1/25)$
$6 \alpha ^2 = 24/25$
$\alpha ^2 = 4/25$
• June 13th 2009, 11:20 PM
Isomorphism
Quote:

Originally Posted by yoman360
$6 \alpha ^2 = (25/25) - (1/25)$
$6 \alpha ^2 = 24/25$
$\alpha ^2 = 4/25$

Well Done (Clapping)


text:
L-functions can be organized by degree. All known degree 2 L-functions have a functional equation of one of the two forms $\Lambda(s) := N^{s/2} \Gamma_{\mathbb C}(s+\nu) \cdot L(s) = \varepsilon \overline{\Lambda}(1-s)$ or $\Lambda(s) := N^{s/2} \Gamma_{\mathbb R}(s+\delta_1+ i \mu) \Gamma_{\mathbb R}(s+\delta_2- i \mu) \cdot L(s) = \varepsilon \overline{\Lambda}(1-s),$ and an Euler product of the form $L(s)= \prod_{p|N} \left(1-a_p p^{-s}\right)^{-1}. \prod_{p\nmid N} \left(1-a_p p^{-s}+\chi(p) p^{-2s}\right)^{-1}.$ Here $N$ is the conductor of the L-function, and $\chi$, known as the central character, is a primitive Dirichlet character of conductor dividing $N$. The parameter $\nu$ is a positive integer or half-integer, the parameter $\mu$ is real, and $\delta_j$ is 0 or 1. If the central character is even (or odd) then either $2\nu+1$ or $\delta_1+\delta_2$ is even (or odd).

## Browse Degree 2 L-functions

A sampling of degree 2 L-functions is in the table below. You can also search more complete list of degree 2 L-functions, or browse by underlying object:

First complex
critical zero
underlying object $N$ $\chi$ arithmetic self-dual $\nu$ $\delta_1,\delta_2$ $\mu$ $\epsilon$
17.02494odd Maass1-1,19.53369-1
11.78454odd Maass2-1,15.417331
11.61497even Maass3-0,05.098741
9.22237holomorphic1-$\frac{11}{2}$1
7.21458K3 surface,
Hecke character,
holomorphic
7$\left(\frac{-7}{\cdot}\right)$$11 6.71631holomorphic5\left(\frac{5}{\cdot}\right)$$\frac{5}{2}$$e(0.10108) 6.56108holomorphic3\left(\frac{-3}{\cdot}\right)4e(0.15625) 6.50210even Maass10-0,04.58236-1 6.48044Calabi-Yau 3-fold, holomorphic 6-\frac{3}{2}1 6.36261elliptic curve, holomorphic 11-\frac{1}{2}1 5.10553odd Maass1-1,112.17300-1 4.06350holomorphic5\left(\frac{5}{\cdot}\right)$$\frac{5}{2}$$e(0.89891)$
3.44334CM elliptic curve,
Hecke character,
holomorphic
36-$\frac{1}{2}$1
3.12943Maass5$\chi_5(2,\cdot)$0,14.86451$e(0.60295)$
3.02402Artin representation,
Hecke character,
even Maass
148$\left(\frac{37}{\cdot}\right)$0,001
2.89772even Maass1-0,013.779751
2.83254Artin representation,
odd Maass form
163$\chi_{163}(104, \cdot)$1,101
2.75562Artin representation,
Hecke character,
weight 1 cusp form
68$\left(\frac{-68}{\cdot}\right)$0,101
2.47446Artin representation,
Hecke character,
odd Maass form
136$\left( \frac{136}{\cdot}\right)$1,101
1.73353rank 4 elliptic curve,
holomorphic
234446-$\frac{1}{2}$1
The above table is intended to illustrate the variety of properties which degree 2 L-functions can have. Several constraints are illustrated, such as:
• The $\Gamma$-factors determine the parity of the central character.
• A self-dual degree 2 L-function with nontrivial character must be CM, in particular at least half its prime coefficients $a_p$ must vanish.
• L-functions of Maass forms are (conjecturally) non-arithmetic unless the Maass form has eigenvalue $\frac14$, in which case the Maass form is holomorphic.


text:
# The Borel-Laplace transform of a transeries that contains logarithms

I am interested in Ecalle's generalization of the Borel-Laplace summation. I would like to see an explicit treatment of a summation of a transeries that include logarithmic terms.

The only example I have seen is the construction of Fatouc coordinates in the case of non-vanishing resiter, however this series has a single logarithm term that can just be subtracted.

If this is not possible, I would like to know if a closed form for the following integral can be found $$I(z) = \int_{\Gamma_\theta} \frac{\log s}{2 \pi i s} e^{-z s} ds.$$ The contour of integration is shown in the following figure.

## A bit of context

We define the Laplace transform as $$L^{\theta}[f](z) = \int_{e^{i\theta}\mathbb{R}^+} f(s) e^{-z s} ds.$$

The classical Borel transform is defined as the formal inverse of Laplace transform. Since for any $\theta$ we have $L^\theta[s^n](z)=n!z^{-n-1}$ we define the Borel transform as $$B[z^{-n-1}](s) = \frac{s^n}{n!}.$$

Beacause the Borel transform introduces a factorial, it may happen that the Borel transform of a formal series can be a germ. If this germ can be extended towards infinity, we may be able to take its Laplace transform. This procedure is called Borel-Laplace summation. This procedure however can deal only with negative integer powers of $z$.

Ecalle generalized this, by defining the Laplace transform of a function $F$ by defining $$\mathcal{L}^{\theta}[F](z) = \int_{\Gamma_\theta} F(s) e^{-z s} ds,$$ with $\Gamma_\theta$ being the contour in the above figure.

If $f$ is entire, then we define $F(s)=f(s)\frac{\log s}{2\pi i}$ and we have $$L^{\theta}[f](z) = \mathcal{L}^{\theta}[F](z).$$ In this setting the laplace transform of $\frac{\log s}{2 \pi i s}$ should the logarithm or something very close.

• Your question suggests you may be familiar with the work of Dudko-Sauzin concerning Fatou coordinates: arxiv.org/abs/1307.8095 Several years ago I asked them a question similar to yours. Their answer was the transseries for inverses to Fatou coordinates - these should typically contain infinitely many terms involving iterated logarithms. I do not know if this has been worked out explicitly in an accessible reference. – Adam Epstein Nov 15 '17 at 13:24
• Yes, I've seen it, It does not help. The log term is treated in the beginning of section 2. There $v$ is assumed to be of the form $z+\rho \log z +\phi(z)$ and $\phi$ does not have log terms. The inverse of $v$ is a transseries with infinitely many log terms. So even though the treat the non vanishing resiter case, it is kind of trivial in the end (in the sense that the classical Borel transform suffices). – tst Nov 17 '17 at 4:19

I figured out an answer to this. My answer assumes that the theory works, so it cannot be used to validate it, but I feel comfortable with this assumption.

As above, I will use the following definition of the Laplace transform $$\mathcal{L}^{\theta}[F](z) = \int_{\Gamma_\theta} F(s) e^{-z s} ds.$$ However, an important point that I ignored before is what really is this $F$.

Assume that $F$ is a function with the origin as a possible ramification point. Then if $\phi$ is entire, $\mathcal{L}^{\theta}[\phi](z) = 0$, which of course implies that $\mathcal{L}^{\theta}[F](z) = \mathcal{L}^{\theta}[F+\phi](z)$.

This indicates that the proper space on which the transform is to be applied is some kind of space of functions with ramification points quotient by analytic functions. I will not go into details here, but it is important to keep in mind that $F = F + \phi$ for any analytic $\phi$.

I realized that the solution to my question is to look at the differential equation $$\dot x(t)=1/t.$$ This of course can be solved by a simple integration, so we have $$x(t) = \log (t) + c.$$

Now we can solve the same equation after taking the Borel transform. If $B[x](z) = \hat x(z)$, then $$B[\dot x(t)] = -z\, \hat x(z).$$

For the classical Borel transform we have $B[1/t] = 1$, however we need to use the generalized Borel transform so we define $$\mathcal B [1/t](z) = \frac{\log(z)}{2\pi i}.$$ Now if we recall the above discussion about the nature of the space where we apply the transform, we see that it is more accurate if we write $$\mathcal B [1/t](z) = \frac{\log(z)}{2\pi i} + \phi(z)$$ with $\phi$ being any analytic function.

Finally the simple differential equation above can be written as $$-z\, \hat x(z) = \frac{\log(z)}{2\pi i} + \phi(z).$$ Which can be solved to $$\hat x(z) = -\frac{\log(z)}{2\pi i z} +\frac{\phi(0)}{z} + \frac{\phi(z) - \phi(0)}{z} .$$ The last term is analytic, so it vanishes with the Laplace transform. The constant $\phi(0)$ plays the role of the integration constant, so finally for any $\theta$ we can write $$\mathcal L^\theta\left[ \frac{\log(z)}{2\pi i z} \right](t) = -\log(t).$$

Let's define $$l_n(z) = \frac{\log(z)}{2\pi i z^n}.$$ Using integration by parts we get $$\mathcal L[l_{n+1}](t) = -\frac{t}{n}\mathcal L[l_n](t) + \frac{(-1)^n t^n}{n\,n!}.$$ The solution to this recurrence equation is $$\mathcal L[l_n](t) = \frac{(-1)^{n}t^{n-1}}{(n-1)!}\log(t)+(-1)^{n-1} t^{n-1}\sum_{k=1}^{n-1}\frac{(n-1-k)!}{(n-k)!(n-1)!}.$$

Similarly we can resolve the convolution after the Laplace transform by writing $$\mathcal L[l_n*l_k](t) = \mathcal L[l_n](t)\cdot\mathcal L[l_m](t).$$

Let's define $$x(t) = - \int_\Gamma e^{-st} \frac{\log(s)}{2\pi i s}ds.$$ Then it's derivative is: $$\dot{x}(t)= \int_\Gamma e^{-st} \frac{\log(s)}{2\pi i}ds.$$ This integral (by collapsing the path $\Gamma$ to a line) is equal to $\int_0^\infty e^{-st} ds=\frac{1}{t}$, so we finally get $$\dot{x}(t) = \frac{1}{t}.$$ So $x(t) = \log(t) + c$.
But unfortunately I was wrong above and the constant does not vanish. We have $c = x(1)$ and the relations for $l_n$'s have to change.


text:
# Limits of binomial distribution

We know that as $n \to \infty$, the binomial distribution $B(n, p)$, with fixed $p$, after appropriate normalization, converges to a normal distribution. If $p = c/n$ for some constant $c$, then it converges to the Poisson distribution.

What happens for intermediate cases, say when $p = c n^{-\alpha}$ for fixed $c$ and $0 < \alpha < 1$. After appropriate normalization, what is the limiting distribution of $B(n,p)$?

-

Assume the distribution of $X_n$ is binomial $(n,p)$. Then, for every real number $t$, $$\mathrm E(\mathrm e^{\mathrm it(X_n-np)})=\mathrm e^{\mathrm itnp}(1-p+p\mathrm e^{\mathrm it})^n.$$ Assuming that $p\to0$ when $n\to\infty$, standard limited expansions yield $$\mathrm E(\mathrm e^{\mathrm it(X_n-np)})=\exp\left(-\tfrac12npt^2(1-p)+O(npt^3)\right).$$ Let us assume that $np\to\infty$ when $n\to\infty$ and choose $t=s/\sqrt{np}$ for a given $s$. Then $npt^2(1-p)\to s^2$ and $npt^3=s^3/\sqrt{np}\to0$, hence $$\mathrm E(\mathrm e^{\mathrm is(X_n-np)/\sqrt{np}})\to\mathrm e^{-s^2/2}.$$ Thus, $(X_n-np)/\sqrt{np}$ converges in distribution to the standard gaussian distribution when $n\to\infty$, as soon as $p\to0$ and $np\to\infty$.

-

I believe with a fairly standard scaling and shifting, we can recover a normal limit for any $0 < \alpha < 1$ by a standard application of the Lindeberg–Feller theorem.

Define the triangular array of random variables $X_{n,m}$, $1 \leq m \leq n$ such that each row contains iid elements distributed as $\mathrm{Bernoulli}(cn^{-\alpha})$ random variables. Then $S_n = \sum_{m=1}^n X_{n,m}$ is $B(n,p)$ with $p = c n^{-\alpha}$.

Now, shift and rescale by taking $Y_{n,m} = n^{-(1-\alpha)/2} (X_{n,m} - c n^{-\alpha})$. Note that $\mathbb E Y_{n,m} = 0$ and $\mathbb E Y_{n,m}^2 = n^{-1} c (1 - c n^{-\alpha})$.

We need only check the Lindeberg–Feller conditions:

1. $\sum_{m=1}^n \mathbb E Y_{n,m}^2 = c (1-cn^{-\alpha}) \to c > 0$, and
2. For all $\epsilon > 0$, $\lim_{n\to\infty} \sum_{m=1}^n \mathbb E |Y_{n,m}|^2 1_{(|Y_{n,m}|^2 > \epsilon)} = 0$.

The second one follows since $1_{(|Y_{n,m}|^2 > \epsilon)} = 0$ for all sufficiently large $n$ since $|Y_{n,m}|^2 \leq n^{-(1-\alpha)} (1+c)^2$ almost surely.

Hence $n^{-(1-\alpha)/2} (S_n - c n^{1-\alpha}) \;\xrightarrow{\;d\;}\; \mathcal N(0,c)$.

To see what fails in the case where $\alpha = 1$, note that the indicator function $1_{(|Y_{n,m}|^2 > \epsilon)}$ will no longer go to zero almost surely. Therefore the second condition will fail because there will be a contribution of $c n^{-1} (1-c/n)^2$ in expectation for each of the $n$ terms, which, when added up yields (obviously) a nonzero limit.

-

The total variation distance between $B(n,p)$ and Poisson($np$) goes to 0 as $n\to\infty$ whenever $p\to 0$. See http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2086772 for example. This means that the Poisson and normal ranges overlap considerably and you don't need anything else.

-
I disagree with the last part of your last sentence, which puts undue significance in the result recalled in the first sentence. For example, if $np\to0$, the distance between Poisson $(np)$ and a Dirac mass at $0$ ALSO goes to $0$ hence in this regime, the result simply says that $B(n,p)$ converges to a Dirac mass at $0$. Similarly, if $np\to\infty$, Poisson $(np)$ is itself (when shifted by $np$ and rescaled by $\sqrt{np}$) approximately standard gaussian hence in this regime, the result is simply an unusual way of stating that a CLT holds. – Did Feb 14 '12 at 10:30
I don't see your point. If $np\to 0$, the explicit bounds on the tdv given in the linked paper show more than just accumulation at 0. However, there are stronger results in that case to be sure (very easily obtained). For $np\to\infty$, you are right that scaled Poisson is close to normal, but that's what "the Poisson and normal ranges overlap considerably" means. The OP asked what happens between the ranges where binomial is like Poisson and where binomial is like normal, and the correct answer is that there is nothing between them. – Brendan McKay Feb 14 '12 at 19:10
My point is that in these two regimes, the Poisson distribution is a red herring, for a Dirac distribution or for a gaussian one. (I read your comment by chance, please use @ when commenting to someone else than the author of the post.) – Did Feb 15 '12 at 0:48
@Didier Piau: Depending on the way $p$ varies as a function of $n$ (except for $p=1-o(1/n)$), $B(n,p)$ is well approximated by either the Poisson or Normal distribution. The details depend on the distance measure, but for most measures (total variation distance being one) the Poisson approximation remains better than the normal well into the range where the binomial is asymptotically normal. For tiny $p$, the Poisson approximation is better than the Dirac approximation. Do you disagree with any of these statements? – Brendan McKay Feb 15 '12 at 9:08
1. Let $X_1,X_2,...,X_n$ be independent and identically distributed random variables such that $E(X_i) = 0, Var(X_i) = 1$ and denote $W=n^{-1/2}\sum X_i$. By using Stein's method, we have that $$d_W(\mathcal{L}(W),N(0,1)) \leq \frac{5 E|X_1|^3}{n^{1/2}},$$ where $d_W$ is the Wasserstein metric.

2. Any binomial distribution $B(n, p)$ is the sum of $n$ independent Bernoulli trials $B(1, p)$, so you can consider $X_i$ as a normalized Bernoulli random variable and apply the above inequality.

-


text:
Published on

# How I manage my bookmarks productively

427 words • 3 min read

Over the years I have found myself bookmarking a lot of websites as I travel around the internet. After a point, carelessly bookmarking websites only increases the clutter, and makes you less productive if you're trying to find something you've saved.

Here is what I came up with to solve this problem for myself. My bookmarks folder only has a bunch of folders and every website I save goes into one of these folders.

Initially my bookmarks were a messy bunch of all sorts of websites and YouTube video and what not. After realising that I need to clean up everything, I made a couple of folders as a baseline that I thought would be able to accomodate all the bookmarks that I had up until that point.

Webdev resources, Side project ideas, Productivity, Music, Read again, Inspiration and Cool tools

I sorted all my existing bookmarks into one of these folders, and if I felt like a bookmark didn't belong to any of these, then I made a new folder based on what the specific bookmark was about. I ended up with a few more folders, like Vim, Ruby on Rails, Books etc.

Now for every website that I want to save, I have a mental framework for how I will be using it in the future. Found a developer's protfolio that I found really cool? Let me save it in Inspiration so that I will find it again when I'm casually going through the folder when I'm feeling a creative block. What about this clever blog that I read? I'll save it in Read again so that I can read it again sometime, or want to share it with someone later on (I also save interesting videos that I technically want to "watch again" in here). Then there is Music where I have a bunch of YouTube playlists and stuff.

I would highly recommend you clean up your bookmarks folder in a similar manner and categorize everything based on some criteria that makes it easier for you to go back to them. It might take you an afternoon, but trust me its worth it. Who knows, you might even even find some old hidden gem of a bookmark that you had forgotten about while cleaning up everything :)


text:
The Azimuthal decorrelation of jets widely separated in rapidity
Phys.Rev.Lett. 77 (1996) 595-600, 1996.
The collaboration

Abstract (data abstract)
Fermilab Tevatron. Measurement of the azimuthal decorrelation between jets with pseudorapidity separation up to 5 units produced in PBAR-P collisions at a centre-of-mass energy of 1800 GeV. The data were taken during 1992-1993 collider run.. Data are read from the plots in the paper.


text:
Comment
Share
Q)

# The structure given below is known as :

$(a)\;Penicillin -F \\ (b)\; Penicillin -G \\(c)\;Penicillin -K \\ (d)\;Ampicillin$

$Penicillin -G$ is correct


text:
## General Chemistry

### Matter

Question
13 out of 14

The following reactions were conducted in a lab for studies related to reaction kinetics. Consider the reactions shown below:

Which of the following is the actual formula of dextrose, if the empirical proportion is 1:2:1, where the proportion number 2 is that of hydrogen. Dextrose has a molecular weight of 180 g/mol? (Dextrose molecule is composed of carbon, hydrogen, and oxygen)

 A CHO B C6H12O6 C C12H6O3 D CH2O
Ans. B From the question, we can say that the empirical formula of dextrose is CH2O. The molecular weight of dextrose is also given. Let's first calculate the weight of the empirical formula. Maybe the empirical formula represents the actual formula. The weight of the empirical formula is 30 g/mol. But the question says it is 180 g/mol. In this case, the molecular formula is not the same as the empirical formula. By dividing the actual weight by the empirical weight, we will get the coefficient with which we have to multiply the empirical formula to get the actual formula. The coefficient is 180/30 = 6. So the molecular formula is C6H12O6. Have you heard of glucose? Well, dextrose is the same thing. If you knew that, you could have picked the answer right away. But more importantly, it is the process that you have to learn from this question.


text:
Last Problem: Partial Fractions Integration

1. Sep 20, 2007

Lanza52

Need a check on the last problem of my test:

integral (3x^2-8x+13)/(x^3+x^2-5x+3)

Factor for the denom is (x-1)(x-1)(x+3). So a/(x-1) + b/(x-1)^2 + c/(x+3) = the f(x) in the integral

Factor out and multiply all the polynomials. Comes down to a = -1, b = -2, c = 2

Integral comes to:

2/(x-1)+ln|(x+3)/(x-1)|+k

2. Sep 21, 2007

Gib Z

Sorry if I sound harsh, but check yourself. Find the derivative of your integral, and if it matches your integrand, then you are correct.


text:
How long is the Greek measure called a "stadium"?

57 views
How long is the Greek measure called a "stadium"?
posted Dec 1, 2017

The Greek unit of measurement, the stade, the distance covered in the original Greek footraces which is about 600 feet or 180 metres.


text:
# Warning: Clusters May Appear More Separated in Textbooks than in Practice

March 23, 2014
By

(This article was first published on Engaging Market Research, and kindly contributed to R-bloggers)

Clustering is the search for discontinuity achieved by sorting all the similar entities into the same piles and thus maximizing the separation between different piles. The latent class assumption makes the process explicit. What is the source of variation among the objects? An unseen categorical variable is responsible. Heterogeneity arises because entities come in different types. We seem to prefer mutually exclusive types (either A or B), but will settle for probabilities of cluster membership when forced by the data (a little bit A but more B-like). Actually, we are more likely to acknowledge that our clusters overlap early on and then forget because it is so easy to see type as the root cause of all variation.

I am asking the reader to recognize that statistical analysis and its interpretation extend over time. If there is variability in our data, a cluster analysis will yield partitions. Given a partitioning, a data analyst will magnify those differences by focusing on contrastive comparisons and assigning evocative names. Once we have names, especially if those names have high imagery, can we be blamed for the reification of minor distinctions? How can one resist segments from Nielsen PRIZM with names like "Shotguns and Pickups" and "Upper Crust"? Yet, are "Big City Blues" and "Low-Rise Living" really separate clusters or simply variations on a common set of dwelling constraints?

Taking our lessons seriously, we expect to see the well-separated clusters displayed in textbooks and papers. However, our expectations may be better formed than our clusters. We find heterogeneity, but those differences are not clumping or distinct concentrations. Our data clouds can be parceled into regions, although those parcels run into one another and are not separated by gaps. So we name the regions and pretend that we have assigned names to types or kinds of different entities with properties that control behavior over space and time. That is, we have constructed an ontology specifying categories to which we have given real explanatory powers.

Consider the following scatterplot from the introductory vignette in the R package mclust. You can find all the R code needed to produce these figures at the end of this post.

This is the Old Faithful geyser data from the "datasets" R package showing the waiting time in minutes between successive eruptions on the y-axis and the duration of the eruptions along the x-axis. It is worth your time to get familiar with Old Faithful because it is one of those datasets that gets analyzed over and over again using many different programs. There seems to be two concentrations of points: shorter eruption that occurs more quickly and longer eruptions that have a longer waiting period. If we told the Mclust function from the mclust package that the scatterplot contains observations from G=2 groups, the function would produce a classification plot that looked something like this:

The red and the blue with their respective ellipses are the two normal densities that are getting mixed. It is such a straightforward example of finite mixture or latent class models (as these models are also called by analysts in other fields of research). If we discovered that there were two pools feeding the geyser, we could write a compelling narrative tying all the data together.

The mclust vignette or manual is comprehensive but not overly difficult. If you prefer a lecture, there is no better introduction to finite mixture than the MathematicalMonk YouTube video. The key to understanding finite mixture models is recognizing that the underlying latent variable responsible for the observed data is categorical, a latent class which we do not observe, but which explains the location and shape of the data points. Do you have a cold or the flu? Without medical tests, all we can observe are your symptoms. If we filled a room with coughing, sneezing, achy and feverish people, we would find a mixture of cold and flu with differing numbers of each type.

This appears straightforward, but for the general case, how does decide how many categories, in what proportions, and with what means and covariance matrices? That is, those two ellipses in the above figure are drawn using a vector with means for the x- and y-axes plus a 2x2 covariance matrix. The means move the ellipse over the space, and the covariance matrix changes the shape and orientation of the ellipse. A good summary of the possible forms is given in Table 1 of the mlcust vignette.

Unfortunately, the mathematics of the EM algorithm used to solve this problem gets complicated quickly. Fortunately, Chris Bishop provides an intuitive introduction in a 2004 video lecture. Starting at 44:14 of Part 4, you will find a step-by-step description of how the EM algorithm works with the Old Faithful data. Moreover, in Chapter 9 of his book, Bishop cleverly compares the workings of the EM and k-means algorithms, leaving us with a better understanding of both techniques.

If only my data showed such clear discontinuity and could be tied to such a convincing narrative.

Product Categories Are Structured around the Good, the Better, and the Best

Almost every product category offers a range of alternatives that can be described as good, better, and best. Such offerings reflect the trade-offs that customers are willing to make between the quality of the products they want and the amount that they are ready to spend. High-end customers demand the best and will pay for it. On the other end, one finds customers with fewer needs and smaller budgets accepting less and paying less. Clearly, we have heterogeneity, but are those differences continuous or discrete? Can we tell by looking at the data?

Unlike the Old Faithful data with well-separated grouping of data points, product quality-price trade-offs look more like the following plot of 300 consumers indicating how much they are willing to spend and what they expect to get for their money (i.e., product quality is a composite index combining desired features and services).

There is a strong positive relationship between demand for quality and willingness to pay, so a product manager might well decide that there was opportunity for at least a high-end and a low-end option. However, there is no natural breaks in the scatterplot. Thus, if this data cloud is a mixture of distinct distributions, then these distributions must be overlapping.

Another example might help. As shown by John Cook, the distribution of heights among adults is a mixture two overlapping normal distribution, one for men and another for women. Yet, as you can observe from Cook's plots, the mixture of men's and women's height does not appear bimodal because the separation between the two distributions is not large enough. If you follow the links in Cook's post, eventually you will find the paper "Is Human Height Bimodal?", which clearly demonstrates that many mixtures of distributions appear to be homogeneous. We simply cannot tell that they are mixture by looking just at the shape of the distribution for the combined data. The Old Faithful data with its well-separated bimodal curve provides a nice contrast, especially when we focus only on waiting time as a single dimension (Fitting Mixture Models with the R Package mixtools).

Perhaps then, segmentation does not require gaps in the data cloud. As Wedel and Kamakura note, "Segments are not homogeneous groupings of customers naturally occurring in the marketplace, but are determined by the marketing manager's strategic view of the market." That is, one could look at the above scatterplot, see the presence of a strong first principal component from the closest of the data points to the principal axis of the ellipse and argue that customer heterogeneity is a single continuous dimension running from the low- to the high-end of the product spectrum. Or, one could look at the same scatterplot and see three overlapping segments seeking basic, value and premium products (good, better, best). Let's run mclust and learn if we can find our three segments.

When instructed to look for three clusters, the Mclust function returned the above result. The 300 observed points are represented as a mixture of three distributions falling along the principal axis of the larger ellipse formed by all the observations. However, if I had not specified three clusters and asked Mclust to use its default BIC criterion to select the number of segments, I would have been told that there was no compelling evidence for more than one homogeneous group. Without any prior specification Mclust would have returned a single homogeneous distribution, although as you can see from the R code below, my 300 observations were a mixture of three equal size distributions falling along the principal axis and separated by one standard deviation.

Number of Segments = Number Yielding Value to Product Management

Market segmentation lies somewhere between mass marketing and individual customization. When mass marketing fails because customers have different preferences or needs and customization is too costly or difficult, the compromise is segmentation. We do not need "natural" grouping, but just enough coherence for customers to be satisfied by the same offering. Feet come in many shapes and sizes. The shoe manufacturer can get along with three sizes of sandals but not three sizes of dress shoes. It is not the foot that is changing, but the demands of the customer. Thus, even if segments are no more than convenient fictions, they can be useful from the manager's perspective.

My warning still holds. Reification can be dangerous. These segments are meaningful only within the context of the marketing problem created by trying to satisfy everyone with products and services that yield maximum profit. Some segmentations may return clusters that are well-separated and represent groups with qualitatively different needs and purchase processes. Many of these are obvious and define different markets. If you don't have a dog, you don't buy dog food. However, when segmentation seeks to identify those who feel that their dog is a member of the family, we will find overlapping clusters that we treat differently not because we have revealed the true underlying typology, but because it is in our interest. Don't be fooled into believing that our creative segment names reveal the true workings of the consumer mind.

Finally, what is true for marketing segmentation is true for all of cluster analysis. "Clustering: Science or Art?" (a 2009 NIPS workshop) raises many of these same issues for cluster analysis in general. Videos of this workshop are available at Videolectures. Unlike supervised learning with its clear criterion for success and failure, clustering depends on users of the findings to tell us if the solution is good or bad, helpful or not. On the one hand, this seems to make everything more difficult. On the other hand, it frees us to be more open to alternative methods for describing heterogeneity as it is now and how it evolves over time.

We seek to understand the dynamic structure of diversity, which only sometimes takes the form of cohesive clusters separated by gaps. Other times, a model with only continuous latent variables seems to be the best choice (e.g., brand perceptions). And, not unexpectedly, there are situations where heterogeneity cannot be explained without both categorical and continuous latent variables (e.g., two or more segments seeking alternative benefit profiles with varying intensities).

Yet, even these three combinations cannot adequately account for all the forms of diversity we find in consumer data.  Innovation might generate a structure appearing more like long arrays or streams of points seemingly pulled toward the periphery by an archetypal ideal or aspirational goal. And if the coordinate space of k-means and mixture models becomes too limiting, we can replace it with pairwise dissimilarity and graphical clustering techniques, such as affinity propagation or spectral clustering. Nor should we be wedded to the stability of our segment solution when those segments were created by dynamic forces that continue to act and alter its structure. Our models ought to be as diverse as the objects we are studying.

R code for all figures and analysis

#attach faithful data setdata(faithful)plot(faithful, pch="+") #run mclust on faithful datarequire(mclust)faithfulMclust<-Mclust(faithful, G=2)summary(faithfulMclust, parameters=TRUE)plot(faithfulMclust) #create 3 segment data setrequire(MASS)sigma <- matrix(c(1.0,.6,.6,1.0),2,2)mean1<-c(-1,-1)mean2<-c(0,0)mean3<-c(1,1)set.seed(3202014)mydata1<-mvrnorm(n=100, mean1, sigma)mydata2<-mvrnorm(n=100, mean2, sigma)mydata3<-mvrnorm(n=100, mean3, sigma)mydata<-rbind(mydata1,mydata2,mydata3)colnames(mydata)<-c("Desired Level of Quality",                    "Willingness to Pay")plot(mydata, pch="+") #run Mclust with 3 segmentsmydataClust<-Mclust(mydata, G=3)summary(mydataClust, parameters=TRUE)plot(mydataClust) #let Mclust decide on number of segmentsmydataClust<-Mclust(mydata)summary(mydataClust, parameters=TRUE)

Created by Pretty R at inside-R.org


text:
Want to ask us a question? Click here
Browse Questions
 Ad
Home  >>  AIMS  >>  Class12  >>  Chemistry
0 votes

# In a crystalline solid, having formula $AB_2O_4$, oxide ions are arranged in cubic close packed lattice while cations A are present in tetrahedral voids and cations B are present in octahedral voids.(i) What percentage of the tetrahedral voids is occupied by A?

$\begin{array}{1 1}(A)\;12\%&(B)\;12.3\%\\(C)\;12.5\%&(D)\;13.5\%\end{array}$

Can you answer this question?

## 1 Answer

0 votes
In a cubic close packed lattice of oxide ions there would be two tetrahedral voids and one octahedral void for each oxide ion.
$\therefore$ For four oxide ions there would be 8 tetrahedral and four octahedral voids two are occupied by B.
Percentage of tetrahedral voids occupied by A =$\large\frac{1}{8}$$\times 100=12.5\%$
Hence (C) is the correct answer.
answered May 28, 2014

0 votes
1 answer


text:
## anonymous 4 years ago explain this equation

1. anonymous

s^2=/_\r^2-c^2/_\t^2

2. anonymous

it is the euclidean spacetime interval equation

3. anonymous

@agentx5 @sami-21 ...i dont know how to write this equation there are no keys of scientific operators in my keyboard

4. anonymous

you type $\text{\[ s^2 = r^2 - c^2 t^2$ } \]

5. anonymous

It will become $s^2 = r^2 - c^2 t^2$

6. anonymous

there are delta symbols before r and t

7. anonymous

$\text{ \[ s^2 = \Delta \r^2 - c^2 \Delta t^2$ } \]

8. anonymous

$s^2 = \Delta r^2 - c^2 \Delta t^2$

9. anonymous

oh thank you very much...

10. anonymous

:)

11. anonymous

Spacetime isn't Euclidean, by the way. Did you have a question about that equation?

12. anonymous

yes found that in wikipedia when i typed spacetime what are those equations and wat do u mean by it is not euclidean? http://en.wikipedia.org/wiki/Spacetime

13. anonymous

In Euclidean three-dimensional space, the distance between two points is defined as $\Delta r = \sqrt{ (\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2 }$ or equivalently, $(\Delta r)^2 = (\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2$

14. anonymous

That distance, which can be thought of as the separation between two points in space, is invariant under translation and rotation. That means that an observer moving through Euclidean space would observe the distance between two objects to be exactly the same no matter which way they were turned and no matter how they happened to be moving.

15. anonymous

However, when we combine the dimension of time with the dimensions of space in a four-dimensional manifold called spacetime, we label our points not as points in space but as events in space and time. However, relativistically it turns out that observers moving at different speeds would not measure the distance above to be the same, and therefore $(\Delta r)^2 = (\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2$ is no longer invariant.

16. anonymous

However, it was found that there is an analogous invariant interval that will be measured to be the same by all observers regardless of velocity. That interval is called s^2, and is written as $s^2 = (\Delta r)^2 - (c\Delta t)^2 = (\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2 - (c\Delta t)^2$ This plays the role of the invariant interval in four-dimensional spacetime.

17. anonymous

Lastly, spacetime is not Euclidean because that invariant interval has a minus sign in it. If it were a plus sign, it would be Euclidean space, but it's not. It's usually referred to as Minkowski space.

18. anonymous

As an FYI, sometimes the minus sign gets reversed. For reasons I'm not going to go into because it requires knowledge of special relativity, I prefer to write the spacetime interval as $s^2 = (c\Delta t)^2 - (\Delta r)^2$

19. anonymous

(Note that the choice of signs for$s^2$ above follows the space-like convention (-+++). Other treatments reverse the sign of $s^2$ Spacetime intervals may be classified into three distinct types based on whether the temporal separation ($c^2\Delta t^2$) or the spatial separation ($\Delta r^2$) of the two events is greater what does this mean please explain it @Jemurray3 ...thank you very much

20. anonymous

if $(c\Delta t)^2 > r^2$ then the interval is called timelike. If $(c\Delta t)^2 < r^2$ then the interval is called spacelike and if they're equal, the interval is called lightlike.

21. anonymous

Events that are separated by spacelike intervals cannot be causally connected because the time it would take for information to travel from one point in space to another (at the speed of light) is greater than the separation of those two points in time. I.e. if I clapped my hands on earth and an alien in the andromeda galaxy fell out of his chair, there couldn't possibly be a causal connection between these two events because it would take years for the signal to traverse the space between us.

22. anonymous

dont be mad at me...could you please explain what this invariant interval actually mean..if it is the distance it should be S right but it is $S^2$ HEREwhich means $m^2$ right

23. anonymous

@theyatin

24. anonymous

@mahmit2012 @musicalrose @mukushla

25. anonymous

@91 @FoolAroundMath

26. anonymous

It is the spacetime equivalent of distance, yes. Take the square root if you'd like, but if s is invariant then s^2 is as well, and because it can be negative you can get into trouble. It's just more useful to refer to s^2, in general.

27. anonymous

so no problem abt the unit

28. anonymous

The units are consistent. Honestly the invariant spacetime interval is not of much use without the rest of special relativity, and the geometry and topological properties of flat spacetime (Minkowski space) require more mathematics to adequately understand, so I don't really think you should worry about it until you have a more thorough grounding in the math and physics.

29. anonymous

one last question how did we incorporate that term $c \Delta t^2$? why do we subtract it from the variant euclidean distance why not plus it?

30. anonymous

though its mathematical pls explain...

31. anonymous

It didn't just pop out of nowhere. If there was a plus sign, rather than a minus sign, then the interval would change depending on the observer. Once you derive the Lorentz transformation equations of special relativity, it can be shown that the quantity s^2 as written above is the same for all inertial observers.


text:
Home » Ask Physics » Planck’s postulates on quantum physics

# Planck’s postulates on quantum physics

Share with:

I don’t seem to get Planck’s postulates on quantum physics. (Posted  Isaac Atia)

The Planck postulate (or Planck’s postulate) is one of the fundamental principles of quantum mechanics. According to Planck, the energy of oscillators in a black body is quantized, and is given by

# E = n hν

where  is an integer (1, 2, 3, …),  is Planck’s constant, and  is the frequency of the oscillator

Name (required)

Email (required)

Subject

Message/Doubt/Question


text:
# californium

The Simple English Wikipedia has an article on:

berkelium${\displaystyle \longleftarrow }$ 98 ${\displaystyle \longrightarrow }$einsteinium

## Noun

 Plural none
1. (uncountable) Californium is a metallic (meaning made of metal) element with an atomic number of 98 and symbol Cf.