text:
## RD Sharma Class 10 Solutions Chapter 9 Constructions Ex 9.3

These Solutions are part of RD Sharma Class 10 Solutions. Here we have given RD Sharma Class 10 Solutions Chapter 9 Constructions Ex 9.3

Other Exercises

Question 1.
Draw a circle of radius 6 cm. From a point 10 cm away from its centre, construct the pair of tangents to the circle and measure their lengths.
Solution:
Steps of construction :
(i)
Draw a circle with O centre and 6 cm radius.
(ii) Take a point P, 10 cm away from the centre O.
(iii) Join PO and bisect it at M.
(iv) With centre M and diameter PO, draw a circle intersecting the given circle at T and S.
(v) Join PT and PS.
Then PT and PS are the required tangents.

Question 2.
Draw a circle of radius 3 cm. Take two points P and Q on one of its extended diameter each at a distance of 7 cm from its centre. Draw tangents to the circle from these two points P and Q.
Solution:
Steps of construction :
(i)
Draw a circle with centre O and radius 3 cm.
(ii) Draw a diameter and produce it to both sides.
(iii) Take two points P and Q on this diameter with a distance of 7 cm each from the centre O.
(iv) Bisect PO at M and QO at N
(v) With centres M and N, draw circle on PO and QO as diameter which intersect the given circle at S, T and S’, T’ respectively.
(vi) Join PS, PT, QS’ and QT’.
Then PS, PT, QS’ and QT’ are the required tangents to the given circle.

Question 3.
Draw a line segment AB of length 8 cm. Taking A as centre, draw a circle of radius 4 cm and taking B as centre, draw another circle of radius 3 cm. Construct tangents to each circle from the centre of the other circle. [CBSE 2013]
Solution:
Steps of construction :
(i)
Draw a line segment AB = 8 cm.
(ii) With centre A and radius 4 cm and with centre B and radius 3 cm, circles are drawn.
(iii) Bisect AB at M.
(iv) With centre M and diameter AB, draw a circle which intersects the two circles at S’, T’ and S, T respectively.
(v) Join AS, AT, BS’and BT’.
Then AS, AT, BS’ and BT’ are the required tangent.

Question 4.
Draw two tangents to a circle of raidus 3.5 cm from a point P at a distance of 6.2 cm from its centre.
Solution:
Steps of construction :
(i) Draw a circle with centre O and radius 3.5 cm
(ii) Take a point P which is 6.2 cm from O.
(iii) Bisect PO at M and draw a circle with centre M and diameter OP which intersects the given circle at T and S respectively.
(iv) Join PT and PS.
PT and PS are the required tangents to circle.

Question 5.
Draw a pair of tangents to a circle of radius 4.5 cm, which are inclined to each other at an angle of 45°.            [CBSE 2013]
Solution:
Steps of construction :
Angle at the centre 180° – 45° = 135°
(i) Draw a circle with centre O and radius 4.5 cm.

(ii) At O, draw an angle ∠TOS = 135°
(iii) At T and S draw perpendicular which meet each other at P.
PT and PS are the tangents which inclined each other 45°.

Question 6.
Draw a right triangle ABC in which AB = 6 cm, BC = 8 cm and ∠B = 90°. Draw BD perpendicular from B on AC and draw a circle passing through the points B, C and D. Construct tangents from A to this circle.
Solution:
Steps of Construction :
Draw a line segment BC = 8 cm
From B draw an angle of 90°
Draw an arc $$\breve { BA }$$  = 6cm cutting the angle at A.
Join AC.
ΔABC is the required A.
Draw ⊥ bisector of BC cutting BC at M.
Take M as centre and BM as radius, draw a circle.
Take A as centre and AB as radius draw an arc cutting the circle at E. Join AE.
AB and AE are the required tangents.
Justification :
∠ABC = 90°                                            (Given)
Since, OB is a radius of the circle.
∴ AB is a tangent to the circle.
Also AE is a tangent to the circle.

Question 7.
Draw two concentric circles of radii 3 cm and 5 cm. Construct a tangent to the smaller circle from a point on the larger circle. Also, measure its length.                      [CBSE 2016]
Solution:
Given, two concentric circles of radii 3 cm and 5 cm with centre O. We have to draw pair of tangents from point P on outer circle to the other.

Steps of construction :
(i) Draw two concentric circles with centre O and radii 3 cm and 5 cm.
(ii) Taking any point P on outer circle. Join OP.
(iii) Bisect OP, let M’ be the mid-point of OP.
Taking M’ as centre and OM’ as radius draw a circle dotted which cuts the inner circle as M and P’.
(iv) Join PM and PP’. Thus, PM and PP’ are the required tangents.
(v) On measuring PM and PP’, we find that PM = PP’ = 4 cm.
Actual calculation:
In right angle ΔOMP, ∠PMO = 90°
∴ PM2 = OP2 – OM2
[by Pythagoras theorem i.e. (hypotenuse)2 = (base)2 + (perpendicular)2]
⇒ PM2 = (5)2 – (3)2 = 25 – 9 = 16
⇒ PM = 4 cm
Hence, the length of both tangents is 4 cm.

Hope given RD Sharma Class 10 Solutions Chapter 9 Constructions Ex 9.3 are helpful to complete your math homework.

If you have any doubts, please comment below. Learn Insta try to provide online math tutoring for you.


text:
Density of a probability distribution

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

probability density

The derivative of the distribution function corresponding to an absolutely-continuous probability measure.

Let be a random vector taking values in an -dimensional Euclidean space , let be its distribution function, and let there exist a non-negative function such that

for any real . Then is called the probability density of , and for any Borel set ,

Any non-negative integrable function satisfy the condition

is the probability density of some random vector.

If two random vectors and taking values in are independent and have probability densities and respectively, then the random vector has the probability density that is the convolution of and :

Let and be random vectors taking values in and and having probability densities and respectively, and let be a random vector in . If then and are independent, has the probability density , which is called the joint probability density of the random vectors and , where

 (1)

Conversely, if has a probability density that satisfies (1), then and are independent.

The characteristic function of a random vector having a probability density is expressed by

where if is absolutely integrable then is a bounded continuous function, and

The probability density and the corresponding characteristic function are related also by the following relation (Plancherel's identity): The function is integrable if and only if the function is integrable, and in that case

Let be a measurable space, and let and be -finite measures on with absolutely continuous with respect to , i.e. implies , . In that case there exists on a non-negative measurable function such that

for any . The function is called the Radon–Nikodým derivative of with respect to , while if is a probability measure, it is also the probability density of relative to .

A concept closely related to the probability density is that of a dominated family of distributions. A family of probability distributions on a measurable space is called dominated if there exists a -finite measure on such that each probability measure from has a probability density relative to (or, what is the same, if each measure from is absolutely continuous with respect to ). The assumption of dominance is important in certain theorems in mathematical statistics.

References

 [1] Yu.V. [Yu.V. Prokhorov] Prohorov, Yu.A. Rozanov, "Probability theory, basic concepts. Limit theorems, random processes" , Springer (1969) (Translated from Russian) [2] W. Feller, "An introduction to probability theory and its applications" , 2 , Wiley (1971) [3] E.L. Lehmann, "Testing statistical hypotheses" , Wiley (1986)
How to Cite This Entry:
Density of a probability distribution. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Density_of_a_probability_distribution&oldid=15505
This article was adapted from an original article by N.G. Ushakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article

format: plain


text:
# On Bellman's Optimality Principle for zs-POSGs

Many non-trivial sequential decision-making problems are efficiently solved by relying on Bellman's optimality principle, i.e., exploiting the fact that sub-problems are nested recursively within the original problem. Here we show how it can apply to (infinite horizon) 2-player zero-sum partially observable stochastic games (zs-POSGs) by (i) taking a central planner's viewpoint, which can only reason on a sufficient statistic called occupancy state, and (ii) turning such problems into zero-sum occupancy Markov games (zs-OMGs). Then, exploiting the Lipschitz-continuity of the value function in occupancy space, one can derive a version of the HSVI algorithm (Heuristic Search Value Iteration) that provably finds an ϵ-Nash equilibrium in finite time.

## Authors

• 8 publications
• 6 publications
• 2 publications
• 7 publications
• 4 publications
10/25/2021

### HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties

Dynamic programming and heuristic search are at the core of state-of-the...
10/21/2020

### Solving Zero-Sum One-Sided Partially Observable Stochastic Games

Many security and other real-world situations are dynamic in nature and ...
06/22/2016

### Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information

Zero-sum stochastic games provide a rich model for competitive decision ...
01/16/2013

### Fast Planning in Stochastic Games

Stochastic games generalize Markov decision processes (MDPs) to a multia...
02/25/2020

### On Reinforcement Learning for Turn-based Zero-sum Markov Games

We consider the problem of finding Nash equilibrium for two-player turn-...
04/08/2022

### The Complexity of Infinite-Horizon General-Sum Stochastic Games

We study the complexity of computing stationary Nash equilibrium (NE) in...
05/14/2020

### Comparison of Information Structures for Zero-Sum Games and a Partial Converse to Blackwell Ordering in Standard Borel Spaces

In statistical decision theory involving a single decision-maker, one sa...
##### This week in AI

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

## 1 Introduction

Bellman’s optimality principle (Bellman’s OP) [3] led to state-of-the-art solvers in many non-trivial sequential decision-making problems, assuming partial observability [25], multi-objective criteria [29, 21], collaborating agents, e.g.

, modeled as decentralized partially observable Markov decision processes (Dec-POMDPs)

[13, 30, 9], or some non-collaborative perfect information games (from Shapley’s seminal work [26] to [6]). In all these settings this principle exploits the fact that sub-problems are nested recursively within the original problem. An open question is whether—and how—it could be applied to imperfect information games, which are encountered in diverse applications such as Poker [18] or security games [1]. This paper answers this question in the setting of 2-player zero-sum partially observable stochastic games (zs-POSGs), i.e., imperfect information games with simultaneous moves, perfect recall, discounted rewards and a possibly infinite time horizon.

As general POSGs and Dec-POMDPs, infinite-horizon zs-POSGs are undecidable, and their finite-horizon approximations are in NEXP [22, 4]. As further discussed in Section 2, solution techniques for finite-horizon POSGs, or other impartial information games that can be formulated as extensive-form games (EFGs), typically solve an equivalent normal-form game [27] or use a dedicated regret-minimization mechanism [34, 5]. They thus do not rely on Bellman’s optimality principle, except (i) a dynamic programming approach that only constructs sets of non-dominated solutions [13], (ii) in collaborative problems (Decentralized POMDPs), adopting the viewpoint of a (blind) central planner [30, 9], and (iii) for (mostly 2-player zero-sum) settings with observability assumptions such that one can reason on player beliefs [12, 7, 2, 15, 8, 14]. Here, we do not make any assumption beyond the game being 2-player zero-sum, in particular regarding observability of the state and actions.

As for a number of Dec-POMDP solvers, our approach adopts the viewpoint not of a player, but of a central (offline) planner that prescribes individual strategies to the players [30], which allows turning a zs-POSG into a non-observable game for which Bellman’s optimality principle applies. This is achieved in Section 4 (after background Section 3) while reasoning not on a player’s belief over the game state (as feasible in POMDPs or some particular games), but on the central planner’s (blind) belief, a statistic called occupancy state and that we prove to be sufficient for optimal planning, as Dibangoye et al. did for Dec-POMDPs [9]. In Section 5, our Bellman/Shapley operator is proved to induce an optimal game value function that is Lipschitz-continuous in occupancy space, which leads to deriving value function approximators, including upper- and lower-bounding ones, and discussing their initialization. Finally, Section 6 describes a variant of HSVI for zs-POSGs, and demonstrates its finite-time convergence to an -optimal solution despite the continuous (occupancy) state and action spaces.

## 2 Related Work

Infinite horizon POSGs are undecidable [22], which justifies searching for near-optimal solutions, e.g., through finite horizon solutions, as we will do. There is little work on solving POSGs, in particular through exploiting Bellman’s optimality principle. One exception is Hansen and Zilberstein’s work on finite horizon POSGs [13] , where dynamic programming (DP) incrementally constructs non-dominated policy trees for each player, which allows then deriving a solver for common-payoff POSGs, i.e., decentralized partially observable Markov decision processes (Dec-POMDPs). Here, Bellman’s OP thus serves as a pre-processing phase, while we aim at employing it in the core of algorithms.

##### Dec-POMDPs

Bellman’s OP appears as the core component of a Dec-POMDP solver when Szer et al. [30] adopt a planner-centric viewpoint whereby the planner aims at providing the players with their private policies without knowing which action-observation histories they have experienced. The planner’s information state at thus contains the initial belief and the joint policy up to . This leads to turning a Dec-POMDP into an information-state MDP, and obtaining a deterministic shortest path problem that can be solved using an A* search called MAA* (multi-agent A*).

Then, another important step is when Dibangoye et al. [9] show that (i) the occupancy state, a statistic used to compute expected rewards in MAA*, is in fact sufficient for planning, and (ii) the optimal value function is piecewise linear and convex (PWLC) in occupancy space, which allows adapting point-based POMDP solvers using approximators of .

##### Subclasses of POSGs

Recent works addressed particular cases of discounted partially observable stochastic games (POSGs), 2-player and zero-sum if not specified otherwise, exploiting the structure of the problem to turn it into an equivalent problem for which Bellman’s principle applies. Ghosh et al. [12] considered POSGs with public actions and shared observations, which can be turned into stochastic games defined over the common belief space, similarly to POMDPs turned into belief MDPs. Chatterjee and Doyen [7], Basu and Stettner [2], and Horák et al. [15] considered One-Sided POSGs, i.e., scenarios where (player) (w.l.o.g.) only partially observes the system state, and has access to the system state, plus the action and observation of . Cole and Kocherlakota [8] considered (-player) POSGs with independent private states, partially shared observability, and ’s utility function depending on his private state and on the shared observation. Horák and Bošanský [14] considered zs-POSGs with independent private states and public observations, i.e., scenarios where (i) each player has a private state he fully observes, and (ii) both players receive the same public observations of each player’s private state. Any player’s belief over the other player’s private state is thus common knowledge.

Focusing on the work of Horák et al. [15, 14], in both cases convexity or concavity properties of the optimal value function are obtained, which allow deriving upper- and lower-bounding approximators. These approximators are then employed in HSVI-based algorithms. Yet, moving from MDPs and POMDPs (as in Smith’s work) to these settings induces a tree of possible futures with an infinite branching factor, which requires changes to the algorithm, and thus to the theoretical analysis of the finite-time convergence. As we shall see, the present work adopts similar changes.

Wiggers et al. [32] prove that, using appropriate representations, the value function associated to a zs-POSG is convex for (maximizing) player and concave for (minimizing) player . Yet, this did not allow deriving a solver based on approximating the value function. Here, we exploit no convexity or concavity property of the optimal value function, as they may not hold, but its Lipschitz continuity.

##### Imperfect Information Games

Finite horizon (general-sum) POSGs can be written as extensive-form games with imperfect information and perfect recall (EFGs, often referred to as imperfect information games) [24], which makes solution techniques for EFGs relevant even for infinite-horizon POSGs. A first approach to solving EFGs is to turn them into a normal-form game before looking for a Nash equilibrium, thus ignoring the temporal aspect of the problem [27]

and inducing a combinatorial explosion. For (2-player) zs-EFGs, this leads to solving two linear programs (one for each player). Koller and Megiddo

[16] propose a different linear programming approach for zs-EFGs that exploits the temporal aspect through the choice of decision variables, but still does not apply Bellman’s OP (see also [31, 17]).

More recently, Counterfactual Regret minimization (CFR) [34] has been introduced, allowing to solve large imperfect-information games with bounded regret such as heads-up no limit hold’em poker, now winning against top human players [5]. While some CFR-based algorithms use heuristic-search techniques, thus somehow exploit the sequentiality of the game, they do not rely on Bellman’s OP either.

## 3 Background

For the sake of clarity, the concepts and results of the EFG literature used in this work will be recast in the POSG setting. We shall employ the terminology of pure/mixed/behavioral strategies and strategy profiles—more convenient in our non-collaborative setting—instead of deterministic or stochastic policies (private or joint ones)—common in the collaborative setting of Dec-POMDPs.

A (2-player) zero-sum partially observable stochastic game (zs-POSG) is defined by a tuple , where

• is a finite set of states;

• is (player) ’s finite set of actions;

• is ’s finite set of observations;

• is the probability to transition to state

and receive observations and when actions and are performed in state ;

• is a (scalar) reward function;

• is a temporal horizon;

• is a discount factor; and

• is the (public/common) initial belief state.

would like to maximize the expected return, defined as the discounted sum of future rewards, while would like to minimize it, what we formalize next.

From the Dec-POMDP, POSG and EFG literature, we use the following concepts and definitions, where :

is ’s opponent.

is a length- action-observation history for . The set of histories is , with one subset per time step.

is a joint history at time . The set of joint histories is , with one subset per time step.

[]

An occupancy state at time

is a probability distribution over state–joint-history pairs

. ( is completely specified by .) The set of occupancy states is , with one subset per time step. Note that this notion applies to POSGs despite the use of stochastic actions.

[]

A pure strategy for is a mapping from private histories in () to single private actions. By default, .

is a pure strategy profile.

[]

A mixed strategy for is a probability distribution over pure strategies. It is used by first sampling one of the pure strategies (at ), and then executing that strategy until .

is a mixed strategy profile.

[]

A (behavioral) decision rule at time for is a mapping from private histories in to distributions over private actions. For convenience, we will note the probability to pick action when facing history .

is a decision rule profile (, and noting ).

is a behavioral strategy for from time step to (included). By default, .

is a behavioral strategy profile.

[]

The value of a behavioral strategy profile in occupancy state (from time step on) is:

 V0(o0,β) =E[∞∑t=0γtRt|O0=o0,β],

where

is the random variable associated to the instant reward at time step

. [Note: This definition extends naturally to pure and mixed strategy profiles.]

The primary objective is here to find a Nash equilibrium strategy (NES), i.e., a mixed strategy profile such that no player has an incentive to deviate, which can be written:

 ∀μ1,V0(o0,μ1∗,μ2∗) ≥V0(o0,μ1,μ2∗), ∀μ2,V0(o0,μ1∗,μ2∗) ≤V0(o0,μ1∗,μ2).

In such a 2-player zero-sum game, all NESs have the same Nash-equilibrium value (NEV) .

Finite horizon POSGs being equivalent to EFGs with imperfect information and perfect recall, the following key result for EFGs applies to (finite ) POSGs:

###### Theorem 1.

[19, 11] In a game of perfect recall, mixed and behavioral strategies are equivalent. (More precisely: Every mixed strategy is equivalent to the unique behavioral strategy it generates, and each behavioral strategy is equivalent to every mixed strategy that generates it.)

## 4 Solving POSGs as Occupancy MGs

In this section, unless stated otherwise, we assume finite horizons and exact solutions (no error).

Here, we show (i) how a zs-POSG can be reformulated as a different zero-sum Markov game, and (ii) that Bellman’s optimality principle applies in this game.

### 4.1 From zs-POSGs to zs-OMGs

To solve a zs-POSG, we take the viewpoint of a central planner that searches offline for the best behavioral strategy profile before providing it to the players. This contrasts with Dec-POMDPs where deterministic strategy profiles suffice, and means exploring a (bounded) continuous space rather than a (finite) discrete one as for Dec-POMDPs. Such a planner grows a partial strategy by appending a decision rule profile .

Note that any partial strategy is in one-to-one correspondence with an occupancy state . So, the controlled process induced in occupancy space, where actions are decision rule profiles, is both deterministic and Markovian (see formal details about the dynamics below): applying in (i.e., appending it to ) leads to a unique . Also, the expected reward at time is linear in occupancy space (more precisely in the corresponding distribution over states). All this allows reasoning not on partial behavioral strategy profiles, but on occupancy states. The central planner will thus (i) infer occupancy states seen as “beliefs” over the possible situations (“situation” here meaning the current state and the players’ joint action-observation history ) which may have been reached, although without knowing what actually happened, and (ii) map each occupancy state to a decision rule profile telling the players how to act depending on their actual action-observation histories.111In contrast, in a POMDP, the belief state depends on the agent’s action-observation history, and is mapped to a single action. Each zs-POSG is thus turned into an equivalent game, called a zero-sum occupancy Markov game (zs-OMG)222We use (i) “Markov game” instead of “stochastic game” because the dynamics are not stochastic, and (ii) “partially observable stochastic game” to stick with the literature. formally defined by the tuple , where:

• is the set of occupancy states induced by the zs-POSG;

• is the set of decision rule profiles of the zs-POSG;

• is a deterministic transition function that maps each pair to the (only) possible next occupancy state ; formally (see Lemma 1 in App. A.1), ,

 T(oτ,βτ)(s′,(θ1τ,a1,z1),(θ2τ,a2,z2)) \rm\tiny def=Pr(s′,(θ1τ,a1,z1),(θ2τ,a2,z2)) =β1τ(θ1τ,a1)β2τ(θ2τ,a2)∑sPz1,z2a1,a2(s′|s)oτ(s,θ1τ,θ2τ));
• is a reward function naturally induced from the zs-POSG as the expected reward for the current occupancy state and decision rule profile:

 r(oτ,βτ)\rm\tiny def=E[r(S,A1,A2)|oτ,β1τ,β2τ] =∑s,θτoτ(s,θ1τ,θ2τ)∑a1,a2β1τ(θ1,a1)β2τ(θ2,a2)r(s,a1,a2);

we use the same notation for zs-POSGs as the context shall indicate which one is discussed;

• , , and are as in the zs-POSG.

Note first that, for convenience, we directly consider behavioral decision rules, which correspond to mixed strategies. Of course, at , ’s possible actions should be decision rules defined over histories that have non-zero probability in current . The dynamics being deterministic and the actions public, both players of that new game (also denoted and while these are different players) know the next state after each transition. But this is no standard zs Markov game also since (i) the mixture of two actions is equivalent to another action already in the (continuous) action space at hand, and (ii) at each time step, the state (occupancy) space is continuous.

We shall study the subgames of a zs-OMG, i.e., situations where some occupancy state has somehow been reached at time step , and the central solver is looking for rational strategies ( and ) to provide to the players. tells which action-observation histories each player could be facing with non-zero probability, and thus which are relevant for planning. We can then extend the definition of value function from time step only to any time step as follows (using behavioral strategies):

 Vτ(oτ,β1τ:H−1,β2τ:H−1) =E[∞∑t=τγt−τRt|Oτ=oτ,β1τ:H−1,β2τ:H−1].

Note that is in one-to-one relationship with a strategy profile , so that we can denote its concatenation with a .

### 4.2 Back to Mixed Strategies

We now re-introduce, and generalize, mixed strategies as a mathematical tool to handle subgames of a zs-OMG as normal-form games, and give some preliminary results.

For a given , let be an arbitrarily chosen mixed strategy profile that leads to (/is compatible with) , thus defined over time interval . To complete this mixed (prefix) strategy, the central planner should provide each player with a different (suffix) strategy to execute for each it could be facing. We now detail how to build an equivalent set of mixed (full) strategies for . Each of the pure (prefix) strategies used in (belonging to a set denoted ) can be extended by appending a different pure (suffix) strategy at each of its leaf nodes, which leads to a large set of pure strategies . Then, let be the set of mixed (full) strategies obtained by considering the distributions over that verify, ,

 ∑πi0:H−1∈Πi0:H−1(πi0:τ−1)μi0:H−1|oτ⟩(πi0:H−1) =μi0:τ−1|oτ⟩(πi0:τ−1). (1)

This is the set of mixed strategies compatible with .

[Proof in App. A.2]lemmalemEquivalence (originally stated on page 4.2) is convex and equivalent to the set of behavioral strategies , thus sufficient to search for a Nash equilibrium in .

While only future rewards are relevant when making a decision at , reasoning with mixed strategies defined from will be convenient because is linear in , which allows coming back to a standard normal-form game and applying known results.

In the remaining, we simply note (without index) the mixed strategies in , set which we now note . Also, since we shall work with local game , let us define: the set of ’s mixed strategies compatible with occupancy states reachable given and (with either or ). Then, (inclusion due to the latter sets being less constrained in their definition). As a consequence, if maximizing some function over ’s mixed strategies compatible with a given :

As can be easily demonstrated (cf. Lemma 2 in App. A.3), any Nash equilibrium solution of our original game induces a Nash equilibrium in any of its reachable subgames.333In contrast, a subgame perfect equilibrium requires a Nash equilibrium in any subgame reachable by some strategy profile, which is more constraining. But this does not tell whether Bellman’s optimality principle applies, what we discuss next.

### 4.3 Bellman’s Optimality Principle

For any and , let us define (i) a NE profile for the subgame at , (ii) the NE value of the subgame at any , and (iii) the local subgame at

 Q∗τ(oτ,βτ) \rm\tiny def=r(oτ,βτ)+γV∗τ+1(T(oτ,βτ)).

Then, given Nash equilibrium solutions for any , the applicability of Bellman’s optimality principle shall be proved if a Nash equilibrium of can be found by (i) solving the local subgame to get a decision rule profile and (ii) appending it to .

##### An Abnormal-Form Game?

A first question is whether this game is in fact a normal-form game, i.e., whether it could be defined by a payoff matrix over pure decision rules, payoffs for behavioral decision rules being obtained through linear mixtures.

is linear in each player’s decision rule space at each time step (i.e., in for any and ), but multilinear in each player’s behavioral strategy space (see Lemma 1 App. A.4.1), which suggests that may not be convex-concave (and thus not (bi)linear) in the space of decision rules at . As a consequence, we are possibly facing an abnormal-form game and cannot use von Neumann’s Minimax theorem.

##### Properties of the Maximin and Minimax Values

Rather than digging the convexity-concavity property further, we now show that computing the maximin and minimax values of induces finding a NE of given NEs for any .

[Proof in App. A.4.2]theoremlemAbnormalMaximinimax (originally stated on page 4.3) In the 2p zs abnormal-form game , the maximin and minimax values are both equal to i.e., as previously defined, the NEV for game —and correspond to a NES.

###### Proof.

(sketch) The proof relies on first developing the maximin of , then using (i) the equivalence of maximin and minimax for mixed strategies (when von Neumann’s minimax theorem applies), and (ii) the equivalence of mixed and behavioral strategies. ∎

[Proof in App. A.4.2]theoremcorAbnormalMaximinimax (originally stated on page 4.3) As in 2p zs normal-form games, game has at least one NES; all its NESs are all value-equivalent; and solving for maximin and minimax values allows finding one NES.

##### Maximin and Minimax Computation

The last results tell us that we can exploit knowledge of the optimal value function at (for all ) to find optimal decision rules at for any given by computing the maximin and minimax values of the local (abnormal-form) game at hand. Yet, we cannot use an LP as for normal-form games. To find an appropriate solution method, let us now look at properties of this game, noting that we lack any convexity/concavity property, and presenting a preliminary result.

[Proof in App. A.4.3]lemmalemOccLin (originally stated on page 4.3) At depth , is linear in , , and , where . It is more precisely -Lipschitz-continuous in (in -norm), i.e., for any , :

 ∥T(o′τ,βτ)−T(oτ,βτ)∥1 ≤1⋅∥o′τ−oτ∥1.

The Lipschitz continuity (LC) property would also hold in -norm or -norm, due to the equivalence between norms, but with different constants.

[Proof in App. A.4.3]lemmalemQLC (originally stated on page 4.3) For any and , is Lipschitz continuous in both and .

The payoff function of our game is thus LC in each private decision-rule space, which suggests using error-bounded global optimization techniques, as Munos’s DOO (Deterministic Optimistic Optimization) [23]. Here, searching for a maximin (resp. minimax) value suggests using two nested optimization processes: an “outer” one for the (resp. ) operator, and an “inner” one for the (resp. ). To ensure being within of the maximin value, each process could, for example, use an tolerance threshold. Yet, in such a nested optimization process, the inner process may stop, at each call, before reaching -optimality if it leads the outer process to explore a different point.

Due to the continuous state space of zs-OMGs, cannot be computed exactly. We shall now see how to approximate it, before exploiting the resulting approximators in a specific version of HSVI in Sec. 6.

## 5 Properties of V∗

In this section, we again assume finite horizon problems (unless stated otherwise). The main objective here is to propose upper- and lower-bounding approximators that exploit ’s Lipschitz continuity (rather than PWLC) property, as Fehr et al. [10] did in the setting of (single agent) information-oriented control, but here with simpler derivations.

### 5.1 Finite-Horizon Lipschitz Continuity of V∗

The following lemma proves that the expected instant reward at any is linear in , and thus so is the expected value of a finite-horizon strategy profile from onwards (trivial proof by induction). [Proof in App. A.5.1]lemmalemVLinOcc (originally stated on page 5.1) At depth , is linear w.r.t. .

[Proof in App. A.5.1]corollarycorVLCOcc (originally stated on page 5.1) is Lipschitz continuous in at any depth .

##### Refining the Lipschitz constant(s)

We have just discussed the LC of based on the LC of finite-horizon strategies, reasoning on worst case Lipschitz constants (one per time step) that hold for all strategies. Now, (i) could we refine those constants based on knowledge regarding , in particular upper and lower bounds and (see next sections)? And (ii) could we make use of those refined constants in the planning process?

Regarding question (i), and tell us that any strategy profile from time on (and thus with remaining horizon ) has values within and , hence the refined Lipschitz constant:

 λLUτ =Umaxτ−Lminτ2.

Regarding question (ii), as and are refined during the planning process, these refined depth-dependent constants would progressively shrink, thus speeding up planning! This phenomenon could encourage improving the value function bounds where they seem high (for ) or low (for ).

### 5.2 Approximating V∗

Note: For the sake of readability, the depth index may be omitted when it can be inferred from the occupancy state.

##### Approximators

An HSVI-like algorithm requires maintaining both an upper and a lower approximator of . We denote them and , and .

The LC of suggests employing LC function approximators for at depth () in the form of a lower envelope of (i) an initial upper-bound and (ii) downward-pointing L1-cones, where an upper-bounding cone —located at , with “summit” value , and slope —induces a function . The upper-bound is thus defined as the lower envelope of and the set of cones , i.e.,

 U(o) =min{U(0)(o),minω∈ΩUτU(ω)(o)}.

Respectively, for the lower-bounding approximator at depth : a lower-bounding (upward-pointing) cone induces a function ; and the lower bound is defined as the upper envelope of an initial lower bound and the set of cones , i.e.,

 L(o) =max{L(0)(o),maxω∈ΩLτL(ω)(o)}.
##### (Point-based) Operator and Value Updates

One cannot apply an operator (noted ) to update a value function approximator uniformly. Instead, when visiting some occupancy state (at depth ), we perform a point-based update of the upper-bound by (i) finding the NEV of the following game (which relies on at ):

 U(o,βτ) =∑s,a1,a2(∑θo(s,θ)β1(θ1,a1)β2(θ2,a2))r(s,a1,a2) +γU(T(o,βτ))

then (ii) adding a downward-pointing cone to . We note the upper bound after this update at point . The same applies to with upward-pointing cones instead, and using notation .

### 5.3 Initializations

Due to the symmetry between players in a zs-POSG, without loss of generality, let us look for an upper bound of the optimal value function , i.e., an optimistic bound (an admissible heuristic) for (maximizing) player 1. A usual approach to look for optimistic bounds is to relax the problem for the player at hand. To that end, one can here envision manipulating the players’ knowledge, their control over the system, the action ordering, or the opponent’s objective, e.g.:

1. providing more (e.g. full) state observability to 1;

2. providing less (e.g. no) state observability to 2;

3. letting 1 know what 2 observes;

4. letting 1 control chance (2’s choice would then only restrict the set of reachable states), but this would require that 1 has full observability;

5. letting 2 act first, and telling 1 about 2’s selected action (exactly or through a partial observation);

6. turning 2 into a collaborator by making him maximize, rather than minimize, the expected return.

Accounting for related Markov models for sequential decision-making, this suggests turning the zs-POSG at hand for example into:

• a Dec-POMDP by turning the opponent into a collaborator (or even into a POMDP or an MDP); or

• a One-Sided POSGs [15] by combining (i) full state observability, (ii) observability of 2’s observation, and (iii) observability of 2’s action.

Note that making both players’ actions or observations public (as in PO-POSGs [14]) would not be a viable solution as this would imply providing more knowledge to both players at the same time, which may prevent the resulting optimal value function from being an upper bound for our problem.

## 6 HSVI for zs-POSGs

In this section, we assume infinite horizon problems (unless stated otherwise) and -optimal solutions.

### 6.1 Algorithm

As we shall see, -optimally solving an -horizon zs-POSG amounts, as often, to solving a problem with finite horizon , which allows exploiting the results derived up to now. For convenience, we assume already known and use horizon-dependent constants (e.g., Lipschitz constants).

HSVI for zs-OMGs is detailed in Algorithm 1. As vanilla HSVI, it relies on (i) generating trajectories while acting optimistically (lines 11), i.e., player (resp. ) acting “greedily” w.r.t. (resp. ), and (ii) locally updating the upper- and lower-bounding approximators (lines 1 and 1). Here, computations of value updates and strategies rely on solving our local zero-sum abnormal form games (possibly a maximin/minimax optimization exploiting the Lipschitz continuity as discussed in Sec. 4.3). A key difference lies in the criterion for stopping trajectories. In vanilla HSVI (for POMDPs), the finite branching factor allows looking at the convergence of and at each point reachable under an optimal strategy. To ensure -convergence at , trajectories just need to be interrupted when the current width at (, where ) is smaller than a threshold . Here, dealing with an infinite branching factor, one may converge towards an optimal solution while always visiting new points of the occupancy space. Yet, as the sequence of generated (deterministic) trajectories converges to an optimal trajectory, the density of visited points around it increases, so that the Lipschitz approximation error tends to zero. One can thus bound the width within balls around visited points by exploiting the Lipschitz continuity of the optimal value function. As proposed by Horák et al. [15], this is achieved by adding a term to ensure that the width is below within a ball of radius around the current point (here the occupancy state ). Hence the threshold

 thr(τ) \rm\tiny def=γ−τϵ−τ∑i=12ρλτγ−i. (2)
##### Setting ρ

As can be observed, this threshold function should always return positive values, which requires a small enough . For a given problem, the maximum possible value shall depend on the Lipschitz constants at each time step, which themselves depend on the upper and lower bounds of the optimal value function (and thus may evolve during the planning process). For the sake of simplicity, let us consider a single Lipschitz constant common to all time steps, which always exists.

[Proof in App. A.6]lemmalemMaxRadius (originally stated on page 6.1) Assuming a single depth-independent Lipschitz constant , and noting that

 thr(τ) =γ−τϵ−2ρλγ−τ−11−γ, (3)

one can ensure positivity of the threshold at any by enforcing

We shall thus pick in . But what is the effect of setting to small or large values?

• The smaller , the larger , the shorter the trajectories, but the smaller the balls and the higher the required density of points around the optimal trajectory, thus the more trajectories needed to converge.

• The larger , the smaller , the longer the trajectories, but the larger the balls and the lower the required density of points around the optimal trajectory, thus the less trajectories needed to converge.

So, setting means making a compromise between the number of generated trajectories and their length.

### 6.2 Finite-Time Convergence

First, the following result bounds the length of HSVI’s trajectories using the bounded width of and the exponential growth of .

[Proof in App. A.6]lemmalemFiniteTrials (originally stated on page 6.2) Assuming a depth-independent Lipschitz constant , and with , the length of trajectories is upper-bounded by

 Tmax \rm\tiny def=⎡⎢ ⎢ ⎢ ⎢⎢logγϵ−2ρλ1−γW−2ρλ1−γ⎤⎥ ⎥ ⎥ ⎥⎥.

Note that (i) the classical upper-bound is retrieved when (Eq. (6.7) in [28]), and (ii) this gives us the maximum horizon needed to solve the problem. Now, knowing that any trial terminates in bounded time allows deriving the following results, in order.

[Proof in App. A.6]theoremlemThr (originally stated on page 6.2) Consider a trial of length and consider that the backward updates of and have not yet been performed. Then

1. , and

2. for every satisfying , it holds:

###### Theorem 2.

Algorithm 1 terminates with an -approximation of .

###### Proof.

(Adapted from [14]) Assume for the sake of contradiction that the algorithm does not terminate and generates an infinite number of explore trials. Since the length of a trial is bounded by a finite number , the number of trials of length (for some ) must be infinite. It is impossible to fit an infinite number of occupancy points satisfying within . Hence there must be two trials of length , and , such that . Without loss of generality, assume that was visited the first. According to Lemma 6.2, the point-based update in resulted in —which contradicts that the condition on line 1 of Algorithm 1 has not been satisfied for (and hence that was a trial of length ). ∎

Note that the number of trials could be (tediously) upper-bounded by determining how many balls of radius are required to cover occupancy simplexes at each depth.

## 7 Discussion

Inspired by techniques solving POMDPs as belief MDPs or Dec-POMDPs as occupancy MDPs, we have demonstrated that zs-POSGs could be turned into a new type of sequential game, namely zs-OMGs, allowing to apply Bellman’s optimality principle. Value function approximators (with heuristic initializations) can be used thanks to the Lipschitz continuity of , and despite possibly not being concave or convex in any relevant statistic. A variant of HSVI has been derived which provably converges in finite time to an -optimal solution.

This approach was motivated by the fact that the corresponding techniques for POMDPs and Dec-POMDPs provide state-of-the-art solvers. The time complexity of the algorithm shall depend, among other things, on that of the maximin/minimax optimization technique in use, and on how many trials are required before convergence. We also currently lack empirical comparisons of the resulting algorithm with existing zs-POSG solution techniques.

Several implementation details could be further discussed as the maximin/minimax error-bounded optimization algorithm, the need to regularly prune dominated cones in and , and the possible use of compression techniques to reduce the dimensionality of the occupancy subspaces, as in FB-HSVI [9].

Regarding execution, as in single-agent or collaborative multi-agent settings, while exploration is guided by optimistic decisions (greediness w.r.t. for and for ), actual decisions should be pessimistic, i.e., should act “greedily” w.r.t. , and w.r.t. .

Handling finite-horizon settings requires little changes. The maximum length of trials shall be the minimum between this horizon and the bound that depends on and . Additionally considering shall require revising the Lipschitz constants and some other formulas.

As often with Dec-POMDPs [30, 9], each player’s strategy is here history-dependent, because one could not come up with private belief states, which is feasible under certain assumptions [15, 14]. One could possibly address this issue as MacDermed and Isbell [20] did by assuming that a bounded number of beliefs is sufficient to solve the problem.

Public actions and observations, as in Poker, could be exploited by turning the non-observable sequential decision problem faced by the central planner into a partially observable one, and thus the deterministic OMG into a probabilistic one.

## References

• [1] N. Basilico, G. De Nittis, and N. Gatti. A security game combining patrolling and alarm–triggered responses under spatial and detection uncertainties. In

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence

, 2016.
• [2] A. Basu and L. Stettner. Finite- and infinite-horizon Shapley games with nonsymmetric partial observation. SIAM Journal on Control and Optimization, 53(6):3584–3619, 2015.
• [3] R. Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Science, 38:716–719, 1952.
• [4] D. Bernstein, R. Givan, N. Immerman, and S. Zilberstein. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research, 27(4):819–840, 2002.
• [5] N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018.
• [6] O. Buffet, J. Dibangoye, A. Saffidine, and V. Thomas. Heuristic search value iteration for zero-sum stochastic games. IEEE Transactions on Games, 2020.
• [7] K. Chatterjee and L. Doyen. Partial-observation stochastic games: How to win when belief fails. volume 15, page 16, 2014.
• [8] H. L. Cole and N. Kocherlakota. Dynamic games with hidden actions and hidden states. Journal of Economic Theory, 98(1):114–126, 2001.
• [9] J. Dibangoye, C. Amato, O. Buffet, and F. Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research, 55:443–497, 2016.
• [10] M. Fehr, O. Buffet, V. Thomas, and J. Dibangoye. -POMDPs have Lipschitz-continuous -optimal value functions. In Advances in Neural Information Processing Systems 31, pages 6933–6943, 2018.
• [11] D. Fudenberg and J. Tirole. The MIT Press, 1991.
• [12] M. K. Ghosh, D. McDonald, and S. Sinha. Zero-sum stochastic games with partial information. Journal of Optimization Theory and Applications, 121(1):99–118, Apr. 2004.
• [13] E. A. Hansen, D. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004.
• [14] K. Horák and B. Bošanský. Solving partially observable stochastic games with public observations. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, pages 2029–2036, 2019.
• [15] K. Horák, B. Bošanský, and M. Pěchouček. Heuristic search value iteration for one-sided partially observable stochastic games. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 558–564, 2017.
• [16] D. Koller and N. Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528–552, 1992.
• [17] D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(51):220–246, 1996.
• [18] H. W. Kuhn. Simplified two-person Poker. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 1. Princeton University Press, 1950.
• [19] H. W. Kuhn. Extensive Games and the Problem of Information, volume Contributions to the Theory of Games II of Annals of Mathematics (AM-28), pages 193–216. Princeton University Press, 1953.
• [20] L. C. MacDermed and C. Isbell. Point based value iteration with optimal belief compression for Dec-POMDPs. In Advances in Neural Information Processing Systems 26, 2013.
• [21] E. Machuca. An analysis of multiobjective search algorithms and heuristics. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
• [22] O. Madani, S. Hanks, and A. Condon. On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 1999.
• [23] R. Munos. From bandits to Monte-Carlo Tree Search: The optimistic principle applied to optimization and planning.

Foundations and Trends in Machine Learning

, 7(1):1–130, 2014.
• [24] F. Oliehoek and N. Vlassis. Dec-POMDPs and extensive form games: equivalence of models and algorithms. Technical Report IAS-UVA-06-02, Intelligent Systems Laboratory Amsterdam, University of Amsterdam, 2006.
• [25] K. Åström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174 – 205, 1965.
• [26] L. S. Shapley. Stochastic games. Proceedings of the National Academy of Science, 39(10):1095–1100, 1953.
• [27] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.
• [28] T. Smith. Probabilistic Planning for Robotic Exploration. PhD thesis, The Robotics Institute, Carnegie Mellon University, 2007.
• [29] B. S. Stewart and C. C. White, III. Multiobjective A*. Journal of the ACM, 38(4):775–814, Oct. 1991.
• [30] D. Szer, F. Charpillet, and S. Zilberstein. MAA*: A heuristic search algorithm for solving decentralized POMDPs. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 576–583, 2005.
• [31] B. von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(50):220–246, 1996.
• [32] A. Wiggers, F. Oliehoek, and D. Roijers. Structure in the value function of two-player zero-sum games of incomplete information. In Proceedings of the Twenty-second European Conference on Artificial Intelligence, pages 1628–1629, 2016.
• [33] A. Wiggers, F. Oliehoek, and D. Roijers. Structure in the value function of two-player zero-sum games of incomplete information. Computing Research Repository, abs/1606.06888, 2016.
• [34] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems 20, 2007.

## Appendix A Appendix

This appendix mainly provides proofs of several theoretical claims of the paper.

### a.1 From zs-POSGs to zs-OMGs

The following result shows that the occupancy state is Markovian, i.e., its value at only depends on its previous value (), the system dynamics (), and the last behavioral decision rules ( and ).

###### Lemma 1.

Given an occupancy state and a behavioral decision rule profile , next occupancy state is given by the following formula (for any , , , , , , ):

 oτ(s′,(θ1τ−1,a1,z1),(θ2τ−1,a2,z2)) =β1τ−1(θ1τ−1,a1)⋅β2τ−1(θ2τ−1,a2)∑sPz1,z2a1,a2(s′|s)⋅oτ−1(s,θ1τ−1,θ2τ−1).
###### Proof.

The proof goes by simply developing the definition:

 oτ(s′,(θ1τ−1,a1,z1),(θ2τ−1,a2,z2)) \rm\tiny def=Pr(s′,(θ1τ−1,a1,z1),(θ2τ−1,a2,z2)) =∑sPr(s,s′,(θ1τ−1,a1,z1),(θ2τ−1,a2,z2)) =∑sPr(s′,z1,z2|s,θ1τ−1,a1,θ2τ−1,a2)⋅Pr(s,θ1τ−1,a1,θ2τ−1,a2) =∑sPz1,z2a1,a2(s′|s)⋅Pr(a1,a2|s,θ1τ−1,θ2τ−1)⋅Pr(s,θ1τ−1,θ2τ−1) =∑sPz1,z2a1,a2(s′|s)⋅Pr(a1|s,θ1τ−1,θ2τ−1)⋅Pr(a2|s,θ1τ−1,θ2τ−1)⋅Pr(s,θ1τ−1,θ2τ−1) =∑sPz1,z2a1,a2(s′|s)⋅β1τ−1(θ1τ−1,a1)⋅β2τ−1(θ2τ−1,a2)⋅oτ−1(s,θ1τ−1,θ2τ−1) =β1τ−1(θ1τ−1,a1)⋅β2


text:
Math Help - Function help..

1. Function help..

Need some help here..

Consider the function f(x) = x / x+ 2

a) show that f'(x) > 0 for all x in the domain

b) State the equation of the horizontal asymptote of y = f(x)

Thanks

2. Re: Function help..

Originally Posted by Deci
Need some help here..

Consider the function f(x) = x / x+ 2
You mean f(x)= x/(x+ 2), right? What you wrote is f(x)= 1+ 2= 3!

a) show that f'(x) > 0 for all x in the domain
What is the derivative? Do you know the "quotient rule"?

b) State the equation of the horizontal asymptote of y = f(x)
Dividing both numerator and denominator of $f(x)= \frac{x}{x+ 1}$ gives
$\frac{1}{1+ \frac{1}{x}}$
What happens as x "goes to infinity"?

Thanks

4. Re: Function help..

Thanks.. i solved a .. 1 by infinity is 0. So y=1 is the asymptote. Is it?


text:
# LaTeX Symbols in Verbatim Mode (using UTF8)

When: Wednesday, 17 March 2010

LaTeX is a great tool for putting together documents. However, sometimes it can be a little bit tricky to get exactly what you want.

Recently, I wanted to use the verbatim mode for the output of a program run on the command line. However, this included UTF8 symbols. These symbols didn't show up in the verbatim mode, and using the equivalent symbol \O didn't work either. I found a way around this, by using the utf8 package:

The resulting document is exactly what we expect — the correct symbols are substituted in verbatim mode.

The main trick is \DeclareUnicodeCharacter which takes a Unicode character code-point, in this case the code point for ∅ is 2205, and defines it to be one of the standard LaTeX symbols. You can do this for whatever symbols you require.

# Comments

## Leave a comment

Please note, comments must be formatted using Markdown. Links can be enclosed in angle brackets, e.g. <www.codeotaku.com>.


text: - Epigraphical cones II Alberto Seeger(alberto.seegeruniv-avignon.fr) Abstract: This is the second part of a work devoted to the theory of epigraphical cones and their applications. A convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is an epigraphical cone if it can be represented as epigraph of a nonnegative sublinear function $f: \mathbb{R}^n\to \mathbb{R}$. We explore the link between the geometric properties of $K$ and the analytic properties of $f$. Keywords: Convex cone, epigraphical cone, sublinear function, smoothness, rotundity, Vinberg characteristic function, conic programming Category 1: Linear, Cone and Semidefinite Programming Citation: JOURNAL OF CONVEX ANALYSIS, 2011, in press. Download: [PDF]Entry Submitted: 01/21/2011Entry Accepted: 01/21/2011Entry Last Modified: 01/21/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.


text:
# E Mapping rates in R

 R spdep classInt RColorBrewer rgdal 4.1.1 1.1.8 0.4.3 1.1.2 1.5.23

In this exercise, we’ll make use of sp’s plot method instead of tmap to take advantage of sp’s scaled keys which will prove insightful when exploring rate mapping techniques that adopt none uniform classification schemes.

The following libraries are used in the examples that follow.

library(spdep)
library(classInt)
library(RColorBrewer)
library(rgdal)

Next, we’ll initialize some color palettes.

pal1 <- brewer.pal(6,"Greys")
pal2 <- brewer.pal(8,"RdYlGn")
pal3 <- c(brewer.pal(9,"Greys"), "#FF0000")

The Auckland dataset from the spdep package will be used throughout this exercise. Some of the graphics that follow are R reproductions of Bailey and Gatrell’s book, Interactive Spatial Data Analysis .

auckland <- readOGR(system.file("shapes/auckland.shp", package="spData")[1])
OGR data source with driver: ESRI Shapefile
Source: "C:\Users\mgimo\Documents\R\win-library\4.1\spData\shapes\auckland.shp", layer: "auckland"
with 167 features
It has 4 fields

The Auckland data represents total infant deaths (under the age of five) for Auckland, New Zealand, spanning the years 1977 through 1985 for different census area units. The following block of code maps these counts by area. Both equal interval and quantile classification schemes of the same data are mapped.

brks1 <- classIntervals(auckland$M77_85, n = 6, style = "equal") brks2 <- classIntervals(auckland$M77_85, n = 6, style = "quantile")
print(spplot(auckland, "M77_85", at = brks1$brks, col.regions = pal1) ,position=c(0,0,.5,1),more=T) print(spplot(auckland, "M77_85", at = brks2$brks, col.regions = pal1)
,position=c(0.5,0,1,1),more=T)

These are examples of choropleth maps (choro = area and pleth = value) where some attribute (an enumeration of child deaths in this working example) is aggregated over a defined area (e.g. census area units) and displayed using two different classification schemes.

Since the area units used to map death counts are not uniform in shape and area across Auckland, there is a tendency to assign more “visual weight” to polygons having larger areas than those having smaller areas. In our example, census units in the southern end of Auckland appear to have an “abnormally” large infant death count. Another perceptual interpretation of the map is one that flags those southern units as being “problematic” or of “great concern.” However, as we shall see in the following sections, this perception may not reflect reality. We therefore seek to produce perceptually tenable maps. Dykes and Unwin define a similar concept called map stability which seeks to produce maps that convey real effects.

## Raw Rates

A popular approach for correcting for biased visual weights (due, for instance, to different unit area sizes) is to normalize the count data by area thus giving a count per unit area. Though this may make sense for population count data, it does not make a whole lot sense when applied to mortality counts; we are usually interested in the number of deaths per population count and not in the number of deaths per unit area.

In the next chunk of code we extract population count under the age of 5 from the Auckland data set and assign this value to the variable pop. Likewise, we extract the under 5 mortality count and assign this value to the variable mor. Bear in mind that the mortality count spans a 9 year period. Since mortality rates are usually presented in rates per year, we need to multiply the population value (which is for the year 1981) by nine. This will be important in the subsequent code when we compute mortality rates.

pop <- auckland$Und5_81 * 9 mor <- auckland$M77_85

Next, we will compute the raw rates (infant deaths per 1000 individuals per year) and map this rate by census unit area. Both quantile and equal interval classification schemes of the same data are mapped.

auckland$raw.rate <- mor / pop * 1000 brks1 <- classIntervals(auckland$raw.rate, n = 6, style = "equal")
brks2 <- classIntervals(auckland$raw.rate, n = 6, style = "quantile") print(spplot(auckland, "raw.rate", at = brks1$brks, col.regions = pal1)
,position=c(0,0,.5,1),more=T)
print(spplot(auckland, "raw.rate", at = brks2$brks, col.regions = pal1) ,position=c(0.5,0,1,1),more=T) Note how our perception of the distribution of infant deaths changes when looking at mapped raw rates vs. counts. A north-south trend in perceived “abnormal” infant deaths is no longer apparent in this map. ## Standardized mortality ratios (relative risk). Another way to re-express the data is to map the Standardized Mortality Ratios (SMR)-a very popular form of representation in the field of epidemiology. Such maps map the ratios of the number of deaths to an expected death count. There are many ways to define an expected death count, many of which can be externally specified. In the following example, the expected death count $$E_i$$ is estimated by multiplying the under 5 population count for each area by the overall death rate for Auckland: $E_i = {n_i}\times{mortality_{Auckland} }$ where $$n_i$$ is the population count within census unit area $$i$$ and $$mortality_{Auckland}$$ is the overall death rate computed from $$mortality_{Auckland} = \sum_{i=1}^j O_i / \sum_{i=1}^j n_i$$ where $$O_i$$ is the observed death count for census unit $$i$$. This chunk of code replicates Bailey and Gatrell’s figure 8.1 with the one exception that the color scheme is reversed (Bailey and Gatrell assign lighter hues to higher numbers). auck.rate <- sum(mor) / sum(pop) mor.exp <- pop * auck.rate # Expected count over a nine year period auckland$rel.rate <- 100 * mor / mor.exp
brks <- classIntervals(auckland$rel.rate, n = 6, style = "fixed", fixedBreaks = c(0,47, 83, 118, 154, 190, 704)) spplot(auckland, "rel.rate", at = brks$brks,col.regions=pal1)

## Dykes and Unwin’s chi-square statistic

Dykes and Unwin propose a similar technique whereby the rates are standardized following:

$\frac{O_i - E_i}{\sqrt{E_i}}$

This has the effect of creating a distribution of values closer to normal (as opposed to a Poisson distribution of rates and counts encountered thus far). We can therefore apply a diverging color scheme where green hues represent less than expected rates and red hues represent greater than expected rates.

auckland$chi.squ = (mor - mor.exp) / sqrt(mor.exp) brks <- classIntervals(auckland$chi.squ, n = 6, style = "fixed",
fixedBreaks = c(-5,-3, -1, -2, 0, 1, 2, 3, 5))
spplot(auckland, "chi.squ", at = brks$brks,col.regions=rev(pal2)) ## Unstable ratios One problem with the various techniques used thus far is their sensitivity (hence instability) to small underlying population counts (i.e. unstable ratios). This next chunk of code maps the under 5 population count by census area unit. brks <- classIntervals(auckland$Und5_81, n = 6, style = "equal")
spplot(auckland, "Und5_81", at = brks$brks,col.regions=pal1) Note the variability in population count with some areas encompassing fewer than 50 infants. If there is just one death in that census unit, the death rate would be reported as $$1/50 * 1000$$ or 20 per thousand infants–far more than then the 2.63 per thousand rate for our Auckland data set. Interestingly, the three highest raw rates in Auckland (14.2450142, 18.5185185, 10.5820106 deaths per 1000) are associated with some of the smallest underlying population counts (39, 6, 21 infants under 5). One approach to circumventing this issue is to generate a probability map of the data. The next section highlights such an example. ### Global Empirical Bayes (EB) rate estimate The idea behind Bayesian approach is to compare the value in some area $$i$$ to some a priori estimate of the value and to “stabilize” the values due to unstable ratios (e.g. where area populations are small). The a priori estimate can be based on some global mean. An example of the use on a global EB infant mortality rate map is shown below. The EB map is shown side-by-side with the raw rates map for comparison. aka Global moment estimator of infant mortality per 1000 per year EB.est <- EBest(auckland$M77_85, auckland$Und5_81 * 9 ) auckland$EBest <- EB.est$estmm * 1000 brks1 <- classIntervals(auckland$EBest, n = 10, style = "quantile")
brks2          <- classIntervals(auckland$raw.rate, n = 10, style = "quantile") print(spplot(auckland, "EBest", at = brks1$brks, col.regions = pal3,
main="EB rates") ,position=c(0,0,.5,1),more=T)
print(spplot(auckland, "raw.rate", at = brks2$brks, col.regions = pal3, main="Raw Rates") ,position=c(0.5,0,1,1),more=T) The census units with the top 10% rates are highlighted in red. Unstable rates (i.e. those associated with smaller population counts) are assigned lower weights to reduce their “prominence” in the mapped data. Notice how the three high raw rates highlighted in the last section are reduced from 14.2450142, 18.5185185, 10.5820106 counts per thousand to 3.6610133, 2.8672132, 3.0283279 counts per thousand. The “remapping” of these values along with others can be shown on the following plot: ### Local Empirical Bayes (EB) rate estimate The a priori mean and variance need not be aspatial (i.e. the prior distribution being the same for the entire Auckland study area). The adjusted estimated rates can be shrunk towards a local mean instead. Such technique is referred to as local empirical Bayes rate estimates. In the following example, we define local as consisting of all first order adjacent census unit areas. nb <- poly2nb(auckland) EBL.est <- EBlocal(auckland$M77_85, 9*auckland$Und5_81, nb) auckland$EBLest <- EBL.est$est * 1000 brks1 <- classIntervals(auckland$EBLest, n = 10, style = "quantile")
brks2           <- classIntervals(auckland$raw.rate, n = 10, style = "quantile") print(spplot(auckland, "EBLest", at = brks1$brks, col.regions = pal3,
main="Local EB rates") ,position=c(0,0,.5,1),more=T)
print(spplot(auckland, "raw.rate", at = brks2\$brks, col.regions = pal3,
main="Raw Rates") ,position=c(0.5,0,1,1),more=T)

The census units with the top 10% rates are highlighted in red.

### References

Bailey, Trevor C., and Anthony C. Gatrell. 1995. Interactive Spatial Data Analysis. England: Prentice Hall.
Dykes, J. A., and D. J. Unwin. 2001. Maps of the Census: A Rough Guide.” In Case Studies of Visualization in the Social Sciences: Technical Report 43 (43): 29–54. http://www.agocg.ac.uk/reports/visual/casestud/dykes/dykes.pdf.


text:
# Alternative A/C adapter for HP Photosmart camera

D

#### David Turrell

Jan 1, 1970
0
I recently purchased an HP Photosmart 435 digital camera. I'm
looking for an A/C adapter that is less expensive than that made
by HP, which costs ~$50 (the camera itself was only ~$100, and I'm
not necessarily going to get another HP camera).

The power requirements for the camera, via A/C adapter, are listed
as 3.3 to 3.7V and 2500mA. I haven't been able to find a generic

The closest that Radio Shack seems to have, of their standard,
the advantage of a wide array of tips, the smallest of which (female,
0.7mm interior diameter) would seem to fit the HP camera.

While 3V seems too low, I wonder how the camera is able to make do
with two 1.5V batteries as a power supply!

on the one I have for a radio, have 3, 4.5, 6, etc. volts, which
seems not close enough; and it probably wouldn't give the correct
amperage.

Digi-Key's catalog has a wider range of voltage and amperage choices,
but only matching the voltage, not the amperage. Also, I don't
see a standard tip for them that is small enough for the camera.
A custom-made tip, which they offer, would possibly bring the cost
to where I might as well buy HP's version.

There's always the possibility of a jury-rigged device, but I'm
trying to avoid something that messy.

What substitutions are possible under the circumstances?

B

#### Bob Salomon

Jan 1, 1970
0
I recently purchased an HP Photosmart 435 digital camera. I'm
looking for an A/C adapter that is less expensive than that made
by HP, which costs ~$50 (the camera itself was only ~$100, and I'm
not necessarily going to get another HP camera).

The power requirements for the camera, via A/C adapter, are listed
as 3.3 to 3.7V and 2500mA. I haven't been able to find a generic

The closest that Radio Shack seems to have, of their standard,
the advantage of a wide array of tips, the smallest of which (female,
0.7mm interior diameter) would seem to fit the HP camera.

While 3V seems too low, I wonder how the camera is able to make do
with two 1.5V batteries as a power supply!

on the one I have for a radio, have 3, 4.5, 6, etc. volts, which
seems not close enough; and it probably wouldn't give the correct
amperage.

Digi-Key's catalog has a wider range of voltage and amperage choices,
but only matching the voltage, not the amperage. Also, I don't
see a standard tip for them that is small enough for the camera.
A custom-made tip, which they offer, would possibly bring the cost
to where I might as well buy HP's version.

There's always the possibility of a jury-rigged device, but I'm
trying to avoid something that messy.

What substitutions are possible under the circumstances?

See:

http://www.ansmann.de/en/index.htm?view=list&pr2id=13

K

#### Ken Weitzel

Jan 1, 1970
0
Hi...

Respectfully, no it sure won't...

The original puts out 2.5 amps; whereas the rs version
delivers only half an amp. That's a world of difference.

Ken

M

#### Michael A. Covington

Jan 1, 1970
0
David Turrell said:
I recently purchased an HP Photosmart 435 digital camera. I'm
looking for an A/C adapter that is less expensive than that made
by HP, which costs ~$50 (the camera itself was only ~$100, and I'm
not necessarily going to get another HP camera).

The power requirements for the camera, via A/C adapter, are listed
as 3.3 to 3.7V and 2500mA. I haven't been able to find a generic

I'm guessing the reason the voltage is higher than the battery voltage is
that there's a protective diode or something. But 3 volts may well work.

2500 mA is a *lot* of current!!!! Does this camera really draw 2500 mA?
If so, it must run down its batteries almost instantaneously.

Does this camera have a flash built in? If so, I'll bet the heavy current
drain is only for charging the flash, and that without flash, you could get
by with a considerably lower-current power supply.

W

#### Watson A.Name - \Watt Sun, the Dark Remover\

Jan 1, 1970
0
David Turrell said:
I recently purchased an HP Photosmart 435 digital camera. I'm
looking for an A/C adapter that is less expensive than that made
by HP, which costs ~$50 (the camera itself was only ~$100, and I'm
not necessarily going to get another HP camera).

The power requirements for the camera, via A/C adapter, are listed
as 3.3 to 3.7V and 2500mA. I haven't been able to find a generic

The closest that Radio Shack seems to have, of their standard,
the advantage of a wide array of tips, the smallest of which (female,
0.7mm interior diameter) would seem to fit the HP camera.

While 3V seems too low, I wonder how the camera is able to make do
with two 1.5V batteries as a power supply!

Thinking about it, the 0.7V diff might be the drop across a rectifier
diode, so maybe all the camera needs is 3VDC.
on the one I have for a radio, have 3, 4.5, 6, etc. volts, which
seems not close enough; and it probably wouldn't give the correct
amperage.
Digi-Key's catalog has a wider range of voltage and amperage choices,
but only matching the voltage, not the amperage. Also, I don't
see a standard tip for them that is small enough for the camera.
A custom-made tip, which they offer, would possibly bring the cost
to where I might as well buy HP's version.

There's always the possibility of a jury-rigged device, but I'm
trying to avoid something that messy.

What substitutions are possible under the circumstances?

You might try using a 3A rectifier diode to drop the 4.5V down to 3.8 or
so volts.

J

#### Jamie

Jan 1, 1970
0
the 3 volt level should be ok since its most likely is putting out more

R

#### Rich Grise

Jan 1, 1970
0
the 3 volt level should be ok since its most likely is putting out more
Yabbut, not a 500 mA wart, when the device needs 2500.

Cheers!
Rich

W

#### Watson A.Name - \Watt Sun, the Dark Remover\

Jan 1, 1970
0
Michael A. Covington said:
I'm guessing the reason the voltage is higher than the battery voltage is
that there's a protective diode or something. But 3 volts may well work.

2500 mA is a *lot* of current!!!! Does this camera really draw 2500
mA?

And a few hundred uF at 330VDC is a lotta capacitor to charge up in a
few seconds. And that takes a lotta current, maybe not forever, but for
quite a few seconds.
If so, it must run down its batteries almost instantaneously.

No, they're 2000 mAh which means they should last for the better part of
an hour. But a camera isn't on very long.
Does this camera have a flash built in? If so, I'll bet the heavy current
drain is only for charging the flash, and that without flash, you could get
by with a considerably lower-current power supply.

The LCD and backlight demand a lot of current, too. A lot.

G

#### Graham W

Jan 1, 1970
0
Watson said:
And a few hundred uF at 330VDC is a lotta capacitor to charge up in a
few seconds. And that takes a lotta current, maybe not forever, but
for quite a few seconds.

No, they're 2000 mAh which means they should last for the better part
of an hour. But a camera isn't on very long.

The LCD and backlight demand a lot of current, too. A lot.

Another factor not yet mentioned is that the supply *may* be able
to recharge the cells while supplying power for taking more photos.

A

#### Al Bundy

Jan 1, 1970
0
[email protected] (David Turrell) wrote in message news: said:
I recently purchased an HP Photosmart 435 digital camera. I'm
looking for an A/C adapter that is less expensive than that made
by HP, which costs ~$50 (the camera itself was only ~$100, and I'm
not necessarily going to get another HP camera).

The power requirements for the camera, via A/C adapter, are listed
as 3.3 to 3.7V and 2500mA. I haven't been able to find a generic

The closest that Radio Shack seems to have, of their standard,
the advantage of a wide array of tips, the smallest of which (female,
0.7mm interior diameter) would seem to fit the HP camera.

While 3V seems too low, I wonder how the camera is able to make do
with two 1.5V batteries as a power supply!

on the one I have for a radio, have 3, 4.5, 6, etc. volts, which
seems not close enough; and it probably wouldn't give the correct
amperage.

Digi-Key's catalog has a wider range of voltage and amperage choices,
but only matching the voltage, not the amperage. Also, I don't
see a standard tip for them that is small enough for the camera.
A custom-made tip, which they offer, would possibly bring the cost
to where I might as well buy HP's version.

There's always the possibility of a jury-rigged device, but I'm
trying to avoid something that messy.

What substitutions are possible under the circumstances?

I've been fooling with my 435 power supply because the battery grain
is so high on these. The NiMH cells only have 1.2V nominal and fully
charged they run the camera fairly well, but within a couple days they
are in the low battery mode. So I searched for a jack to use on the
AC/3.3V input and found one at an electronics store for $1.99. It's the same size as slot car power supply jacks and Radio Shack sells them for$4.95. I am sure you can use a 3.6V cell phone charger on
that jack with no harm. At least it worked for me. However, the
charger will try to charge any batteries in the camera. I did not want
that happening. What I was really after is to put a DC source into
that jack so I could furnish more total power to the device. So that
idea flunked my testing.

What I ended up doing was working from the battery compartment. I took
an old AA cell and cut it in half. I cleaned out the inside. Then I
ran a wire to the plus and minus ends. I replaced the missing half of
each cell with a wood dowel with a hole drilled in the center. In
essence I made these fake batteries to put into the battery
compartment and run a cable out the door, with a slot cut in the door.
I took a 3.6V cell phone battery (removed from the case) and cabled it
to that compartment. Fully charged the battery puts out 4.2V. I
estimate the dam thing will take 200 pictures on a charge, but I
recharge at 3.7V. I took the chance of over powering the camera
because I was fed up and got to the point that I considered it
expendable. I was stupid lucky this time. I have the power supply
problems absolutely solved. I've taken 600 pictures with no problem
from a power standpoint. I often get dark pictures and always have,
but that's an unrelated issue. The white balance and E/V adjustments
don't fix that consistently.

That's what I did anyway.

Replies
3
Views
336
Replies
7
Views
1K
Replies
2
Views
735
Replies
11
Views
1K
Replies
3
Views
834


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

 SIGMA: Year: Volume: Issue: Page: Find

 SIGMA, 2012, Volume 8, 098, 73 pages (Mi sigma775)

Loop Quantum Gravity Phenomenology: Linking Loops to Observational Physics

Florian Girelliab, Franz Hinterleitnerc, Seth A. Majord

a University Erlangen-Nuremberg, Institute for Theoretical Physics III, Erlangen, Germany
b Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario, Canada
c Department of Theoretical Physics and Astrophysics, Faculty of Science of the Masaryk University, Kotlářská 2, 61137 Brno, Czech Republic
d Department of Physics, Hamilton College, Clinton NY 13323, USA

Abstract: Research during the last decade demonstrates that effects originating on the Planck scale are currently being tested in multiple observational contexts. In this review we discuss quantum gravity phenomenological models and their possible links to loop quantum gravity. Particle frameworks, including kinematic models, broken and deformed Poincaré symmetry, non-commutative geometry, relative locality and generalized uncertainty principle, and field theory frameworks, including Lorentz violating operators in effective field theory and non-commutative field theory, are discussed. The arguments relating loop quantum gravity to models with modified dispersion relations are reviewed, as well as, arguments supporting the preservation of local Lorentz invariance. The phenomenology related to loop quantum cosmology is briefly reviewed, with a focus on possible effects that might be tested in the near future. As the discussion makes clear, there remains much interesting work to do in establishing the connection between the fundamental theory of loop quantum gravity and these specific phenomenological models, in determining observational consequences of the characteristic aspects of loop quantum gravity, and in further refining current observations. Open problems related to these developments are highlighted.

Keywords: quantum gravity; loop quantum gravity; quantum gravity phenomenology; modified dispersion relation

DOI: https://doi.org/10.3842/SIGMA.2012.098

Full text: PDF file (1291 kB)
Full text: http://emis.mi.ras.ru/.../098
References: PDF file   HTML file

Bibliographic databases:

ArXiv: 1210.1485
MSC: 83-02; 83B05; 83C45; 83C47; 83C65
Received: May 30, 2012; in final form December 3, 2012; Published online December 13, 2012
Language:

Citation: Florian Girelli, Franz Hinterleitner, Seth A. Major, “Loop Quantum Gravity Phenomenology: Linking Loops to Observational Physics”, SIGMA, 8 (2012), 098, 73 pp.

Citation in format AMSBIB
\Bibitem{GirHinMaj12} \by Florian~Girelli, Franz~Hinterleitner, Seth~A.~Major \paper Loop Quantum Gravity Phenomenology: Linking Loops to Observational Physics \jour SIGMA \yr 2012 \vol 8 \papernumber 098 \totalpages 73 \mathnet{http://mi.mathnet.ru/sigma775} \crossref{https://doi.org/10.3842/SIGMA.2012.098} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3007261} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000312436800001} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84871522571}

• http://mi.mathnet.ru/eng/sigma775
• http://mi.mathnet.ru/eng/sigma/v8/p98

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Xiao K., He X.-K., Zhu J.-Ya., “Note on the Super-Inflation in Loop Quantum Cosmology”, Phys. Lett. B, 727:4-5 (2013), 349–356
2. Dupuis M., Girelli F., “Quantum Hyperbolic Geometry in Loop Quantum Gravity with Cosmological Constant”, Phys. Rev. D, 87:12 (2013), 121502
3. Satunin P., “Width of Photon Decay in a Magnetic Field: Elementary Semiclassical Derivation and Sensitivity to Lorentz Violation”, Phys. Rev. D, 87:10 (2013), 105015
4. Linsefors L., Cailleteau T., Barrau A., Grain J., “Primordial Tensor Power Spectrum in Holonomy Corrected Omega Loop Quantum Cosmology”, Phys. Rev. D, 87:10 (2013), 107503
5. S. A. Major, J. C. Zappala, “Granularity in angle: Observability in scattering experiments”, Springer Proceedings in Physics, 157 (2014), 547–554
6. Barrau A. Bojowald M. Calcagni G. Grain J. Kagan M., “Anomaly-Free Cosmological Perturbations in Effective Canonical Quantum Gravity”, J. Cosmol. Astropart. Phys., 2015, no. 5, 051
7. O. M. Lecian, “Semiclassical length measure from a quantum-gravity wave function”, Technologies, 5:3, SI (2017), 56
8. G. Tomar, “Lorentz invariance violation as an explanation of the muon excess in Auger data”, Phys. Rev. D, 95:9 (2017), 095035
9. G. Rubtsov, P. Satunin, S. Sibiryakov, “Constraints on violation of Lorentz invariance from atmospheric showers initiated by multi-TeV photons”, J. Cosmol. Astropart. Phys., 2017, no. 5, 049
10. P. Satunin, “One-loop correction to the photon velocity in Lorentz-violating qed”, Phys. Rev. D, 97:12 (2018), 125016
11. J. Ben Achour, S. Brahma, “Covariance in self-dual inhomogeneous models of effective quantum geometry: spherical symmetry and gowdy systems”, Phys. Rev. D, 97:12 (2018), 126003
12. Dubey A.K., Sen A.K., Nath S., “The Variation of Photon Speed With Photon Frequency in Quantum Gravity”, Indian J. Phys., 92:10 (2018), 1319–1323
13. Oshita N., Afshordi N., “Probing Microstructure of Black Hole Spacetimes With Gravitational Wave Echoes”, Phys. Rev. D, 99:4 (2019), 044002
14. Nilsson N.A., Czuchry E., “Horava-Lifshitz Cosmology in Light of New Data”, Phys. Dark Universe, 23 (2019), UNSP 100253
15. Astapov K., Kirpichnikov D., Satunin P., “Photon Splitting Constraint on Lorentz Invariance Violation From Crab Nebula Spectrum”, J. Cosmol. Astropart. Phys., 2019, no. 4, 054
•  Number of views: This page: 166 Full text: 33 References: 30


text:
3-manifolds with nilpotent embeddings in $$S^4$$

J. A. Hillman

Abstract

We consider embeddings of 3-manifolds $$M$$ in $$S^4$$ such that the two complementary regions $$X$$ and $$Y$$ each have nilpotent fundamental group. If $$\beta=\beta_1(M)$$ is odd then these groups are abelian and $$\beta\leq3$$. In general, $$\pi_1(X)$$ and $$\pi_1(Y)$$ have 3-generator presentations, and $$\beta\leq6$$. We determine all such nilpotent groups which are torsion-free and have Hirsch length $$\le5$$.

Keywords: embedding, homologically balanced, nilpotent, 3-manifold, restrained, surgery.

: Primary 57N13.

This paper is available as a pdf (280kB) file.

 Tuesday, December 10, 2019


text:
# C-14: Absurd range- how high would the muzzle velocity have to be?

1. Nov 11, 2012

### Galorian

I've been debating various Sci-Fi vs debates for a while now and I've decided to try and figure out how powerful the C-14 Gauss assault rifle from StarCraft needs to be in order to achieve the following feat:

A league is 5.556km, so halfway up a 20 league vortex would be 55.56km from the ground.

The standard issue C-14 Gauss rifle fires 8mm DU spikes with a fairly aerodynamic shape (narrow rounded tip and slightly rounded rear) that is either 5cm or 6.4cm long. It is neosteel tipped so I'd assume that's how it avoids getting vaporized by the friction, neosteel being a super hard future alloy. The projectile mass should be somewhere between 43 and 66 grams.

Assuming earthlike gravity and atmospheric pressure (it is an inhabited planet), ignoring the winds from the vortex and assuming the Marines were firing at a perfect 90 degrees angle, what would be the minimal muzzle velocity of a C-14 spike to reach 55.56km straight up?

Last edited: Nov 11, 2012
2. Nov 11, 2012

### Simon Bridge

3. Nov 12, 2012

### Ibix

I presume Simon means a lower bound. You can do it by equating the kinetic energy at the muzzle with the gravitational potential energy at the target height - (1/2)mv2=mgh. Back of the envelope, that's about 1km/s. Since that's about Mach 3, air resistance is in no way negligible, so the real answer is a lot higher (note that Wikipedia gives a muzzle velocity for the M16 of 948m/s and an effective range of about 800m). Serious aerodynamic knowledge is needed to give an accurate answer to your question.

4. Nov 12, 2012

### Simon Bridge

Um - yes... we have the height, so sans air resistance gives the minimum initial velocity needed to get there grrrr.
Also that would have the shards almost at rest when they hit the fighter - raising a "bright corona" off the shields.
So - y'know, we cannot actually answer the question without knowing how strong the shields are... that would provide the upper bound.
Did the marines expect to have some effect at that range?

5. Nov 12, 2012

### Galorian

The end result is probably going to be ridiculously high anyway so the minimal initial velocity required to reach the target would do.

Problem is, I haven't learned how to solve equations where the variable is dependent on itself yet so I can't solve the problem at hand...

6. Nov 12, 2012

### Simon Bridge

... but... I gave you a bunch of links... which variable depends on itself?

The projectile starts out with speed v, it gets to height h, decelerating all the while at rate g. At h, it's speed is zero.

the v-t graph is, therefore, a triangle - with height v and base T, neither of which we know. The slope of the v-t graph is the acceleration (g) which we know, and the area of the triangle is the height (h) which we know. 2 equations, 2 unknowns.

You do it - builds character.

7. Nov 13, 2012

### Ibix

By the way, isn't the Wraith a single seat fighter/bomber? An F15E is about 20m long. 55,000m away, that has an angular size of about 0.02 degrees. For comparison, the 10-ring on a 10m olympic air rifle range has an angular size of 0.002 degrees. Scoring any hits at all on the Wraith under perfect conditions would be competition-quality shooting. These guys are getting hits in combat in a storm. I know very little about firearms, but I have my doubts about the quality of technical thought that went into this passage.

Also, I know marines are stereotypically dumb, but shooting at a vertically descending target that is right above you? Is that wise?

8. Nov 13, 2012

### Galorian

Another book has marines hold fire until the Zerglings were a km away to make every shot count and when they opened fire the first person perspective of one of them described the targeting system as "eerily effective" as he rapidly switched targets between skittering zerglings.

9. Nov 13, 2012

### Mech_Engineer

I have a weak spot for hypersonic objects flying through the atmosphere (), so I tried adapting a calculation sheet I made several years ago to try and estimate the projectile range of a railgun. According to this StarCraft Wiki reference, the C-14 Gauss rifle fire hypersonic rounds, so that's a good starting point.

Basically I model the projectile as a sphere, and using a basic aerodynamic drag model (F.d = 1/2*rho*v*A*C.d) and equations describing air density as a function of altitude (and gravity as a function of altitude although it is a smaller effect), I numerically solve for the trajectory. I've attached the sheet printout in case anyone is curious what it looks like. Note: I'm not sure the drag equation I used is valid for hypersonic speeds, oh well.

From what I can tell from the sheet (unless there's a glaring error), a launch speed of around mach 3 (~33 kJ muzzle energy, about 65% more than a .50 BMG) would get you to a maximum altitude of about 50km, but that leaves no kinetic energy left over to do any damage. A launch speed of mach 4 (~60kJ muzzle energy, 3x that of a .50 BMG) gives a kinetic energy of around 25 kJ (about 25% higher than a .50 BMG's initial muzzle energy) at 50 KM altitude, which I would say is a pretty good hit but maybe not enough to damage heavy armor.

Basically, the kind of muzzle energy you're looking at really doesn't seem like a shoulder-fired weapon to me, maybe a vehicle-mounted weapon?

#### Attached Files:

• ###### Mathcad - DU Hypersonic Round Shot Straight Up.pdf
File size:
157.9 KB
Views:
123
Last edited: Nov 13, 2012
10. Nov 13, 2012

### chasrob

I don't understand. You're saying an M16 shooting straight up (muzzle velocity about Mach 3) will go 30 miles up before falling back?

11. Nov 14, 2012

### Galorian

It is meant to be fired by men in powered armor and there's probably inertial dampening involved (the C-14 rather blatantly delivers more impulse to the target than recoil to the shooter- there are cases where one marine "held down" another by shooting at him full auto, causing the impact force of the spikes to prevent him from moving despite the spikes' failure to penetrate the armor).

12. Nov 14, 2012

### Mech_Engineer

I agree it sounds crazy. I'm going to try comparing the calculations (in a horizontal configuration) to ballistic data for a couple of rounds and see if I can come up with some correlation. I kind of get the feeling the drag force isn't high enough in the calculation, artificially inflating the range estimates.

13. Nov 14, 2012

### AlephZero

The drag formula should be v squared, not v.

I haven't checked the arithmetic, but you have the same wrong formula on page 3 of your PDF attachment.

14. Nov 14, 2012

### Mech_Engineer

There you go, that could be the difference!

Edit- Well, I tried updating the equation in the calculation sheet, but now the ODE solver isn't converging to a solution. I'll have to troubleshoot the problem later on and see what I can do, I'm guessing I might need to tweak the initial conditions of the solve.

Last edited: Nov 14, 2012
15. Nov 14, 2012

### AlephZero

Be careful with the signs. v squared is always positive, whether the bullet is moving up or down!

In one dimension using v * abs(v) should give you the right sign for the force. In 2D, $v^2 = v_x^2 + v_y^2$ and you have to resolve the force into the x and y components.

16. Nov 14, 2012

### Mech_Engineer

Good call, I'll take a look at it on Friday if I can get to it.


text:
# Proving two Dedekind cuts represent the same number.

Hey guys I have a quiz soon and I really dont know how to prove this question. I tried my best but it is not working. Please help out with anything or hints.

Let $(A'_1, A'_2)$ be a Dedekind cut of ${\mathbb{Q}}$ that represents the same real number as $(A_1, A_2)$. Let $C'_1 = A'_1 + B_1$ and $C'_2 = {\mathbb{Q}} \diagdown C'_1$.

Prove that $(C'_1, C'_2)$ represents the same real number as $(C_1, C_2)$.

By Dedekind cut, it means a pair $(A,B)$ such that:

(i) $A,B\neq\emptyset,$

(ii) $A\cap B=\emptyset,$

(iii) $A\cup B=\Bbb Q,$

(iv) $y\in A$ whenever $y\in\Bbb Q$ and there is some $x\in A$ with $y<x,$ and

(v) $A$ has no greatest element.

-
What is $C_1$ and $C_2$? –  Pedro Tamaroff Feb 26 '13 at 17:50
@Peter: Presumably $C_1=A_1+B_1$ and $C_2=\Bbb Q\setminus C_1$. –  Brian M. Scott Feb 26 '13 at 17:52
Do you know when two Dedekind cuts represent the same real number? You’ve not given us your definition of Dedekind cut $-$ there are different ones in use $-$ but if it’s what I think, this happens only when the cut represents a rational. For example, $0$ is represented by both $\langle(\leftarrow,0),[0,\to)\rangle$ and $\langle(\leftarrow,0],(0,\to)\rangle$. –  Brian M. Scott Feb 26 '13 at 17:54
i will fix the question again –  MathGeek Feb 26 '13 at 17:56
If that’s your definition of a Dedekind cut, $\langle A_1',A_2'\rangle$ and $\langle A_1,A_2\rangle$ represent the same real number if and only if $A_1=A_1'$ and $A_2=A_2'$, i.e., if and only if they’re the same cut. But that’s the definition that Cameron Buie used in his answer to your other question; are you sure that it’s the same as the one that you’re actually using? In particular, does yours include condition (v)? –  Brian M. Scott Feb 26 '13 at 18:31


text:
# Homework Help: Aproximation question

1. Jun 16, 2009

### transgalactic

why the "a" disappears
i cant understand the process of the approximation .

if r1 goes to be equal r2 =r1=r
that "a " should be 0 .

http://i42.tinypic.com/119ndqt.gif

2. Jun 16, 2009

### Cyosis

Yes if r2=r1 then a=0, exactly. But we're making an approximation. If r is way bigger than a then r2 is almost equal to r1, because r2-r1 is a very small part of r2. Therefore you can approximate r1r2 as r^2.

3. Jun 16, 2009

### transgalactic

but why "a" disappears
?

i agree that if r>>a that r1r2=r^2
because the are close to each other
but there a multiplication by 'a'
i cant understand mathematically
why "a" disappears
?

4. Jun 16, 2009

### Cyosis

What is the definition of a dipole moment?

5. Jun 16, 2009

### transgalactic

electric dipole moment is p=qd

where p is the moment created by the charges separated by a distance d. (on each end of the first body). It's an induced dipole moment.

6. Jun 16, 2009

### Cyosis

Yes and what is the electrical dipole moment of this particular configuration?

7. Jun 16, 2009

### transgalactic

"electric field created by two point charges +q and and -q, separated by a (small) distance d.

If you reduce the distance and increase the charge so that qd remains constant, the field stays approximately the same, except for the region close to the charges.

A dipole is the limiting case of this, as d goes to zero and q goes to infinity but qd remains finite."

in my case how qd is a charge of one ball q
d is 'a'
and if there multiplication stays the same
then the field has the value
still it doesnt explain how 'a' dissapears

8. Jun 16, 2009

### Cyosis

You didn't answer my question, you just cited a book. I want you to calculate the electrical dipole moment for the configuration in your problem. Can you do that?

9. Jun 16, 2009

### transgalactic

p=aq

10. Jun 16, 2009

### Cyosis

Almost, but not quite. Can you describe the configuration quantitatively to me using terms such as positive charge = ? ,negative charge =? separation distance =?

11. Jun 16, 2009

### transgalactic

positive charge = +q
negative charge =-q
separation distance =a

12. Jun 16, 2009

### Cyosis

Nope the separation distance is not a, I suggest you take a good look at the picture. After that calculate the correct electrical dipole moment.

13. Jun 16, 2009

### transgalactic

separation distance =2a

14. Jun 16, 2009

### Cyosis

I would appreciate if you would reply to my entire post. Calculate the correct electrical dipole moment now that you have found the correct separation distance.

15. Jun 16, 2009

### transgalactic

p=q2a

16. Jun 16, 2009

### Cyosis

Yes can you see now why the a "disappears"?

17. Jun 16, 2009

### transgalactic

lol its being substituted by dipole moment sign
thanks

18. Jun 16, 2009

### Cyosis

Indeed, I am glad you finally see it!

19. Jun 16, 2009

### transgalactic

i cant understand why they change the drawing in that way.
i know that if we go far far away than our dipole will look like a single charge.
and there will not be any r1 and r2 only r.
so i cant see why they change the drawing in such way
?

20. Jun 16, 2009

### Cyosis

Because the drawing represents a real physical dipole. They then show you how to calculate it when r>>a by using an approximation. Their intend most likely is that you realise the dipole potential is an approximation for a physical dipole. The dipole you're talking about is a mathematical dipole in the limit a->0, they don't exist in reality.

21. Jun 16, 2009

### transgalactic

the distance between r2 an r1 lines
is not what they are calculating it the other side of the triangle (the blue line)
why they take the cosine

http://i39.tinypic.com/90vvc9.jpg

22. Jun 17, 2009

### transgalactic

why they take this side
and not the other
??

23. Jun 17, 2009

### Staff: Mentor

I'm not sure what your question is. The page you scanned shows that
$$V \approx \frac{k_e q}{r_1 r_2}2a cos \theta \approx \frac{k_e p cos \theta}{r^2}$$

All they have done is replace q*2a with p, and $r_1 r_2$ with $r^2$.

Last edited: Jun 17, 2009
24. Jun 17, 2009

### transgalactic

but they say that $$cos \theta =r_2 - r_1$$

i think that the difference from the lines should be sine of this angle
the shortest way between two lines in the perpendicular lines between them
??

25. Jun 17, 2009

### Cyosis

You should really review your trigonometry. r2-r1 is the adjacent side of the angle theta and 2a is the hypotenuse.

$$\cos \theta=\frac{adjacent side}{hypotenuse}=\frac{r_2-r_1}{2a}$$