text:
### Archive

Posts Tagged ‘profit maximization’

## MHR, Regular Distributions and Myerson’s Lemma

May 30th, 2011 No comments

Monotone Hazard Rate (MHR) distributions and its superclass regular distributions keep appearing in the Mechanism Design literature and this is due to a very good reason: they are the class of distributions for which Myerson’s Optimal Auction is simple and natural. Let’s brief discuss some properties of those distributions. First, two definitions:

1. Hazard rate of a distribution $f$ : $h(z) = \frac{f(z)}{1-F(z)}$
2. Myerson virtual value of a distribution $f$ : $\phi(z) = z - \frac{1-F(z)}{f(z)}$

We can interpret the hazard rate in the following way: think of $T \sim f$ as a random variable that indicates the time that a light bulb will take to extinguish. If we are in time $t$ and the light bulb hasn’t extinguished so far, what is the probability it will extinguish in the next $\delta$ time:

$\mathbb{P}[T \leq t+\delta \vert T > t] \approx \frac{f(t) \delta}{1-F(t)}$

We say that a distribution is monotone hazard rate, if $h(z)$ is non-decreasing. This is very natural for light bulbs, for example. Many of the distributions that we are used to are MHR, for example, uniform, exponential and normal. The way that I like to think about MHR distributions is the following: if some distribution has hazard rate $h(z)$, then it means that $F'(z) = (1-F(z)) h(z)$. If we define $G(z) = 1-F(z)$, then $(log G(z))' = \frac{G'(z)}{G(z)} = -h(z)$, so:

$F(z) = 1-\text{exp}(-\int_0^z h(u) du)$

From this characterization, it is simple to see that the extremal distributions for this class, i.e. the distributions that are in the edge of being MHR and non-MHR are constant hazard rate, which correspond to the exponential distribution $F(z) = 1-e^{-\lambda z}$ for $z \in [0,\infty)$. They way I like to think about those distributions is that whenever you are able to prove something about the exponential distribution, then you can prove a similar statement about MHR distributions. Consider those three examples:

Example 1: $\mathbb{P}[\phi(z) \geq 0] \geq \frac{1}{e}$ for MHR distributions. This fact is straightforward for the exponential distribution. For the exponential distribution $\phi(z) = z-\lambda^{-1}$ and therefore

$\mathbb{P}[\phi(z) \geq 0] \geq \mathbb{P}[z > \lambda^{-1}] = 1-F(\lambda^{-1}) = e^{-1}$

but the proof for MHR is equally simple: Let $r = \inf \{z; \phi(z) \geq 0\}$, therefore $r h(r) \leq 1$.
$P\{ \phi(v) \geq 0\} = P\{ v \geq r \} = 1 - F(r) = e^{-\int_0^r h(u) du} \geq e^{-r h(r)} \geq e^{-1}$

Example 2: Given $z_1, z_2 \sim f$ iid where $f$ is MHR and $v_1 = \max \{z_1, z_2\}$ and $v_2 = \min \{z_1, z_2\}$, then $\mathbb{E}[v_2] \geq \frac{1}{3} \mathbb{E}[v_1]$. The proof for the exponential distribution is trivial, and in fact, this is tight for the exponential, the trick is to use the convexity of $z \mapsto \int_0^z h(u) du$. We use that $\int_0^{2z} h \geq 2 \int_0^z h$ in the following way:

$\mathbb{E} [v_2] = \int_0^\infty (1 - F(z))^2 dz = \int_0^\infty e^{-2 \int_0^z h} dz$

$\geq \int_0^\infty e^{-\int_0^{2z} h} dz= \frac{1}{2} \int_0^\infty 1 - F(z) dz = \frac{1}{2} \mathbb{E} [z]$

Since $\mathbb{E} [v_1 + v_2] = \mathbb{E} [z_1 + z_2] = 2 \mathbb{E} [z]$, we have that $\mathbb{E}[v_1] = 2 \mathbb{E}[z] - \mathbb{E}[v_2] \leq \frac{3}{2} \mathbb{E}[z]$. This way, we get: $\mathbb{E}[v_2] \geq \frac{1}{2}\mathbb{E}[z] \geq \frac{1}{2} \cdot \frac{2}{3} \mathbb{E}[v_1] = \frac{1}{3} \mathbb{E}[v_1]$

Example 3: For MHR distributions, there is a simple lemma that relates the virtual value and the real value and this lemma is quite useful in various settings: let $r = \inf \{z; \phi(z) > 0 \}$, then for $z \geq r$, $\phi(z) \geq z - r$. Again, this is tight for exponential distribution. The proof is quite trivial:

$x - \phi(x) = \frac{1-F(x)}{f(x)} \leq \frac{1-F(r)}{f(r)} = r$

Now, MHR distributions are a subclass of regular distributions, which are the distributions for which Myerson’s virtual value $\phi(z)$ is a monotone function. I usually find harder to think about regular distributions than to think about MHR (in fact, I don’t know so many examples that are regular, but not MHR. Here is one, though, called the equal-revenue-distribution. Consider $z \in [1, \infty)$ distributed according to $f(z) = 1/z^2$. The cumulative distribution is given by $F(z) = 1-1/z$. The interesting thing of this distribution is that posted prices get the same revenue regardless of the price. For example, if we post any price $r \in [1,\infty)$, then a customer with valuations $z \sim f$ buys the item if $z > r$ by price $r$, getting  revenue is $r (1-F(r)) = 1$. This can be expressed by the fact that $\phi(z) = 0$. I was a bit puzzled by this fact, because of Myerson’s Lemma:

Myerson Lemma: If a mechanism sells to some player that has valuation $v \sim f$ with probability $x(v)$ when he has value $v$, then the revenue is $\mathbb{E} [x(v) \phi(v)]$.

And it seemed that the auctioneers was doomed to get zero revenue, since $\phi(z) = 0$. For example, suppose we fix some price $r$ and we sell the item if $v \geq r$ by price $r$. Then it seems that Myerson’s Lemma should go through by a derivation like that (for this special case, although the general proof is quite similar):

$\mathbb{E} [x(v) \phi(v)] = \int_r^\infty \phi(z) f(z) dz = \int_r^\infty z f(z) - (1-F(z)) dz =$

$= \int_r^\infty [ z f(z) - \int_z^\infty f(u) du ] dz = \int_r^\infty z f(z) dz - \int_r^\infty \int_r^u f(u) dz du$

$= r (1-F(r))$

but those don’t seem to match, since one side is zero and the other is 1. The mistake we did above is classic, which is to calculate $\infty - \infty$. We wrote:

$\mathbb{E}[\phi(v)] = \int_r^\infty z f(z) dz - \int_r^\infty 1-F(z) dz$

but both are infinity! This made me realize that Myerson’s Lemma needs the condition that $\mathbb{E}[z] < \infty$, which is quite a natural a distribution over valuations of a good. So, one of the bugs of the the equal-revenue-distribution is that $\mathbb{E}[z] = \infty$. A family that is close to this, but doesn’t suffer this bug is: $f(z) = \frac{\alpha-1}{z^\alpha}$ for $z \in [1,\infty)$, then $F(z) = 1 - z^{1-\alpha}$. For $\alpha > 2$ we have $\mathbb{E}[v] < \infty$, then we get $\phi(z) = \frac{\alpha-2}{\alpha-1} z$.

Categories: theory Tags:

## More about hats and auctions

October 29th, 2009 No comments

In my last post about hats, I told I’ll soon post another version with some more problems, which I ended up not doing and would talk a bit more about those kind of problems. I ended up not doing, but here are a few nice problems:

Those ${n}$ people are again a room, each with a hat which is either black or white (picked with probability ${\frac{1}{2}}$ at random) and they can see the color of the other people’s hats but they can’t see their own color. They write in a piece of paper either “BLACK” or “WHITE”. The whole team wins if all of them get their colors right. The whole team loses, if at least one writes the wrong color. Before entering the room and getting the hats, they can strategyze. What is a strategy that makes them win with ${\frac{1}{2}}$ probability?

If they all choose their colors at random, the probability of winning is very small: ${\frac{1}{2^n}}$. So we should try to correlate them somehow. The solution is again related with error correcting codes. We can think of the hats as a string of bits. How to correct one bit if it is lost? The simple engineering solution is to add a parity check. We append to the string ${x_0, x_1, \hdots, x_n}$ a bit ${y = \sum_i x_i \mod 2}$. So, if bit ${i}$ is lost, we know it is ${x_i = (y + \sum_{j \neq i} x_j) \mod 2}$. We can use this idea to solve the puzzle above: if hats are places with ${\frac{1}{2}}$ probability, the parity check will be ${0}$ with probability ${\frac{1}{2}}$ and ${1}$ with probability ${\frac{1}{2}}$. They can decide before hand that everyone will use ${y = 0}$ and with probability ${\frac{1}{2}}$ they are right and everyone gets his hat color right. Now, let’s extend this problem in some ways:

The same problem, but there are ${k}$ hat colors, they are choosen independently with probability ${\frac{1}{k}}$ and they win if everyone gets his color right. Find a strategy that wins with probability ${\frac{1}{k}}$.

There are again ${k}$ hat colors, they are choosen independently with probability ${\frac{1}{k}}$ and they win if at least a fraction ${f}$ (${0 < f < 1}$) of the people guesses the right color. Find a strategy that wins with probability ${\frac{1}{fk}}$.

Again to the problem where we just have BLACK and WHITE colors, they are chosen with probability ${\frac{1}{2}}$ and everyone needs to find the right color to win, can you prove that ${\frac{1}{2}}$ is the best one can do? And what about the two other problems above?

The first two use variations of the parity check idea in the solution. For the second case, given any strategy of the players, for each string ${x \in \{0,1\}^n}$ they have probability ${p_x}$. Therefore the total probability of winning is ${\frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x}$. Let ${x' = (1-x_1, x_2, \hdots, x_n)}$, i.e., the same input but with the bit ${1}$ flipped. Notice that the answer of player ${1}$ is the same (or at least has the same probabilities) in both ${x}$ and ${x'}$, since he can’t distinguish between ${x}$ and ${x'}$. Therefore, ${p_{x} + p_{x'} \leq 1}$. So,

$\displaystyle 2 \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x = \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x + \frac{1}{2^n}\sum_{x \in \{0,1\}^n} p_x' \leq 1$

. This way, no strategy can have more than ${\frac{1}{2}}$ probability of winning.

Another variation of it:

Suppose now we have two colors BLACK and WHITE and the hats are drawn from one distribution ${D}$, i.e., we have a probability distribution over ${x \in \{0,1\}^n}$ and we draw the colors from that distribution. Notice that now the hats are not uncorrelated. How to win again with probability ${\frac{1}{2}}$ (to win, everyone needs the right answer).

I like a lot those hat problems. A friend of mine just pointed out to me that there is a very nice paper by Bobby Kleinberg generalizing several aspects of hat problems, for example, when players have limited visibility of other players hats.

I began being interested by this sort of problem after reading the Derandomization of Auctions paper. Hat guessing games are not just a good model for error correcting codes, but they are also a good model for truthful auctions. Consider an auction with a set ${N}$ single parameter agents, i.e., an auction where each player gives one bid ${b_i}$ indicating how much he is willing to pay to win. We have a set of constraints: ${\mathcal{X} \subseteq 2^N}$ of all feasible allocations. Based on the bids ${(b_i)_{i \in N}}$ we choose an allocation ${S \in \mathcal{X}}$ and we charge payments to the bidders. An example of a problem like this is the Digital Goods Auction, where ${\mathcal{X} = 2^N}$.

In this blog post, I discussed the concept of truthful auction. If an auction is randomized, an universal truthful auction is an auction that is truthful even if all the random bits in the mechanism are revealed to the bidders. Consider the Digital Goods Auction. We can characterize universal truthful digital goods auction as bid-independent auctions. A bid-independent auction is given by function ${f_i(b_{-i})}$, which associated for each ${b_{-i}}$ a random variable ${f_i(b_{-i})}$. In that auction, we offer the service to player ${i}$ at price ${f_i(b_{-i})}$. If ${b_i \geq f_i(b_{-i})}$ we allocate to ${i}$ and charge him ${f_i(b_{-i})}$. Otherwise, we don’t allocate and we charge nothing.

It is not hard to see that all universal truthful mechanisms are like that: if ${x_i(b_i)}$ is the probability that player ${i}$ gets the item bidding ${b_i}$ let ${U}$ be an uniform random variable on ${[0,1]}$ and define ${f_i(b_{-i}) = x_i^{-1}(U)}$. Notice that here ${x_i(.) = x_i(., b_{-i})}$, but we are inverting with respect to ${b_i}$. It is a simple exercise to prove that.

With this characterization, universal truthful auctions suddenly look very much like hat guessing games: we need to design a function that looks at everyone else’s bid but not on our own and in some sense, “guesses” what we probably have and with that calculated the price we offer. It would be great to be able to design a function that returns ${f(b_{-i}) = b_i}$. That is unfortunately impossible. But how to approximate ${b_i}$ nicely? Some papers, like the Derandomization of Auctions and Competitiveness via Consensus use this idea.

Categories: Tags:

## Competitive Auctions

September 17th, 2009 No comments

This week I will present the Theory Discussion Group about Competitive Auctions. It is mainly a serie of results in papers from Jason Hartline, Andrew Goldberg, Anna Karlin, Amos Fiat, … The first paper is Competitive Auctions and Digital Goods and the second is Competitive Generalized Auctions. My objective is to begin with a short introduction about Mechanism Design, the concept of truthfulness and the characterization of Truthful Mechanisms for Single Parameter Agents. Then we describe the Random Sampling Auction for Digital Goods and in the end we discuss open questions. I thought writting a blog post was a good way of organizing my ideas to the talk.

1. Mechanism Design and Truthfulness

A mechanism is an algorithm augmented with economic incentives. They are usually applied in the following context: there is an algorithmic problem and the input is distributed among several agents that have some interest in the final outcome and therefore they may try manipulate the algorithm. Today we restrict our attention to a specific class of mechanisms called single parameter agents. In that setting, there is a set ${N}$ consisting of ${n}$ agents and a service. Each agent ${i \in N}$ has a value ${v_i}$ for receiving the service and ${0}$ otherwise. We can think of ${v_i}$ as the maximum player ${i}$ is willing to pay for that service. We call an environment ${\mathcal{X} \subseteq 2^N}$ the subsets of the bidders that can be simultaneously served. For example:

1. Single item auction: ${\mathcal{X} =\{S; \vert S \vert \leq 1\}}$
2. Multi item auction: ${\mathcal{X} =\{S; \vert S \vert \leq k\}}$
3. Digital goods auction: ${\mathcal{X} =2^N}$
4. Matroid auctions: ${\mathcal{X}}$ is a matroid on ${N}$
5. Path auctions: ${N}$ is the set of edges in a graph and ${\mathcal{X}}$ is the set of ${s-t}$-paths in the graph
6. Knapsack auctions: there is a size ${s_i}$ for each ${i \in N}$ and ${S \in \mathcal{X}}$ iff ${\sum_{i \in S} s_i \leq C}$ for a fixed ${C}$

Most mechanism design problems focus in maximizing (or approximating) the social welfare, i.e., finding ${S \in \mathcal{X}}$ maximizing ${\sum_{i \in S} v_i}$. Our focus here will be maximizing the revenue of the auctioneer. Before we start searching for such a mechanism, we should first see which properties it is supposed to have, and maybe even first that that, define what we mean by a mechanism. In the first moment, the agents report their valuations ${v_i}$ (which can be their true valuations or lies), then the mechanism decides on an allocation ${S \subseteq N}$ (in a possibly randomized way) and charges a payment ${P_i}$ for each allocated agents. The profit of the auctioneer is ${\sum_{i \in S} P_i}$ and the utility of a bidder is:

\displaystyle u_i = \left\{ \begin{aligned} v_i - P_i &, i \in S \\ 0 &, i \notin S \end{aligned} \right.

The agents will report valuations so to maximize their final utility. We could either consider a general mechanism e calculate the profit/social welfare in the game induced by this mechanism or we could design an algorithm that gives incentives for the bidders to report their true valuation. The revelation principle says there is no loss of generality to consider only mechanisms of the second type. The intuition is: the mechanisms of the first type can be simulated by mechanisms of the second type. So, we restrict our attention to mechanisms of the second type, which we call truthful mechanisms. This definnition is clear for deterministic mechanisms but not so clear for randomized mechanisms. There are two such definitions:

• Universal Truthful mechanisms: distribution over deterministic truthful mechanisms, i.e., some coins are tossed and based on those coins, we choose a deterministic mechanism and run it. Even if the players knew the random coins, the mechanism would still be truthful.
• Truthful in Expectation mechanisms: Let ${u_i(b_i)}$ be the utility of agent ${i}$ if he bids ${b_i}$. Since it is a randomized mechanism, then it is random variable. Truthful in expectation means that ${\mathop{\mathbb E}[u_i(v_i)] \geq \mathop{\mathbb E}[u_i(b_i)], \forall b_i}$.

Clearly all Universal Truthful mechanisms are Truthful in Expectation but the converse is not true. Now, before we proceed, we will redefine a mechanism in a more formal way so that it will be easier to reason about:

Definition 1 A mechanism ${\mathcal{M}}$ is a function that associated for each ${v \in {\mathbb R}^N}$ a distribution over elements of ${\mathcal{X}}$.

Theorem 2 Let ${x_i(v) = \sum_{i \in S \in \mathcal{X}} Pr_{\mathcal{M}(v)}[S]}$ be the probability that ${i}$ is allocated by the mechanism given ${v}$ is reported. The mechanism is truthful iff ${x_i(v)}$ is monotone and each allocated bidder is charged payment:

$\displaystyle P_i = v_i - \frac{1}{x_i(v_i, v_{-i})} \int_0^{v_i} x_i(w, v_{-i}) dw$

This is a classical theorem by Myerson about the characterization of truthful auctions. It is not hard to see that the auction define above is truthful. We just need to check that ${x_i(v_i, v_{-i}) (v_i - P(v_i, v_{-i})) \geq x_i(v'_i, v_{-i}) (v_i - P(v'_i, v_{-i}))}$ for all ${v'_i}$. The opposite is trickier but is also not hard to see.

Note that this characterization implies the following characterization of deterministic truthful auctions, i.e., auctions that map each ${v \in {\mathbb R}^N}$ to a set ${S \in \mathcal{X}}$, i.e., the probability distribution is concentrated in one set.

Theorem 3 A mechanism is a truthful deterministic auction iff there is a functions ${f_i(b_{-i})}$ such that for each we allocate to bidder ${i}$ iff ${b_i \geq f_i(b_{-i})}$ and in case it is allocated, we charge payment ${f_i(b_{-i})}$.

It is actually easy to generate this function. Given a mechanism, ${b_i \mapsto x_i(b_i, b_{-i})}$ is a monotone and is a ${\{0,1\}}$-function. Let ${f_i(b_{-i})}$ the point where it transitions from ${0}$ to ${1}$. Now, we can give a similar characterization for Universal Truthful Mechanism:

Theorem 4 A mechanism is a universal truthful randomized auction if there are functions ${f_i(r,b_{-i})}$ such that for each we allocate to bidder ${i}$ iff ${b_i \geq f_i(r,b_{-i})}$ and in case it is allocated, we charge payment ${f_i(r,b_{-i})}$, where ${r}$ are random bits.

2. Profit benchmarks

Let’s consider a Digital Goods auction, where ${\mathcal{X} = 2^N}$. Two natural goals for profit extraction would be ${\mathcal{T}(v) = \sum_i v_i}$ and ${\mathcal{F}(v) = \max_i i v_i}$ where we can think of ${v_1 \geq v_2 \geq \hdots \geq v_n}$, the first is the best profit you can extract charging different prices and the second is the best profit you can hope to extract by charging a fixed price. Unfortunately it is impossible to design a mechanism that even ${O(1)}$-approximates both benchmarks on every input. The intuition is that ${v_1}$ can be much larger then the rest, so there is no way of setting ${f_1(b_{-1})}$ in a proper way. Under the assumption that the first value is not much larger than the second, we can do a good profit approximation, though. This motivates us to find an universal truthful mechanism that approximates the following profit benchmark:

$\displaystyle \mathcal{F}^{(2)}(v) = \max_{i \geq 2} i v_i$

which is the highest single-price profit we can get selling to at least ${2}$ agents. We will show a truthful mechanism that ${4}$-approximates this benchmark.

3. Profit Extractors

Profit extractor are building blocks of many mechanisms. The goal of a profit extractor is, given a constant target profit ${C}$, extract that profit from a set of agents if that is possible. In this first moment, let’s see ${C}$ as an exogenous constant. Consider the following mechanism called CostShare${_C (v)}$: find the largest ${k}$ s.t. ${k \cdot v_k \geq C}$. Then allocate to

Lemma 5 CostShare${_C}$ is a truthful profit-extractor that can extract profit ${C}$ whenever ${\mathcal{F}(v) = \max_i i v_i \geq C}$.

Proof: It is clear that it can extract profit at most ${C}$ if ${\mathcal{F}(v) \geq C}$. We just need to prove it is a truthful mechanism and this can be done by checking the characterization of truthful mechanisms. Suppose that under CostShare${_C (v)}$ exacly ${k}$ bidders are getting the item, then let’s look at a bidder ${i}$. If bidder ${i}$ is not getting the item, then his value is smaller than ${C/k}$, otherwise we could incluse all bidders up to ${i}$ and sell for a price ${C/k_1}$ for some ${k_1 > k}$. It is easy to see that bidder ${i}$ will get the item just if he changes his value ${v_i}$ to some value greater or equal than ${C/k}$.

On the other hand, it ${i}$ is currently getting the item under ${v}$, then increasing his value won’t make it change. It is also clear that for any value ${v_i \geq C/k}$, he will still get the item. For ${v_i < C/k}$ he doesn’t get it. Suppose it got, then at least ${k+1}$ people get the item, because the price they sell it to ${i}$ must be less than ${v_i < C/k}$. Thefore, increasing ${v_i}$ back to its original value, we could still sell it to ${k+1}$ players, what is a contradiction, since we assumed we were selling to ${k}$ players.

We checked monotonicity and we also need to check the payments, but it is straightforward to check they satisfy the second condition, since ${x_i(v_i) = 1}$ for ${v_i \geq C/k}$ and zero instead. $\Box$

4. Random Sampling Auctions

Now, using that profit extractor as a building block, the main idea is to estimate ${C}$ smaller than ${\mathcal{F}(v)}$ for one subset of the agents and extract that profit from them using a profit extractor. First we partition ${N}$ is two sets ${N'}$ and ${N''}$ tossing a coin for each agent to decide in which set we will place it, then we calculate ${\mathcal{F}' = \mathcal{F}(v_{N'})}$ and ${\mathcal{F}'' = \mathcal{F}(v_{N''})}$. Now, we run CostShare${_{\mathcal{F}'} (v'')}$ and CostShare${_{\mathcal{F}''} (v')}$. This is called Random Cost Sharing Auction.

Theorem 6 The Random Cost Sharing Auction is a truthful auction whose revenue ${4}$-approximates the benchmark ${\mathcal{F}^{(2)}(v)}$.

Proof: Let ${\mathcal{R}}$ be a random variable associated with the revenue of the Sampling Auction mechanism. It is clear that ${\mathcal{R} = \min \{ \mathcal{F}', \mathcal{F}'' \}}$. Let’s write ${\mathcal{F}^{(2)}(v) = kp}$ meaning that we sell ${k}$ items at price ${p}$. Let ${k = k' + k''}$ where ${k'}$ and ${k''}$ are the items among those ${k}$ items that went to ${N'}$ and ${N''}$ respectively. Then, clearly ${\mathcal{F}' \geq p k'}$ and ${\mathcal{F}'' \geq p k''}$, what gives us:

$\displaystyle \frac{\mathcal{R}}{\mathcal{F}^{(2)}} = \frac{\min\{\mathcal{F}', \mathcal{F}''\}}{\mathcal{F}^{(2)}} \geq \frac{\min\{k'p, k''p\}}{kp} = \frac{\min\{k', k''\}}{k}$

and from there, it is a straighforward probability exercise:

$\displaystyle \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} = \mathop{\mathbb E}\left[{ \frac{\min\{k', k''\}}{k} }\right] = \frac{1}{k} \sum_{i=1}^{k-1} \min\{ i, k-i \} \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}$

since:

$\displaystyle \frac{k}{2} = \sum_{i = 0}^k i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k} \leq \frac{k}{4} + 2 \sum_{i = 0}^{k/2} i \begin{pmatrix} k \\ i \end{pmatrix} 2^{-k}$

and therefore:

$\displaystyle \frac{\mathop{\mathbb E}[{\mathcal{R}}]}{\mathcal{F}^{(2)}} \geq \frac{1}{4}$ $\Box$

This similar approximations can be extended to more general environments with very little change. For example, for multi-unit auctions, where ${\mathcal{X} = \{ S; \vert S \vert \leq k \}}$ we use the benchmark ${\mathcal{F}^{(2,k)} = \max_{2 \leq i \leq k} i v_i}$ and we can be ${O(1)}$-competitive against it, by random-sampling, evaluating ${\mathcal{F}^{(1,k)} = \max_{\leq i \leq k} i v_i}$ on both sets and running a profit extractor on both. The profit extractor is a simple generalization of the previous one.

Categories: theory Tags:


text:
• ### Appraisal of the BAO equations(1708.03068)

March 20, 2019 astro-ph.CO, astro-ph.GA
The commonly used isotropic baryon acoustic oscillation (BAO) equation is an approximation derived from empirical and geometric arguments, and the equivalent anisotropic BAO equations were written down by analogy. Using fit-lines to CMB compatible solutions, {\Omega}_{m} and H_{0} values have been derived for BAO studies without recourse to those equations, and have been applied for their appraisal. The isotropic expression becomes problematic at precision levels of ~1 percent or better, and at high redshift values of z = / >1. Most revealing, the anisotropic equations, D_{M}(z)/D_{M,fid}(z)={\alpha}_{\perp}r_{d}/r_{d,fid}, and D_{H}(z)/D_{H,fid}(z)={\alpha}_{\parallel}r_{d}/r_{d,fid}, are invalid when {\alpha} ~ 1, since under that condition, D_{M}(z)/D_{M,fid}(z)=D_{H}(z)/D_{H,fid}(z)=r_{d}/r_{d,fid} ~ 1, and neither equation can be satisfied with anisotropic data. (The ratios are respectively, the angular distance, the inverse Hubble parameter, and the comoving acoustic horizon, each divided by its fiducial value). {\alpha} can be driven towards unity for any data set, e.g., by applying the derived {\Omega}_{m}, H_{0} pair as the core of a second iteration fiducial parameter-set. Thus, the anisotropic equations are untenable. Dissociated from the BAO equations, we have extracted weighted mean values of {\Omega}_{mw}=0.299+/-0.011 and H_{0w}=68.6+/-0.7 km s-1 Mpc-1 for eight uncorrelated BAO data sets.
• ### Spins of primordial black holes formed in the matter-dominated phase of the Universe(1707.03595)

Angular momentum plays very important roles in the formation of PBHs in the matter-dominated phase if it lasts sufficiently long. In fact, most collapsing masses are bounced back due to centrifugal force, since angular momentum significantly grows before collapse. As a consequence, most of the formed PBHs are rapidly rotating near the extreme value $a_{*}=1$, where $a_{*}$ is the nondimensional Kerr parameter at their formation. The smaller the density fluctuation $\sigma_{H}$ at horizon entry is, the stronger the tendency towards the extreme rotation. Combining the effect of angular momentum with that of anisotropy, we estimate the black hole production rate. We find that the production rate suffers from suppression dominantly due to angular momentum for a smaller value of $\sigma_{H}$, while due to anisotrpopy for a larger value of $\sigma_{H}$. We argue that matter domination significantly enhances the production of PBHs despite the suppression. If the matter-dominated phase does not last so long, the effect of the finite duration significantly suppresses PBH formation and weakens the tendency towards large spins. (abridged)
• ### Effects of Completeness and Purity on Cluster Dark Energy Constraints(1611.05468)

March 15, 2019 astro-ph.CO
The statistical properties of galaxy clusters can only be used for cosmological purposes if observational effects related to cluster detection are accurately characterized. These effects include the selection function associated to cluster finder algorithms and survey strategy. The importance of the selection becomes apparent when different cluster finders are applied to the same galaxy catalog, producing different cluster samples. We consider parametrized functional forms for the observable-mass relation, its scatter as well as the completeness and purity of cluster samples, and study how prior knowledge on these function parameters affects dark energy constraints derived from cluster statistics. Under the assumption that completeness and purity reach 50 % at masses around 10^{13.5} Msun/h, we find that self-calibration of selection parameters in current and upcoming cluster surveys is possible, while still allowing for competitive dark energy constraints. We consider a fiducial survey with specifications similar to those of the Dark Energy Survey (DES) with 5000 deg^2, maximum redshift of zmax ~ 1.0 and threshold observed mass M_{th} ~ 10^{13.8} Msun/h, such that completeness and purity ~ 60 % - 80 % at masses around M_{th}. Perfect knowledge of all selection parameters allows for constraining a constant dark energy equation of state to sigma(w)=0.033. Employing a joint fit including self-calibration of the effective selection degrades constraints to sigma(w)=0.046. External calibrations at the level of 1 % in the parameters of the observable-mass relation and completeness/purity functions are necessary to improve the joint constraints to sigma(w)=0.041. In the lack of knowledge of selection parameters, future experiments probing larger areas and greater depths suffer from stronger relative degradations on dark energy constraints compared to current surveys.
• ### A Convolutional Neural Network For Cosmic String Detection in CMB Temperature Maps(1708.08878)

March 14, 2019 hep-th, hep-ph, gr-qc, astro-ph.CO
We present in detail the convolutional neural network used in our previous work to detect cosmic strings in cosmic microwave background (CMB) temperature anisotropy maps. By training this neural network on numerically generated CMB temperature maps, with and without cosmic strings, the network can produce prediction maps that locate the position of the cosmic strings and provide a probabilistic estimate of the value of the string tension $G\mu$. Supplying noiseless simulations of CMB maps with arcmin resolution to the network resulted in the accurate determination both of string locations and string tension for sky maps having strings with string tension as low as $G\mu=5\times10^{-9}$. The code is publicly available online. Though we trained the network with a long straight string toy model, we show the network performs well with realistic Nambu-Goto simulations.
• ### Vacuum Condensate Picture of Quantum Gravity(1707.08188)

March 14, 2019 hep-th, gr-qc, astro-ph.CO
In quantum gravity perturbation theory in Newton's constant G is known to be badly divergent, and as a result not very useful. Nevertheless some of the most interesting phenomena in physics are often associated with non-analytic behavior in the coupling constant and the existence of nontrivial quantum condensates. It is therefore possible that pathologies encountered in the case of gravity are more likely the result of inadequate analytical treatment, and not necessarily a reflection of some intrinsic insurmountable problem. The nonperturbative treatment of quantum gravity via the Regge-Wheeler lattice path integral formulation reveals the existence of a new phase involving a nontrivial gravitational vacuum condensate, and a new set of scaling exponents characterizing both the running of G and the long-distance behavior of invariant correlation functions. The appearance of such a gravitational condensate is viewed as analogous to the (equally nonperturbative) gluon and chiral condensates known to describe the physical vacuum of QCD. The resulting quantum theory of gravity is highly constrained, and its physical predictions are found to depend only on one adjustable parameter, a genuinely nonperturbative scale xi in many ways analogous to the scaling violation parameter Lambda MSbar of QCD. Recent results point to significant deviations from classical gravity on distance scales approaching the effective infrared cutoff set by the observed cosmological constant. Such subtle quantum effects are expected to be initially small on current cosmological scales, but could become detectable in future high precision satellite experiments.
• ### Testing CCDM Cosmology with the Radiation Temperature-Redshift Relation(1605.04857)

March 13, 2019 gr-qc, astro-ph.CO
The standard $\Lambda$CDM model can be mimicked at the background and perturbative levels (linear and non-linear) by a class of gravitationally induced particle production cosmology dubbed CCDM cosmology. However, the radiation component in the CCDM model follows a slightly different temperature-redshift $T(z)$-law which depends on an extra parameter, $\nu_r$, describing the subdominant photon production rate. Here we perform a statistical analysis based on a compilation of 36 recent measurements of $T(z)$ at low and intermediate redshifts. The likelihood of the production rate in CCDM cosmologies is constrained by $\nu_r = 0.024^{+0.026}_{-0.024}$ ($1\sigma$ confidence level), thereby showing that $\Lambda$CDM ($\nu_r=0$) is still compatible with the adopted data sample. Although being hardly differentiated in the dynamic sector (cosmic history and matter fluctuations), the so-called thermal sector (temperature law, abundances of thermal relics and CMB power spectrum) offers a clear possibility for crucial tests confronting $\Lambda$CDM and CCDM cosmologies.
• ### Cosmic shear without shape noise(1311.1489)

March 8, 2019 astro-ph.CO
We describe a new method for reducing the shape noise in weak lensing measurements by an order of magnitude. Our method relies on spectroscopic measurements of disk galaxy rotation and makes use of the Tully-Fisher relation in order to control for the intrinsic orientations of galaxy disks. For this new proposed method, so-called Kinematic Lensing (KL), the shape noise ceases to be an important source of statistical error. We use the CosmoLike software package to simulate likelihood analyses for two Kinematic Lensing survey concepts (roughly similar in scale to Dark Energy Survey Task Force Stage III and Stage IV missions) and compare their constraining power to a cosmic shear survey from the Large Synoptic Survey Telescope (LSST). Our forecasts in seven-dimensional cosmological parameter space include statistical uncertainties resulting from shape noise, cosmic variance, halo sample variance, and higher-order moments of the density field. We marginalize over systematic uncertainties arising from photometric redshift errors and shear calibration biases considering both optimistic and conservative assumptions about LSST systematic errors. We find that even the KL-Stage III is highly competitive with the optimistic LSST scenario, while evading the most important sources of theoretical and observational systematic error inherent in traditional weak lensing techniques. Furthermore, the KL technique enables a narrow-bin cosmic shear tomography approach to tightly constrain time-dependent signatures in the dark energy phenomenon.
• ### Towards Searching for Entangled Photons in the CMB Sky(1701.03437)

March 4, 2019 quant-ph, hep-th, hep-ph, astro-ph.CO
We explore the possibility of detecting entangled photon pairs from cosmic microwave background or other cosmological sources coming from two patches of the sky. The measurements use two detectors with different photon polarizer directions. When two photon sources are separated by a large angle relative to the earth, such that each detector has only one photon source in its field of view, a null test of unentangled photons can be performed. The deviation from this unentangled background is, in principle, the signature of photon entanglement. To confirm whether the deviation is consistent with entangled photons, we derive a photon polarization correlation to compare with, similar to that in a Bell inequality measurement. However, since photon coincidence measurement cannot be used to discriminate unentangled cosmic photons, it is unlikely that the correlation expectation value alone can violate Bell inequality to provide the signature for entanglement.
• ### Anisotropic cosmological solutions to the $Y(R)F^2$ gravity(1203.1531)

July 31, 2019 gr-qc, astro-ph.CO
We investigate anisotropic cosmological solutions of the theory with non-minimal couplings between electromagnetic fields and gravity in $Y(R) F^2$ form. After we derive the field equations by the variational principle, we look for spatially flat cosmological solutions with magnetic fields or electric fields. Then we give exact anisotropic solutions by assuming the hyperbolic expansion functions. We observe that the solutions approach to the isotropic case in late-times.
• ### Probing the missing baryons with the Sunyaev-Zel'dovich effect from filaments(1709.10378)

March 1, 2019 astro-ph.CO
Observations of galaxies and galaxy clusters in the local universe can account for only $\sim\,10\%$ of the total baryon content. Cosmological simulations predict that the `missing baryons' are spread throughout filamentary structures in the cosmic web, forming a low-density gas with temperatures of $10^5-10^7\,\!$K. We search for this warm-hot intergalactic medium (WHIM) by stacking the Planck Compton $y$-parameter map of the thermal Sunyaev-Zel'dovich (tSZ) effect for 1,002,334 pairs of CMASS galaxies from the Sloan Digital Sky Survey. We model the contribution from the galaxy halo pairs assuming spherical symmetry, finding a residual tSZ signal at the $2.9\mbox{$\sigma$}$ level from a stacked filament of length $10.5\,h^{-1}\,\rm Mpc$ with a Compton parameter magnitude $y=(0.6\pm0.2)\times10^{-8}$. We consider possible sources of contamination and conclude that bound gas in haloes may contribute only up to $20\%$ of the measured filamentary signal. To estimate the filament gas properties we measure the gravitational lensing signal for the same sample of galaxy pairs; in combination with the tSZ signal, this yields an inferred gas density of $\rho_{\rm b}=(5.5\pm 2.9)\times\bar{\rho_{\rm b}}$ with a temperature $T=(2.7\pm 1.7) \times 10^6\,$K. This result is consistent with the predicted WHIM properties, and overall the filamentary gas can account for $11\pm 7\%$ of the total baryon content of the Universe. We also see evidence that the gas filament extends beyond the galaxy pair. Averaging over this longer baseline boosts the significance of the tSZ signal and increases the associated baryon content to $28\pm 12\%$ of the global value.
• ### A Search for Warm/Hot Gas Filaments Between Pairs of SDSS Luminous Red Galaxies(1709.05024)

March 1, 2019 astro-ph.CO
We search the Planck data for a thermal Sunyaev-Zel'dovich (tSZ) signal due to gas filaments between pairs of Luminous Red Galaxies (LRG's) taken from the Sloan Digital Sky Survey Data Release 12 (SDSS/DR12). We identify $\sim$260,000 LRG pairs in the DR12 catalog that lie within 6-10 $h^{-1} \mathrm{Mpc}$ of each other in tangential direction and within 6 $h^{-1} \mathrm{Mpc}$ in radial direction. We stack pairs by rotating and scaling the angular positions of each LRG so they lie on a common reference frame, then we subtract a circularly symmetric halo from each member of the pair to search for a residual signal between the pair members. We find a statistically significant (5.3$\sigma$) signal between LRG pairs in the stacked data with a magnitude $\Delta y = (1.31 \pm 0.25) \times 10^{-8}$. The uncertainty is estimated from two Monte Carlo null tests which also establish the reliability of our analysis. Assuming a simple, isothermal, cylindrical filament model of electron over-density with a radial density profile proportional to $r_c/r$ (as determined from simulations), where $r$ is the perpendicular distance from the cylinder axis and $r_c$ is the core radius of the density profile, we constrain the product of over-density and filament temperature to be $\delta_c \times (T_{\rm e}/10^7 \, {\rm K}) \times (r_c/0.5h^{-1} \, {\rm Mpc}) = 2.7 \pm 0.5$. To our knowledge, this is the first detection of filamentary gas at over-densities typical of cosmological large-scale structure. We compare our result to the BAHAMAS suite of cosmological hydrodynamic simulations (McCarthy et al. 2017) and find a slightly lower, but marginally consistent Comptonization excess, $\Delta y = (0.84 \pm 0.24) \times 10^{-8}$.
• ### Dark Energy Survey Year 1 Results: Cosmological Constraints from Galaxy Clustering and Weak Lensing(1708.01530)

March 1, 2019 astro-ph.CO
We present cosmological results from a combined analysis of galaxy clustering and weak gravitational lensing, using 1321 deg$^2$ of $griz$ imaging data from the first year of the Dark Energy Survey (DES Y1). We combine three two-point functions: (i) the cosmic shear correlation function of 26 million source galaxies in four redshift bins, (ii) the galaxy angular autocorrelation function of 650,000 luminous red galaxies in five redshift bins, and (iii) the galaxy-shear cross-correlation of luminous red galaxy positions and source galaxy shears. To demonstrate the robustness of these results, we use independent pairs of galaxy shape, photometric redshift estimation and validation, and likelihood analysis pipelines. To prevent confirmation bias, the bulk of the analysis was carried out while blind to the true results; we describe an extensive suite of systematics checks performed and passed during this blinded phase. The data are modeled in flat $\Lambda$CDM and $w$CDM cosmologies, marginalizing over 20 nuisance parameters, varying 6 (for $\Lambda$CDM) or 7 (for $w$CDM) cosmological parameters including the neutrino mass density and including the 457 $\times$ 457 element analytic covariance matrix. We find consistent cosmological results from these three two-point functions, and from their combination obtain $S_8 \equiv \sigma_8 (\Omega_m/0.3)^{0.5} = 0.783^{+0.021}_{-0.025}$ and $\Omega_m = 0.264^{+0.032}_{-0.019}$ for $\Lambda$CDM for $w$CDM, we find $S_8 = 0.794^{+0.029}_{-0.027}$, $\Omega_m = 0.279^{+0.043}_{-0.022}$, and $w=-0.80^{+0.20}_{-0.22}$ at 68% CL. The precision of these DES Y1 results rivals that from the Planck cosmic microwave background measurements, allowing a comparison of structure in the very early and late Universe on equal terms. Although the DES Y1 best-fit values for $S_8$ and $\Omega_m$ are lower than the central values from Planck ...
• ### Number counts, confusion, mapping issues and sky coverage analysis for radio continuum surveys through EMU Early Science, EMU-ASKAP, and WODAN especially for cosmology science goals(1612.08226)

Feb. 25, 2019 astro-ph.CO
Looking deep into the space in search for truth has been a long time goal of humanity. With the development of new technologies and observational techniques, we are now well equipped to see objects billions of light years away from us. In this study we are going to discuss some of the challenges radio astronomers face while observing radio continuum sources. We will discuss issues related to rms noise, confusion, position accuracy, shot noise and how these issues can affect observation results, data analysis and the science goals we are trying to achieve. We will mainly focus on the Evolutionary Map of the Universe (EMU-ASKAP) sky survey, EMU Early science survey and Westerbork Observations of the Deep APERTIF Northern sky (WODAN), for our study. The study will also be useful for future surveys like with possible continuum surveys through MeerKAT (e.g. MIGHTEE) and SKA-1. The late time Integrated Sachs-Wolfe (ISW) effect detection is one of the major areas of research related to dark energy cosmology. We will particularly discuss how technical, data analysis and mapping issues, affect galaxy over/under density dependent science goals like the detection of the late time Integrated Sachs-Wolfe (ISW) effect through wide field radio continuum surveys.
• ### Primordial fluctuations of scale factor in closed Universe in Einstein$-$Cartan gravity(1612.06292)

Feb. 25, 2019 gr-qc, astro-ph.CO
We consider a homogeneous and isotropic Universe, described by the minisuperspace Lagrangian with the scale factor as a generalized coordinate. We show that the energy of a closed Universe is zero. We apply the uncertainty principle to this Lagrangian and propose that the quantum uncertainty of the scale factor causes the primordial fluctuations of the matter density. We use the dynamics of the early Universe in the Einstein$-$Cartan theory of gravity with spin and torsion, which eliminates the big-bang singularity and replaces it with a nonsingular bounce. Quantum particle production in highly curved spacetime generates a finite period of cosmic inflation that is consistent with the Planck satellite data. From the inflated primordial fluctuations, we determine the magnitude of the temperature fluctuations in the cosmic microwave background, as a function of the numbers of the thermal degrees of freedom of elementary particles and the particle production coefficient, which is the only unknown parameter.
• ### Primordial-black-hole mergers in dark-matter spikes(1708.08449)

Feb. 23, 2019 astro-ph.CO
It has been suggested that primordial black holes (PBHs) of roughly 30 solar masses could make up the dark matter and if so, might account for the recent detections by LIGO involving binary black holes in this mass range. It has also been argued that the super-massive black holes (SMBHs) that reside at galactic centers may be surrounded by extremely-dense dark-matter (DM) spikes. Here we show that the rate for PBH mergers in these spikes may well exceed the merger rate considered before in galactic dark-matter halos, depending on the magnitudes of two competing effects on the DM spikes: depletion of PBHs due to relaxation and replenishment due to PBHs in loss cone. This may provide a plausible explanation for the current rate of detection of mergers of 30-solar-mass black holes, even if PBHs make up a subdominant contribution to the dark matter. The gravitational-wave signals from such events will always originate in galactic centers, as opposed to those from halos, which are expected to have little correlation with luminous-galaxy positions.
• ### Constraining quantum collapse inflationary models with current data: The semiclassical approach(1709.06237)

Feb. 20, 2019 astro-ph.CO
The hypothesis of the self-induced collapse of the inflaton wave function was introduced as a candidate for the physical process responsible for the emergence of inhomogeneity and anisotropy at all scales. In particular, we consider different proposal for the precise form of the dynamics of the inflaton wave function: i) the GRW-type collapse schemes proposals based on spontaneous individual collapses which generate non-vanishing expectation values of various physical quantities taken as ansatz modifications of the standard inflationary scenario; ii) the proposal based on a Continuous Spontaneous Localization (CSL) type modification of the Schr\"odinger evolution of the inflaton wave function, based on a natural choice of collapse operator. We perform a systematic analysis within the semi-classical gravity approximation, of the standing of those models considering a full quasi-de sitter expansion scenario. We note that the predictions for the Cosmic Microwave Background (CMB) temperature and polarization spectrum differ slightly from those of the standard cosmological model. We also analyse these proposals with a Bayesian model comparison using recent CMB and Baryonic Acoustic Oscillations (BAO) data. Our results show a moderate preference of the joint CMB and BAO data for one of the studied collapse schemes model over the $\Lambda$CDM one, while there is no preference when only CMB data are considered. Additionally, analysis using CMB data provide the same Bayesian evidence for both the CSL and standard models, i.e. the data have not preference between the simplicity of the LCDM model and the complexity of the collapse scenario.
• ### Gravitational waves from bubble dynamics: Beyond the Envelope(1707.03111)

Feb. 19, 2019 hep-th, hep-ph, gr-qc, astro-ph.CO
We study gravitational-wave production from bubble dynamics (bubble collisions and sound waves) during a cosmic first-order phase transition with an analytic approach. We first propose modeling the system with the thin-wall approximation but without the envelope approximation often adopted in the literature, in order to take bubble propagation after collisions into account. The bubble walls in our setup are considered as modeling the scalar field configuration and/or the bulk motion of the fluid. We next write down analytic expressions for the gravitational-wave spectrum, and evaluate them with numerical methods. It is found that, in the long-lasting limit of the collided bubble walls, the spectrum grows from $\propto f^3$ to $\propto f^1$ in low frequencies, showing a significant enhancement compared to the one with the envelope approximation. It is also found that the spectrum saturates in the same limit, indicating a decrease in the correlation of the energy-momentum tensor at late times. We also discuss the implications of our results to gravitational-wave production both from bubble collisions (scalar dynamics) and sound waves (fluid dynamics).
• ### Does Quartessence Ease Tensions?(1704.06277)

Feb. 18, 2019 astro-ph.CO
Tensions between cosmic microwave background observations and the growth of the large-scale structure inferred from late-time probes pose a serious challenge to the concordance $\Lambda$CDM cosmological model. State-of-the-art data from the Planck satellite predicts a higher rate of structure growth than what preferred by low-redshift observables. Such tension has hitherto eluded conclusive explanations in terms of straightforward modifications to $\Lambda$CDM, e.g. the inclusion of massive neutrinos or a dynamical dark energy component. Here, we investigate models of 'quartessence' -- a single dark component mimicking both dark matter and dark energy -- whose non-vanishing sound speed inhibits structure growth at late times on scales smaller than its corresponding Jeans' length. In principle, this could reconcile high- and low-redshift observations. We put this hypothesis to test against temperature and polarisation spectra from the latest Planck release, SDSS DR12 measurements of baryon acoustic oscillations and redshift-space distortions, and cosmic shear correlation functions from KiDS. This the first time that any specific model of quartessence is applied to actual data. We show that, if we naively apply $\Lambda$CDM nonlinear prescription to quartessence, the combined data sets allow for tight constraints on the model parameters. Apparently, quartessence alleviates the tension between the total matter fraction and late-time structure clustering, although in fact the tension is transferred from the latter to the quartessence sound speed parameter. However, we found that this strongly depends upon information from nonlinear scales. Indeed, if we relax this assumption, quartessence models appear still viable. For this reason, we argue that the nonlinear behaviour of quartessence deserves further investigation and may lead to a deeper understanding of the physics of the dark Universe.
• ### Quantification of the multi-streaming effect in Redshift Space Distortion(1611.09075)

Feb. 13, 2019 astro-ph.CO
Both multi-streaming (random motion) and bulk motion cause the Finger-of-God (FoG) effect in redshift space distortion (RSD). We apply a direct measurement of the multi-streaming effect in RSD from simulations, proving that it induces an additional, non-negligible FoG damping to the redshift space density power spectrum. We show that, including the multi-streaming effect, the RSD modelling is significantly improved. We also provide a theoretical explanation based on halo model for the measured effect, including a fitting formula with one to two free parameters. The improved understanding of FoG helps break the $f\sigma_8-\sigma_v$ degeneracy in RSD cosmology, and has the potential of significantly improving cosmological constraints.
• ### The Sources of Extreme Ultraviolet and Soft X-ray Backgrounds(1710.07295)

Feb. 12, 2019 astro-ph.CO, astro-ph.GA
Radiation in the extreme ultraviolet (EUV) and soft X-ray holds clues to the location of the missing baryons, the energetics in stellar feedback processes, and the cosmic enrichment history. Additionally, EUV and soft X-ray photons help determine the ionization state of most intergalactic and circumgalactic metals, shaping the rate at which cosmic gas cools. Unfortunately, this band is extremely difficult to probe observationally due to absorption from the Galaxy. In this paper, we model the contributions of various sources to the cosmic EUV and soft X-ray backgrounds. We bracket the contribution from (1) quasars, (2) X-ray binaries, (3) hot interstellar gas, (4) circumgalactic gas, (5) virialized gas, and (6) supersoft sources, developing models that extrapolate into these bands using both empirical and theoretical inputs. While quasars are traditionally assumed to dominate these backgrounds, we discuss the substantial uncertainty in their contribution. Furthermore, we find that hot intrahalo gases likely emit an O(1) fraction of this radiation at low redshifts, and that interstellar and circumgalactic emission potentially contribute tens of percent to these backgrounds at all redshifts. We estimate that uncertainties in the angular-averaged background intensity impact the ionization corrections for common circumgalactic and intergalactic metal absorption lines by ~0.3-1 dex, and we show that local emissions are comparable to the cosmic background only at r_prox = 10-100 kpc from Milky Way-like galaxies.
• ### Analysis of branon dark matter and extra-dimensional models with AMS-02(1709.09819)

Feb. 11, 2019 hep-ph, astro-ph.CO
In the following work, we compute the positron production from branon dark matter annihilations in order to constrain extra-dimensional theories. By having assumed that the positron fraction measured by AMS-02 is well explained just with astrophysical sources, exclusion diagrams for the branon mass and the tension of the brane, the two parameters characterising the branon phenomenology become possible. Our analysis has been performed for a minimal and a medium diffusion model in one extra dimension for both pseudo-isothermal and Navarro Frenck White dark matter haloes. Our constraints in the dark matter mass candidate range between 200 GeV and 100 TeV. Combined with previous cosmological analyses and experimental data in colliders, it allows us to set bounds on the parameter space of branons. In particular, we have discarded regions in the mass-tension diagram up to a branon mass of 28 TeV for the pseudo-Isothermal prole and minimal diffusion, and 63 TeV for the Navarro-Frenck-White profile and medium diffusion.
• ### Measuring the baryon fraction in cluster of galaxies with Kinematic Sunyaev Zeldovich and a Standard Candle(1703.02021)

Feb. 11, 2019 astro-ph.CO
We propose a new method to use the kinematic Sunyaev-Zeldovich for measuring the baryon fraction in cluster of galaxies. In this proposal we need a configuration in which a supernova Type Ia resides in a brightest cluster galaxy of intermediate redshift clusters. We show this supernova Type Ia can be used to measure the bulk velocity of a galaxy cluster. We assert that the redshift range of $0.4<z<0.6$ is suitable for this proposal. The main contribution to the deviation of standard candles distance modulus from cosmological background prediction in this redshift range comes from peculiar velocity of the host galaxy and gravitational lensing. In this work we argue that by the knowledge of the bulk flow of the galaxy cluster and the cosmic microwave background photons temperature change due to kinematic Sunyaev-Zeldovich, we can constrain the baryon fraction of galaxy cluster. The probability of this configuration for clusters is obtained. We estimate in a conservative parameter estimation the large synoptic survey telescope can find spectroscopically followed $\sim 4500$ galaxy clusters with a bright cluster galaxy which hosts a type Ia Supernova each year. Finally, we show the improving of the distance modulus measurement is the key improvement in future surveys which will be crucial to detect the baryon fraction of cluster with the proposed method.
• ### Minimal inflationary cosmologies and constraints on reheating(1610.00173)

Feb. 7, 2019 hep-ph, astro-ph.CO
With the growing consensus on simple power law inflation models not being favored by the PLANCK observation, dynamics for the non-standard form of the inflaton potential gain significant interest in the recent past. In this paper, we analyze in great detail classes of phenomenologically motivated inflationary models with non-polynomial potential which are the generalization of the potential introduced in \cite{mhiggs}. After the end of inflation, inflaton field will coherently oscillate around its minimum. Depending upon the initial amplitude of the oscillation and coupling parameters standard parametric resonance phenomena will occur. Therefore, we will study how the inflationary model parameters play an important role in understanding the resonant structure of our model under study. Subsequently, the universe will go through the perturbative reheating phase. However, without any specific model consideration, we further study the constraints on our models based on model independent reheating constraint analysis.
• ### Gravitational lensing by wave dark matter halos(1707.09929)

Feb. 6, 2019 gr-qc, astro-ph.CO
Wave Dark Matter (WaveDM) has recently gained attention as a viable candidate to account for the dark matter content of the Universe. In this paper we explore the extent to which dark matter halos in this model, and under what conditions, are able to reproduce strong lensing systems. First, we analytically explore the lensing properties of the model -- finding that a pure WaveDM density profile, a soliton profile, produces a weaker lensing effect than other similar cored profiles. Then we analyze models with a soliton embedded in an NFW profile, as has been found in numerical simulations of structure formation. We use a benchmark model with a boson mass of $m_a=10^{-22}{\rm eV}$, for which we see that there is a bi-modality in the contribution of the external NFW part of the profile, and actually some of the free parameters associated with it are not well constrained. We find that for configurations with boson masses $10^{-23}$ -- $10^{-22}{\rm eV}$, a range of masses preferred by dwarf galaxy kinematics, the soliton profile alone can fit the data but its size is incompatible with the luminous extent of the lens galaxies. Likewise, boson masses of the order of $10^{-21}{\rm eV}$, which would be consistent with Lyman-$\alpha$ constraints and consist of more compact soliton configurations, necessarily require the NFW part in order to reproduce the observed Einstein radii. We then conclude that lens systems impose a conservative lower bound $m_a > 10^{-24}$ and that the NFW envelope around the soliton must be present to satisfy the observational requirements.
• ### Maximum a posteriori CMB lensing reconstruction(1704.08230)

Feb. 4, 2019 astro-ph.CO
Gravitational lensing of the CMB is a valuable cosmological signal that correlates to tracers of large-scale structure and acts as a important source of confusion for primordial $B$-mode polarization. State-of-the-art lensing reconstruction analyses use quadratic estimators, which are easily applicable to data. However, these estimators are known to be suboptimal, in particular for polarization, and large improvements are expected to be possible for high signal-to-noise polarization experiments. We develop a method and numerical code, $\rm{LensIt}$, that is able to find efficiently the most probable lensing map, introducing no significant approximations to the lensed CMB likelihood, and applicable to beamed and masked data with inhomogeneous noise. It works by iteratively reconstructing the primordial unlensed CMB using a deflection estimate and its inverse, and removing residual lensing from these maps with quadratic estimator techniques. Roughly linear computational cost is maintained due to fast convergence of iterative searches, combined with the local nature of lensing. The method achieves the maximal improvement in signal to noise expected from analytical considerations on the unmasked parts of the sky. Delensing with this optimal map leads to forecast tensor-to-scalar ratio parameter errors improved by a factor $\simeq 2$ compared to the quadratic estimator in a CMB stage IV configuration.

format: plain


text:
# 3.9. Notes for building LAMMPS on Windows

## 3.9.1. General remarks

LAMMPS is developed and tested primarily on Linux machines. The vast majority of HPC clusters and supercomputers today run on Linux as well. While portability to other platforms is desired, it is not always achieved. The LAMMPS developers are dependent on LAMMPS users giving feedback and providing assistance in resolving portability issues. This is particularly true for compiling LAMMPS on Windows, since this platform has significant differences in some low-level functionality.

## 3.9.2. Running Linux on Windows

Before trying to build LAMMPS on Windows, please consider if the pre-compiled Windows binary packages are sufficient for your needs. If it is necessary for you to compile LAMMPS on a Windows machine (e.g. because it is your main desktop), please also consider using a virtual machine software and compile and run LAMMPS in a Linux virtual machine, or - if you have a sufficiently up-to-date Windows 10 installation - consider using the Windows subsystem for Linux. This optional Windows feature allows you to run the bash shell from Ubuntu from within Windows and from there on, you can pretty much use that shell like you are running on an Ubuntu Linux machine (e.g. installing software via apt-get and more). For more details on that, please see this tutorial.

## 3.9.3. Using a GNU GCC ported to Windows

One option for compiling LAMMPS on Windows natively that has been known to work in the past is to install a bash shell, unix shell utilities, perl, GNU make, and a GNU compiler ported to Windows. The Cygwin package provides a unix/linux interface to low-level Windows functions, so LAMMPS can be compiled on Windows. The necessary (minor) modifications to LAMMPS are included, but may not always up-to-date for recently added functionality and the corresponding new code. A machine makefile for using cygwin for the old build system is provided. Using CMake for this mode of compilation is untested and not likely to work.

When compiling for Windows do not set the -DLAMMPS_MEMALIGN define in the LMP_INC makefile variable and add -lwsock32 -lpsapi to the linker flags in LIB makefile variable. Try adding -static-libgcc or -static or both to the linker flags when your resulting LAMMPS Windows executable complains about missing .dll files. The CMake configuration should set this up automatically, but is untested.

In case of problems, you are recommended to contact somebody with experience in using Cygwin. If you do come across portability problems requiring changes to the LAMMPS source code, or figure out corrections yourself, please report them on the lammps-users mailing list, or file them as an issue or pull request on the LAMMPS GitHub project.

## 3.9.4. Using a cross-compiler

If you need to provide custom LAMMPS binaries for Windows, but do not need to do the compilation on Windows, please consider using a Linux to Windows cross-compiler. This is how currently the Windows binary packages are created by the LAMMPS developers. Because of that, this is probably the currently best tested and supported way to build LAMMPS executables for Windows. A CMake preset selecting all packages compatible with this cross-compilation build is provided. The GPU package can only be compiled with OpenCL support. To compile with MPI support, a pre-compiled library and the corresponding header files are required. When building with CMake the matching package will be downloaded automatically, but MPI support has to be explicitly enabled with -DBUILD_MPI=on.

Please keep in mind, though, that this only applies to compiling LAMMPS. Whether the resulting binaries do work correctly is rarely tested by the LAMMPS developers. We instead rely on the feedback of the users of these pre-compiled LAMMPS packages for Windows. We will try to resolve issues to the best of our abilities if we become aware of them. However this is subject to time constraints and focus on HPC platforms.

## 3.9.5. Native Visual C++ support

Support for the Visual C++ compilers is currently not available. The CMake build system is capable of creating suitable a Visual Studio style build environment, but the LAMMPS source code itself is not ported to fully support Visual C++. Volunteers to take on this task are welcome.


text:
×

# Can you solve it?

Note by Swapnil Rajawat
3 years, 4 months ago

Sort by:

yeah this question appeared in KVPY 2012 ! The solution is easy, [Please check out the Formatting Guide since the sq root and squares are not appearing]

\sqrt{3^{2}+p^{2}} = \sqrt{2} . \sqrt{3^{2}+p^{2}-17}

3^{2} + p^{2} = 2(3^{2} + p^{2} -17)

therefore, 0 = 3^{2} + p^{2} - 34

| p | = 5

~Hence Solved~ · 3 years, 4 months ago

ok that's perfectly correct. · 3 years, 4 months ago


text:
# Math Help - Loci in the Complex Plane

1. ## Loci in the Complex Plane

Does anyone have any good links for loci in the complex plane? Preferably a video.
The book I has skims over it a bit too much.

Also if someone could help me with this question on my paper, I have no idea what to do, not in any rush though.

The complex numbers z and and w are represented respectively, by points P(x,y) and Q(u,v) in Argand Diagrams and
$w = z(1-z)$.

(a). Show that
$v=y(1-2x)$
and find an expression for u in terms of x and y.

(b). The point P moves along the line y=x. Find the Cartesian equation and the locus of Q.

Diolch yn fawr

2. Here's what I have so far:
a.
$
\begin{array}{lll}
z=x+yi & w = u+vi & w = z-z^2 \\
& & \\
\to u+vi & = &
x+yi - (x+yi)^2 \\
& = & x+yi-(x^2+2xyi-y^2)\\
& = & x+yi-x^2-2xyi+y^2 \\
& = & (x-x^2+y^2)+(y-2xy)i \\
& & \\
\therefore u=x-x^2+y^2 & , & v= y-2xy \\
& & v=y(1-2x)
\end{array}
$

b. $
y = x \:\:
\therefore
\begin{array}{lll}
u = x-x^2+x^2 & & v=x(1-2x)\\
u = x & & v=x-2x^2
\end{array}
$

No idea what now, pretty sure I need to eliminate x and only get things in terms of u and v but have no idea how.

Cheers

3. Originally Posted by alexgeek
Here's what I have so far:
a.
$
\begin{array}{lll}
z=x+yi & w = u+vi & w = z-z^2 \\
& & \\
\to u+vi & = &
x+yi - (x+yi)^2 \\
& = & x+yi-(x^2+2xyi-y^2)\\
& = & x+yi-x^2-2xyi+y^2 \\
& = & (x-x^2+y^2)+(y-2xy)i \\
& & \\
\therefore u=x-x^2+y^2 & , & v= y-2xy \\
& & v=y(1-2x)
\end{array}
$
Yes, that's correct.

b. $
y = x \:\:
\therefore
\begin{array}{lll}
u = x-x^2+x^2 & & v=x(1-2x)\\
u = x & & v=x-2x^2
\end{array}
$

No idea what now, pretty sure I need to eliminate x and only get things in terms of u and v but have no idea how.

Cheers
You've done almost everything! Yes, $u= x$ and $v= x- 2x^2$. And since $x= u$, $v= x- 2x^2= u- 2u^2$. That is, of course, a parabola.

4. I feel a fool now ha. Thanks for that!


text:
# Location final image diveraging and converging lens

1. Aug 10, 2008

### crazyog

1. The problem statement, all variables and given/known data
A 1.5 cm tall object is placed 0.50 m to the left of a diverging lens with a focal length of 0.20 m. A converging lens with a focal length of 0.17 m is located 0.08 m to the right of the diverging lens.
a)What is the location of the final image with respect to the object? answer = final image is lcoated 1.3 m to the right of the object
b)What is the height and orientation with respect to the orginal object of the final image?

2. Relevant equations
1/q+1/p =1/f
M=hi/h =-q/p

3. The attempt at a solution
Ok, well i need to figure out part a before I can do part b...so
I did 1/p1+1/q2=1/f
1/0.5+1/q=-1/0.2 (negative focal length for diverging)
solve for q = -0.14285
I'm a little confused, when I draw my picture to help me visualize where the image is...i dont know whether or not to add the 0.08 or subtract it ...
I thought I would add it (negative q means the image is in front of the lens (virtual))
so i did...
1/0.22285 +1/q2=1/0.17
1/q2 = 1.39 but if i inverse it then it become 0.71 and that is not the answer....hm

2. Aug 10, 2008

### alphysicist

Hi crazyog,

I think everything you've done so far looks fine, but you still have one more step to go. You have found the image distance for the second lens, which tells you where the final image is relative to the second lens. But the question asks you to find out how far the final image is from the object.

3. Aug 10, 2008

### crazyog

Oh ok I think I get it, so since it is the distance from the object to the image I want to add 0.71683 + 0.08+0.5 = 1.3 and the image is to the right
thanks!!

ok now for part b...
I know M= -q/p so would I do -0.7168/.22285 = -3.216
and we know the orginal height M=hi/h
-3.216=hi/1.5
but the answer is not 1.4...what am i missing?

4. Aug 10, 2008

### crazyog

Oh I just realized when I find the magnification due to the first lens, and then the second lens, the product of the two gave me the final magnification and I used this with the orginal height to find it to be 1.4 ....
why does the product give me the final magnification? and inverted?

5. Aug 10, 2008

### crazyog

Ok I just realized again haha...my first M is postive and 2nd negative

M1=-2/7
M2=-3.216
-0.918=hi/1.5
hi=-1.4 so inverted
ok I get the answer!! but I dont understand why it is the product why not add together?

6. Aug 10, 2008

### alphysicist

The product gives the overall magnification, because of the way the system of lens works. For example, just to use easy numbers, let's say your first lens had a magnification of -2, and the second lens had a magnification of -3. So the image of the first lens is twice as large as its object and inverted, and the image of the second lens is three times larger than its object and inverted. But the image of the first lens is the object for the second lens, so overall the final image is 6 times larger than the (original) object; also, since its inverted twice, the final image is upright.

or in equation form:

\begin{align} m_{\rm total}&=m_1 m_2\nonumber\\ m_{\rm total} &=(-2) (-3) = +6\nonumber \end{align}

7. Aug 10, 2008

### crazyog

Oh ok that makes a lot more sense! Thank you so much! You have been a great help :) !!

8. Aug 10, 2008


text:
# When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?

A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.

If the machine halts when it's in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.

Now, when introduce $$\epsilon$$ transitions the machine doesn't necessarily halt when the whole input string has been consumed, for it is possible that there are still $$\epsilon$$ transitions available.

Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $$\epsilon$$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $$\epsilon$$ transitions until we reach a state where no other transition is available?

With a DFA, we can say "the DFA is in state $$q$$ after reading the input". That is well-defined for a DFA.


text:
18 questions linked to/from Can Reduce *really* not solve for x here?
24 views

### Why doesn't mathematica recognize the exponential expression with Solve but it will plot it written exactly the same way? [duplicate]

I can Plot these two functions written exactly this way and see intersection but Solve will not recognize the exponential expression. Please help me with feedback... Solve[1/3Exp[-x/5]==Cos[x], x]
93 views

### How can I solve $\coth (2 x )=x$? [duplicate]

I have this equation $$\coth (2 x )=x$$ and I want to solve it to find $x$. The methods Solve and Reduce do not work. Coth[2 x] == x
57 views

### I need help solving this hyperbolic equation [duplicate]

I have some data and I'd like to calculate the radius of curvature. The formula is: $$R_{oc}\space Sinh\left[\frac{D_{LSS}}{R_{OC}}\right]=\frac{s_*}{\theta_*}$$ Noting that $s_*$ is sh, $\theta_*$ ...
184 views

### NSolve/Solve with equations containing periodic functions

I first tried this command: NSolve[(2 Cos[x] Sin[x])/x^2 - (2 Sin[x]^2)/x^3 == 0, x, Reals] which yields "This system cannot be solved with the methods available ...
432 views

### Why Wolfram|Alpha can solve an equation but not Mathematica? [duplicate]

I want to numerically solve $$\cosh\left(\frac{1}{x}\right)-\frac{1}{x^2}\sinh\left(\frac{1}{x}\right)=0.$$ A strange thing is that Wolfram|Alpha it solves it perfectly, but Mathematica I have this: ...
193 views

### Solve $1/a - \sin(1/a)$ [duplicate]

I need to find $a$ from this equation: Solve[(2*b)/a - 1/(n*π)*Sin[(2*n*π*b)/a] - 1/2 == 0, a] but I get the response: Solve::nsmet: This system cannot be ...
11k views

### Solving simple transcendental equation [duplicate]

I would like to solve Tan[x] == 1/x Solve[] does not work, suggesting that there is no nice analytical solution for x. Surprisingly, NSolve[] does not work ...
4k views

### How do I solve for the roots of $\sin(x) - x^2=0$? [duplicate]

I have defined h[x] := Sin[x] - x^2. When I submit Solve[h[x] == 0, x], Mathematica tells me Solve::nsmet: This system ...
4k views

### How to obtain all solutions for Cos[x] Cosh[x] == 1?

Both analytical solutions or all numerical solutions are good enough. FindRoot may be a possible solution, any better solution? ...
69 views

### Problem with solving an equation [duplicate]

I dont understand why Mathematica cannot solve this equation: Solve[Log[x^2 + 5] + 0.5 x + 1 == 0, x] I get this error message: Solve::inex: Solve was unable to solve the system with inexact ...


text:
# derivatives_of_inverse

## 2695 days ago by chrisphan

x = var('x') def tang_and_inv_tan1(a, showtanglines=true): graph1 = plot(exp(x), x, -4, 2, rgbcolor=(0, 0, 0.5), ymin=-4, ymax=7, aspect_ratio=1) graph2 = plot(log(x), x, 0.01, 7, rgbcolor=(0, 0.5, 0), ymin=-4, ymax=7, aspect_ratio=1) mirrorline = plot(x, x, -4, 7, rgbcolor=(0.5, 0, 0.5), linestyle=":", ymin=-4, ymax=7, aspect_ratio=1) reflectline = line([[a, exp(a)], [exp(a), a]], linestyle=":", ymin=-4, ymax=7, aspect_ratio=1) lab1 = text("(" + str(round(a, 3)) + ", " + str(round(exp(a), 3)) + ")", [a + 1.5, exp(a)], rgbcolor=(0,0,0)) lab2 = text("(" + str(round(exp(a), 3)) + ", " + str(round(a, 3)) + ")", [exp(a) + 1.5, a], rgbcolor=(0,0,0)) tanline1 = plot(exp(a)*(x-a) + exp(a), x, -4, 7, rgbcolor=(0.5, 0, 0), ymin=-4, ymax=7, aspect_ratio=1) tanline2 = plot((1/exp(a))*(x - exp(a)) + a, -4, 7, rgbcolor=(0.5, 0, 0), ymin=-4, ymax=7, aspect_ratio=1) pts = point([a, exp(a)], rgbcolor=(1, 0, 0)) + point([exp(a), a], rgbcolor=(1, 0, 0), ymin=-4, ymax=7, aspect_ratio=1) outimg = graph1 + graph2 + pts + mirrorline + reflectline + lab1 + lab2 if showtanglines: outimg = outimg + tanline1 + tanline2 return(outimg) html("Suppose $f$ is a one-to-one function. For every point $P_1 = (a, b)$
on the graph of $y = f(x)$, there is a corresponding point $P_2 = (b, a)$ on the
graph of $y = f^{-1}(x)$. The points $P_1$ and $P_2$ are reflections of each other
over the line $y=x$. In the illustration below, $a = 1.2$ and $b = 3.32$.") show(tang_and_inv_tan1(1.2, false)) html("Now, suppose we have a line tangent to $y = f(x)$ at the point $(a,b)$. The
slope $m$ of this line will be $m = f'(a)$. Since the graph of $y = f^{-1}(x)$ is
the reflection of the graph of $y = f(x)$, the line tangent to $y = f^{-1}(x)$
at $(b,a)$ will have a slope of $1/m$, the reciprocal of $m$.") show(tang_and_inv_tan1(1.2, true)) anim = animate([tang_and_inv_tan1(0.1*t, true) for t in range(-28, 18)], ymin=-4, ymax=7, aspect_ratio=1) html("Here is an animation showing the two tangent lines at various values of $a$:") show(anim)
 Suppose f is a one-to-one function. For every point P_1 = (a, b)on the graph of y = f(x), there is a corresponding point P_2 = (b, a) on thegraph of y = f^{-1}(x). The points P_1 and P_2 are reflections of each otherover the line y=x. In the illustration below, a = 1.2 and b = 3.32.Now, suppose we have a line tangent to y = f(x) at the point (a,b). Theslope m of this line will be m = f'(a). Since the graph of y = f^{-1}(x) isthe reflection of the graph of y = f(x), the line tangent to y = f^{-1}(x)at (b,a) will have a slope of 1/m, the reciprocal of m.Here is an animation showing the two tangent lines at various values of a: Suppose f is a one-to-one function. For every point P_1 = (a, b)on the graph of y = f(x), there is a corresponding point P_2 = (b, a) on thegraph of y = f^{-1}(x). The points P_1 and P_2 are reflections of each otherover the line y=x. In the illustration below, a = 1.2 and b = 3.32.Now, suppose we have a line tangent to y = f(x) at the point (a,b). Theslope m of this line will be m = f'(a). Since the graph of y = f^{-1}(x) isthe reflection of the graph of y = f(x), the line tangent to y = f^{-1}(x)at (b,a) will have a slope of 1/m, the reciprocal of m.Here is an animation showing the two tangent lines at various values of a:
def tang_and_inv_tan2(a, showtanglines=true, showpts=true): graph1 = plot(sin(x), x, (-1/2)*pi, (1/2)*pi, rgbcolor=(0, 0, 0.5)) graph1_dotted1 = plot(sin(x), x, (-5/8)*pi, (-1/2)*pi, rgbcolor=(0, 0, 0.5), linestyle=":") graph1_dotted2 = plot(sin(x), x, (1/2)*pi, (5/8)*pi, rgbcolor=(0, 0, 0.5), linestyle=":") graph2 = plot(asin(x), x, -1, 1, rgbcolor=(0, 0.5, 0)) mirrorline = plot(x, x, (-2/3)*pi, (2/3)*pi, rgbcolor=(0.5, 0, 0.5), linestyle=":") reflectline = line([[a, sin(a)], [sin(a), a]], linestyle=":") lab1 = text("(" + str(round(a, 3)) + ", " + str(round(sin(a), 3)) + ")", [a + 0.4, sin(a)- 0.125], rgbcolor=(0,0,0)) lab2 = text("(" + str(round(sin(a), 3)) + ", " + str(round(a, 3)) + ")", [sin(a) - 0.5, a], rgbcolor=(0,0,0)) tanline1 = plot(cos(a)*(x-a) + sin(a), x, (-2/3)*pi, (2/3)*pi, rgbcolor=(0.5, 0, 0)) tanline2 = plot((1/cos(a))*(x - sin(a)) + a, (-2/3)*pi, (2/3)*pi, rgbcolor=(0.5, 0, 0)) pts = point([a, sin(a)], rgbcolor=(1, 0, 0)) + point([sin(a), a], rgbcolor=(1, 0, 0)) outimg = graph1 + graph1_dotted1 + graph1_dotted2 + graph2 + mirrorline if showpts: outimg = outimg + pts + reflectline + lab1 + lab2 if showtanglines: outimg = outimg + tanline1 + tanline2 return(outimg) html("Here is the graph of $y = \sin x$, with domain restricted to $[-\pi/2, \pi/2]$,
and the inverse function $y = \\arcsin x$.") show(tang_and_inv_tan2(pi/3, false, false), xmin=(-5/8)*pi, xmax=5/8*pi, ymin=(-1/2)*pi, ymax=(1/2)*pi, aspect_ratio=1) html("Here in an animation showing the lines tangent to $y = \sin x$ at $(a, \sin a)$
 and $y = \\arcsin x$ at $(\sin a, a)$, for various values of $a$:") anim2 = animate([tang_and_inv_tan2(0.1*t, true, true) for t in range(-15, 15)], xmin=(-5/8)*pi, xmax=(5/8)*pi, ymin=-1.5, ymax=1.5, aspect_ratio=1) show(anim2)
 Here is the graph of y = \sin x, with domain restricted to [-\pi/2, \pi/2],and the inverse function y = \arcsin x.Here in an animation showing the lines tangent to y = \sin x at (a, \sin a) and y = \arcsin x at (\sin a, a), for various values of a: Here is the graph of y = \sin x, with domain restricted to [-\pi/2, \pi/2],and the inverse function y = \arcsin x.Here in an animation showing the lines tangent to y = \sin x at (a, \sin a) and y = \arcsin x at (\sin a, a), for various values of a:
html("Here is a plot of $f(x) = \\arcsin x$, an animated tangent line,
and the derivative $f'(x) = \\frac{1}{\sqrt{1 - x^2}}$.
(The derivative may appear first.)") anim3 = animate([plot((1/sqrt(1-a^2))*(x - a) + asin(a), x, -1, 1, rgbcolor=(0.5, 0, 0)) + plot(asin(x), x, -1, 1, rgbcolor=(0, 0.5, 0)) + point([a, asin(a)], rgbcolor=(1, 0, 0)) for a in srange(-0.95, 1, 0.05)], ymin=-1*pi/2, ymax = pi/2, aspect_ratio=1, figsize=[4,4]) show(anim3) plot(1/sqrt(1 - x^2), x, -0.99, 0.99, figsize=[2.6,2.6])
 Here is a plot of f(x) = \arcsin x, an animated tangent line,and the derivative f'(x) = \frac{1}{\sqrt{1 - x^2}}.(The derivative may appear first.) Here is a plot of f(x) = \arcsin x, an animated tangent line,and the derivative f'(x) = \frac{1}{\sqrt{1 - x^2}}.(The derivative may appear first.)


text:
# Tag Info

Most white dwarfs consist of fully ionised carbon and oxygen atoms$^1$. Each carbon nucleus must be accompanied by 6 electrons and each oxygen nucleus by 8 electrons. The electrons are essentially a ...


text:
# peano-axioms's questions - Chinese 1answer

452 peano-axioms questions.

### 3 Decidability of quantifier-free formulae in Peano- and True Arithmetic

It is well-known that validity in Peano Arithmetic is undecidable. It is less well-known that validity is already undecidable in True Arithmetic (the theory of the standard model of Peano Arithmetic). ...

### 4 Systems of arithmetic models [on hold]

Presburger Arithmetic is decidable theory but weaker than Peano Arithmetic. Are there systems in some sense that are: stronger than Presburger but weaker than Peano and remain decidable? weaker than ...

### 2 proof of commutativity of multiplication for natural numbers using Peano's axiom

2 answers, 1.824 views natural-numbers peano-axioms
How do you prove commutativity of multiplication using peano's axioms.I know we have to use induction and I have already proved n*1=1*n.But I cant think of how to prove the inductive step.

### 10 Is it a paradox if I prove something as unprovable?

1 answers, 1.360 views logic proof-theory peano-axioms
The Goldbach Conjecture asserts: It is possible to write every even number greater that 2 as the sum of two primes. Assume I can prove that the Goldbach Conjecture is unprovable from the Peano ...

### 1 How to prove Peano induction axiom for a candidate model

0 answers, 30 views logic induction peano-axioms
Suppose you have a candidate structure, and you want to prove it satisfies the Peano axioms. For example, let 1 serve as the first element, and let $s(x)=x/(1+x)$. It's easy to see the non-induction ...

### 1 How Long is the Shortest Proof of 0=1?

Assume we have a countable, non-standard model of PA where 0=1 is provable. We construct a TM that recursively enumerates every proof in PA. This TM halts if it finds a proof of $0=1$. Will this TM ...

### 3 Reflection schema over PA for Rosser provability predicate

1 answers, 66 views logic peano-axioms
I have a couple of questions concerning the reflection schema over PA, Suppose that we want to consider a deviant reflection schema over PA formalized by $Prov_{Ros-PA}(\varphi)\rightarrow \varphi$, ...

### 1 Mathematical induction - the set version v.s. predicate version

0 answers, 54 views logic induction set-theory peano-axioms

### 3 About ZFC, peano's axioms, first order logic and completeness?

2 answers, 271 views first-order-logic peano-axioms
I read somewhere that the Peano's axioms can be derived out of ZFC. But if that is the case ZFC would be incomplete right( by Godel's incompleteness theorem)? But since ZFC is in first order logic , ...

### Is $K_{n-1}$ a $\Sigma_{n-1}$-elementary substruture of $K_n$ [closed]

1 answers, 42 views logic model-theory peano-axioms
Is $K_{n-1}$ a $\Sigma_{n-1}$ elementary substruture of $K_n$? Let $M$ be any non-standard model of PA. $K_n$ is define to be the set of $\Sigma_n$-definable elements of $M$. I have a feeling the ...

### 2 Why is it impossible to define multiplication in Presburger arithmetic yet possible to define exponentiation in Peano Arithmethic?

1 answers, 129 views peano-axioms presburger-arithmetic
Hello my question is related to Why is it impossible to define multiplication in Presburger arithmetic? and to How is exponentiation defined in Peano arithmetic?. I would have preferred to add it as a ...

### Different arithmetics

The original Peano axioms were based on a single unary operator $\operatorname{succ}$ and one second-order induction axiom: $\lbrace \operatorname{succ} \rbrace + \operatorname{IND}_2$ Peano ...

### 2 An infinite set of axioms in ZF? What does that mean?

1 answers, 101 views logic set-theory axioms peano-axioms
Before write this question, I looked around enough in this forum for a possible answer and although there are many similar questions, I couldn't find one answer which understand or satisfies me. I did ...

### 17 Do we have to prove how parentheses work in the Peano axioms?

One thing that has bothered me so far while learning about the Peano axioms is that the use of parentheses just comes out of nowhere and we automatically assume they are true in how they work. For ...

### 2 Proof of Strong Induction Using Well-Ordering Principle

Context: I keep running into circular reasoning in attempting to derive strong induction (more generally "induction" whether it be weak or strong) from the well-ordering principle. Assume: Peano ...

### How do I know what I need to show when using induction? (Peano axioms)

As an exercise I wanted to prove that addition was commutative using the Peano axioms. To quickly restate the definition of addition (where $S(n)$ is the successor function of $n$, which we can show ...

### 4 Prove addition is commutative using axioms, definitions, and induction

I wanted to try to prove the commutative property of addition before reading too much about it and "spoiling" things for myself. So I am curious how close I got. First, some axioms (statements/...

### 1 Some questions about the successor function

So I am learning about the successor function $S(n)$ where we have $S(n) = n+1$ basically. So $S(0) = 1, S(1) = 2, S(2) = 3, S(3) = 4$, etc. But are we explicitly mapping $0$ through $9$ "by hand" ...


text: Non-dominated sorting is a technique often used in evolutionary algorithms to determine the quality of solutions in a population. The most common algorithm is the Fast Non-dominated Sort (FNS). This algorithm, however, has the drawback that its performance deteriorates when the population size grows. The same drawback applies also to other non-dominating sorting algorithms such as the Efficient Non-dominated Sort with Binary Strategy (ENS-BS). An algorithm suggested to overcome this drawback is the Divide-and-Conquer Non-dominated Sort (DCNS) which works well on a limited number of objectives but deteriorates when the number of objectives grows. This article presents a new, more efficient algorithm called the Efficient Non-dominated Sort with Non-Dominated Tree (ENS-NDT). ENS-NDT is an extension of the ENS-BS algorithm and uses a novel Non-Dominated Tree (NDTree) to speed up the non-dominated sorting. ENS-NDT is able to handle large population sizes and a large number of objectives more efficiently than existing algorithms for non-dominated sorting. In the article, it is shown that with ENS-NDT the runtime of multi-objective optimization algorithms such as the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) can be substantially reduced.


text:
# Problem in writing a program using C

#### kencool1

Joined Aug 22, 2007
3
Dear all,
I am learning C programming by myself using some books and notes from the internet.
I have got stuck in writing a program as I dont know where to start writing it...
Can someone please help me by writing a program using C to implement the following airline reservation system.
Can I have a reply from anyone as soon as possible...

The program is as followed:

A small airline that operates flights to one destination uses a computer system to:

1) Provide an enquiry system regarding the number and type of seats available for a flight on a specified day.

2) Issue a single ticket to a passenger containing the following information:

a) Name of destination
b) Types of seat booked, i.e., first or tourist class.
c) Departure, arrival times and date
d) Cost of ticket
e) Name of passenger

3) Output a passenger list for each flight.

The following have to be assumed:
1. There is only one flight per day at different times over a period of five days. The airline operates from Monday to Friday only. The duration of the flight is 2 hours.

2. Every aeroplane used has a maximum of 50 seats, the distribution of first class seats to tourist class seats being 10 and 40 respectively.

3. A seat is bookable up to one week in advance but not on the day of the flight.

4. The cost of the first class seat is $500, whilst that of a tourist class seat is$250.

#### beenthere

Joined Apr 20, 2004
15,819
You may find that a flowchart will help a lot in getting started. By diagramming every step in the process, you will see what things the code needs to accomplish. It sounds tedious, but correcting bad code is no fun, either. The flowchart lets you do program development in a controlled fashion - now this works, so I can try to do the next step.

You also break it down into small modules. Like setting up screens to input passenger names and travel dates. That lets you start assigning variables that can be referenced in other parts of the program. It's easy to combine the small steps as the program grows.

#### Mark44

Joined Nov 26, 2007
628
It sounds like you haven't been able to start in on this, but can you give us some idea of what you've learned already about C? E.g., that you know how to do input and output, know about variable types, that you know some control structures such as loops, and so on. Letting us have an idea of where you are can make it easier for us to help you write this.
Mark

#### kencool1

Joined Aug 22, 2007
3
I have learn if-else statements, switch staement, break statement, continue statement,
Loop: while, do-while, for.
Variable: global and local.
I know also how to input and ouput (scanf, printf)

If you will not be able to do the program, can you at least write the pseudocodes for me please.

#### mik3ca

Joined Feb 11, 2007
189
create functions and then use them in your program. This prevents your code from appearing as endless.

Or, if you really want to learn C and you want to do it hard-core electronics style, Let me introduce you to a device that starts with a C. It is a CAPACITOR.

#### Papabravo

Joined Feb 24, 2006
13,972
That is a fiarly ambitious program to use for learning a language. I suggest you start with something smaller. I also note that it would require a fair amount of effort with very little payoff for one of the members to do it for you.

#### beenthere

Joined Apr 20, 2004
15,819
Please remember that the program and the grade are yours. We can provide guidance - see above - but it's up to you to make the effort for the grade.


text:
# Which mathematician are you?

How do you like your numbers? Prime? Positive but infinitely small? Find out which famous mathematician you are

• ### Book of the Year 2020

We announce the winner of this coveted prize