text:
Implementing SpECTRE vectors

Overview of SpECTRE Vectors

In SpECTRE, sets of contiguous or related data are stored in specializations of vector data types. The canonical implementation of this is the DataVector, which is used for storage of a contiguous sequence of doubles which support a wide variety of mathematical operations and represent data on a grid used during an evolution or elliptic solve. However, we support the ability to easily generate similar vector types which can hold data of a different type (e.g. std::complex<double>), or support a different set of mathematical operations. SpECTRE vector classes are derived from the class template VectorImpl. The remainder of this brief guide gives a description of the tools for defining additional vector types.

For reference, all functions described here can also be found in brief in the Doxygen documentation for VectorImpl.hpp, and a simple reference implementation can be found in DataVector.hpp and DataVector.cpp.

The class definition

SpECTRE vector types inherit from vector types implemented in the high-performance arithmetic library Blaze. Using inheritance, SpECTRE vectors gracefully make use of the math functions defined for the Blaze types, but can be customized for the specific needs in SpECTRE computations.

The pair of template parameters for VectorImpl are the type of the stored data (e.g. double for DataVector), and the result type for mathematical operations. The result type is used by Blaze to ensure that only compatible vector types are used together in mathematical expressions. For example, a vector representing double data on a grid (DataVector) cannot be added to a vector representing spectral coefficients (ModalVector). This avoids subtle bugs that arise when vector types are unintentionally mixed. In nearly all cases the result type will be the vector type that is being defined, so, for instance, DataVector is a derived class of VectorImpl<double, DataVector>. This template pattern is known as the "Curiously Recurring Template Pattern" (CRTP).

For the Blaze system to use the CRTP inheritance appropriately, it requires the specification of separate type traits in the blaze namespace. These traits can usually be declared in a standard form, so are abstracted in a macro. For any new vector MyNewVector, the pattern that must appear at the beginning of the file (i.e. before the class definition) is:

///
namespace blaze {
DECLARE_GENERAL_VECTOR_BLAZE_TRAITS(MyNewVector);
}

The class template VectorImpl defines various constructors, assignment operators, and iterator generation members. Most of these are inherited from Blaze types, but in addition, the methods set_data_ref, and pup are defined for use in SpECTRE. All except for the assignment operators and constructors will be implicitly inherited from VectorImpl. The assignment and constructors may be inherited calling the following alias code in the vector class definition:

using VectorImpl<T,VectorType>::operator=;
using VectorImpl<T,VectorType>::VectorImpl;

Only the mathematical operations supported on the base Blaze types are supported by default. Those operations are determined by the storage type T and by the Blaze library. See blaze-wiki/Vector_Operations.

Allowed operator specification

Blaze keeps track of the return type of unary and binary operations using "type trait" structs. These specializations for vector types should be placed in the header file associated with the VectorImpl specialization. For DataVector, the specializations are defined in DataStructures/DataVector.hpp. The presence or absence of template specializations of these structs also determines the set of allowed operations between the vector type and other types. For example, if adding a double to a DataVector should be allowed and the result should be treated as a DataVector for subsequent operations, then the struct blaze::AddTrait<DataVector, double> needs to be defined as follows:

namespace blaze {
// the template <> head tells the compiler that
// AddTrait<DataVector, double> is a class template specialization
template <>
struct AddTrait<DataVector, double> {
// the Type alias tells blaze that the result should be treated like a
// DataVector for any further operations
using Type = DataVector;
};
} // namespace blaze

Note that this only adds support for DataVector + double, not double + DataVector. To get the latter the following AddTrait specialization must be defined

namespace blaze {
// the template <> head tells the compiler that
// AddTrait<double, DataVector> is a class template specialization
template <>
struct AddTrait<double, DataVector> {
// the Type alias tells blaze that the result should be treated like a
// DataVector for any further operations
using Type = DataVector;
};
} // namespace blaze

Four helper macros are defined to assist with generating the many specializations that binary operations may require. Both of these macros must be put inside the blaze namespace for them to work correctly.

The first of these helper macros is BLAZE_TRAIT_SPECIALIZE_BINARY_TRAIT(VECTOR_TYPE, BLAZE_MATH_TRAIT), which will define all of the pairwise operations (BLAZE_MATH_TRAIT) for the vector type (VECTOR_TYPE) with itself and for the vector type with its value_type. This reduces the three specializations similar to the above code blocks to a single line call,

namespace blaze {
} // namespace blaze

The second helper macro is provided to easily define all of the arithmetic operations that will typically be supported for a vector type with its value type. The macro is VECTOR_BLAZE_TRAIT_SPECIALIZE_ARITHMETIC_TRAITS(VECTOR_TYPE), and defines all of:

• IsVector<VECTOR_TYPE> to std::true_type
• TransposeFlag<VECTOR_TYPE>, which informs Blaze of the interpretation of the data as a "column" or "row" vector
• AddTrait for the VECTOR_TYPE and its value type (3 Blaze struct specializations)
• SubTrait for the VECTOR_TYPE and its value type (3 Blaze struct specializations)
• MultTrait for the VECTOR_TYPE and its value type (3 Blaze struct specializations)
• DivTrait for the VECTOR_TYPE and its value type (3 Blaze struct specializations)

This macro is similarly intended to be used in the blaze namespace and can substantially simplify these specializations for new vector types. For instance, the call for DataVector is:

namespace blaze {
VECTOR_BLAZE_TRAIT_SPECIALIZE_ARITHMETIC_TRAITS(DataVector)
} // namespace blaze

The third helper macro is provided to define a combination of Blaze traits for symmetric operations of a vector type with a second type (which may or may not be a vector type). The macro is BLAZE_TRAIT_SPECIALIZE_COMPATIBLE_BINARY_TRAIT(VECTOR, COMPATIBLE, TRAIT), and defines the appropriate trait for the two combinations <VECTOR, COMPATIBLE> and <COMPATIBLE, VECTOR>, and defines the result type to be VECTOR. For instance, to support the multiplication of a ComplexDataVector with a DataVector and have the result be a ComplexDataVector, the following macro call should be included in the blaze namespace:

namespace blaze {
BLAZE_TRAIT_SPECIALIZE_COMPATIBLE_BINARY_TRAIT(ComplexDataVector, DataVector,
MultTrait);
} // namespace blaze

Finally, the fourth helper macro is provided to define all of the blaze traits which are considered either unary or binary maps. This comprises most named unary functions (like sin() or sqrt()) and named binary functions (like hypot() and atan2()). The macro VECTOR_BLAZE_TRAIT_SPECIALIZE_ALL_MAP_TRAITS(VECTOR_TYPE) broadly specializes all blaze-defined maps in which the given VECTOR_TYPE as the sole argument (for unary maps) or both arguments (for binary maps). This macro is also intended to be used in the blaze namespace. The call for DataVector is:

namespace blaze {
VECTOR_BLAZE_TRAIT_SPECIALIZE_ALL_MAP_TRAITS(DataVector)
} // namespace blaze

Supporting operations for <tt>std::array</tt>s of vectors

In addition to operations between SpECTRE vectors, it is useful to gracefully handle operations between std::arrays of vectors element-wise. There are general macros defined for handling operations between array specializations: DEFINE_STD_ARRAY_BINOP and DEFINE_STD_ARRAY_INPLACE_BINOP from Utilities/StdArrayHelpers.hpp.

In addition, there is a macro for rapidly generating addition and subtraction between arrays of vectors and arrays of their data types. The macro MAKE_STD_ARRAY_VECTOR_BINOPS(VECTOR_TYPE) will define:

• the element-wise + and - with std::array<VECTOR_TYPE, N> and std::array<VECTOR_TYPE, N>
• the element-wise + and - of either ordering of std::array<VECTOR_TYPE, N> with std::array<VECTOR_TYPE::value_type, N>
• the += and -= of std::array<VECTOR_TYPE, N> with a std::array<VECTOR_TYPE, N>
• the += and -= of std::array<VECTOR_TYPE, N> with a std::array<VECTOR_TYPE::value_type, N>.

Equivalence operators

Equivalence operators are supported by the Blaze type inheritance. The equivalence operator == evaluates to true on a pair of vectors if they are the same size and contain the same values, regardless of ownership.

MakeWithValueImpl

SpECTRE offers the convenience function make_with_value for various types. The typical behavior for a SpECTRE vector type is to create a new vector type of the same type and length initialized with the value provided as the second argument in all entries. This behavior may be created by placing the macro MAKE_WITH_VALUE_IMPL_DEFINITION_FOR(VECTOR_TYPE) in the .hpp file. Any other specializations of MakeWithValueImpl will need to be written manually.

Interoperability with other data types

When additional vector types are added, small changes are necessary if they are to be used as the base container type either for Tensors or for Variables (a Variables contains Tensors), which contain some vector type.

In Tensor.hpp, there is a static_assert which white-lists the possible types that can be used as the storage type in Tensors. Any new vectors must be added to that white-list if they are to be used within Tensors.

Variables is templated on the storage type of the stored Tensors. However, any new data type should be appropriately tested. New vector types should be tested by invoking new versions of existing testing functions templated on the new vector type, rather than DataVector.

Writing tests

In addition to the utilities for generating new vector types, there are a number of convenience functions and utilities for easily generating the tests necessary to verify that the vectors function appropriately. These utilities are in VectorImplTestHelper.hpp, and documented individually in the TestingFrameworkGroup. Presented here are the salient details for rapidly assembling basic tests for vectors.

Utility check functions

Each of these functions is intended to encapsulate a single frequently used unit test and is templated (in order) on the vector type and the value type to be generated. The default behavior is to uniformly sample values between -100 and 100, but alternative bounds may be passed in via the function arguments.

<tt>TestHelpers::VectorImpl::vector_test_construct_and_assign()</tt>

This function tests a battery of construction and assignment operators for the vector type.

<tt>TestHelpers::VectorImpl::vector_test_serialize()</tt>

This function tests that vector types can be serialized and deserialized, retaining their data.

<tt>TestHelpers::VectorImpl::vector_test_ref()</tt>

This function tests the set_data_ref method of sharing data between vectors, and that the appropriate owning flags and move operations are handled correctly.

<tt>TestHelpers::VectorImpl::vector_test_math_after_move()</tt>

Tests several combinations of math operations and ownership before and after use of std::move.

<tt>TestHelpers::VectorImpl::vector_ref_test_size_error()</tt>

This function intentionally generates an error when assigning values from one vector to a differently sized, non-owning vector (made non-owning by use of set_data_ref). The assertion test which calls this function should search for the string "Must copy into same size". Three forms of the test are provided, which are switched between using a value from the enum RefSizeErrorTestKind in the first function argument:

• RefSizeErrorTestKind::Copy: tests that the size error is appropriately generated when copying to a non-owning vector of the wrong size.
• RefSizeErrorTestKind::ExpressionAssign: tests that the size error is appropriately generated when assigning the result of a mathematical expression to a non-owning vector of the wrong size.
• RefSizeErrorTestKind::Move: tests that the size error is appropriately generated when a vector is std::moved into a non-owning vector of the wrong size

<tt>TestHelpers::VectorImpl::test_functions_with_vector_arguments()</tt>

This is a general function for testing the mathematical operation of vector types with other vector types and/or their base types, with or without various reference wrappers. This may be used to efficiently test the full set of permitted math operations on a vector. See the documentation of test_functions_with_vector_arguments() for full usage details.

An example simple use case for the math test utility:

const TestHelpers::VectorImpl::Bound generic{{-100.0, 100.0}};
const TestHelpers::VectorImpl::Bound mone_one{{-1.0, 1.0}};
const TestHelpers::VectorImpl::Bound gt_one{{1.0, 100.0}};
const TestHelpers::VectorImpl::Bound positive{{0.01, 100.0}};
const auto unary_ops = std::make_tuple(
std::make_tuple(funcl::Abs<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Acos<>{}, std::make_tuple(mone_one)),
std::make_tuple(funcl::Acosh<>{}, std::make_tuple(gt_one)),
std::make_tuple(funcl::Asin<>{}, std::make_tuple(mone_one)),
std::make_tuple(funcl::Asinh<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Atan<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Atanh<>{}, std::make_tuple(mone_one)),
std::make_tuple(funcl::Cbrt<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Cos<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Cosh<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Erf<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Exp<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Exp2<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Fabs<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::InvCbrt<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::InvSqrt<>{}, std::make_tuple(positive)),
std::make_tuple(funcl::Log<>{}, std::make_tuple(positive)),
std::make_tuple(funcl::Log10<>{}, std::make_tuple(positive)),
std::make_tuple(funcl::Log2<>{}, std::make_tuple(positive)),
std::make_tuple(funcl::Sin<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Sinh<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::StepFunction<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Square<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Sqrt<>{}, std::make_tuple(positive)),
std::make_tuple(funcl::Tan<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::Tanh<>{}, std::make_tuple(generic)),
std::make_tuple(funcl::UnaryPow<1>{}, std::make_tuple(generic)),
std::make_tuple(funcl::UnaryPow<-2>{}, std::make_tuple(generic)),
std::make_tuple(funcl::UnaryPow<3>{}, std::make_tuple(generic)));
TestHelpers::VectorImpl::TestKind::Normal, DataVector>(unary_ops);

More use cases of this functionality can be found in Test_DataVector.cpp.

Vector storage nuts and bolts

Internally, all vector classes inherit from the templated VectorImpl, which inherits from a blaze::CustomVector. Most of the mathematical operations are supported through the Blaze inheritance, which ensures that the math operations execute the optimized forms in Blaze.

Blaze also offers the possibility of restricting operations via groups in the blaze::CustomVector template arguments. Currently, we do not use the blaze::GroupTag functionality to determine available operations for vectors, but in principle this feature could allow us to further simplify our operator choice logic in the SpECTRE vector code.

SpECTRE vectors can be either "owning" or "non-owning". If a vector is owning, it allocates and controls the data it has access to, and is responsible for eventually freeing that data when the vector goes out of scope. If the vector is non-owning, it acts as a (possibly complete) "view" of otherwise allocated memory. Non-owning vectors do not manage memory, nor can they change size. The two cases of data ownership cause the underlying data to be handled fairly differently, so we will discuss each in turn.

When a SpECTRE vector is constructed as owning, or becomes owning, it allocates its own block of memory of appropriate size, and stores a pointer to that memory in a std::unique_ptr named owned_data_. The std::unique_ptr ensures that the SpECTRE vector needs to perform no further direct memory management, and that the memory will be appropriately managed whenever the std::unique_ptr owned_data_ member is deleted or moved. The base blaze::CustomVector must also be told about the pointer, which is always accomplished by calling the protected function VectorImpl.reset_pointer_vector(const size_t set_size), which sets the blaze::CustomVector internal pointer to the pointer obtained by std::unique_pointer.get().

When a SpECTRE vector is constructed as non-owning by the VectorImpl(ValueType* start, size_t set_size) constructor, or becomes non-owning by the set_data_ref function, the internal std::unique_ptr named owned_data_ no longer points to the data represented by the vector and can be thought of as "inactive" for the purposes of computation and memory management. This behavior is desirable, because otherwise the std::unique_ptr would attempt to free memory that is presumed to be also used elsewhere, causing difficult to diagnose memory errors. The non-owning SpECTRE vector updates the base blaze::CustomVector pointer directly by calling blaze::CustomVector.reset from the derived class (on itself).

funcl::Sin
Functional for computing sin on an object.
Definition: Functional.hpp:273
funcl::StepFunction
Functional for computing step_function on an object.
Definition: Functional.hpp:276
funcl::Log
Functional for computing log on an object.
Definition: Functional.hpp:269
funcl::Exp
Functional for computing exp on an object.
Definition: Functional.hpp:263
funcl::Atan
Functional for computing atan on an object.
Definition: Functional.hpp:256
funcl::Log2
Functional for computing log2 on an object.
Definition: Functional.hpp:271
funcl::Atanh
Functional for computing atanh on an object.
Definition: Functional.hpp:257
funcl::InvCbrt
Functional for computing invcbrt on an object.
Definition: Functional.hpp:267
funcl::Cos
Functional for computing cos on an object.
Definition: Functional.hpp:260
funcl::Sqrt
Functional for computing sqrt on an object.
Definition: Functional.hpp:275
funcl::Tan
Functional for computing tan on an object.
Definition: Functional.hpp:277
funcl::Acos
Functional for computing acos on an object.
Definition: Functional.hpp:252
funcl::Acosh
Functional for computing acosh on an object.
Definition: Functional.hpp:253
std::array< double, 2 >
funcl::Cbrt
Functional for computing cbrt on an object.
Definition: Functional.hpp:258
funcl::Erf
Functional for computing erf on an object.
Definition: Functional.hpp:262
DataVector
Stores a collection of function values.
Definition: DataVector.hpp:46
funcl::Exp2
Functional for computing exp2 on an object.
Definition: Functional.hpp:264
funcl::Sinh
Functional for computing sinh on an object.
Definition: Functional.hpp:274
funcl::Cosh
Functional for computing cosh on an object.
Definition: Functional.hpp:261
funcl::UnaryPow
Function for computing an integer power, forwards to template pow<N>()
Definition: Functional.hpp:283
funcl::Abs
Functional for computing abs on an object.
Definition: Functional.hpp:251
funcl::Log10
Functional for computing log10 on an object.
Definition: Functional.hpp:270
funcl::Tanh
Functional for computing tanh on an object.
Definition: Functional.hpp:278
funcl::Asin
Functional for computing asin on an object.
Definition: Functional.hpp:254
funcl::InvSqrt
Functional for computing invsqrt on an object.
Definition: Functional.hpp:268
funcl::Fabs
Functional for computing fabs on an object.
Definition: Functional.hpp:265
funcl::Asinh
Functional for computing asinh on an object.
Definition: Functional.hpp:255
funcl::Square
Function for squaring a quantity.
Definition: Functional.hpp:305
TestHelpers::VectorImpl::test_functions_with_vector_arguments
void test_functions_with_vector_arguments(const std::tuple< FunctionsAndArgumentBounds... > &tuple_of_functions_and_argument_bounds) noexcept
General entry function for testing arbitrary math functions on vector types.
Definition: VectorImplTestHelper.hpp:878


text:
# Caching the workspace and warm-starts

SCS supports reusing the workspace between solves so long as the data matrices $$A$$ and $$P$$ do not change. After an initial solve the workspace can be updated with new $$b$$ and $$c$$ vectors if desired. This can substantially speed up subsequent solve times since we can cache important quantities such as the matrix factorization and the data equilibration. Moreover, SCS supports warm-starting the solver with a guess of the solution, which can significantly reduce the total number of iterations required for convergence.

Re-using the workspace and warm-starting can be useful, for example, when solving a sequence of related problems such as in Model predictive control or solving for the entire regularization path in the the Lasso.

In the C API call scs_init once to initialize the workspace, then use the scs_solve in conjunction with scs_update to solve a sequence of problems. Warm-starting can be done by setting the warm-start setting to True when calling scs_solve, and then including the guess of the solution in the x, y, s members of the Solution struct, where those members correspond to the guess of the solution in the standard form. SCS will initialize the solver at those points and then overwrite the Solution struct members with the real solution at termination.

In other languages caching the workspace and warm-starting is documented in their respective Interfaces.

format: plain


text:
Consider the system of linear congruences below: x -= 2(mod 5) 2x -= 22(mod 8) 3x -= 12(mod 21) (i)Determine two different systems of linear congruences for which the Chinese Remainder Theorem can be used and which will give at least two of these solutions.

Consider the system of linear congruences below:
$x\equiv 2\left(\text{mod}5\right)$
$2x\equiv 22\left(\text{mod}8\right)$
$3x\equiv 12\left(\text{mod}21\right)$
(i)Determine two different systems of linear congruences for which the Chinese Remainder Theorem can be used and which will give at least two of these solutions.
You can still ask an expert for help

Want to know more about Congruence?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

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

curwyrm
Step 1
i)Given that
$x\equiv 2\left(\text{mod}5\right)$
$2x\equiv 22\left(\text{mod}8\right)$
$3x\equiv 12\left(\text{mod}21\right)$
Notice first that the moduli are pairwise relatively prime, therefore, we can use the Chinese remainder theorem. In the notation of the Chinese remainder theorem,
${m}_{1}=5,{m}_{2}=8,{m}_{3}=21$
$M={m}_{1}{m}_{2}{m}_{3}=5.8.21$
M=840
${M}_{1}=\frac{M}{{m}_{1}}=\frac{840}{5}=168$
${M}_{2}=\frac{M}{{m}_{2}}=\frac{840}{8}=105$
${M}_{3}=\frac{M}{{m}_{3}}=\frac{840}{21}=40$
Step 2
Now the linear congruences
${M}_{1}{y}_{1}\equiv 1\left(\text{mod}5\right)⇒168{y}_{1}\equiv 1\left(\text{mod}5\right)$
${M}_{2}{y}_{2}\equiv 1\left(\text{mod}8\right)⇒105{y}_{2}\equiv 1\left(\text{mod}8\right)$
${M}_{3}{y}_{3}\equiv 1\left(\text{mod}21\right)⇒40{y}_{3}\equiv 1\left(\text{mod}21\right)$
which are satisfied by
${y}_{1}=2$
${y}_{2}=\frac{1}{8}$
${y}_{3}=-\frac{1}{2}$
Thus the solution to the system is given by
$x=\left(2.168.2\right)+\left(22.105\frac{.1}{8}\right)+\left(12.40.\left(-\frac{1}{2}\right)\right)$
$=672+\frac{561}{2}-\frac{480}{2}$
$=672+\frac{81}{2}$
x=676.5
x=677
modulo 840.So the solutions form the congruence class of 677 modulo 840.
Thus, the general solution is
x=677 + 840k, $k\in \mathbb{Z}$.


text:
# Robustness and visualization of blend's production

Abstract : The oil blending process (BP) consists in determining the optimal proportions to blend from a set of available components such that the final product fulfills a set of specifications on their properties. Two important characteristics of the blending problem are the hard bounds on the blend's properties and the uncertainty pervading the process. In this work, a real-time optimization method is proposed for producing robust blends while minimizing the blend quality giveaway and the recipe's cost. The method is based on the Robust Optimization techniques and under the assumption that the components properties blend linearly. The blending intrinsic polytopes are exploited in order to measure, visualize and characterize the infeasibility of the BP. A fine analysis of the components bounds modifications is conducted to guide the process towards the best robust blend. A set of indices and visualizations provide a helpful support for the decision maker.
Keywords :
Document type :
Theses

Cited literature [42 references]

https://tel.archives-ouvertes.fr/tel-00647297
Contributor : ABES STAR :  Contact
Submitted on : Thursday, December 1, 2011 - 5:54:12 PM
Last modification on : Friday, March 25, 2022 - 9:42:39 AM
Long-term archiving on: : Friday, March 2, 2012 - 2:40:13 AM

### File

20748_AGUILERA_-_CABANAS_2011_...
Version validated by the jury (STAR)

### Identifiers

• HAL Id : tel-00647297, version 1

### Citation

Jorge Antonio Aguilera Cabanas. Robustness and visualization of blend's production. General Mathematics [math.GM]. Université de Grenoble, 2011. English. ⟨NNT : 2011GRENM052⟩. ⟨tel-00647297⟩

Record views


text:
19th Ave New York, NY 95822, USA

# 统计代写| Gibbs sampling stat代写

## 统计代考

12.2 Gibbs sampling
Gibbs sampling is an MCMC algorithm for obtaining approximate draws from a joint distribution, based on sampling from conditional distributions one at a time: at each stage, one variable is updated (keeping all the other variables fixed) by drawing from the conditional distribution of that variable given all the other variables. This approach is especially useful in problems where these conditional distributions are pleasant to work with.
First we will run through how the Gibbs sampler works in the bivariate case, where the desired stationary distribution is the joint PMF of discrete r.v.s $X$ and $Y$. There are several forms of Gibbs samplers, depending on the order in which updates are done. We will introduce two major kinds of Gibbs sampler: systematic scan, in which the updates sweep through the components in a deterministic order, and random scan, in which a randomly chosen component is updated at each stage.

Algorithm 12.2.1 (Systematic scan Gibbs sampler). Let $X$ and $Y$ be discrete r.v.s with joint PMF $p_{X, Y}(x, y)=P(X=x, Y=y)$. We wish to construct a two-dimensional Markov chain $\left(X_{n}, Y_{n}\right)$ whose stationary distribution is $p_{X, Y}$. The systematic scan Gibbs sampler proceeds by updating the $X$-component and the $Y$-component in alternation. If the current state is $\left(X_{n}, Y_{n}\right)=\left(x_{n}, y_{n}\right)$, then we the $Y$-component while holding the $X$-component fixed:

1. Draw $x_{n+1}$ from the conditional distribution of $X$ given $Y=y_{n}$, and set $X_{n+1}=x_{n+1}$.
2. Draw $y_{n+1}$ from the conditional distribution of $Y$ given $X=x_{n+1}$, and set $Y_{n+1}=y_{n+1}$.
Repeating steps 1 and 2 over and over, the stationary distribution of the chain $\left(X_{0}, Y_{0}\right),\left(X_{1}, Y_{1}\right),\left(X_{2}, Y_{2}\right), \ldots$ is $p_{X, Y}$. Algorithm 12.2.2 (Random scan Gibbs sampler). As above, let $X$ and $Y$ be discrete r.v.s with joint PMF $p_{X, Y}(x, y)$. We wish to construct a two-dimensional Markov chain Monte Carlo Markov chain ( $X_{n}, Y_{n}$ ) whose stationary distribution is $p_{X, Y}$. Each move of the random scan Gibbs sampler picks a uniformly random component and updates it, according to the conditional distribution given the other component: 1. Choose which component to update, with equal probabilities. 2. If the $X$-component was chosen, draw a value $x_{n+1}$ from the condi- tional distribution of $X$ given $Y=y_{n}$, and set $X_{n+1}=x_{n+1}, Y_{n+1}=y_{n} .$ Similarly, if the $Y$-component was chosen, draw a value $y_{n+1}$ from the con- ditional distribution of $Y$ given $X=x_{n}$, and set $X_{n+1}=x_{n}, Y_{n+1}=y_{n+1}$. Repeating steps 1 and 2 over and over, the stationary distribution of the chain sequence of $d$-dimensional random vectors. At each stage, we choose one component of the vector to update, and we draw from the conditional distribution of that component given the most recent values of the other components. We can either cycle through the components of the vector in a systematic order, or choose a random component to update each time. Gibbs sampling generalizes naturally to higher dimensions. If we want to sample from a $d$-dimensional joint distribution, $\left(X_{2}, Y_{2}\right), \ldots$ is $p_{X, Y}$.
The Gibbs sampler is less flexible than the Metropolis-Hastings algorithm in the sense that we don’t get to choose a proposal distribution; this also makes it simpler in the sense that we don’t have to choose a proposal distribution. The flavors of Gibbs distributions while Metropolis-Hastings emphasizes acceptance probabilities. But the algorithms are closely connected, as we show below.
Theorem 12.2.3 (Random scan Gibbs as Metropolis-Hastings). The random scan Gibbs sampler is a special case of the Metropolis-Hastings algorithm, in which the proposal is always accepted. In particular, it follows that the stationary distribution of the random scan Gibbs sampler is as desired.

Proof. We will show this in two dimensions, but the proof is similar in any dimension. Let $X$ and $Y$ be discrete r.v.s whose joint PMF is the desired stationary distribution. Let’s work out what the Metropolis-Hastings algorithm says to do, using the following proposal distribution: from $(x, y)$, randomly update one coordinate by running one move of the random scan Gibbs sampler.
To simplify notation, write
$P(X=x, Y=y)=p(x, y), P(Y=y \mid X=x)=p(y \mid x), P(X=x \mid Y=y)=p(x \mid y) .$
More formally, we should write $p_{Y \mid X}(y \mid x)$ instead of $p(y \mid x)$, to avoid issues like wondering what $p(5 \mid 3)$ means. But writing $p(y \mid x)$ is more compact and does not create ambiguity in this proof.
Let’s compute the Metropolis-Hastings acceptance probability for going from $(x, y)$

## 统计代考

12.2 吉布斯抽样
Gibbs 抽样是一种 MCMC 算法，用于从联合分布中获得近似抽取，基于一次一个条件分布的抽样：在每个阶段，通过抽取该变量的条件分布来更新一个变量（保持所有其他变量不变）变量给定所有其他变量。这种方法在处理这些条件分布很愉快的问题中特别有用。

1. 给定$Y=y_{n}$，从$X$的条件分布中抽取$x_{n+1}$，设$X_{n+1}=x_{n+1}$。
2. 给定$X=x_{n+1}$，从$Y$的条件分布中抽取$y_{n+1}$，设$Y_{n+1}=y_{n+1}$。
一遍又一遍地重复步骤 1 和 2，链的平稳分布 $\left(X_{0}, Y_{0}\right),\left(X_{1}, Y_{1}\right),\left (X_{2}, Y_{2}\right), \ldots$ 是 $p_{X, Y}$。算法 12.2.2（随机扫描吉布斯采样器）。如上所述，让 $X$ 和 $Y$ 是具有联合 PMF $p_{X, Y}(x, y)$ 的离散 r.v.s。我们希望构建一个二维马尔可夫链蒙特卡洛马尔可夫链（$X_{n}, Y_{n}$），其平稳分布为$p_{X, Y}$。随机扫描吉布斯采样器的每一次移动都会选择一个均匀随机的分量并根据给定另一个分量的条件分布对其进行更新： 1. 以相等的概率选择要更新的分量。 2. 如果选择了$X$-分量，在$Y=y_{n}$ 的情况下，从$X$ 的条件分布中抽取一个值$x_{n+1}$，并设置$X_{n+ 1}=x_{n+1}, Y_{n+1}=y_{n} .$ 类似地，如果选择了 $Y$-组件，则从 con- 中绘制一个值 $y_{n+1}$给定$X=x_{n}$，$Y$的二分分布，设$X_{n+1}=x_{n}，Y_{n+1}=y_{n+1}$。一遍又一遍地重复步骤 1 和 2，$d$ 维随机向量的链序列的平稳分布。在每个阶段，我们选择要更新的向量的一个分量，并在给定其他分量的最新值的情况下从该分量的条件分布中提取。我们可以按系统顺序循环遍历向量的分量，也可以每次选择一个随机分量进行更新。吉布斯抽样自然地推广到更高的维度。如果我们想从 $d$ 维联合分布中采样，$\left(X_{2}, Y_{2}\right)，\ldots$ 是 $p_{X, Y}$。
Gibbs 采样器不如 Metropolis-Hastings 算法灵活，因为我们无法选择提议分布；这也使得它更简单，因为我们不必选择提案分布。 Gibbs 分布的风格，而 Metropolis-Hastings 强调接受概率。但是这些算法是紧密相连的，如下所示。
定理 12.2.3（随机扫描吉布斯作为 Metropolis-Hastings）。随机扫描 Gibbs 采样器是 Metropolis-Hastings 算法的一个特例，在该算法中，提案总是被接受。特别是，随机扫描吉布斯采样器的平稳分布是符合要求的。

$P(X=x, Y=y)=p(x, y), P(Y=y \mid X=x)=p(y \mid x), P(X=x \mid Y=y) =p(x \mid y) .$


text:
bmc:remedy:message-catalog:792

AR System Message Catalog

# ARERR [792] Failure while writing to the definition file.

Product:
AR System server
Description:
Type:
Error
Number:
792

An error occurred while the system tried to write updates to the definition file. An associated error message contains details. Fix the problem (for example, if you are out of space, remove some files to create more space), and perform the operation again.

• bmc/remedy/message-catalog/792.txt


text:
## Algebra 2 Common Core

a. $109.4$ b. $10.4$ c. $-11.1$ d. $-7.2$
a. Write formula $F=\frac{9}{5}C+32$ Plug values into formula $m=\frac{9}{5}(43)+32$ Multiply $m=77.4+32$ Add $m=109.4$ b. $F=\frac{9}{5}C+32$ $n=\frac{9}{5}(-12)+32$ $n=-21.6+32$ $n=10.4$ c. $F=\frac{9}{5}C+32$ $12=\frac{9}{5}p+32$ $-20=\frac{9}{5}p$ $\frac{-20}{\frac{9}{5}}=\frac{\frac{9}{5}p}{\frac{9}{5}}$ $-11.1=p$ d. $F=\frac{9}{5}C+32$ $19=\frac{9}{5}q+32$ $-13=\frac{9}{5}q$ $\frac{-13}{\frac{9}{5}}=\frac{\frac{9}{5}q}{\frac{9}{5}}$ $-7.2=q$


text:
# zbMATH — the first resource for mathematics

A converse to the mean value theorem for harmonic functions. (English) Zbl 0808.31004
Let $$U$$ be a bounded domain in $$\mathbb{R}^ d$$, $$d\geq 1$$, $$\rho(x)= \text{dist} (x,U^ c)$$, and $$r:U\to \mathbb{R}$$ a function satisfying $$0<r\leq\rho$$. Let $$B^ x$$, $$x\in U$$, denote the open ball centered at $$x$$ with radius $$r(x)$$. A Lebesgue measurable function $$f$$ on $$U$$ satisfying $f(x)= {1\over {\lambda(B^ x)}} \int_{B^ x} f d\lambda$ for every $$x\in U$$ (where $$\lambda$$ denotes the Lebesgue measure), is said to be $$r$$-median. Results of the type under what conditions is an $$r$$-median function $$f$$ actually harmonic, are usually known as a converse to the mean value theorem.
The main result of the present paper states that if $$f$$ is $$r$$-median, continuous (on $$U$$) and $$h$$-bounded (i.e. $$| f|\leq h$$ with $$h$$ harmonic on $$U$$), then $$f$$ is harmonic on $$U$$. As a rather simple consequence of this result, the authors show that an $$r$$-median, $$h$$- bounded, Lebesgue measurable function $$f$$ on $$U$$ is harmonic provided that the function $$r$$ is bounded away from zero on compact subsets of $$U$$, thus improving the result of W. A. Veech [Ann. Math., II. Ser. 97, 189-216 (1973; Zbl 0282.60048)], where $$U$$ was assumed to be a Lipschitz domain.
The proof of the results is analytic, but with the strong probabilistic flavor in the background. It uses the minimal fine topology of the Martin compactification of $$U$$, an appropriate (transfinite) sweeping of measures, and certain properties of the Schrödinger equation $$\Delta u- \delta\rho^{-2} 1_ A=0$$ on $$U$$ ($$\delta>0$$, $$A$$ a suitable subset of $$U$$).

##### MSC:
 31B05 Harmonic, subharmonic, superharmonic functions in higher dimensions 31C35 Martin boundary theory 60J45 Probabilistic potential theory
Full Text:
##### References:
 [1] Akcoglu, M. A. &Sharpe R. W., Ergodic theory and boundaries.Trans. Amer. Math. Soc., 132 (1968), 447–460. · Zbl 0162.19402 · doi:10.1090/S0002-9947-1968-0224770-7 [2] Baxter, J. R., Restricted mean values and harmonic functions.Trans. Amer. Math. Soc., 167 (1972), 451–463. · Zbl 0238.31006 · doi:10.1090/S0002-9947-1972-0293112-4 [3] –, Harmonic functions and mass cancellation.Trans. Amer. Math. Soc., 245 (1978), 375–384. · Zbl 0391.60065 · doi:10.1090/S0002-9947-1978-0511416-X [4] Bliedtner, J. & Hansen, W.,Potential Theory–An Analytic and Probabilistic Approach to Balayage. Universitext, Springer, 1986. · Zbl 0706.31001 [5] Boukricha, A., Hansen, W., &Hueber, H., Continuous solutions of the generalized Schrödinger equation and perturbation of harmonic spaces.Exposition. Math., 5 (1987), 97–135. · Zbl 0659.35025 [6] Brunel, A., Propriété restreinte de valeur moyenne caractérisant les fonctions harmoniques bornées sur un ouvert dansR n (selon D. Heath et L. Orey). Exposé no XIV, inSéminaire, Goulaouic-Schwartz, Paris, 1971–1972. [7] Burckel, R. B., A strong converse to Gauss’s mean value theorem.Amer. Math. Monthly, 87 (1980), 819–820. · Zbl 0475.31003 · doi:10.2307/2320795 [8] Doob, J. L.,Classical Potential Theory and its Probabilistic Counterpart. Grundlehren Math. Wiss., 262. Springer, 1984. · Zbl 0549.31001 [9] Feller, W., Boundaries induced by nonnegative matrices.Trans. Amer. Math. Soc., 83 (1956), 19–54. · Zbl 0071.34901 · doi:10.1090/S0002-9947-1956-0090927-3 [10] Fenton, P. C., Functions having the restricted mean value property.J. London Math. Soc., 14 (1976), 451–458. · Zbl 0344.31002 · doi:10.1112/jlms/s2-14.3.451 [11] – On sufficient conditions for harmonicity.Trans. Amer. Math. Soc., 253 (1979), 139–147. · Zbl 0368.31001 · doi:10.1090/S0002-9947-1979-0536939-X [12] – On the restricted mean value property.Proc. Amer. Math. Soc., 100 (1987), 477–481. · Zbl 0634.31002 · doi:10.1090/S0002-9939-1987-0891149-1 [13] Gong, X., Functions with the restricted mean value property.J. Xiamen Univ. Natur. Sci., 27 (1988), 611–615. · Zbl 0693.31002 [14] de Guzmán, M.,Differentiation of Integrals in R n . Lecture Notes in Math., 481. Springer, 1975. [15] Hansen, W., Valeurs propres pour l’opérateur de Schrödinger, inSéminaire de Théorie du Potentiel, Paris, No. 9. Lecture Notes in Math., 1393, pp. 117–134. Springer, 1989. [16] Hansen, W. &Ma, Zh., Perturbations by differences of unbounded potentials.Math. Ann., 287 (1990), 553–569. · Zbl 0685.31005 · doi:10.1007/BF01446913 [17] Heath, D., Functions possessing restricted mean value properties.Proc. Amer. Math. Soc., 41 (1973), 588–595. · Zbl 0251.31004 · doi:10.1090/S0002-9939-1973-0333213-1 [18] Helms, L. L.,Introduction to Potential Theory. Wiley, 1969. · Zbl 0188.17203 [19] Huckemann, F., On the ’one circle’ problem for harmonic functions.J. London Math. Soc., 29 (1954), 491–497. · Zbl 0056.32601 · doi:10.1112/jlms/s1-29.4.491 [20] Kellogg, O. D., Converses of Gauss’s theorem on the arithmetic mean.Trans. Amer. Math. Soc., 36 (1934), 227–242. · Zbl 0009.11205 [21] Littlewood, J. E.,Some Problems in Real and Complex Analysis. Heath Math. Monographs. Lexington, Massachusetts, 1968. · Zbl 0185.11502 [22] Netuka, I., Harmonic functions and mean value theorems. (In Czech.)Časopis Pěst. Mat., 100 (1975), 391–409. [23] Veech, W. A., A zero-one law for a class of random walks and a converse to Gauss’ mean value theorem.Ann. of Math., 97 (1973), 189–216. · Zbl 0282.60048 · doi:10.2307/1970845 [24] –, A converse to the mean value theorem for harmonic functions.Amer. J. Math., 97 (1975), 1007–1027. · Zbl 0324.31002 · doi:10.2307/2373685 [25] Veselý, J., Restricted mean value property in axiomatic potential theory.Comment. Math. Univ. Carolin., 23 (1982), 613–628. · Zbl 0513.31009 [26] Volterra, V., Alcune osservazioni sopra proprietà atte individuare una funzione.Atti della Reale Academia dei Lincei, 18 (1909), 263–266. · JFM 40.0453.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Question on Pearson's Chi-squared test

1. Feb 3, 2014

### mnb96

Hello,

I was trying to interpret the formula of Pearson's Chi-squared test:
$$\chi^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}$$

I thought that if we assume that each $O_i$ is an observation of the random variable $X_i$, then the above formula essentially considers the sum-of-squares of n standardized random variables $Y_i=\frac{X_i-\mu_i}{\sigma_i}$. In fact, if such random variables are $Y_i \sim N(0,1)$, then the random variable $S = \sum_{i=1}^n Y_i^2$ follows a $\chi^2$-distribution. Thus, the formula of the Chi-squared test would essentially evaluate the probability $\mathrm{P}\left( S = \chi^2 \right)$, and of course compare it to some chosen P-value.

My question is about the standardization of the random variables $X_i$.
If my interpretation above is correct, then Pearson's Chi-squared test somehow assumes that each random variable $X_i$ has variance equal to its expected value, that is: $$\sigma_i^2 = \mu_i$$

Why so?
Can anybody explain why we would need to assume that variance and expected values are numerically equal? That condition is satisfied only for some distributions like Poisson and Gamma (with $\theta=1)$. Why such a restriction?

Last edited: Feb 3, 2014
2. Feb 3, 2014

### Stephen Tashi

The $O_i$ are supposed to be a count of how many observations of a random variable fall within a "cell". How are you are defining the $i$th cell?

3. Feb 4, 2014

### mnb96

I see! That is an important observation. It probably means that the random variables $X_i$ are supposed to follow a multinomial distribution.

For instance, if we have only one cell, then $X_1$ could be the amount of successes out of $m$ independent trials of some experiment. Thus, $X_1$ would follow a binomial distribution, which in fact approaches a Poisson distribution for $m$ large, and which has $\sigma^2=\mu=\lambda$.

If the above reasoning is correct, then Pearson's Chi-squared test should work only when the number of trials is sufficiently large.

4. Feb 4, 2014

### Stephen Tashi

I'm not sure what you mean by that statement.

The test can be applied to repeated independent samples of a single random variable. The single random variable can have any distribution. It is only necessary to define the cells so that they partition the range of the random variable.

5. Feb 4, 2014

### mnb96

Hi Stephen, and thanks for your help!

What I meant, is that $X_i$ is a random variable that "counts" the number of observations that happened to fall into the i-th cell. For instance, if we consider a continuous random variable Z having some unknown probability density function, and we partition the real line into two cells corresponding to the events: $Z\geq 10$ (=success) and $Z< 10$ (=failure), then the two events will have probabilities p and (1-p).

We can sample the random variable Z many times, say n times.
Now, $X_1$ is the random variable that keeps the total counts of successes, thus $X_1$ follows a binomial distribution, i.e. $X_1\sim B(n,p)$.

I thought that if we extend this reasoning to $k$ cells, then the vector of random variables $(X_1,\ldots,X_k)$ should follow a multinomial distribution, i.e. $(X_1,\ldots,X_k) \sim M(n;p_1,\ldots,p_k)$.

Or am I misunderstanding something?


text:
If for any $M' \subseteq M$ there is an embedding of $M'$ into a $Mod(T)$, then there is an embedding of $M$ into $Mod(T)$.

I need to prove that, for $M$ a given $L$-structure and $T$ be a theory in the language $L$. Show that if for any finitely generated substructure $M'$ of $M$ there is an embedding of $M'$ into a model of $T$, then there is an embedding of $M$ into the model of $T$.

So, I have that for every $M' \subseteq M$ there is an embedding $h : M' \rightarrow Mod(T)$, so I know that I need to apply compactness, I can do that because I have a finitely generated substructures. I also can see that I need to apply the notion of diagram: The map $h$ is an embedding (from M to N) iff (N,h) is a model of Diag(M ). A diagram is defined as follows. $Diag(M) = {\varphi \in L(M) | \ \varphi \ is \ quantifier \ free \ M_M \models \varphi}$.

Now, I feel like I have all the pieces but i have issues putting them together in their place, I think I need to do something like this:

Let $M' \subseteq M$ a finite model of $M$ and let $h$ be an embedding $h : M' \rightarrow Mod(T)$, then $(Mod(T),h)$ is a model of the $Diag(M)$. Here I apply compactness but I think I'm either skipping a step or missing a decent argumentation of why I can do it. Once I have applied compactness, I think I can use the same argument in reverse to say that there is an embedding from $M$ to $Mod(T)$: so "by compactness" $Mod(T,h')$ is is a model of $Diag(M)$, therefore, $h$ is an embedding from $M$ to $Mod(T)$. I would really appreciate your input on how to improve this proof and give in more details.

If every finitely generated structure of $M$ is embeddable in a model of $T$ then Diag$(M)\cup T$ is finitely consistent. By compactness there is $N\models$ Diag$(M)\cup T$. The model $N$ has signature $L(M)$ and interprets the elements on $M$. This interpretation gives the required embedding of $M$ into $N$. (The model you asked for is $N$ reduced to the signature $L$.)
• @Sara Your last paragraph is a kind of messy. You say finite model for finitely generated (I guess), then you say embeddings of $M'$ into Mod($T$) for embedding of $M'$ into some model in Mod($T$) (I guess). I cannot guess you mean by Mod$(T,h)$....etc.... – Primo Petri May 8 '15 at 18:50


text:
OpenKattis
National University of Singapore

# An I for an Eye

Ken has been having trouble lately staying under the word limit in Twitter, so he’s decided to write a little front-end program which will take in text and shorten it using a fixed set of abbreviations for commonly used letter sequences. Those abbreviations are shown in the table below:

 The character ... ... substitutes for the letter sequence @ at & and 1 one, won 2 to, too, two 4 for, four b bea, be, bee c sea, see i eye o oh, owe r are u you y why

Ken is about to start writing this program when he realizes that the extent of his computer knowledge is ... well ... using Twitter. He’s looking for someone to help him – r u [email protected] some1?

## Input

Input starts with a single integer $n$ indicating the number of lines of text to process. Following this are $n$ lines of text. Each line will contain only alphanumeric characters and spaces, and each line will have at least one non-space character. Each line has at most $200$ characters.

## Output

Display each line with the appropriate substitutions made. Substitutions should also be made inside words, e.g., the word that should be changed to [email protected]. If two letter sequences overlap (like at and to in the word baton) just replace the first one (in this case resulting in [email protected]). If two letter sequences start at the same location (like be and bee in been) replace the longer one (in this case resulting in bn). If the letter sequence starts with an upper-case letter, then the abbreviation should also be in upper-case (if appropriate). Finally, no substituted letter should later be part of another substitution. For example, if the input is oweh, you would first replace the owe with an o to get oh. At this point you do NOT replace the oh with an o since the oh contains a substituted letter.

Sample Input 1 Sample Output 1
3
Oh say can you see
I do not understand why you are so cranky just because Karel won
Formation

O say can u c
I do not underst& y u r so cranky just bcause Krl 1
[email protected]


text:
# [texhax] changing chapter (+ code)

Christian Deindl deindl at soziologie.uzh.ch
Fri Jan 9 14:35:00 CET 2009

I've got an off-list remark to give more information.
below you'll find the example I'm currently using.

I'm about to finish a report and I want to change the positon of the
chapter-headlines. the default is a large gap between the page and the
It shouldn't be that complicated but I couldn't find anything useful by a

secondly I want to suppress a pagenumer on the first page of each chapter.

christian

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%example

\documentclass[a4paper,12pt]{report}
\usepackage[ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage[ansinew]{inputenc}
\usepackage[marginal]{footmisc}
\usepackage{longtable}
\usepackage{graphicx}
\usepackage{float}
\usepackage{apager}
\usepackage{subfigure}
\usepackage{url}
\usepackage{setspace}
\usepackage{chngcntr}
\usepackage{lmodern}
\usepackage{lscape}
\usepackage[hang,bf]{caption}
\usepackage{eurosym}
\usepackage{dcolumn}
\usepackage{rotating}
\usepackage{fancyhdr}

\pagestyle{fancy}

\clubpenalty = 10000 \widowpenalty = 10000 \displaywidowpenalty = 10000

\setlength{\belowcaptionskip}{2pt}

\counterwithout{footnote}{chapter}

\begin{document}

\pagenumbering{roman}

\tableofcontents

\clearpage
\onehalfspacing
\pagenumbering{arabic}

\fancyhf{}

\chapter{Name}

text text text text text text text text text text text text text text text
text text text text text text text text text text text text text text text
text text text text text text text text text text text text text text text
text text text text text text text text text text text text text

text text text text text text text text text text text text text text text
text text text text text text text text text text text text text text text
text text text text text text text text text text text text text text text
text text text text text text text text text text text text text text

\end{document}


text:
# Difference: Hig11002TWiki (2 vs. 3)

#### Revision 32011-03-21 - VivekSharma

Line: 1 to 1

 META TOPICPARENT name="PasChHiggs2011"

# Search for charged Higgs boson in ttbar in pp collisions at TeV

Line: 27 to 27

 Table 2 Number of expected events for the backgrounds, signal events from (HH) and (WH) processes at =120 GeV/, and the number of observed events after the final event selection. Statistical and systematic uncertainties are shown. The statistical uncertainties are due to MC statistics, while for the $\tau$-fakes the statistical uncertainties are due to the fake rate in the data. Of the 40 events found in the data, 16~(24) events are in the () final state, which is expected as the electron efficiency is lower than the muon efficiency.

-- MicheleGallinaro - 14-Mar-2011

<!--
-->


text:
#### MiningMath

Get the NPV upper bound better than the Best Case scenario!

# Optimization Hints

Mima 231 views

## Global Optimization Overview

The general relation between the number of Constraints and NPV tends to be inversely proportional, which means that scenarios with fewer constraints imposed, the optimization tends to find higher NPV since the algorithm free to search for better solutions. Therefore, it is always recommended that the full potentials of the mining project are tested first, as recommended in the optimized workflow, which starts at the Data Validation generating results that could be used in further steps. Regarding these aspects, a pretty useful approach was done by the MiningMath team throughout 2000 simulations (Figure 1) on a project seeking to identify the main impacts that the constraints had.

The firsts executions considered the individual variation of each constraint, therefore, Copper Selling Price, Mining Widths, Vertical Rate of Advance, and the rest of the parameters were modified to understand the tendency of each one. As we can see, most of them, when individually varied, have a high probability of generating NPVs around 900M$. Figure 1: Project evaluation over 2000 executuions. The second round was performed by running “Overall” scenarios, which consider a random value of each one of the 11 variables at the same time on the project. As you can see, the combination of this amount of constraints has a higher probability of generating NPVs around 200M$.

In summary, these results illustrate the intuitive assumption that by adding more and more constraints the probability of getting higher NPVs decreases drastically that is why the users have to apply “smart” concepts and constraints to achieve such results.

MiningMath deals with multiple constraints and aims to maximize NPV simultaneously. Remember that it is computationally impossible to guarantee that all possible solutions are evaluated by any algorithm and, therefore, it is impossible to guarantee that the maximum NPV will be delivered by a single run. Having such concepts in mind, a simple modification on a single parameter can generate unexpected effects on NPV. Thus, is always worthwhile to identify tendency, what it is not possible to find with only two runs. Note that is required to create a curve with a set of runs if we wish to find tendencies of an algorithm that includes such heuristics.

The logic behind such analysis is quite simple: for any optimization algorithm that aims to solve such complex problems, if we put too many constraints, we give no freedom for the algorithm to explore the solution space. Therefore, we tend to find solutions with lower NPV. On the other hand, when we give too much freedom, the algorithm will have the whole space to search for solutions, with no guidance on what would be reasonable in real life, so good solutions might not be found. The best compromise is when the user starts free of constraints and, then, starts giving some reasonable guidance (Figure 2). Therefore, smart constraints might help the algorithm in focusing only on a certain part of the space and actually deliver higher NPVs.

Figure 2: Applying smart constraints to reduce a broader solution space and find best results on a limited one.

The main suggestions to explore the potential is by running the first iterations and evaluations with as few constraints as possible and without geometries (most complex in the mathematical model). Then, starts to move gradually to detailed scenarios, by adding parameters one-by-one, which will allow you to understand the impact of each constraint in the NPV, and guide decisions through an Integrated Workflow. Thus, by measuring how much each assumption “costs” to the project in the long-term, the managers will be able to choose the best way to use them.

MiningMath is a technology composed of mathematical programming and heuristics, which do not disrespect the constraints imposed to increase the NPV as the hierarchy (Figure 3) disclosed on this content explains. Experienced users take advantage of this aspect and slowly place constraints that might even help the optimizer to find solutions with higher NPV. A scenario with the total movement/production free, for instance, results in the better distribution of waste over time while adding/modifying a total limit makes the algorithm search the best result within these capacities and even find surprising NPVs among them. Therefore, to assess tendencies, it’s recommended to draw a curve of scenarios, such as free, 100 Mtpa, 90 Mtpa, 80 Mtpa, and so forth versus NPV.

The user always can guide the optimization by relaxing constraints on the hierarchy whenever possible, which works as hints to the algorithm to reach feasible outcomes. Flexibilyzing the Slope Angles in the short term could bring better designs to your project, for instance. Whereas the user has an understanding of the optimization problem, and how the constraints are acting on it, it is possible to insert smart hints to the algorithm to reach a reasonable result.

Figure 3: Constraints hierarchy order.

## Key takeaways

One of the main advantages of MiningMath’s algorithm is the capability of finding intermediary solutions between the extremes outcomes. Therefore, the user can give hints to guide the algorithm, such as:

• Letting the algorithm free, with fewer constraints (bigger solution space), is great for exploring the economic potential of a project.

• When dealing with more constraints, reducing the solution space might give some hints to the algorithm and help it to achieve the goals set.

• Starting to optimize from the most free scenario up to the most constrained one.

• Relaxing low-priority constraints manually to guide the algorithm.

• Breaking complex scenarios into smaller problems and iterating over multiple scenarios.

• Avoid using constraints for the same purpose with the same priority in the hierarchy order.|

## Relaxed Constraints vs Violated Constraints

These are subtle nuances that should be evaluated along about this topic as: When are constraints disrespected a consequence of the algorithm pursue to an intermediary outcome? When such deviations should be considered as a violation or an improper solution?

Constraints relaxed to achieve a feasible outcome. Examples:

• Processing stream shortfalls.

• Operational constraints.

• Average constraints (depending on the deviation).

• Constraints based on Sums (depending on the deviation).

Constraints violated that would represent, in fact, an unfeasible project. Examples:

• Production limits exceeded.

• Slope constraints.

• Average constraints (depending on the deviation).

• Constraints based on Sums (depending on the deviation).

This information are usually reported at the report tab on the excel output file.


text:
# Introduction

Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.

The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by

• points on an infinite checkerboard;

• centers of a hexagonal tessellation;

• integers on the real number line.

The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."

# Definitions

A lattice $L$ is a subgroup of $\mathbb{R}^n$generated by $b_i$, i.e.

$L=\sum_{i=1}^d\mathbb{Z} b_i = \left\{\left. \sum_{i=1}^d a_i b_i \right | a_i \in \mathbb{Z} \right\}$

where $b_i$ are linearly independent vectors. Collectively, $\left\{b_i\right\}_{i=1}^d$ form a basis of$L$.

We say a set of vectors $v_i$are linearly independent if the only solution to the equation $\sum_{i} a_i b_i = 0$ is when all $a_i$are zero.

Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.

Some more terminology from linear algebra will be useful. The dimension of a lattice, denoted$\dim L$, is $d$. A lattice is complete if $d=n$. Note that we can always choose a subspace of $\mathbb R^n$such that the lattice is complete, namely the subspace generated by $b_i$.

The region

$\Phi=\left\{\left.\sum_{i=1}^dx_ib_i\right|0\leq x_i<1\right\}$

is known as the fundamental mesh.

In the image above, we see the points of a lattice in $\mathbb R^2$. The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.

Although the fundamental mesh is not unique, it turns out that the ($m$dimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:

Let$\mathcal B$be a$d\times n$matrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by

$\text{vol}(L)=\sqrt{\left|\det\left(\mathcal B\mathcal B^T\right)\right|}$

A subset $X$of $\mathbb R^n$is known as centrally symmetric if $x\in X$implies $-x\in X$. It is convex if for any $x,y\in X$, the line joining $x,y$ is contained in $X$, i.e. $\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X$. Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:

Let $L$be a complete lattice of dimension$n$ and $X$be a centrally symmetric convex set. Suppose

$\text{vol}(X)>2^n\text{vol}(L)$

Then $X$contains at least one nonzero point of $L$. This result is primarily used to prove the existence of lattice vectors.

Throughout this section, $\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}$ denotes the $\ell_2$norm and $\langle a,b\rangle=\sum_ia_ib_i$ denotes the inner product.

# Proof sketch of Minkowski's theorem

This proof is by some sort of a pigeonhole argument on volumes. Consider the set

$\frac12X=\left\{\frac12x|x\in X\right\}$

We have $\text{vol}\left(\frac12 X\right)>\text{vol}(L)$, hence the inclusion $\frac12X\to\mathbb R^n/L$cannot be injective, thus we can find some $x_1=x_2+\ell$, $x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2$. Hence $x_1-x_2\in L$is a nontrivial lattice point.

# Exercises

1) Let $L$be the lattice generated by $\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}$(take the rows as basis vectors).

• Compute the volume of this lattice

• Show that $\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$generates the same lattice

• Show that each row in $\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}$is in the lattice but$\mathcal C$does not generate the lattice. This is one key difference from the case of linear algebra (over fields).

2) Let$\mathcal B,\mathcal B'$be $d\times n$matrices whose row vectors are basis for lattices $L,L'$. Both lattices are the same iff there exists some $U\in\text{GL}_d(\mathbb Z)$ such that $\mathcal B'=U\mathcal B$. Find $U$for problem 1. Note that $\text{GL}_d(\mathbb Z)$is the group of invertible matrices with integer coefficients, meaning $U$and $U^{-1}$have integer coefficients.

3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete lattice$L$of dimension $n$, we can find some centrally symmetric convex set$X$with$\text{vol}(X)=2^n\text{vol}(L)$but the only lattice point in$X$is the origin.

4*) Let$v$be the shortest nonzero vector for some lattice $L$with dimension$n$. Show that

$\left\lVert v\right\rVert\leq\frac2{\sqrt\pi}\Gamma\left(\frac n2+1\right)^{\frac1n}\text{vol}(L)^\frac1n$


text:
## Intermediate Algebra for College Students (7th Edition)

The product of a binomial sum and a binomial difference is: $(A+B)(A-B)=A^2-B^2$. $9x^2-16=(3x)^2-4^2=(3x+4)(3x-4)$, so the answer is e


text:
Tag Info

5

Although, I do not know if a general proof exists, I think that the Casimir effect of a renormalizable quantum field theory should be completely understood by means of a theory of renormalization on manifolds with boundary. The key feature is that one cannot, in general, neglect the renormalization of the coupling constants in the boundary terms. Using this ...

4

The objects whose number is lower in between the plates are not really particles per se but the different modes - different possible values of the wavelength or frequency, in particular - in which the particles may be created. If the distance of the parallel plates is $L$, then the electric field has to vanish at the boundary between the vacuum and the ...

4

Ref [19] in the arXiv paper, C. M. Caves and B. L. Schumaker, Phys Rev A 31, 3068 (1985), gives a clean description of a parametric amplifier as the prototype of a two-photon device, at the bottom of its second page: In a [parametric amplifier], an intense laser beam at frequency $2\Omega$ —the pump beam— illuminates a suitable nonlinear medium. The ...

4

The reason why the Alcubierre drive is not feasible as an FTL drive has nothing to do with absence of exotic matter; in fact, we likely had plenty of the required matter during cosmic inflation era, or something with identical geometrical effects. Physicists that dismiss it as impossible because "there is no exotic matter" play ignorance to the fact that ...

3

I don't think the formation of lipid bilayers is analogous to the Casimir effect because it's a surface energy effect. However there is an effect called depletion flocculation that is very closely analogous. This happens in a polymer solution when surfaces approach more closely than the size of the polymer molecule. The polymer is excluded from the region ...

3

Thank you for your interesting question. The following is what I assumed in the paper. If you accelerate to the right, the Rindler horizon to your left is a boundary beyond which things are in principle unobservable for you. So, as soon as the nearer Rindler horizon forms, the far cosmic horizon behind it becomes unobservable and therefore (following the ...

3

The Casimir effect is analogous to gravity in only one way--- it has a negative energy which varies as a power of the distance. In all other ways, it is different. The power-law is different, the cause is different, it is a quantum effect, not a classical effect, and the mediator is the electromagnetic field, not the gravitational field. Negative energy is ...

3

The Casimir effect and the Van der Waals force between two conducting plates are one and the same thing. To see this, consider the boundary conditions postulated for the Casimir effect. The electric field has to be exactly zero at the plates. Because of this, it is said, the zero point energy of the vacuum is lower in between the plates than outside, which ...

2

Dear Carl, the correct paper to derive the 0.1-second lifetime of the anti-Hydrogen atom in the gravitational field is described after the very sentence you quoted. There is a "[20]" symbol which means that the sentence is justified in the reference number 20 in the list of literature at the end of the paper you quoted. So the correct paper that answers ...

2

A friend recently brought to my attention that this experiment was actually performed 6 months after i posted the question in this site: http://blogs.nature.com/news/2011/11/light_coaxed_from_nothingness.html http://www.chalmers.se/en/news/pages/chalmers-scientists-create-light-from-vacuum.aspx Christopher Wilson from Chalmers (and his team) used the ...

2

Virtual particles influence physics at every point of space, whether or not there is a nearby atomic nucleus or orbital. All electrons in an atom receive energy shifts analogous to the Lamb shift (from virtual photons), aside from other quantum corrections. In fact, the influence of the virtual particles only becomes truly measurable if there are some nearby ...

2

The zero-point energy for the quantum mechanical harmonic oscillator can be related to the Heisenberg uncertainty principle (HUP). A bit oversimplified, the point is intuitively that if the mechanical energy $$H~=~\frac{p^2}{2m}+\frac{1}{2}m\omega^2 q^2, \qquad \omega ~:=~ 2\pi f,$$ is zero, then the position $q$ and the momentum $p$ must also both be ...

2

I think you are confusing the CMB with radiation from the apparent horizon. CMB is just relic light from the surface of last-scattering - it behaves like any light which is emitted from a source. It is totally unrelated to the Hawking radiation emitted from the horizon. A neat coincidence (as afar as we know) is that the surface of last scattering is "close" ...

2

The interaction between the geometry of spacetime (how precisely it is "warped"), and energy, is a fundamental notion in general relativity. Specifically, the Einstein field equations tell us that if there is energy or momentum near some spacetime point, then the geometry nearby will bend (warp, curve, whatever you'd like to call it) in a particular way. ...

2

The energy density between the Casimir conductors can indeed be positive or negative. The calculation of Casimir energies is often done by noting that the plates impose boundary conditions on the field modes that can exist between them. Therefore in the presence of the plates, a more restricted set of modes is allowed than would be the case if the plates ...

1

When you have two parallel mirrors you get standing waves between them, and the standing waves can only form if the spacing between the mirrors is a half integral number of wavelengths. Exactly this principle is used in the Fabry-Perot interferometer. The restriction of the wavelength happens because if the mirror spacing is not a half integral number of ...

1

I'm happy to see that Mike himself has replied to the question (being him the author of the paper in question, and the inertia-as-a-cosmological-casimir-cutoff effect idea), but i wanted to underline a few items. A derivation of a MOND-like acceleration cutoff for inertia as proposed by quantised inertia using heuristic by physically sound arguments, which ...

1

It's associated with the confinement of the particle. As the coefficient of the quadratic term in the harmonic potential goes to zero, the particle becomes less & less localized and the the zero point energy drops accordingly. It can be as small as you want. When you speak of photons, now you're referring to QFT and the energy in a mode of the EM field. ...

1

All interactions at the quantum dynamical level are subject to an analysis with Feynman diagrams, and the Casimir effect is not different in this case. Virtual pairs are internal lines in Feynman diagrams. R.L.Jaffe has a arXiv paper that goes into the detail on the Casimir force and corresponding diagrams. the abstract: In discussions of the ...

1

The problem is not the availability of exotic matter. It is the manipulation of it in a practical manner that is not known. The stuff of exotic matter (quantum fluctuation) is everywhere. The Casimir Effect is only a demonstration of its existence in a practical manner. To do more with that so called negative energy that the quantum fluctuation can present ...

1

Virtual particles are mostly the name given to a category of mathematical expressions (contained in Feynman diagrams). While virtual particles are mathematically associated to real, physical particles (virtual electron, etc.), they have no reason to exist physically. Essentially, the name is a somewhat of a misnomer. Now, there is a point of view in which ...

1

Casimir force is an effect of interaction of two neutral but quantum mechanical plates. Neutral means they are not globally charged. Quantum mechanical means they consist of many real particles and fields bound together with laws of quantum mechanics. When people use the conditions of ideal conductivity of plates and write the filed boundary conditions like ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
Timezone: »

Workshop
Learning in the Presence of Strategic Behavior
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan

Fri Dec 08 08:00 AM -- 06:30 PM (PST) @ 101 A

Traditionally, learning theory has adopted two extreme views in this respect: First, when learning occurs in isolation from strategic behavior, such as in the classical PAC setting where the data is drawn from a fixed distribution; second, when the learner faces an adversary whose goal is to inhibit the learning process, such as the minimax setting where the data is generated by an adaptive worst-case adversary. While these extreme perspectives have lead to elegant results and concepts, such as VC dimension, Littlestone dimension, regret bounds, and more, many types of problems that we would like to solve involve strategic behaviors that do not fall into these two extremes. Examples of these problems include but are not limited to

1. Learning from data that is produced by agents who have vested interest in the outcome or the learning process. For example, learning a measure of quality of universities by surveying members of the academia who stand to gain or lose from the outcome, or when a GPS routing app has to learn patterns of traffic delay by routing individuals who have no interest in taking slower routes.

2. Learning a model for the strategic behavior of one or more agents by observing their interactions, for example, learning economical demands of buyers by observing their bidding patterns when competing with other buyers.

3. Learning as a model of interactions between agents. Examples of this include applications to swarm robotics, where individual agents have to learn to interact in a multi-agent setting in order to achieve individual or collective goals.

4. Interactions between multiple learners. In many settings, two or more learners learn about the same or multiple related concepts. How do these learners interact? What are the scenarios under which they would share knowledge, information, or data. What are the desirable interactions between learners? As an example, consider multiple competing pharmaceutical firms that are learning about the effectiveness of a certain treatment. In this case, while competing firms would prefer not to share their findings, it is beneficial to the society when such findings are shared. How can we incentivize these learners to perform such desirable interactions?

The main goal of this workshop is to address current challenges and opportunities that arise from the presence of strategic behavior in learning theory. This workshop aims at bringing together members of different communities, including machine learning, economics, theoretical computer science, and social computing, to share recent results, discuss important directions for future research, and foster collaborations.

 Fri 9:00 a.m. - 9:45 a.m. (Invited Talk) Yiling Chen: Learning in Strategic Data Environments. (Invited Talk) We live in a world where activities and interactions are recorded as data: food consumption, workout activities, buying and selling products, sharing information and experiences, borrowing and lending money, and exchanging excess resources. Scientists use the rich data of these activities to understand human social behavior, generate accurate predictions, and make policy recommendations. Machine learning traditionally take such data as given, often treating them as independent samples from some unknown statistical distribution. However, such data are possessed or generated by potentially strategic people in the context of specific interaction rules. Hence, what data become available depends on the interaction rules. For example, people with sensitive medical conditions may not reveal their medical data in a survey but could be willing to share them when compensated; crowd workers may not put in a good-faith effort in completing a task if they know that the requester cannot verify the quality of their contributions. In this talk, I argue that a holistic view that jointly considers data acquisition and learning is important. I will discuss two projects. The first project considers acquiring data from strategic data holders who have private cost for revealing their data and then learning from the acquired data. We provide a risk bound on learning, analogous to classic risk bounds, for situations when agents’ private costs can correlate with their data in arbitrary ways. The second project leverages techniques in learning to design a mechanism for obtaining high-quality data from strategic data holders. The mechanism has a strong incentive property: it is a dominant strategy for each agent to truthfully reveal their data even if we have no ground truth to directly evaluate their contributions. This talk is based on joint works with Jacob Abernethy, Chien-Ju Ho, Yang Liu, and Bo Waggoner. Yiling Chen 🔗 Fri 9:45 a.m. - 10:00 a.m. Strategic Classification from Revealed Preferences (Talk) We study an online linear classification problem, in which the data is generated by strategic agents who manipulate their features in an effort to change the classification outcome. In rounds, the learner deploys a classifier, and an adversarially chosen agent arrives, possibly manipulating her features to optimally respond to the learner. The learner has no knowledge of the agents' utility functions or real'' features, which may vary widely across agents. Instead, the learner is only able to observe theirrevealed preferences'' --- i.e. the actual manipulated feature vectors they provide. For a broad family of agent cost functions, we give a computationally efficient learning algorithm that is able to obtain diminishing Stackelberg regret'' --- a form of policy regret that guarantees that the learner is obtaining loss nearly as small as that of the best classifier in hindsight, even allowing for the fact that agents will best-respond differently to the optimal classifier. Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner and Zhiwei Steven Wu Jinshuo Dong 🔗 Fri 10:00 a.m. - 10:15 a.m. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium (Talk) In online advertising markets, advertisers often purchase ad placements through bidding in repeated auctions based on realized viewer information. We study how budget-constrained advertisers may compete in such sequential auctions in the presence of uncertainty about future bidding opportunities and competition. We formulate this problem as a sequential game of incomplete information, where bidders know neither their own valuation distribution, nor the budgets and valuation distributions of their competitors. We introduce a family of practical bidding strategies we refer to as adaptive pacing strategies, in which advertisers adjust their bids according to the sample path of expenditures they exhibit. Under arbitrary competitors’ bids, we establish through matching lower and upper bounds the asymptotic optimality of this class of strategies as the number of auctions grows large. When all the bidders adopt these strategies, we establish the convergence of the induced dynamics and characterize a regime (well motivated in the context of display advertising markets) under which these strategies constitute an approximate Nash equilibrium in dynamic strategies: The benefit of unilaterally deviating to other strategies, including ones with access to complete information, becomes negligible as the number of auctions and competitors grows large. This establishes a connection between regret minimization and market stability, by which advertisers can essentially follow equilibrium bidding strategies that also ensure the best performance that can be guaranteed off-equilibrium. Yonatan Gur and Santiago Balseiro. Yonatan Gur 🔗 Fri 10:15 a.m. - 10:30 a.m. Spotlights (Talks) Strategyproof Linear Regression. Yiling Chen, Chara Podimata and Nisarg Shah Incentive-Aware Learning for Large Markets. Mohammad Mahdian, Vahab Mirrokni and Song Zuo. Learning to Bid Without Knowing Your Value. Zhe Feng, Chara Podimata and Vasilis Syrgkanis. Budget Management Strategies in Repeated Auctions. Uniqueness and Stability of System Equilibria. Santiago Balseiro, Anthony Kim, Mohammad Mahdian and Vahab Mirrokni. Dynamic Second Price Auctions with Low Regret. Vahab Mirrokni, Renato Paes Leme, Rita Ren and Song Zuo. Chara Podimata · Song Zuo · Zhe Feng · Anthony Kim 🔗 Fri 11:00 a.m. - 11:45 a.m. (Invited Talk) Eva Tardos: Online learning with partial information for players in games. (Invited Talk) Learning has been adopted as a general behavioral model for players in repeated games. Learning offers a way that players can adopt to (possibly changing) environment. Learning guarantees high social welfare in many games (including traffic routing as well as online auctions), even when the game or the population of players is dynamically changing. The rate at which the game can change depends on the speed of convergence of the learning algorithm. If players observe all other participants, which such full information feedback classical learning algorithms offer very fast convergence. However, such full information feedback is often not available, and the convergence of classical algorithms with partial feedback is much good. In this talk we develop a black-box approach for learning where the learner observes as feedback only losses of a subset of the actions. The simplicity and black box nature of the approach allows us to use of this faster learning rate as a behavioral assumption in games. Talk based on joint work with Thodoris Lykouris and Karthik Sridharan. Eva Tardos 🔗 Fri 11:45 a.m. - 12:30 p.m. (Invited Talk) Mehryar Mohri: Regret minimization against strategic buyers. (Invited Talk) This talk presents an overview of several recent algorithms for regret minimization against strategic buyers in the context of posted-price auctions, which are crucial for revenue optimization in online advertisement. Joint work with Andres Munoz Medina. Mehryar Mohri 🔗 Fri 12:30 p.m. - 1:50 p.m. Lunch Break (Break) 🔗 Fri 1:50 p.m. - 2:35 p.m. (Invited Talk) Percy Liang: Learning with Adversaries and Collaborators (Invited Talk) We argue that the standard machine learning paradigm is both too weak and too string. First, we show that current systems for image classification and reading comprehension are vulnerable to adversarial attacks, suggesting that existing learning setups are inadequate to produce systems with robust behavior. Second, we show that in an interactive learning setting where incentives are aligned, a system can learn a simple natural language from a user from scratch, suggesting that much more can be learned under a cooperative setting. Percy Liang 🔗 Fri 2:35 p.m. - 3:00 p.m. Spotlights (Talks) Multi-Agent Counterfactual Regret Minimization for Partial-Information Collaborative Games. Matthew Hartley, Stephan Zheng and Yisong Yue. Inference of Strategic Behavior based on Incomplete Observation Data. Antti Kangasrääsiö and Samuel Kaski. Inferring agent objectives at different scales of a complex adaptive system. Dieter Hendricks, Adam Cobb, Richard Everett, Jonathan Downing and Stephen Roberts. A Reinforcement Learning Framework for Eliciting High Quality Information. Zehong Hu, Yang Liu, Yitao Liang and Jie Zhang. Learning Multi-item Auctions with (or without) Samples. Yang Cai and Constantinos Daskalakis. Competing Bandits: Learning under Competition. Yishay Mansour, Aleksandrs Slivkins and Zhiwei Steven Wu. Robust commitments and partial reputation. Vidya Muthukumar and Anant Sahai Learning with Abandonment. Ramesh Johari and Sven Schmit. Antti Kangasrääsiö · Richard Everett · Yitao Liang · Yang Cai · Steven Wu · Vidya Muthukumar · Sven Schmit 🔗 Fri 3:00 p.m. - 3:30 p.m. Poster Session & Coffee break (Break) 🔗 Fri 3:30 p.m. - 4:15 p.m. (Invited Talk) Alex Peysakhovich: Towards cooperative AI (Invited Talk) Social dilemmas are situations where individuals face a temptation to increase their payoffs at a cost to total welfare. Importantly, social dilemmas are ubiquitous in real world interactions. We show how to modify modern reinforcement learning methods to construct agents that act in ways that are simple to understand, begin by cooperating, try to avoid being exploited, and forgiving (try to return to mutual cooperation). Such agents can maintain cooperation in Markov social dilemmas with both perfect and imperfect information. Our construction does not require training methods beyond a modification of self-play, thus if an environment is such that good strategies can be constructed in the zero-sum case (eg. Atari) then we can construct agents that solve social dilemmas in this environment. Alexander Peysakhovich 🔗 Fri 4:15 p.m. - 4:30 p.m. Statistical Tests of Incentive Compatibility in Display Ad Auctions (Talk) Consider a buyer participating in a repeated auction in an ad exchange. How does a buyer figure out whether her bids will be used against her in the form of reserve prices? There are many potential A/B testing setups that one can use. However, we will show many natural experimental designs have serious flaws. For instance, one can use additive or multiplicative perturbation to the bids. We show that additive perturbations to bids can lead to paradoxical results, as reserve prices are not guaranteed to be monotone for non-MHR distributions, and thus higher bids may lead to lower reserve prices! Similarly, one may be tempted to measure bid influence in reserves by randomly perturbing one's bids. However, unless the perturbations are aligned with the partitions used by the seller to compute optimal reserve prices, the results are guaranteed to be inconclusive. Finally, in practice additional market considerations play a large role---if the optimal reserve price is further constrained by the seller to satisfy additional business logic, the power of the buyer to detect the effect to which his bids are being used against him is limited. In this work we develop tests that a buyer can user to measure the impact of current bids on future reserve prices. In addition, we analyze the cost of running such experiments, exposing trade-offs between test accuracy, cost, and underlying market dynamics. We validate our results with experiments on real world data and show that a buyer can detect reserve price optimization done by the seller at a reasonable cost. Andres Munoz Medina, Sebastien Lahaie, Sergei Vassilvitskii and Balasubramanian Sivan Andres Munoz 🔗 Fri 4:30 p.m. - 4:45 p.m. Optimal Economic Design through Deep Learning (Talk) Designing an auction that maximizes expected revenue is an intricate task. Despite major efforts, only the single-item case is fully understood. We explore the use of tools from deep learning on this topic. The design objective is revenue optimal, dominant-strategy incentive compatible auctions. For a baseline, we show that multi-layer neural networks can learn almost-optimal auctions for a variety of settings for which there are analytical solutions, and even without encoding characterization results into the design of the network. Looking ahead, deep learning has promise for deriving auctions with high revenue for poorly understood problems. Paul Duetting, Zhe Feng, Harikrishna Narasimhan, and David Parkes David Parkes 🔗 Fri 4:45 p.m. - 5:00 p.m. Learning Against Non-Stationary Agents with Opponent Modeling & Deep Reinforcement Learning (Talk) Humans, like all animals, both cooperate and compete with each other. Through these interactions we learn to observe, act, and manipulate to maximize our utility function, and continue doing so as others learn with us. This is a decentralized non-stationary learning problem, where to survive and flourish an agent must adapt to the gradual changes of other agents as they learn, as well as capitalize on sudden shifts in their behavior. To date, a majority of the work in deep multi-agent reinforcement learning has focused on only one of these types of adaptations. In this paper, we introduce the Switching Agent Model (SAM) as a way of dealing with both types of non-stationarity through the combination of opponent modeling and deep multi-agent reinforcement learning. Richard Everett Richard Everett 🔗

#### Author Information

##### Jennifer Wortman Vaughan (Microsoft Research)

Jenn Wortman Vaughan is a Senior Principal Researcher at Microsoft Research, New York City. Her research background is in machine learning and algorithmic economics. She is especially interested in the interaction between people and AI, and has often studied this interaction in the context of prediction markets and other crowdsourcing systems. In recent years, she has turned her attention to human-centered approaches to transparency, interpretability, and fairness in machine learning as part of MSR's FATE group and co-chair of Microsoft’s Aether Working Group on Transparency. Jenn came to MSR in 2012 from UCLA, where she was an assistant professor in the computer science department. She completed her Ph.D. at the University of Pennsylvania in 2009, and subsequently spent a year as a Computing Innovation Fellow at Harvard. She is the recipient of Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology, a National Science Foundation CAREER award, a Presidential Early Career Award for Scientists and Engineers (PECASE), and a handful of best paper awards. In her "spare" time, Jenn is involved in a variety of efforts to provide support for women in computer science; most notably, she co-founded the Annual Workshop for Women in Machine Learning, which has been held each year since 2006.


text:
# Mersenne prime

A prime number of the form $M_p = 2^p-1$ where $p$ is prime.

• The Mersenne number $M_p$ is prime for exponent $p$ =

 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11 213 19 937 21 701 23 209 44 497 86 243 110 503 132 049 216 091 756 839 859 433 1 257 787 1 398 269 2 976 221 3 021 377 6 972 593 13 466 917 20 996 011 24 036 583 25 964 951 30 402 457 32 582 657 37 156 667 42 643 801 43 112 609 ... 57 885 161 ... 74 207 281 ... 77 232 917 ... 82 589 933 ...

For all other prime exponents less than 46,118,053 $M_p$ is known to be composite (tested and double-checked), and for those less than 81,835,723 it is probably composite (tested at least once). (As of 23 Dec 2018)

... it is the greatest that will ever be discovered for, as they are merely curious without being useful, it is not likely that any person will attempt to find one beyond it.

-- Peter Barlow, 1811, on M31 = 2,147,483,647

• Mersenne numbers have a particulary simple test for primality, the Lucas-Lehmer test.
• The number-theoretic interest in Mersenne primes comes from the following theorem: if $m$ and $n$ are natural numbers, with $n$ greater than $1$, and if $m^n-1$ is prime, then $m$ is $2$ and $n$ is prime.
$$n>1 \land m^n \in \mbox{prime} \implies m=2 \land n \in \mbox{prime}$$

### Factors of Mersenne Numbers

Not all the non-prime Mersennes have been completely factored. Some factoring data is

• M11 = 2,047 = 23 × 89
• M23 = 8,388,607 = 47 × 178,481
• M29 = 233 × 1,103 × 2,089
• M37 = 223 × 616,318,177
• M41 = 13,367 × 164,511,353
• M43 = 431 × 9,719 × 2,099,863
• M47 = 2,351 × 4,513 × 13,264,529
• M53 = 6,361 × 69,431 × 20,394,401
• M59 = 179,951 × 3,203,431,780,337
• M67 = 193,707,721 × 761,838,257,287
• M71 = 228,479 × 48,544,121 × 212,885,833
• M73 = 439 × 2,298,041 × 9,361,973,132,609
• M79 = 2,687 × 202,029,703 × 1,113,491,139,767
• M83 = 167 × 57,912,614,113,275,649,087,721
• M97 = 11,447 × 13,842,607,235,828,485,645,766,393
• M101 = 7,432,339,208,719 × ...
• M103 = 2,550,183,799 × ...
• M109 = 745,988,807 × ...
• M113 = 3,391 × 23,279 × 65,993 × 1,868,569 × ...
• 2125-1 = 31 × 601 × 1801 × 269,089,806,001 × 4,710,883,168,879,506,001
• M131 = 263 × ...
• M137 = 32,032,215,596,496,435,569 × 5,439,042,183,600,204,290,159
• M139 = 5,625,767,248,687 × ...
• M149 = 86,656,268,566,282,183,151 × ...
• M151 = 18,121 × 55,871 ×165,799 × 2,332,951 × ...
• M157 = 852,133,201 × 60,726,444,167 × 1,654,058,017,289 × ...
• M163 = 150,287 × 704,161 × 110,211,473 × 27,669,118,297 × ...
• M167 = 2,349,023 × ...
• M173 = 730,753 × 1,505,447 × 70,084,436,712,553,223 × ...
• M179 = 359 × 1,433 ×...
• M181 = 43,441 × 1,164,193 × 7,648,337 × ...
• M191 = 383 × 7,068,569,257 × 39,940,132,241 × 332,584,516,519,201 × ...
• M193 = 13,821,503 × 61,654,440,233,248,340,616,559 × ...
• M197 = 7,487 × ...
• M199 = 164,504,919,713 × ...
• M211 = 15,193 × 60,272,956,433,838,849,161 × ...
• M223 = 18,287 × 196,687 × 1,466,449 × 2,916,841 × 1,469,495,262,398,780,123,809 × ...
• M227 = 26,986,333,437,777,017 × ...
• M229 = 1,504,073 × 20,492,753 × 59,833,457,464,970,183 × ...
• M233 = 1,399 × 135,607 × 622,577 × ...
• M239 = 479 × 1,913 × 5,737 × 176,383 × 134,000,609 × 7,110,008,717,824,458,123,105,014,279,253,754,096,863,768,062,879
• M241 = 22,000,409 × ...
• M251 = 503 × 54217 × 178,230,287,214,063,289,511 × 61,676,882,198,695,257,501,367 × ...
• M257 = 535,006,138,814,359 × 1,155,685,395,246,619,182,673,033 × ...
• M263 = 23,671 × 13,572,264,529,177 × 120,226,360,536,848,498,024,035,943 × ...

More of this factorisation data, including the known information for all exponents less than 200,000. Some other data taken from Robert Munafo's Large Number Notes page.


text:
Posts: 1
Registered: 09-28-2011

# Network Magic install size

Hi all,

I've installed Network Magic 5.5.9195.0 on my Windows 7 based PC and in the process of performing some housekeeping, the installation size of Network Magic is telling me it's 32.6 Gb ( Control Panel / Programs / Programs and Features ). The installation directory of Network Magic under program files is only 44Mb so is there another area where logfiles are kept ? Or is this a Windows 'feature' and giving me the wrong sizing.

TIA,

Skeeterrs

Posts: 1
Registered: 01-30-2012

## Re: Network Magic install size

I have the same issue its taking up a huge chunk of hard drive space

Highlighted
Posts: 1
Registered: 02-25-2012

## Re: Network Magic install size

Same problem here