text:
Modeling the train reservation kata - Part 2

In our last article, we covered the basics of TLA+. This article is about the last rule left to implement: we want ideally 70% of coach occupation. Before implementing the rule, let's refine the implementation of our algorithm.

Refining implementation

So far our specification describes an abstract algorithm. We choose seats randomly in the train which would certainly not be the case of a real world implementation. Let's refine the Reserve action to a more realistic approach.

We need to choose between a lot of alternatives. Let's say that our database imposes us to reserve seats in a numerical order order, A1 first then A2 and so forth. For instance:

To order seats, we need to compare them. We implement an \prec operator to do so:

a \prec b == \/ a[1] < b[1]
\/ a[1] = b[1] /\ a[2] < b[2]

In the formula, a and b are two different seats. Remember they are something like <<"A", 1>> or <<"B", 5>>. The issue is that TLA+ does not implement comparison for strings. We can easily alleviate this issue by replacing coach labels with numbers. So:

Coaches = 1..2

We now have to express the idea of reserving in order. If you were to implement it in a regular language, you'd use something like:

seats.sort(SeatOrdering).take(n);

This javascript expression is descriptive of the how: we first order the list of seats, and then take the n first items. It tells how the n first seats are selected, but now what it means to be the n first seats. For TLA+ we need to change our mindset: what does it mean to reserve the first free seats. First we know that it is a subset of n seats. So we can still write:

SequenceSeatsStrategy(seats, count) ==
/\ Cardinality(seats) = count
/\ SameCoach(seats)
/\ reservations' = reservations \union {seats}

What does it mean to have successive seats reservation in set theory? You could start by stating that every seats in the current reservation needs to be below the new reservation. But this condition does not guarantee to have holes in your reservation. So we can refine this definition by not allowing holes in the reservation: there is no remaining free seat within the reserved seats.

SequenceSeatsStrategy(seats, count) ==
/\ Cardinality(seats) = count
/\ SameCoach(seats)
/\ ~(\E s \in FreeSeats \ seats: \E t \in seats: s \prec t)
/\ reservations' = reservations \union {seats}

The ~ operator is the proposition negation. We read the expression "There is no seat such as...". Why don't we write FreeSeats' using the ' operator instead of FreeSeats \ seats? We just cannot write that. The ' next state operator only works for describing the next state, not querying it.

You verify that the specification is still valid with our previous invariants.

Expressing the last rule

Instead of trying to explain the ideal 70% rule, let's study the ambiguous case for which this rule isn't clear. Let's say two coaches have respectively 5 seats reserved and 6. How should we place a reservation of 3 seats:

We know that our current implementation does not respect these scenarios. Do both respect the third rule "Ideally, all coaches have 70% occupation"? "Ideally" is relative to your experience. The rule is more interesting with more ambiguity, so we allow both cases to occur.

Let's first try to understand the rule in our interpretation: for any reservation, either the coach respects its 70% occupation, or there is no other coach which has enough free seats to handle the reservation. We want the 70% rule to be violated in last resort.

There is a little problem: so far we stated reservations to be a set, an unordered collection. There is no way to get to the "last" reservation since the order of reservations is not maintained. We need to refactor our whole spec to use the ordered collection: sequences.

We already used sequences as tuples, but this time we want to have variable length collection. The easiest change is the Init action:

Init == reservations = <<>>

We then replace the reservation state change with the Append operation of sequences:

reservations' = Append(reservations, seats)

Changing the type of the variable means we need to change the type checking we set at the start:

TypeCheck == \A i \in DOMAIN reservations: reservations[i] \in SUBSET Seats

Sets have a native way of exploring the values with the \in operator. Unfortunately TLA+ does not have the equivalent syntax for sequences. We use instead the DOMAIN keyword that provides all keys of a structure, in the case of sequences, the set of indexes. Be aware that since the return of DOMAIN is a set, it is not ordered and there are no guarantees on the order in which the indexes are iterated over.

Now we run our refactored specification. We check that even though we have changed the state of reservations, from an unordered set to a sequence, there's no violation of our previous invariants. TLA+ is pretty solid. Time to implement the invariant for the last rule. First we need to find the number of seats reserved by coach:

ReservationCountFor(coach) == Cardinality({<<c, _i>> \in ReservedSeats: c = coach})

We have already met this syntax when trying to count the occurence of the same seat in reservations in the SeatsCanBeReservedOnce invariant. As the name suggest, this time we count the number of seat reserved in a given coach.

Next we want to find the coach of a given reservation. We are going to use our friend CHOOSE:

ReservationCoach(reservation) == (CHOOSE seat \in reservation: TRUE)[1]

CHOOSE provides a way of selecting an element of a set respecting a predicate. CHOOSE x \in {1, 2, 3}: x % 2 = 1 returns either 1 or 3, the two odd numbers of the set. Note that TLA+ does not guarantee to be fair in the selection. In our case, the predicate is TRUE, meaning we select any seat in the reservation. We Finally we need to select the latest reservation made:

LatestReservation == reservations[Len(reservations)]

Len yield the same result for sequences as Cardinality for sets. Sequences are 1-indexed. They start at index 1, not index 0 as most programming languages. We have all we need to check the third rule:

LatestReservationShouldNotHaveBeenMadeIfAnotherCoachCanReceiveItWhileKeepingUnder70PercentOccupation ==
\/ reservations = <<>>
\/ ReservationCountFor(ReservationCoach(LatestReservation)) <= 70PercentCoachOccupation
\/ ~(\E other \in Coaches: ReservationCountFor(other) + Cardinality(LatestReservation) <= 70PercentCoachOccupation)

The name of this invariant is over the top. I love it and hate it at the same time. We have three possibilities:

• Or there is no reservation to check
• Or the latest reservation in a coach does not make the coach go over 70%
• Or there is no other coach which could have the reservation and still be under 70%

The first predicate allows the Init state to check the invariant. Other state contains at least a reservation and one of the two other predicate has to be true.

Our current specification violates this final rule, and the first found example shows why.

Final implementation

Now that we finally expressed the three rules and checked that our current algorithm does not respect them, let's choose a better algorithm. There are many options and we advise you to take some time to think about it. Even try implementing it in TLA+! We choose to reserve this way: reservations will be made in the least occupied coach.

LeastOccupiedCoach == CHOOSE c \in Coaches: \A x \in Coaches:
ReservationCountFor(c) <= ReservationCountFor(x)

LeastOccupiedCoachStrategy(seats, count) ==
/\ \A <<c, _i>> \in seats: c = LeastOccupiedCoach
/\ Cardinality(seats) = count
/\ count <= Cardinality(SeatNumbers)
/\ reservations' = Append(reservations, seats)

We already covered all the operators used here. CHOOSE is used to select the least occupied coach, if two coaches are candidate, any of them would do. The rest is familiar.

Conclusion

Implementing the final specification takes me between 1 and 2 hours of work. TLA+ has this incredible power of letting logic drive the algorithm design, and not language features or implementation details. It yields a much clearer mental model of the problem at hand.

You might think that this specification is useless: you could have made it in your head. We did not try to convince you otherwise. These articles are an introduction to TLA+ syntax, and a discovery of the train reservation kata. If you want to challenge TLA+ you could:

• Add the possibility to cancel reservation or part of the reservation
• Have a job replacing single reservation to optimize the 70% occupation of coach
• Keep reservations grouped together (pair in neighboring seats)
• Model a distributed system: reservations and place choice is done by different processes

If you have to think of all the possible scenarios of such systems in your head, you need a lot of time and end up with an headache and no clear call on the correctness of your design. TLA+ and formal methods allow to explore tons of scenarios while learning a lot from your system.


text:
### Zeardoe's blog

By Zeardoe, history, 4 weeks ago,

In Chinese CSP-S1 today morning, there was a question to use "The Method of Four Russians" to solve RMQ problem. Can anyone do me a favor to teach me what it is? Thank you!

• +15

 » 4 weeks ago, # |   +15 You don't need to learn it now.CCF just had water in it's mind.Don't pay too much attention on that F*** problem
•  » » 4 weeks ago, # ^ |   +16 Haha. But the contest is good, I think. I've found that even in Codeforces this Russian website there are few explanations about TMoFR.
 » 4 weeks ago, # |   +16
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 And CCF says this algorithm is $\Theta(N+Q)$ , but OI-wiki says that it should be $\Theta(N\log\log N+Q)$ ! I think CCF is wrong.UPD:I didn't see clearly. It should be $\Theta(N+Q)$
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 That's a $+1/-1$ RMQ problem because the depths of adjacent nodes in the euler sequence only can be differ by one. So this algorithm is $\Theta (N+Q)$.
•  » » » » 4 weeks ago, # ^ |   +8 Oh yes I didn't see that clearly.Sorry!
•  » » 4 weeks ago, # ^ |   -7 Great, is this blog from you? That's nice.
•  » » » 4 weeks ago, # ^ |   +8 Nope,but OI-wiki.
 » 4 weeks ago, # |   +10 In a word, I think it's quite not proper to put an Russian alorgithm in a Chinese exam :DMaybe "The Method of some numbers of Chinese" should be put in.
 » 4 weeks ago, # |   0 One of the things you DON'T need to know.
•  » » 4 weeks ago, # ^ |   0 Sure. I even don't know what the Cartesian tree is about.
 » 4 weeks ago, # |   +19 The Method of Four Russians is a very general technnique, and not just limited to the RMQ. It roughly has to do with "precomputing" the answers for small parts of the problems, and use some other more general structure for the larger parts of the problem.For instance, in RMQ with The Method of Four Russians, you essentially try to make a sparse table on the range-minima of blocks of small size, and precompute the answers for all small blocks. However, just doing a brute force doesn't work for all small blocks, so rather than solving this for the original problem, we try to find the position of the minimum in equivalence classes of small blocks (which are $C_s$ in number, where $s$ is the size of blocks, and $C_s$ is the $s$-th Catalan number), which are few in number, and recognize which block each small array corresponds to.For a more detailed explanation, you can consider reading https://web.stanford.edu/class/cs166/lectures/01/Small01.pdf

format: plain


text:
Products
Rewards
from HOLOOLY

We are determined to provide the latest solutions related to all subjects FREE of charge!

Enjoy Limited offers, deals & Discounts by signing up to Holooly Rewards Program

HOLOOLY

HOLOOLY
TABLES

All the data tables that you may search for.

HOLOOLY
ARABIA

For Arabic Users, find a teacher/tutor in your City or country in the Middle East.

HOLOOLY
TEXTBOOKS

Find the Source, Textbook, Solution Manual that you are looking for in 1 click.

HOLOOLY
HELP DESK

Need Help? We got you covered.

## Q. 1.11

Consider the following circuit, where a voltage source and a current source are connected to three resistors. Find the value $i_{x}$, that is, the current across the 3 Ω resistor.

## Verified Solution

First, we label the nodes, define the directions of the currents, and define the voltages in accordance with the sign convention, as follows.

Then, using KVL and Ohm’s law, we have $v_{x}$ = 3$i_{x}$, $v_{y}$ = 6$i_{x}$, and
• KVL(1 → 2 → 3 → 1): −24 + $v_{x} + v_{x} = 0 \longrightarrow v_{x} + v_{y} = 24V$

Therefore, we have
$3i_{x} + 6i_{y} = 24 \longrightarrow i_{x} + 2i_{y} = 8 A$.
Furthermore, using KCL (see below for some details), we derive
• KCL(2):$i_{x} − i_{y} − i_{z} = −2A$.
Using $v_{y} = v_{z} and i_{y} = v_{y}∕6 = v_{z}∕6 = i_{z}$, we obtain
$i_{x} − 2i_{y} = −2 A$.
Finally, solving two equations with two unknowns, we get
$i_{x} = 3 A$.
In the above, we note that node 2 (as well as node 3) is defined simultaneously at two
intersections, and KCL is written accordingly by considering all entering and leaving currents, as follows.

This is a common practice in circuit analysis in order to reduce the number of equations.
Specifically, intersections without a component between them can be considered as a
single node to avoid writing redundant equations with redundant unknowns. On the
other hand, this not mandatory. For example, one can consider each intersection as a node, as follows.

In this case, we need to define a current $i_{w}$ between nodes 2 and 4.Writing KCL at the nodes, we now have
• KCL(2): $i_{x} − i_{y}− i_{w} = 0$,
• KCL(4): $i_{w} + 2 − i_{z} = 0$.
Obviously, when these equations are combined (directly added), we arrive at the same
equation in the original solution,
$i_{x} − i_{y} − i_{z} = −2 A$.


text:
I Introduction
###### Abstract

We present and analyze a new robust feedback and transmit strategy for multiuser MIMO downlink communication systems, termed Rate Approximation (RA). RA combines the flexibility and robustness needed for reliable communications with the user terminal under a limited feedback constraint. It responds to two important observations. First, it is not so significant to approximate the channel but rather the rate, such that the optimal scheduling decision can be mimicked at the base station. Second, a fixed transmit codebook at the transmitter is often better when therefore the channel state information is more accurate. In the RA scheme the transmit and feedback codebook are separated and user rates are delivered to the base station subject to a controlled uniform error. The scheme is analyzed and proved to have better performance below a certain interference plus noise margin and better behavior than the classical Jindal formula. LTE system simulations sustain the analytic results showing performance gains of up to or compared to zeroforcing when using multiple antennas at the base station and multiple antennas or a single antenna at the terminals, respectively. A new feedback protocol is developed which inherently considers the transmit codebook and which is able to deal with the complexity issue at the terminal.

[0.5] IEEE Transactions on Wireless Communications

– accepted for publication –

[]

Nearly Doubling the Throughput of Multiuser

MIMO Systems Using Codebook Tailored

Limited Feedback Protocol

[0.5]

Gerhard Wunder, Jan Schreck and Peter Jung Fraunhofer Heinrich Hertz Institute, Einsteinufer 37, D-10587 Berlin, Germany

Technische Universität Berlin Lehrstuhl für Informationstheorie und Theoretische Informationstechnik, Einsteinufer 25, D-10587 Berlin, Germany July 5, 2019©2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

## I Introduction

Multiuser multiple input multiple output (MU–MIMO) communication systems have been in the focus of intensive research over many years. The optimal transmission technique for these systems is dirty paper coding (DPC), which, under perfect channel state information at the transmitter (CSIT), achieves superior performance gains over linear schemes. However, in practical systems CSIT is obtained via a rate–constrained feedback channel, which is known to be a sensitive part of the overall system and must be carefully designed.

In this paper we revisit the limited feedback problem in MU–MIMO systems. We consider linear beamforming and assume that the transmit beamforming vectors are defined by a fixed transmit codebook known to the base stations and all users. In contrast to previous work, we use a different codebook for the feedback and apply a new feedback strategy which we call Rate Approximation (RA). Loosely speaking, using the proposed RA feedback strategy, the terminal selects a channel quantization vector from the feedback codebook considering any possible scheduling decision that can be taken by the base station. As we show, this will enable the base station to approximate the user rates (rather than the user channels) subject to a small uniform a priori error. Then, given the feedback message, the base station is permitted to assert any beamforming vector from the transmit codebook for some network oriented optimization purpose (not just the beamforming vector dictated by the user).

### I-a Related Work

An extensive survey on limited feedback in wireless multiple antennas systems can be found in [1]. The standard reference for point–to–point multiple input single output (MISO) systems is [2] where groundbreaking analytical expressions for the problem are derived. Reference [3] evaluates the performance of point–to–point MISO systems using random vector quantization (RVQ). In [4] is shown that RVQ is asymptotically optimal for point–to–point MIMO systems.

For MU–MIMO systems, which are in the focus of this paper, reference [5] provides the standard performance analysis for the throughput degradation assuming RVQ. In [6] different feedback schemes are proposed that enable the base station to estimate the signal–to–noise–plus–interference ration (SINR) of each user. However, both papers specifically assume zeroforcing (ZF) beamforming and no individual user rate analysis is provided. Reference [7] also considers ZF and jointly designs the receive filters and the channel quantization to maximize the expected SINR of each user. In [8] different kinds of partial CSIT are assumed and the performance of DPC and ZF is compared.

Another popular transmission technique is unitary beamforming (UB). UB with a sum feedback rate constraint is considered in [9]. In [10] a UB scheme named per user unitary rate control (PU2RC) has been proposed for LTE. In [11] an improved user selection scheme for PU2RC is proposed. Again, no error analysis for individual user rates has been presented.

In contrast to previous work, this paper considers an arbitrary transmission scheme for a fixed transmit codebook and analyzes the individual rate error.

### I-B Organization and Main Results

In Section II we introduce the system model and in Section III the RA scheme is introduced. In Section IV:

1. We analyze the a priori rate error at the base station (before any scheduling decision) for each individual terminal evoked by our RA feedback strategy. We prove that it has better scaling properties compared to the classical result in [5] and that this benefit improves with an increasing number of transmit antennas.

2. We outline an advanced vector quantization problem related to the RA scheme by replacing the common chordal distance with a new distance function which inherently uses the structure of the transmit codebook.

In Section V we underline our results with LTE system simulations showing the benefit obtained by the proposed RA scheme and develop a suboptimal feedback protocol dealing with the complexity issue. This feedback protocol is proposed to replace the common approach for LTE. Finally, in Sec. VI the conclusion is drawn with emphasis on the impact on future standards.

Notation: Bold letters denote vectors and bold capital letters matrices. The inner product between vectors and is defined as , where is the conjugate transpose of the vector . The (euclidean) -norm is . is the unit sphere in . The –norm of a vector with components is defined as and denotes its –norm.

## Ii System Setup

We consider the MU–MIMO downlink channel of a cellular system where a base station, equipped with transmit antennas, serves multiple users, equipped with receive antennas, on the same time and frequency resource with a single data stream. The users are collected in the set . Let be the signal transmitted by the base station in a single transmission interval (time index omitted). User receives the transmitted signal through the channel and applies a fixed receive filter to recover its intended signal,

 ym=⟨um,Hmx⟩+nm=:⟨^hm,x⟩+nm

where is additive white Gaussian noise (zero–mean with variance ) and is the effective channel vector from the base station to user . In the sequel we assume each user has perfect knowledge of its own channel and that the channels are constant over one transmission interval; no fading model is imposed. Moreover, we assume no delay in the CSIT report, scheduling or transmission.

In MU–MIMO systems adaptive adjustment of the number of active users is crucial to achieve high spectral efficiency, see [12] and references therein. In each transmission interval the base station selects a subset of users for transmission on the same spectral resource and assigns each user a beamforming vector out of a finite transmit codebook , known to the base station and all users. We will denote with the set of codeword indices. The assignment of users to beamforming vectors is defined by a mapping

 π:S→[C],

that maps each element to a codebook element . We assume that , where is the maximum number of users that can be scheduled on a spectral resource. Note that we do not state the domain of explicitly, if it is clear from the context. In the sequel we may assume that the codebook has the property111This condition means that the codebook constitutes a tight frame for with frame constant that for every

 ∑w∈C|⟨w,f⟩|2=A∥f∥22, (1)

with a fixed constant . If , constitutes an orthonormal base (ONB) and we call an unitary codebook (used for UB).

Define the complex information symbols intended for user as , the transmitted signal is given by the superposition

 x=√P|S|⋅∑m∈Swπ(m)dm,

where we assumed equal power allocation with the power budget . The achieved sum rate for some user set and mapping is

 R(π,S,H)=∑m∈Srm(π,S,^hm)

where is the list of effective channels. The per user contributions to the sum rate are given by the Shannon rates

 rm(π,S,^hm):=log(1+|⟨^hm,wπ(m)⟩|2σ2|S|/P+∑l∈S∖{m}|⟨^hm,wπ(l)⟩|2)

Throughout the paper we assume maximum sum rate scheduling, for instance, with perfect CSIT the optimal user set and mapping is given as

 (SH,πH)=argmaxS⊆Uπ:S→[C]R(π,S,H). (2)

However, due to the rate–constrained feedback channel, the base station takes its decisions based solely on partial CSIT. Partial CSIT message of each user contains channel direction information (CDI) which is an element of the feedback codebook of size and channel quality information (CQI) given by a scalar . The feedback codebook is a priori known to all users and the base station. Moreover, CQI is perfectly transferred to the base station, which is a typical assumption, see e.g. [5].

If the beamforming vectors are restricted to a fixed codebook the scheduling decision based on partial CSIT of all users can be found by solving

 (SV,πV)=argmaxS⊆Uπ:S→[C]R(π,S,V), (3)

where . Equation (3) is a combinatorial problem that can be solved either by a brute force search over the user sets , with , and the mappings or more efficiently in a greedy fashion [13, 7]. Clearly, the decisions in (3) should match with the optimal decision (2) as good as possible. This is the motivation for the following RA scheme.

## Iii Rate Approximation

### Iii-a RA Key Inequality

The key idea of the RA scheme is to minimize the worst case rate mismatch between the individual user rates in (2) and (3) a priori and independent of the (unknown) scheduling decision. The feedback message is selected to make this error as small as possible.

Consider any baseline transmit scheme with perfect CSIT and sum rate . Define the average rate gap between the baseline transmit scheme and beamforming based on a fixed codebook with perfect CSIT as

 ΔRCSIT:=EH[R(H)−R(πH,SH,H)]

and the average rate gap between the real sum rates and the approximated (based on partial CSIT) sum rates for a given user set and mapping as:

Now, the rate gap between the baseline transmit scheme with perfect CSIT and beamforming based on a fixed codebook with partial CSIT can be bounded from above by

 ΔR =EH[R(H)−R(πV,SV,H)] =ΔRCSIT+EH[R(πH,SH,H)−R(πV,SV,H)] =ΔRCSIT+ΔR(πH,SH)+EH[R(πH,SH,V)−R(πV,SV,H)] ≤ΔRCSIT+ΔR(πH,SH)−ΔR(πV,SV) (4) ≤ΔRCSIT+2⋅EH[∑m∈SH∪SVmaxS∈Smπ:S→[C]∣∣rm(π,S,^hm)−rm(π,S,ϑmνm)∣∣], (5)

where (4) must hold since is the optimal mapping of users to beamforming vectors under the channel state information . In (5) we defined the set of user selections with maximal cardinality

 Sm:={S⊆U|m∈Sand|S|≤ns},

which include user . Moreover, we exploited that the rate gap is bounded from above by the worst case rate gap

 ΔRRA:=2⋅EH[∑m∈SH∪SVmaxS∈Smπ:S→[C]∣∣rm(π,S,^hm)−rm(π,S,ϑmνm)∣∣] (6)

From (5) we observe the following strategy which is the motivation for the RA scheme, described in the next subsection.

###### Observation 1.

To control each user needs to individually minimize the individual rate gap for any and mapping .

### Iii-B RA Feedback Scheme

To determine its feedback message each user must find a tuple that minimizes the RA distance222A closer look reveals that it is neither in all cases a distance on nor on the Grassmann manifold.

 d(x,y)=maxS∈Smπ:S→[C]|rm(π,S,x)−rm(π,S,y)|. (7)

Hence, each user finds its feedback message by solving

 (8)

The RA scheme can be easily extended to users with multiple receive antennas . In this case for each scheduling decision the optimal receive filter can be considered in the RA distance according to

 rm(π,S,λmhm)=maxu∈Cnrrm(π,S,HHmu).

Although not apparent at this point let us indicate some relevant properties of the RA scheme: first, in the RA distance the transmit codebook matters which seems good engineering practice as we use all the available information. Second, the terminals provide an uniform error which indicates how well the rates are approximated and leads to inherent robustness. This becomes particularly beneficial in the LTE multi antenna case where channel state information is averaged over the subcarriers (see Simulations in Section V). Third, the RA scheme is amendable to codebook optimization based on the RA distance function (7); in [14] we presented a codebook optimization algorithm for the RA scheme which is based on the Lloyd algorithm.

Finally, consider the example in Figure 1 which establishes that the RA distance indeed yields different feedback decisions compared to the standard chordal distance [5]

 dC(hm,ν)=√1−|⟨hm,ν⟩|2. (9)

The RA scheme’s feedback decisions is obviously more oriented towards the transmit codebook. In the following we analyze its performance. Moreover, as a by-product a simpler distance is derived which is easier to calculate than the computationally complex RA distance.

## Iv Performance Analysis

### Iv-a Benchmarking Strategy

Many papers prove that a particular transmission scheme achieves the optimal multiuser multiplexing gain. That is, for sufficiently large the sum rate scales like . For instance this was shown for random beamforming [15], ZF [16], UB [17] and RA [18]. However, since rates and the number of users are finite in a practical system, the significance of these asymptotic results can at least be questioned. Putting it the other way around: two methods achieving the optimal gain might behave completely different in a practical system.

Our analysis is different and more inspired by the finite user results in [5] and [19]. We assume: the number of users is equal to the number of transmit antennas , all users are active and the transmit codebook constitutes an ONB which corresponds to UB. This assumptions enable stringent comparison to Jindal’s result in [5] with ZF beamforming. Later, in Section IV-C we consider also user selection and general codebooks.

In the remainder of this section we will solely evaluate in (6). The term in (5) was analyzed in [20] and [19], where it is shown that for a certain SNR range (in the low SNR regime) can be even negative.

### Iv-B Uniform RA Error with UB

For the ease of presentation define the normalized effective channel and the receive SNR (normalized to the number of transmit antennas) of user as

 λ2m:=P∥^hm∥22ntσ2.

Let us first provide a general expression for the maximum in (6) which gives us a hint how the RA scheme operates. Note that when the RA scheme operates on a unitary transmit codebook we will denote this scheme by RA–UB.

###### Lemma 1.

If and then for some pair under the RA–UB scheme equation (10) holds,

 d(^hm,ϑν)≤maxw≠w∗log⎛⎜ ⎜ ⎜ ⎜⎝1+λ2m(∣∣|⟨hm,w⟩|2−|⟨ν,w⟩|2∣∣+|⟨ν,w⟩|2|⟨ν,w∗⟩|2∣∣|⟨ν,w∗⟩|2−|⟨hm,w∗⟩|2∣∣)1+λ2m(1−max{|⟨hm,w⟩|2,|⟨ν,w⟩|2})⎞⎟ ⎟ ⎟ ⎟⎠ (10)

where we defined by for all . The strategy minimizing the upper bound is to pick close to (in the chordal distance) constrained by .

The proof can be found in Appendix A.

###### Observation 2.

The suboptimal strategy in Lemma 1 supports the intuition that the error for the best beamformer should be set to zero by the applied feedback strategy, see the example in Figure 2.

So far we are not able to effectively bound which is now settled based on Lemma 1. The following lemma shows that remains bounded when the SNR increases and that the rate error depends solely on the function

 Dm(B):=minV,|V|=2BEH[11−~λm⋅min1>~ϑm>0ν∈Vmaxw∈C∣∣~λm|⟨hm,w⟩|2−~ϑm|⟨ν,w⟩|2∣∣],

where we defined and in the proof of Lemma 1 and is the number of feedback bits.

###### Lemma 2.

If and then under the RA–UB scheme

 ΔRRA≤2nt∑m=1log(1+minϵ>0(1+ϵ)Dm(B)1+ϵnt−1Dm(B))

The proof can be found in Appendix B. The following lemma gives a fundamental bound on .

###### Lemma 3.

If the transmit codebook is unitary, then

 Dm(B)≤c(nt)EH[λ2m]2−Bnt−1,

with

 c(nt)=⎛⎜⎝Θ(Bnt−12)(2nt−2nt−1)Γ(1+nt−12)√nt(nt−1)!πnt−12⎞⎟⎠1nt−1 (11)

and . For small tight bounds are known for the covering density , e.g. (Kershner, 1939), (Bambah, 1954), (Delone & Ryshkov, 1963). For the Rogers bound [21] can be used.

The complete proof can be found in the Appendix C. Note that is close to unity and falls below unity not before , as required for improved scaling compared to Jindal’s result. As the following illustration for the case shows, this is simply an artefact of the proof technique.

Without loss of generality, we assume the unitary transmit codebook is given by the standard ONB. We drop the user index and define from its channel direction the real positive vectors with and with for each . Per definition, all these vectors have unit –norm, and, hence, define points on the standard –simplex. Further, defines a distance between two points on the standard –simplex. Hence, for a given feedback codebook we can define the Voronoi region around the point for a particular as If and , the feedback codebook can be chosen such that the Voronoi regions are –simplices with edge length . Now, using the symmetry of the covering and projecting the quantization points back on the coordinate axes (see Figure 3) we get .

Now we can compute the volumes of the –simplices (the standard simplex and the scaled simplex) and proceed as in the proof of Lemma 3 to obtain the result

 δ=maxx∈V(ϕν)∥x−ϕν∥∞=2−Bnt−1−1.

Hence, if and Rayleigh fading is assumed (i.e. for and ), the rate loss due to the rate–constrained feedback channel scales like

 ΔRRA≤2nt∑m=1log⎛⎜ ⎜ ⎜⎝1+minϵ>0(1+ϵ)EH[~λm1−~λm]2−Bnt−1−11+EH[~λm1−~λm]ϵnt−12−Bnt−1−1⎞⎟ ⎟ ⎟⎠≤2nt∑m=1log(1+Pσ22−Bnt−1−1).

Therefore, we have an improvement of bits in the exponential term compared to Jindal’s result for ZF with feedback based on minimizing the chordal distance (see [5]), under the very same assumptions.

### Iv-C Uniform RA Error with User Selection and General Codebooks

In this subsection we no longer assume unitary transmit codebooks and allow user selection at the base station.

###### Theorem 1.

Assuming Rayleigh fading, arbitrary transmit codebooks and user selection , then for any under the RA scheme

 ΔRRA≤4nslog(1+Pntσ2EH[minν∈Vmaxw∈C∣∣|⟨h,w⟩|2−|⟨ν,w⟩|2∣∣]).

The proof can be found in Appendix D. The expected value

 ^Dm(B):=minV,|V|=2BEH[minν∈Vmaxw∈C∣∣|⟨h,w⟩|2−|⟨ν,w⟩|2∣∣]

has been shown to be analytically tractable, in the previous section, for unitary transmit codebooks. For codebooks constituting a tight frame (see the condition (1)) we devise the following corollary.

###### Corollary 1.

If the transmit codebook is a tight frame, then where is defined in (11) and is the frame constant in (1).

The proof is a simple extension of Lemma 3 and omitted. The previous result is remarkable since all the possible user rates are uniformly recovered at the base station with better scaling properties than the classical result. The RA scheme is now applied in a practical scenario.

## V Practical Considerations and Simulations

### V-a Efficient and Robust Feedback Protocol

Mobile user equipments usually have limited computing capabilities, therefore, most systems require that the complexity at the user side is as low as possible. Hence, solving the full rate approximation problem (the min–max problem (8)) may not be feasible. Fortunately, our analysis in Section IV yields the (suboptimal) distance function

 dS(h,ν)=maxw∈C∣∣|⟨h,w⟩|2−|⟨ν,w⟩|2∣∣, (12)

which can be used at the user side to uniformly bound the rate approximation error (6). Further, we define the CQI reported by user as

 ϑ2m=λ2m|⟨hm,νm⟩|2, (13)

which can be interpreted as the effective channel gain of user over the quantized channel . Equation (13) captures two important aspects. On the one hand, if the CDI is equal to the channel direction, the user gets no penalty () on the other hand if the CDI is orthogonal to the channel direction, the effective channel is zero (). Hence, the CQI (13) reflects the receive SNR and the quantization error, which is also in accordance with the results in [16]. In Algorithm 1 the efficient feedback protocol is summarized.

#### Complexity of the proposed feedback protocol

Figure 4 (bottom) shows a flow chart of the CDI computation with the proposed feedback protocol using the distance function defined in (12). We point out that the terms , for and , only need to be computed ones and can be stored in the memory. Therefore, during the feedback phase user must only compute for all and the difference for all . Figure 4 (top) shows the steps that need to be performed to compute the CDI based on the chordal distance (9). To compute the chordal distance each user must compute for all .

If we assume a fixed transmit codebook and a feedback codebook with elements, the complexity of computing the CDI based on (9) or (12) is asymptotically equal, i.e., using Landau notation . However, this result is only valid for growing asymptotically large. For small values and the number of scalar products that needs to be evaluated are summarized in Table I.

### V-B Simulations

In the simulations we consider a LTE like system architecture. That is, multiple base stations transmit to multiple users using the spectrum. The spectrum is divided in orthogonal subcarriers using orthogonal frequency–division multiplexing OFDM. In the sequel we use a frequency reuse factor of one, i.e., each base station uses the whole frequency band. Since, we assume no cooperation between the base stations inter cell interference is indispensable. In the sequel the channel from base station to user on subcarrier is given by .

The transmit protocol can be summarized as follows. First, each base station transmits orthogonal common pilots. Then, each user quantizes and feeds back its channel state information. Based on the quantized channel state information each base station solves the scheduling problem (3). Finally, dedicated (i.e. precoded) pilots are transmitted by all base stations.

The simulation parameters are given in Table II, they can be summarized as follows. base stations located in adjacent cells and users uniformly distributed over the network area; given by a radius of meter around the center of the base stations. The physical layer is configured according to LTE [22]. The base station are equipped with transmit antennas and each user is equipped with or receive antenna (specified in the caption). The transmit codebook and feedback codebook is given by the LTE codebook defined in [22] which has elements and, hence, requires bit to feedback back the CDI. The channels are modeled by the spatial channel model extended (SCME) [23] using the urban macro scenario.

In total subcarriers per base station are available. The subcarriers are clustered in groups of subcarriers; one subcarrier group is denoted as physical resource block (PRB). One PRB is the smallest scheduling unit. The subcarrier indexes of PRB are collected in the index set . We define the average channel gain of PRB as , where is the Frobenius norm of matrix , and assume that each user is assigned to that base station with maximal total average channel gain . Each user reports one feedback message per PRB to that base station it is assigned to.

Each of the base stations runs an independent local scheduler. In every transmission interval up to users can be scheduled by each base station on every PRB. Scheduling is performed in a greedy fashion according to [24]. For simplicity we assume no delay in the CSIT report, scheduling, transmission or performance evaluation.

The performance is evaluated based on the network spectral efficiency which we define by where is the SINR of user on subcarrier and are the users scheduled by base station on PRB .

In the simulation we compare four different feedback strategies.

1. Perfect (average) CSIT: the base station knows the channel averaged over all subcarriers perfectly, where is the channel of user on subcarrier .

2. Minimum chordal distance: user determines its CDI feedback by minimizing the chordal distance (9) to the channel , where is chosen to maximize .

3. Rate Approximation as described in Section III with the rates

 rm(π,S,λmhm)=1FF∑f=1rm(π,S,λmhm,f).
4. Efficient Rate Approximation as described in Section V-A, where is given by the average channel as defined for minimum chordal distance above.

Figure 5 depicts the CDF of the spectral efficiency for users with receive antenna. The ZF scheme is implemented according to [7]. The PU2RC scheme is based on the same transmit codebook as RA and is implemented according to [10]. We observe that with perfect CSIT ZF outperforms greedy scheduling with a fixed codebook. With partial CSIT the RA scheme significantly outperforms ZF with a gain of approximately . Remarkable is also the gain of about of RA over PU2RC. Moreover, Figure 5 shows that RA with the efficient distance function (12) performs very close to the full RA scheme.

Figure 6 depicts the CDF of the spectral efficiency for users with receive antennas. We observe that with perfect CSIT ZF outperforms greedy scheduling with a fixed codebook. With partial CSIT the RA scheme significantly outperforms all other schemes and achieves a gain of approximately over ZF. Remarkable is also the gain of RA over PU2RC.

In Figure 7 we compare the performance of RA and partial CSIT ZF with different receive filters, i.e. the MMSE receive filter that maximizes the SINR of each user by considering the interference from all other users, the global ZF receive filter that tries to minimize interference from all base stations and the local ZF receive filter that considers only interference from the own base station. We observe that both transmit schemes achieve the highest network sum rate with the SINR optimal receive filter. The performance degradation with the local and global ZF receive filter are similar for both transmit schemes.

## Vi Conclusion

In this paper we invented and analyzed the rate approximation scheme. It was shown that each user can individually minimize its rate error a priori by selecting the feedback message in a robust fashion incorporating the transmit codebook. The respective error expressions and feedback schemes are derived and compared to the standard expressions. It is proved that a better scaling is possible when the size of the transmit code book is small. A remarkable result is that it is often much better to reduce flexibility at the base station in favor of having more reliable CSIT.

## Appendix A Proof of Lemma 1

###### Proof:

Let us first drop the user index , i.e. and . Further abbreviate , and without explicitly writing the dependency of . Using with we get for any and normalized vector

 rm(π,S,λh)−rm(π,S,ϑν)= log((λ2+1)(1+ϑ2(1−ϕ))(ϑ2+1)(1+λ2(1−ψ))) (14) = log(1−~ϑϕ1−~λψ)=log(1+~λψ−~ϑϕ1−~λψ). (15)

Here, we have set . Similarly, the negative term can be rewritten as . Recall, that and depend on which in turn depends again on the mapping . With the assumptions of this lemma we have that the set of possible scheduling subsets in the definition of RA distance (7) is simple, i.e. and we get from (15) the following upper bound

 dm(λh,ϑν)=maxπ|rm(π,S,λh)−rm(π,S,ϑν)|≤maxπmax[log(1+~λψ−~ϑϕ1−~λψ),log(1+~ϑϕ−~λψ1−~ϑϕ)]≤maxπlog(1+max[~λψ−~ϑϕ1−~λψ,~ϑϕ−~λψ1−~ϑϕ]) (16)

which is still valid for any . Now, consider the following (sub–optimal) three-step strategy for the feedback protocol: (a) define to be the codeword nearest to true channel direction in the chordal distance (see (9)) and (b) select then a CDI from the feedback codebook which is closer to as is, i.e. which has the property . Since such vector always exists. (c) Determine the CQI by setting , which yields after some calculations . The result of this strategy is that we get for the first term in the ”” of (16):

 ~λψ−~ϑϕ1−~λψ ≤~λ⋅ψ−ηθϕ1−~λψ≤~λ1−~λψ(|ψ−ϕ|+ϕθ|θ−η|).

for any (which ensures that ). Similar, for the second term in upper bound (16) we obtain

 ~ϑϕ−~λψ1−~ϑϕ ≤~λ⋅ηθϕ−ψ1−~ληθϕ(η≤θ)≤~λ⋅ηθϕ−ψ1−~λϕ ≤~λ1−~λϕ(|ψ−ϕ|+ϕθ|θ−η|)

where we now need the additional property of step (b) that which proves the claim. ∎

## Appendix B Proof of Lemma 2

###### Proof:

According to the rule (8), RA aims on minimizing the maximal rate error over the elements of . Under the assumptions of this lemma (the list of scheduling subsets is ) the maximal rate error at user achieved for given CDI and CQI is:

 dm(λmhm,ϑν)=maxπ|rm(π,S,λmhm)−rm(π,S,ϑmνm)| (17)

and from (6) we have in this case:

 ΔRRA:=2∑m∈SEH[dm(λmhm,ϑmνm)]

Let us consider the contribution of user to this sum. Using the notation of Appendix A we have from (16) and Jensen’s inequality that

 EH[dm(λh,ϑν)]≤log⎛⎝1+EH⎡⎢⎣min1>~ϑm>0ν∈Vmaxπ|~λψ−~ϑϕ|1−~λψ⎤⎥⎦⎞⎠+log⎛⎝1+EH⎡⎢⎣min1>~ϑm>0ν∈Vmaxπ|~λψ−~ϑϕ|1−~ϑϕ⎤⎥⎦⎞⎠. (18)

Let us re-write the first term on the right side of (18). The idea is to use Lemma 1 with as an ultimate upper bound to the RA error. Then, subsequently we improve by using the full potential of . We first exploit that whenever , for some , then by Lemma 1 the error can be uniformly bounded from above by , and since clearly and for we have for , for any (even that for ). On the other hand, we have . Hence, we can write for some pair : and setting , where and with respect to maximizing mapping and minimizing arguments . This yields Equivalently, for the second term on the right side of (18) we have


text:
# Make bold year and author in in-text citation with biblatex

I'm trying to get the year and the author in bold for all in-text citations.

Thanks to @moewe I already managed to get my prefered style of the Bibliography and also to print the author in the in-text citation in bold. Now there is missing the last step to get my prefered format style.

I would be very happy if someone had a hint for me. I think it's only one line that is missing but I don't know how to edit the year.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{csquotes}
\usepackage[backend=biber,
citestyle=ext-authoryear,
bibstyle=ext-authortitle,
sorting=nyt,
introcite=label,
maintitleaftertitle=true,
maxcitenames=2,
dashed=false
]{biblatex}

\setlength{\introcitewidth}{4cm}
\setlength{\introcitesep}{\bibhang}

\DeclareFieldFormat{bbx@introcite}{\mkbibbold{#1}}
\DeclareNameAlias{sortname}{family-given}
\renewcommand*{\mkbibnamefamily}{\textbf}

% make square brackets around citation in text
\makeatletter
\newrobustcmd*{\parentexttrack}[1]{%
\begingroup
\blx@blxinit
\blx@setsfcodes
\blx@bibopenparen#1\blx@bibcloseparen
\endgroup}
\AtEveryCite{%
\let\parentext=\parentexttrack%
\let\bibopenparen=\bibopenbracket%
\let\bibcloseparen=\bibclosebracket}
\makeatother

\AtBeginBibliography{
\renewcommand*{\mkbibnamefamily}[1]{\textsc{#1}}}

\begin{filecontents}{Bibliography.bib}
@book{Loftin80,
title={Subsonic Aircraft: Evolution and the Matching of Size to Performance},
author={Laurence K. Loftin},
year={1980},
}
\end{filecontents}

\begin{document}
The author and year should be in bold. \autocite{Loftin80}
\printbibliography
\end{document}

• What about pre- and postnotes? What should be bold if you say \autocite[cf.][20-22]{Loftin80}? – moewe Jan 7 at 8:22
• Only the author and year; pre- and postnotes not in bold – MoritzLo Jan 7 at 8:33

Unfortunately, there are no built-in formats to change the citation label in this way, so we have to redefine the cite bibmacro. The definition used by ext-authoryear.cbx is inherited from authoryear.cbx (ll. 10-18 in v3.16). We just add a \printtext[bold]{...} in the right place.

That code will automatically make the citation in the bibliography bold as well, so we can drop the \DeclareFieldFormat{bbx@introcite}{\mkbibbold{#1}}.

Note that with biblatex-ext it is much easier to get square brackets around citations than with the standard styles. You don't need \parentexttrack and friends. See my answer to Biblatex, author-year, square brackets, where you find \parentexttrack in the accepted answer.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{csquotes}
\usepackage[backend=biber,
citestyle=ext-authoryear,
bibstyle=ext-authortitle,
sorting=nyt,
introcite=label,
maintitleaftertitle=true,
maxcitenames=2,
dashed=false
]{biblatex}

\setlength{\introcitewidth}{4cm}
\setlength{\introcitesep}{\bibhang}

\DeclareNameAlias{sortname}{family-given}

\DeclareOuterCiteDelims{parencite}{\bibopenbracket}{\bibclosebracket}

\renewbibmacro*{cite}{%
\printtext[bold]{%
\iffieldundef{shorthand}
{\ifthenelse{\ifnameundef{labelname}\OR\iffieldundef{labelyear}}
{\usebibmacro{cite:label}%
\setunit{\printdelim{nonameyeardelim}}}
{\printnames{labelname}%
\setunit{\printdelim{nameyeardelim}}}%
{\usebibmacro{cite:shorthand}}}}

\AtBeginBibliography{%
\renewcommand*{\mkbibnamefamily}{\textsc}}

\begin{filecontents}{\jobname.bib}
@book{Loftin80,
title  = {Subsonic Aircraft: Evolution and the Matching of Size to Performance},
author = {Laurence K. Loftin},
year   = {1980},
}
\end{filecontents}

\begin{document}
The author and year should be in bold. \autocite{Loftin80}
\printbibliography
\end{document}

• Thank you so much for your time and help! Now it works exactly the way I want :) – MoritzLo Jan 7 at 9:47


text:
The goal of Automated Theorem Proving is to automatically generate a proof, given a conjecture (the target theorem) and a knowledge base of known facts, all expressed in a formal language. Automated Theorem Proving is useful in a wide range of applications, including the verification and synthesis of software and hardware systems.

TREND DATASET BEST METHOD PAPER TITLE PAPER CODE COMPARE

# HOList: An Environment for Machine Learning of Higher-Order Theorem Proving

5 Apr 2019tensorflow/deepmath

We present an environment, benchmark, and deep learning driven automated theorem prover for higher-order logic.

751

# HolStep: A Machine Learning Dataset for Higher-order Logic Theorem Proving

1 Mar 2017tensorflow/deepmath

We propose various machine learning tasks that can be performed on this dataset, and discuss their significance for theorem proving.

751

# Learning to Prove Theorems via Interacting with Proof Assistants

21 May 2019princeton-vl/CoqGym

Proof assistants offer a formalism that resembles human mathematical reasoning, representing theorems in higher-order logic and proofs as high-level tactics.

195

# On-demand Injection of Lexical Knowledge for Recognising Textual Entailment

We approach the recognition of textual entailment using logical semantic representations and a theorem prover.

165

127

# Learning as Abduction: Trainable Natural Logic Theorem Prover for Natural Language Inference

29 Oct 2020kovvalsky/LangPro

Tackling Natural Language Inference with a logic-based method is becoming less and less common.

77

# LangPro: Natural Language Theorem Prover

LangPro is an automated theorem prover for natural language (https://github. com/kovvalsky/LangPro).

77

# GamePad: A Learning Environment for Theorem Proving

In this paper, we introduce a system called GamePad that can be used to explore the application of machine learning methods to theorem proving in the Coq proof assistant.

65

# G2SAT: Learning to Generate SAT Formulas

The Boolean Satisfiability (SAT) problem is the canonical NP-complete problem and is fundamental to computer science, with a wide array of applications in planning, verification, and theorem proving.

29

# Holophrasm: a neural Automated Theorem Prover for higher-order logic

8 Aug 2016dwhalen/holophrasm

I propose a system for Automated Theorem Proving in higher order logic using deep learning and eschewing hand-constructed features.

26


text:
# Rearrange positive and negative numbers in O(n) time and O(1) extra space in C++

We are given an integer type array containing both positive and negative numbers, let's say, arr[] of any given size. The task is to rearrange an array in such a manner that all positive and negative numbers should be at alternate positions and if there are extra positive or negative elements then they will be placed in the end of an array.

## Let us see various input output scenarios for this −

Input − int arr[] = {4, 2, -1, -1, 6, -3}

Output − Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 - 1 6 -1 4 -3

Explanation − we are given an integer array of size 6 containing both positive and negative elements. Now, we will rearrange the array in such a manner that all the positive elements and the negative elements are at an alternate positions and all the extra elements will be added in the end of an array i.e 2 -1 6 -1 4 -3 will be the final result

Input − int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

Output − Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Explanation − we are given an integer array of size 12 containing both positive and negative elements. Now, we will rearrange the array in such a manner that all the positive elements and the negative elements are at an alternate positions and all the extra elements will be added in the end of an array i.e 2 -2 3 -5 5 -3 5 -1 1 3 1 1 will be the final result

## Approach used in the below program is as follows

• Input an array of integer type elements and calculate the size of an array.

• Print an array before performing the rearrangement action using the FOR loop.

• Call to the function Rearrangement(arr, size) by passing array and size of an array as a parameter.

• Inside the function Rearrangement(arr, size)

• Declare temporary integer type variables i.e.temp to -1, positive to temp + 1 and negative to 0.

• Start loop FOR from i to 0 till i less than the size of an array. Inside the loop, check IF arr[i] less than 0 then increment the temp by 1 and call the inbuilt method of C++ STL i.e. swap(arr[temp], arr[i]) and pass arr[temp] and arr[i] as a parameter.

• Start loop WHILE positive less than the size of an array AND negative less than the positive AND arr[negative] less than 0. Inside the loop, call swap by passing arr[negative] and arr[positive] as a parameter. Increment the positive by 1 and set negative to negative + 2.

• Print the result.

## Example

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
int temp = -1;
for(int i = 0; i < size; i++){
if (arr[i] < 0){
temp++;
swap(arr[temp], arr[i]);
}
}
int positive = temp + 1;
int negative = 0;
while(positive < size && negative < positive && arr[negative] < 0){
swap(arr[negative], arr[positive]);
positive++;
negative = negative + 2;
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3};
int size = sizeof(arr)/sizeof(arr[0]);
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}

## Output

If we run the above code it will generate the following Output

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3


text:
AAS 207th Meeting, 8-12 January 2006
Session 175 Recent Discoveries in the Far UV
Poster, Thursday, 9:20am-4:00pm, January 12, 2006, Exhibit Hall

## [175.04] Deuterium, Oxygen, and Nitrogen Abundance Toward LSE 44

S.D. Friedman (STScI), G. Hebrard (IAP), T.M. Tripp (UMASS), P. Chayer (JHU), K.R. Sembach (STScI)

We present FUSE measurements of D, O, N, H2, and \ion{Fe}{2}, and IUE measurements of H toward LSE 44, an sdO star at a distance of 554±6 pc. This is among the most distant Galactic targets for which D/H, D/O, and D/N have been measured. Both profile fitting and curve-of-growth techniques have been utilized in the analysis. We find D/H = (2.24+1.39-1.32) \times 10-5, D/O = (1.99+1.30-0.67) \times 10-2, D/N = (2.75+1.19-0.89) \times 10-1, and O/H = (1.13+0.96-0.71) \times 10-3 (all errors 2\sigma). This is one of the few sight lines probing material well beyond the Local Bubble for which D/H is higher than the Local Bubble value. Sight line to sight line variability of D/H for some targets, particularly those outside the Local Bubble, could be explained by varying degrees of depletion of deuterium onto dust grains, by infall of deuterium-rich primordial material, or by some other mechanism. However, D/O for these distant targets is uniform, and this discrepancy has yet to be explained.

This work is based on data obtained for the Guaranteed Time Team by the NASA-CNES-CSA FUSE mission operated by The Johns Hopkins University. Financial support has been provided to U.S. participants by NASA and to French participants by CNES.


text:
## Notes. Some basic terms

1. Let $R$ be a commutative ring, $S$ be a multiplicatively closed subset in the sense that $a,b\in S \Rightarrow ab \in S$. Then we consider the localization $S^{-1}R$ as the quotient $S\times R/\sim$, where $(r,a)\sim (s,b)$ if $(br-as)t=0$ for some $t\in S$.

Let $f\in R$. We can construct a m.c.subset $S=\{f^n: n\ge 0\}$, and denote the corresponding local ring by $R_f=S^{-1}R$.

Let $p\triangleleft R$ be a prime ideal of $R$. Then $S=R\backslash p$ is m.c. We denote the corresponding local ring by $R_p=S^{-1}R$.

Let $\text{Spec}R$ be the set of all prime ideals of $R$. For each ideal $I\triangleleft R$, let $V_I=\{p\in \text{Spec}R: p\supset I\}$. The Zariski topology on $\text{Spec}R$ is defined that the closed subsets are exactly $\{V_I: I\triangleleft R\}$.

A basis for the Zariski topology on $\text{Spec}R$ can be constructed as follows. For each $f\in R$, let $D_f\subset \text{Spec}R$ to be the set of prime ideals not containing $f$. Then each $D_f= \text{Spec}R\backslash V_{(f)}$ is open.

The points corresponding to maximal ideals $m \triangleleft R$ are closed points in the sense that the singleton $\{m\}=V_m$.

In the case $R=C[x_1, \dots, x_n]$, we see that each maximal ideal $m=\langle x_1-a_1,\dots, x_n-a_n \rangle$ corresponds to a point $(a_1,\dots, a_n)\in C^n$. So one can interprat this as $C^n \subset X= \text{Spec} R$. A non-max prime ideal $p$ (a non-closed point) corresponds an affine variety $P$, which is a closed subset in $C^n$. Then $p$ is called the generic point of the varity $P$.

2. Let $(M,\omega)$ be a symplectic manifold, $G$ be a Lie group acting on $M$ via symplectic diffeomorphisms. Let $\mathfrak{g}$ be the Lie algebra of $G$. Each $\xi \in \mathfrak{g}$ induces a vector field $\rho(\xi):x\in M \mapsto \frac{d}{dt}\Big|_{t=0}\Big(\exp(t\xi)\cdot x\Big)$. Note that $\rho(g^{-1}\xi g)=g_\ast \rho(\xi)$, and $\rho([\xi,\eta])=[\rho(\xi),\rho(\eta)]$.

Consider the 1-form induced by the contraction $\iota_{\rho(\xi)}\omega$. Clearly this 1-form is closed: $d\iota_{\rho(\xi)}\omega=L_{\rho(\xi)}\omega=0$ since $G$ preserves the form $\omega$.

Then the action is called weakly Hamiltonian, if for every $\xi\in \mathfrak{g}$, the one-form $\iota_{\rho(\xi)} \omega$ is exact: $\iota_{\rho(\xi)} \omega=dH_\xi$ for some smooth function $H_{\xi}$ on $M$. Although $H_\xi$ is only determined up to a constant $C_\xi$, the constant $\xi \mapsto C_\xi$ can be chosen such that the map $\xi\mapsto H_\xi$ becomes linear.

The action is called Hamiltonian, if the map $\mathfrak{g} \to C^\infty(M)$, $\xi\mapsto H_\xi$ is a Lie algebra homomorphism with respect to Poisson structure. Then $\rho(\xi)=X_{H_\xi}$ and $H_{g^{-1}\xi g}(x)=H_\xi(gx)$.

A moment map for a Hamiltonian $G$-action on $(M,\omega)$ is a map $\mu: M\to \mathfrak{g}^\ast$ such that $H_\xi(x)=\mu(x)\cdot \xi$ for all $\xi\in \mathfrak{g}$. In other words, for each fixed point $x\in M$, the map $\xi \mapsto H_\xi(x)$ from $\mathfrak{g}$ to $\mathbb{R}$ is a linear functional on $\mathfrak{g}$ and is denoted by $\mu(x)$. Also note that $\mu(gx)\cdot \xi=H_\xi(gx)=H_{g^{-1}\xi g}(x)$. So $\mu(gx)=g\mu(x)g^{-1}$.


text:
# With low power comes low credibility?

## Or: How much should we distrust significant results from tests with low power?

Disclaimer: I’ll explain it further down below, but at no point should this blog post be used as an excuse to conduct underpowered studies! Also, I realized that this post turned out to be more “opinionated” than I planned. So please be aware that what I write here is just my opinion – if you disagree, I would be happy to know about it in the comments or twitter!

Some time ago, a colleague came to me and asked me for advice. He had found a nice and theoretically interesting significant result – but for various reason, his sample size was rather small, and he deemed it likely that his test had been underpowered. He was therefore worried that the result was not credible (his exact word was „robust“), and asked me if there was any way to show that the test indicated a real effect, despite the low power. Something about his concern felt weird to me, but I couldn‘t quite nail it down. I said I didn’t really know how to help at the moment, and the issue resolved itself eventually – but I kept wondering what felt so off for me about his question. Additionally, I started noticing similar concerns more often. Talking with colleagues, following discussions online or reading reviews, time and again I heard or read things like „the result is significant, but the sample is quite small, so it’s likely to be just a fluke“, or „Because this study obviously has very low power, I don’t find these results credible“.

So, at least in my community (psychologists and neuroscientists), there appeared to be something of an unspoken consensus that significant results from low-powered tests were in some way less credible than significant results from highly-powered studies. I guess it did sound right… if living through the replication crisis had taught us one thing, it was that „High power = GOOD! Low power = BAD“. But I realized eventually that the notion felt so weird to me because it conflicted with my intuition of how frequentist significance tests are supposed to work. If test results from small samples are meaningless, why do statistical programs give me critical values of the t-distribution for dfs < 10, instead of telling me „these values don’t make any sense, you idiot“ – or a more polite version of the same? Of course a low-powered test is bad at detecting an existing effect – but if it does deliver a significant result, is it then also more probable that the effect does not really exist? But wasn’t the whole shtick of frequentist significance tests that they would, at least, nicely control the number of false-positives? Something didn‘t add up for me. So, I now finally decided to think these things through a bit, and hope that you find some of my ruminations useful.

First of all, let‘s translate the vague concern about the credibility of low-powered tests into statements that we can talk about in formal statistical terms. I believe that the concerns described above can all be translated into one of the following two propositions:

1. Tests with low power are more likely to give a significant result although there is no effect. In other words, tests with low power have an increased type-I-error rate.
2. Significant results from low-powered tests are less likely to be due to a real effect. In other words, the probability that H1 is true in view of a significant result from a low-powered test is not as high as it would be if the test had greater power.

In terms of statistical „schools“ of inference, proposition #1 is something that a frequentist analyst might worry about, while proposition #2 indicates a more Bayesian perspective. My research community is mostly frequentists, with some Bayesianism sprinkled on top whenever useful (how I feel about such statistical eclecticism should become more apparent later on). Therefore, I think it might make sense to look at these concerns from both a frequentist’s and a Bayesian’s perspective [1], and see what there really is to worry about.

Let‘s first put ourselves into the somewhat worn-out, but comfortable, old-fashioned but solid-until-you-look-closer shoes of a frequentist. To recap, when we perform a frequentist significance test, we …

• … make assumptions regarding what our data should look like if the null hypothesis were true;
• … identify the range of statistics that are so extreme that we would observe one of them in only α% of cases if the null hypothesis were true;
• … check if the statistic from our sample belongs to the α% of cases. If it does, we call the result „significant“, and regard it as evidence that the null hypothesis is not true.

Provided that our assumptions are correct, we can rest assured that we will make a type-I-error in only α% of the cases, meaning that we will obtain a significant result in only so many cases if the null hypothesis is actually true. Now, the thought that keeps every devout frequentist up at night is that the type-I-error might actually be higher than α. The frequentist spent so much effort, sacrificed so many things, just to be comfortably wrong in a maximum of α% of cases, that an actually increased error rate would spell certain doom. Does low power invoke this miniature apocalypse, summon forth the Beelzebub [2] of failed error control? Well, in principle, no! The power of the test does not enter into the calculation of critical thresholds or p-values. If the assumptions of your test hold, and the null hypothesis is true, you will obtain a significant result in only α% of the cases, independent of your sample size or power. So, if you believe that the test assumptions are met, and that p < 0.05 tells you something meaningful about the world, you should be as convinced by a significant result from a sample of ten subjects as from a sample of one thousand [3]. However, the „ifs“ in the preceding sentences are very important: Most tests assuming that the data is normally distributed (read: nearly all them tests) will only be robust to deviations from normality if the sample size is considerably large. If the sample size is too small, not meeting the assumptions is likely to change the type-I-error rate – but it depends on the test and the type of the deviation if the error rate will be increased or decreased. So, if you have good reason to worry that the assumptions of your test are not met, small samples are a problem, and you might end up with an increased type-I-error rate. However, modern statistics provide robust alternatives to most tests, so even this issue can be resolved in most cases.

So, as long as the assumptions of a test are fulfilled, or a robust alternative is available, a frequentist should not be worried that low power leads to an increased type-I-error rate. But what about the other concern, that significant results from low-powered studies come with a lower probability that the H1 is true? Well, it is true that significant results tell the frequentist little about this probability if the test had had low power – but that’s also the case for a perfectly powered test. In fact, no test can tell the frequentist anything about the probability of H1, because it is not even a valid concept within his/her school of thought. (To the best of my understanding, the only probabilities a frequentist can meaningfully assign to hypotheses are 0 and 1, for false and true hypotheses respectively. Of course, whether or not a hypothesis is true or false is not known in most cases, and if it is, there is no need to perform inference.)

We can therefore now step out of the frequentist’s shoes, and get comfortable in the hip sneakers of a Bayesian. We can safely skip proposition #1 (Type-I-errors are of as much interest to a Bayesian as the Immaculate Conception is to a Buddhist [4] ) and proceed with #2: should we be worried that low power decreases the probability that significant results indicate a true effect?

This question was famously, and influentially, discussed by Katherine Button, John Ioannidis and colleagues in their paper Power failure: why small sample size undermines the reliability of neuroscience in Nature Reviews Neuroscience. In fact,  I am quite certain that many of the worries about low power that my colleagues and friends voiced in the intro stem directly or indirectly from this article. I’d therefore like to address proposition #2 in the form of a short review of Button et al.‘s argumentation. To summarize in advance: the paper raises, without question, many valid points about the perils of a research field seemingly dedicated to underpowered studies. However, I think that it also incited some major misunderstandings regarding the interpretation of significant results from low-powered tests, mainly due to two reasons:

1. The authors are not transparent about the fact that their argumentation is deeply dependent on the (Bayesian) assumption that ascribing probabilities to hypotheses is meaningful – a notion that is not consistent with frequentist thought. At the same time, they make heavy use of frequentist vocabular, misleading the reader into thinking that their argument is based on canonical frequentist theory, when it is really not.
2. Under the assumption that probabilities can be assigned to hypotheses, the authors deduce correctly that significant results from low-powered tests are less likely to indicate a true effect than significant results from tests with higher power. However, the authors downplay the surprisingly strong support that significant results from even very underpowered studies give to the hypothesized effects.

But let’s look at the paper in more detail. After the truism that low power comes with a low probability of detecting a true effect, the author’s put the following statement into the summary bulletpoints:

Perhaps less intuitively, low power also reduces the likelihood that a statistically significant result reflects a true effect.

So, that sounds like a proper Bayesian statement – and to be very honest, I started writing this post with the vague memory that Button et al. explicitly invoked Bayes‘ theorem to support their claim. I was thus very surprised when, upon re-reading, I could not find the name „Bayes“ anywhere in the paper, except for a few off-hand mentions of „alternative Bayesian approaches“. What the authors do refer to are two of Ioannidis‘ own previous papers, neither of which contain any prominent reference to Bayesian theory either. Instead, the concept at the center of the authors‘ argumentation is the „positive predictive value“, or PPV – a term that I believe is not used often in psychology and neuroscience, but appears to be more prominent in epidemiology. The PPV of a diagnostic test is the probability that some condition is really present (e.g., a patient really has some disease), given that the test provided a positive result. Button et al. now simply calculated the „PPV“ of a statistical test, by exchanging „patient has some disease“ with „hypothesis is true“, and „positive result“ with „significant result“, to arrive at the probability that the hypothesis is true, given that the test provided a significant result. If you are now wondering „wait, isn‘t that just the posterior probability of the hypothesis being true?“, you are absolutely right. To see that more clearly, consider Bayes‘ theorem for the posterior probability of H1 being true, given a significant result:

\begin{aligned} P(\text{H1}|\text{sig}) &= \frac{P(\text{sig}|\text{H1})P(\text{H1})}{P(\text{sig}|\text{H1})P(\text{H1})+ P(\text{sig}|\text{H0})P(\text{H0})} \\ &= \frac{P(\text{sig}|\text{H1})\frac{P(\text{H1})}{P(\text{H0})}}{P(\text{sig}|\text{H1})\frac{P(\text{H1})}{P(\text{H0})}+ P(\text{sig}|\text{H0})} \end{aligned}

where in the second line I just divided nominator and denominator by P(H0) to show that it is enough to consider the prior odds P(H1)/P(H0). Now, let’s give the terms in the equation their frequentist names, where possible: P(sig|H0) is just good old α, and P(sig|H1) is the power of the test, commonly written as (1-β), where β is the type-II-error rate. The prior odds (which I’ll call R, to be consistent with Button et al.) don’t have a frequentist equivalent because, of course, prior probabilities are not a meaningful concept in frequentism. We thus arrive at

$P(\text{H1}|\text{sig}) = \frac{(1-\beta)R}{(1-\beta)R+\alpha},$

which is the exact formula that Button et al. report – without any mention of Bayes‘ theorem, or of the fact that assigning prior odds to hypotheses isn’t exactly a very „frequentist“ thing to do. Now, with no reference to Bayesianism in sight, but heavy focus on frequentist significance tests and power, any quick reader can be forgiven to assume that the authors‘ arguments are firmly grounded in frequentist theory. However, no one can tell me that sentences like this are not prime examples of Bayesian thought:

[…] the lower the power of a study, the lower the probability that an observed effect that passes the required threshold of claiming its discovery (that is, reaching nominal statistical significance, such as p < 0.05) actually reflects a true effect.

If it walks like a Bayesian duck, and talks like a Bayesian duck, it is a Bayesian duck… right? Now, I do understand that the PPV can be meaningfully applied to medical diagnostic tests without any further reference to the Bayesian school of inference – because the prior probability of some disease being present in a randomly selected member of the population might be known, or can at least be estimated. (In fact, that’s exactly how Bayes‘ theorem is taught in every introductory course on probability theory: If you have a test with sensitivity X and specificity Y and a prevalence of the disease of Z, what is the probability yada yada yada…). However, I am pretty sure that we cannot just treat the probability of a scientific hypothesis being true the same way as the prevalence of some disease, without taking a huge leap into Bayesian territory – or at least, out of frequentist territory, where the assignment of probabilities to hypotheses is not valid. So, to re-emphasize my first point of criticism, I believe it to be a great oversight by the authors to not make clear to their readers that they are criticizing the use of frequentist inference based on notions that are not consistent with frequentist inference. (I mean, I’m thankful if a doctor tells me I have some problem – but I’d probably like to know if he/she is basing that diagnosis on a medical tradition I believe in.)

But enough of that – let’s give the authors a break, and look at the problem from the perspective of a Bayesian (or anybody who is comfortable with assigning odds to hypotheses). If we take the above formula and hold α and R constant, we get the posterior probability of H1/the PPV as a function of the power of the test. Some quick calculus tells us that this function is monotonically increasing for all allowed values of α and R. Thus, Button et al. are definitely, absolutely, undisputably mathematically right when they say that with lower power comes lower posterior probability (or PPV). However, that doesn’t mean that low power always leads to practically relevant differences in evidence. Let’s just try out the formula with some representative numbers. Let’s use the typical α of 0.05, and say that we have no prior preference for one hypothesis over the other, so R = 1. When we obtain a significant result from a study with the rather low power of 50%, what is your guess for the posterior probability of H1 being true? If it is anything below 90%, reconsider: it is actually 90.09090…%, or H1 is 10 times more likely to be true than H0, given the significant result. The generally agreed upon „good“ power of 80% would increase that number by about 4%. But okay, you say, a power of 50% isn’t actually that bad, many studies have much lower power than that. So let’s consider a study with the truly abyssmal power of 20%. Clearly, a significant result from such a trainwreck of a failure of a bad excuse of a study will not convince me of anything, with its puny posterior probability of … 80%? So, the H1 is 4 times more likely to be true than the H0? Huh, that doesn’t actually sound that bad… I mean, sure, it’s not as good as 94% or 90%, but from the way people were talking about low power lately, I assumed that the posterior probability of H1 would be so low it would fall out of the graph, stand up, look at me, climb creepily out of my computer screen and kill everyone I ever loved, before slowly devouring me, and then receding back into the monitor, into the void, waiting, waiting, forever waiting… Or, you know, be at least a bit more closer to 50%.

Here’s the graph (turquoise curve):

Now, of course, a Bayesian would choose the prior odds R very carefully. Button et al. themselves chose to report the numbers for R = 0.25, reflecting a situation in which we give H1 only a 20% chance of being true. This curve is also in the graph (in red). Of course, P(H1|sig) looks worse under this assumption – but also not too bad, considering how little faith we put into H1 to begin with. In any case, I don‘t quite understand why the authors present such low prior odds as „typical“ (in one of his prior papers, Ioannidis presented graphs similar to the one given here, but with R = 1 as the upper extreme of the scale). For me, it is difficult to believe that many (neuro)scientists would take the very great trouble of conducting studies if they did not have the (implicit or explicit) prior belief that their hypothesis had at least a 50% chance of being true.

But these mindgames about what prior odds a Bayesian would choose bring me to the another issue: A “true” Bayesian would also not bother about p-values and significance tests to begin with! Bayesian statistics offer so many “nicer” ways to perform inference (full posterior distributions, model comparison, model averaging, the odd Bayes factor…) that there is not really a good reason to reduce the data to a Bernoulli trial like that. In contrast, a frequentist who takes their own school of thought seriously cannot assign prior probabilities to H0 and H1, turning the whole enterprise into nothing more than a mindgame for them.

That is not to say that I don’t see the merit of Button et al.‘s perspective: looking at a frequentist field from a Bayesian (or “epidemiological“) point of view, we must definitely come to the conclusion that the research field as a whole has accumulated less evidence for its diverse H1’s than it could have if studies had had higher power. I do see a problem, however, if this argument is used to dismiss any single significant result as a fluke just because of low power. If a frequentist criticizes the result on this grounds, it is inconsistent, because he/she shouldn’t even care about the posterior probability to begin with – and if a Bayesian (or scientific „epidemiologist“) does it, he/she needs additional arguments, because, as we saw, even significant results from very low-powered studies put a surprising amount of posterior probability mass on H1.

So, what to make of this? Importantly, none of these points should ever be used as an excuse to deliberately plan a study with too little power. All of the reasons why low-powered studies are bad a priori still hold: you probably won’t be able to detect your effect of interest, thus you will waste time and resources, and when you don’t find your effect you’ll be tempted to squeeze findings out of a weak study using questionable research practices, etc. etc…  I am just trying to argue that, if we „believe“ in the frequentist logic of inference, there is little ground to criticize significant results from a low-powered study a posteriori. If a robust test obtains a significant result, however low the power, we cannot just dismiss it as a fluke without implicitly questioning the logic of frequentist inference as a whole. I am sympathetic to the intuition that a significant result from a study of ten people should be less credible than a significant result from a study of ten thousand – but this intuition is not reflected in the logic of significance tests. (The sample size only affects how small effects can be to still be labelled as significant – but the test remains completely agnostic to whether or not the effects are more or less „credible“). Indeed, if frequentists wanted to obtain some form of posterior measure of credibility, they would probably just have to adapt Bayesian inference – but there is limited place for significance tests in Bayes‘ brave new world.

##### Footnotes

[1] In hindsight, I am sorry for excluding the likelihoodist and fiducial folks here, but to my defense, I have never seen their ideas used in any empirical paper ever.

[2] Writing this, I noticed that for some reason I keep mentally equating frequentism and catholicism. Maybe because they are both traditionally dominant ideologies I was raised in, don’t believe in anymore, but remain member of out of a love/hate relationship (and because I’m to lazy to actively declare my apostasy)?

[3] Some people even go so far to say that you should be more convinced by significant results from small samples – e.g., Karl Friston in this paper. His arguments don’t convince me, but best see Tal Yarkoni’s response in his blog.

[4] So here I was now wondering if the Bayesian is a protestant, a Buddhist, or some hip form of I-don’t-even-think-in-categories-like-that-man. I chose the Buddhist because it made the sentence sound snappier. Also, I guess that for theoretical reasons, the Bayesian is slightly more interested in the type-I-error rate than the Buddhist is in the freedom-from-original-sin of Mary, but let’s move on.

## One thought on “With low power comes low credibility?”

1. Nace Mikus says:

awesome! insightful and witty! keep em coming!

Like


text:
# Solutions in a product of projective spaces

Solving systems over a product of projective spaces

When your system has a multiprojective structure, you can declare variables groups for accelerating the computations.

Here is a simple example for the following system defined over $\mathbb{CP}^1\times \mathbb{CP}^1$:

$$f(u,y,u,v) = \begin{bmatrix} xy - 6uv\\ x^2 - u^2 \end{bmatrix}.$$

The Julia code for the variable groups ${x,y}$ and ${u,v}$ is as follows.

julia> using HomotopyContinuation
julia> @polyvar x y u v
julia> f = [x*y - 6u*v, x^2 - u^2]
julia> S = solve(f, variable_groups=[(x,u), (y,v)])
Result with 2 solutions
==================================
• 2 non-singular solutions (0 real)
• 0 singular solutions (0 real)
• 2 paths tracked
• random seed: 127575

With out the declaration of groups we would have

julia> S = solve(f)
Result with 2 solutions
==================================
• 2 non-singular solutions (2 real)
• 0 singular solutions (0 real)
• 4 paths tracked
• random seed: 202895

The number of solutions found is the same, but the number of paths tracked is different. This is because

julia> bezout_number(f, variable_groups=[[x], [y]])
2
julia> bezout_number(f)
4

It is also possible to declare variable groups for affine systems:

julia> @polyvar x y z
julia> g = [x*y - 6, x^2 - 5]
julia> R = solve(g, variable_groups=[(x,), (y,)])
Result with 2 solutions
==================================
• 2 non-singular solutions (2 real)
• 0 singular solutions (0 real)
• 2 paths tracked
• random seed: 192959
julia> all(isaffine, R)
true


text:
## Edgeworth expansions in small noise asymptotics

June, 2005

Tech Report

### Author(s)

Lan Zhang, Per A. Mykland, and Yacine Aït-Sahalia

### Abstract

The paper considers Edgeworth expansions for estimators of volatility. Unlike the usual exanpsions, we have found that in order to obtain meaningful terms, one needs to let the size of the noise to go zero asymptotically. This is reflected in our expansions. The results have application to Cornish-Fisher inversion and bootstrapping.


text:
# Introspection

Standard

I have written many philosophical blog posts motivated by the idea of existence of reason for everything.  So far I have written (and revised) my point of view regarding topics like Being Alive, Loving MathematicsBecoming Mathematician and Dreaming Big.

A more fundamental and more disturbing question is:

Since each and everything is made up of atoms, what is the borderline between a living organism and non-living object.

Clearly, mathematics will fail to answer this question since there are no absolute quantifiers involved. But still we can try deducing an answer from logical arguments. Following video by Kurzgesagt – In a Nutshell illustrates my question:

We generally describe living organism as something capable of reproduction, growth and consciousness. So, can we convert anything into living organism by somehow adding artificial intelligence to it? Is internet itself a living organism?

Once you call yourself a living organism, the immediate question is about the purpose of your existence (since we believe that there is reason for everything). So we can use this as a quantifier to classify something as living and non-living. Many people have tried (and failed) to answer this question. I came across a possible answer for this question in the film Kubo and the two strings:

We live to write a story and then become immortal in memories of others in form of our stories.

Kubo and the two strings (© 2016, Focus Features)

I really liked this point of view. Being alive is all about being able to create memories. But this view point is very much human centred since we don’t know how other organisms (like other animals, plants, cells, organelles…) interact. Moreover, non-living objects also have stories associated with them (like monuments, paintings,…). So this view point also fails to capture the central idea for classification of something as living or non-living.

I will be happy to know your viewpoint of being able to classify something as living or non-living.

# Not all numbers are computable

Standard

When we hear the word number, symbols like 1,$\sqrt{2}$,¼, π (area enclosed by a unit circle), ι (symbol for $\sqrt{-1}$), ε (infinitesimal),  ω (ordinal infinity), ℵ (cardinal infinity), …. appear in our mind.  But not all numbers are  computable:

A computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number [encoded on its tape].

In other words, a real number is called computable if there is an algorithm which, given n, returns the first n digits of the number. This is equivalent to the existence of a program that enumerates the digits of the real number. For example, π is a computable number (why? see here).

Using Cantor’s diagonal argument on a list of all computable numbers, we get a non-computable number (here is the discussion). For example, a sum of series of real numbers called Chaitin’s constant, denoted by Ω, is a non-computable number (why? see here).

Fun fact: We don’t know whether π is a normal number or not (though we want it to be a normal number), but Ω is known to be a normal number (just like the Mahler’s Number discussed here).

# Celebrity Mathematicians

Standard

In my opinion, currency notes are one of the biggest motivation to learn arithmetical operations (like addition, multiplication,…). In fact, most of our elementary school problems are about buying a particular quantity of something.

Historically, there had been currencies notes featuring great mathematicians like Carl Friedrich Gauss, Leonard Euler and Rene Descartes. But, today there are no currencies featuring mathematicians. The database of currency notes featuring mathematicians is available here: http://web.olivet.edu/~hathaway/math_money.html

Since honouring people by featuring them on currency notes is politically challenging, government rather issues special postage stamps. The database of stamps featuring mathematicians is available here:  http://jeff560.tripod.com/stamps.html

Apart from illustrating various mathematical concepts (like graphs, metric system, binomial theorem… ) on stamps, India Post has issued stamps to honour mathematicians like Damodar Dharmananda Kosambi , Srinivasa Ramanujan Iyengar and Bertrand Russell.

# Real Numbers

Standard

Few days ago I found something very interesting on 9gag:

There are lots of interesting comments, but here is a proof from the comments:

…. Infinite x zero (as a limit) is indefinite. But infinite x zero (as a number) is zero. So lim( 0 x exp (x²) ) = 0 while lim ( f(X) x exp(X) ) with f(X)->0 is indefinite …

Though the statement made in the post is very vague and can lead to different opinions, like what about doing the product with surreal numbers, but we can safely avoid this by considering the product of real numbers only.

Now an immediate question should be (since every positive real number has a negative counterpart):

Is the sum of all real numbers zero?

In my opinion the answer should be “no”. As of now I don’t have a concrete proof but the intuition is:

Sum of a convergent series is the limit of partial sums, and for real numbers due to lack of starting point we can’t define a partial  sum. Hence we can’t compute the limit of this sum and the sum of series of real numbers doesn’t exist.

Moreover, since the sum of all “positive” real numbers is not a finite value (i.e. the series of positive real numbers is divergent) we conclude that we can’t rearrange the terms in series of “all” real numbers (Riemann Rearrangement Theorem). Thus the sum of real numbers can only be conditionally convergent. So, my above argument should work. Please let me know if you find a flaw in these reasonings.

Also I found following interesting answer on Quora:

The real numbers are uncountably infinite, and the standard notions of summation are only defined for countably many terms.

Note: Since we are dealing with infinite product and sum, we can’t argue using algebra of real numbers (like commutativity etc.).

# Packing Problems

Standard

Easy to state and hard to solve problems make mathematics interesting. Packing problems are one such type. In fact there is a very nice Wikipedia article on this topic:

Packing problems involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible.

I came across this problem a couple of years ago, while watching the following TED Talk by Eduardo Sáenz de Cabezón:

In this talk, the object of attraction is the Weaire-Phelan structure made from six 14-hedrons and two dodechedrons. This object is believed to be the solution of Kelvin’s problem:

How you can chop 3d space into cells of equal volume with the minimum surface area per cell?

The packing problem for higher dimensions was in news last year, since a problem about “Densest Packing Problem in Dimensions 8 and 24” was solved by a young mathematician (Maryna Viazovska). The mathematics involved in the solution is very advanced but we can start gaining knowledge from this book:

A classic reference in this field by two well known geniuses.

Recently, while reading Matt Parker’s book, I discovered a wonderful website called Packomania by Eckard Specht (Otto-von-Guericke-Universität Magdeburg) containing data about packing problems in 2D and 3D. (also checkout his Math4u.de website, it’s a good reference for elementary triangle geometry and inequalities problems.)

Screen-shot of Dr. Eckard Specht’s homepage, his online problem collection (with solutions; each problem in GIF, PS and PDF formats) and Packomania.

Computers also have a role to play in solving such optimization problems For example, in 2015 Thomas Hales formally proved Kepler’s Conjecture about 3D packing:

No arrangement of equally sized spheres filling space has a greater average density than that of the cubic close packing (face-centered cubic) and hexagonal close packing arrangements.

using HOL Light proof assistant.

The proof was a huge collaboration and was called Flyspeck Project. The details about this proof are available in this book:

NOTE: You can construct your own Truncated octahedron and Weaire-Phelan polyhedra by printing the nets available at Matt Parker’s website.

# Clocks

Standard

Clocks are amazing. They tell us time. In this post I want to talk about working of analog clocks. In case you haven’t seen an analog clock, this is how it looks like:

A wall clock, it’s working part in the back and inside of the working part.

But, what clocks have to do with mathematics? As I have mentioned several times, one major part of mathematics is about counting and clocks “count”! Clocks are amazing counting device, they perform mod 12 and mod 60 calculations (that’s why modular arithmetic is also called clock arithmetic).

Unfortunately, the ideal cases exist only in our abstract world of mathematics. In real world, whatever we build has some error percentage and our motive to minimize this error. A mathematical construction, called Stern-Brocot tree, was created to help build timepieces and understand number theory.

By Aaron Rotenberg (Own work) [GFDL or CC-BY-SA-3.0], via Wikimedia Commons

This “tree” gives an exceptionally elegant way to enumerate the positive rational numbers and is a surprisingly useful tool for constructing clocks.  For more information about this construction read this feature column article by David Austin.

Just like continued fractions, this tree gives us good rational approximations of a given real number. Clocks typically have a source of energy–such as a spring, a suspended weight, or a battery–that using gears turns a shaft at a fixed rate. We can increase the precision by using more number of gears of different teeth count in appropriate combination.

I will end this post with an example from Austin’s article:

Suppose we place a pinion on a shaft that rotates once every hour and ask to drive a wheel that rotates once in a mean tropical year, which is 365 days, 5 hours, 49 minutes. Converting both periods to minutes, we see that we need the ratio 720 / 525,949. The problem here is that the denominator 525,949 is prime so we cannot factor it. To obtain this ratio exactly, we cannot use gears with a smaller number of teeth. It is likewise impossible to find a multi-stage gear train to obtain this ratio. But, as we slide down the “tree” toward 720 / 525,949, the rationals we meet along the way will give good approximations with relatively small numerators and denominators. As we descend the Stern-Brocot tree towards 720 / 525,949, we find the fraction 196 / 143,175, which may be factored into four rational factors, 2/3, 2/25, 7/23 and 7/83. We can therefore construct a four-stage gear train and can get a pretty accurate clock.

I hope I have been able to convince you that clocks are much more interesting than they would appear and you should read the article by David Austin for further references.

# Arithmetic Operations

Standard

There are only 4 binary operations which we call “arithmetic operations”. These are:

• Subtractions (-)
• Multiplication (×)
• Division (÷)

Reading this fact, an obvious question is:

Why only four out of the infinitely many possible binary operations are said to be arithmetical?

Before presenting my attempt to answer this question, I would like to remind you that these are the operations you were taught when you learnt about numbers i.e. arithmetic.

In high school when $\sqrt{2}$ is introduced, we are told that real numbers are of two types: “rational” and “irrational”. Then in college when $\sqrt{-1}$ is introduced, we should be told that complex numbers are of two types: “algebraic” and “transcendental“.

As I have commented before, there are various number systems. And for each number system we have some valid arithmetical operations leading to a valid algebraic structure. So, only these 4 operations are entitled to be arithmetic operations because only these operations lead to valid algebraic numbers when operated on algebraic numbers.

Now this leads to another obvious question:

Why so much concerned about algebraic numbers?

To answer this question, we will have to look into the motivation for construction of various number systems like integers, rational, irrationals, complex numbers… The construction of these number systems has been motivated by our need to be able to solve polynomials of various degree (linear, quadratic, cubic…). And the Fundamental Theorem of Algebra says:

Every polynomial with rational coefficients and of degree n in variable $x$ has n solutions in  complex number system.

But, here is a catch. The number of complex numbers which can’t satisfy any polynomial (called transcendental numbers) is much more than the number of complex numbers which can satisfy a polynomial equation (called algebraic numbers). And we wish to find solutions of a polynomial equation (ie.e algebraic numbers) in terms of sum, difference, product, division or $m^{th}$ root of rational numbers (since coefficients were rational numbers). Therefore, sum, difference, product and division are only 4 possible arithmetic operations.

My previous statement may lead to a doubt that:

Why taking $m^{th}$ root isn’t an arithmetic operation?

This is because it isn’t a binary operation to start with, since we have fixed $m$. Also, taking $m^{th}$ root is allowed because of the multiplication property.

CAUTION: The reverse of $m^{th}$ root is multiplying a number with itself m times and it is obviously allowed. But, this doesn’t make the binary operation of taking exponents, $\alpha^{\beta}$ where $\alpha$ and $\beta$ are algebraic numbers, an arithmetic operation. For example, $2^{\sqrt{2}}$ is transcendental (called Gelfond–Schneider constant or Hilbert number) even though 2 and $\sqrt{2}$ are algebraic.


text:
# double integral $e^{-x^2-y^2}$

Given $$\iint\limits_{R}e ^{-x^2-y^2}dxdy$$ for $R=\{(x,y):x^2+y^2 \le 9\}$. Is it $$\int\limits_{0}^{2\pi}\int\limits_{0}^{3}e ^{-r^2} r dr d \theta$$

-
Yes it is.   –  Did Nov 1 '12 at 18:41
As I recall the $dxdy$ changes to $rdrd\theta$ in polar. So shouldn't there be an extra factor of $r$ in the transformed integral? If so that would mean one could substitute say $w=-r^2$ and make headway... –  coffeemath Nov 1 '12 at 18:45
is the answer pi- pi/(e^9) –  Jack F Nov 1 '12 at 18:45
You need to be very careful with missing the $dx$, $dy$, $dr$ and $d\theta$ in your integrals! –  JavaMan Nov 1 '12 at 18:49
Actually the outside integral goes to $2\pi$ so I'm getting $2\pi(1-e^{-9})$, i.e. twice your answer. –  coffeemath Nov 1 '12 at 18:50

I assume you're asking whether $$\int \text{d}x\int \text{d}y\ e^{-x^2-y^2} = \int_0^{2\pi}\text{d}\phi\int_0^3\text{d}r\ e^{-r^2}\ ,$$ where the first integral is restricted to $x^2+y^2\leq9$. The answer is 'no', as $\text{d}x\text{d}y=r\text{d}r\text{d}\phi$, so you need a further factor $r$ on the right-hand-side.


text:
# Circle has the equation  (x-2)^2 + (y-5)^2=100, how do you graph the circle using the center (h,k) radius r?

Dec 19, 2015

Draw a circle with center $\left(2 , 5\right)$ and radius $10$
The general equation for a circle centered at $\left(\textcolor{red}{h} , \textcolor{b l u e}{k}\right)$ with radius $\textcolor{g r e e n}{r}$ is:
$\textcolor{w h i t e}{\text{XXX}} {\left(x - \textcolor{red}{h}\right)}^{2} + {\left(y - \textcolor{b l u e}{k}\right)}^{2} = {\textcolor{g r e e n}{r}}^{2}$
${\left(x - \textcolor{red}{2}\right)}^{2} + {\left(y - \textcolor{b l u e}{5}\right)}^{2} = {\textcolor{g r e e n}{10}}^{2} \left(= 100\right)$