TITLE: Distribution of count data with large spread and heavy concentration of small values
QUESTION [1 upvotes]: I have a dataset of the counts of each user visiting a set of websites in a year (each user visits at least 1 website in my data). Half of the users visit 7 or fewer sites though the top user visits 9384 sites. I want to find a count distribution that can fit the data well but it seems challenging.
Here is the data summary:

46285 observations
Mean: 33.1
Std. Dev.: 138.5
Skewness: 20.0
Kurtosis: 808.1

Percentile: Value - Smallest

1%: 1 - 1
5%: 1 - 1
10%: 1 - 1
25%: 1 - 3

Median

50%: 7

Percentile: Value - Largest

75%: 19 - 4947
90%: 53 - 5281
95%: 116 - 7111
99%: 522 - 9384

I tried Poisson which obviously doesn't work because mean << std. dev. Negative binomial does not do too much better.
Any suggestions?
Thanks!

REPLY [1 votes]: I don't know any nice families of count models that might fit this.  Have you tried to find any explanatory variables that you might put into a count regression model?  Maybe a covariate can explain the extreme values and you can get a better fit.  Another possibility is finding a mixture of count distributions.


TITLE: Tietze extension theorem for SL(C,n)
QUESTION [3 upvotes]: Let $X$ be a compact Hausdorff space, $K$ be a closed subset of it. $f:K\to SL(C,n)$ is continuous. Can $f$ be extended to a continuous function on $X$?

REPLY [6 votes]: This is an elaboration on Martin's comment on JSchlather's answer. The answer is no. Let $Y$ be any topological space, let $X = D^n$ be the $n$-disk, and let $K = S^{n-1}$ be its boundary. If a map $S^{n-1} \to Y$ extends to a continuous function on $D^n$, then the corresponding map is necessarily trivial in $\pi_{n-1}(Y)$. Hence the Tietze extension theorem in this setting fails as soon as some homotopy group of $Y$ is nontrivial.
$\text{SL}_n(\mathbb{C})$ is homotopy equivalent to $\text{SU}(n)$, which has nontrivial $\pi_3$ ($n \ge 2$), so taking $X = D^4$, $K = S^3$, and $f : S^3 \to \text{SL}_n(\mathbb{C})$ a map representing a nontrivial element of $\pi_3$ gives a counterexample.


TITLE: Building bicubic coons patch from four boundary curves
QUESTION [0 upvotes]: I want to create s coons patch surface from four boundary curves s1(u), s2(u) q1(v), q2(v)
I know that equations are the following (added screenshots from a presentation):

There are a few parts of the equations that are not fully understand and i did not find any good explanation:

In s1(u,v) what is the meaning of p1v(u) and p2v(u)? same goes for q1u(v) and q2u(v) in s2(u,v).
In the A matrix, what is the meaning of A00(u,v)..A11(u,v). What would be the value of these parameters if p1,p2 are only functions of u (and not v) and q1,q2 are only function of v.

I would appreciate any help on this issue.

REPLY [0 votes]: The boundary curves are $P_1(u), P_2(u), Q_1(\nu), Q_2(\nu)$ and are complemented by four transverse derivative functions $P_1^\nu(u), P_2^\nu(u), Q_1^u(\nu), Q_2^u(\nu)$. (Verifying compatibility conditions at the corners.)
The $^u$ and $^\nu$ exponents denote the derivative with respect to these variables.
The $A_{ij}$ elements are values of the boundary curves and their partial derivatives (first order and mixed) at the four corners.
Even though the boundary curves are functions of a single parameter, one can think of them as being embedded in a surface for which the tangent plane is known on the whole boundary.


text:
\section{Sequential greedy algorithms based on the MM principle} \label{sec:mm_alg}

We now explore algorithms of a slightly different flavor, which are still greedy in a sense but do not necessarily make the locally optimal choice corresponding to incremental gain. They are based on the MM  (minorize--maximize or majorize--minimize)  principle \cite{Lange_2016_MMOpt}, and involve maximizing (resp.\ minimizing) at every step a minorizing (resp.\ majorizing) counterpart function to eventually obtain the $\argmax$ (resp.\ $\argmin$). Every instance of applying the MM principle is prompted by the need to transform a hard optimization problem into a sequence of simpler ones. Here simplicity can refer to one of many desirable attributes, such as reduction in overall computational complexity, linearization or convexification of the problem, easing the handling of complex constraints, and so on. For a broad survey of techniques and algorithms based on the MM principle we refer the readers to the excellent text \cite{Lange_2016_MMOpt}.

While most of the work in optimization using the MM principle has been in the setting of continuous functions, in the recent past these have been adapted to the world of set functions \cite{IyerJegelkaBilmes2012_mirror,IyerJegBil2013}. In \cite{NarBil2005,IyerBilmes2012_diff2SM}, the authors explored these ideas for the most general case of  difference between two submodular functions. Concrete hardness results on multiplicative inapproximability of such optimization problems were also shown in the same work \cite{IyerBilmes2012_diff2SM}. The MM principle proves handy in these scenarios; it is deployed by first seeking tight modular bounds for one (or both) of the terms in the difference, and subsequently optimizing the resulting submodular (or modular) objective using existing methods. The key property of submodular functions that enables such approaches is that one can define a subgradient \cite{fujishige2005} (\Cref{def:sub_grad_diff_SM}) and supergradient \cite{Jegelka_Bilmes_2011} (\Cref{def:super_grad_diff_SM}) at every point, meaning for every subset in the power set. Calculation of those semigradients, however, will require repeated function evaluations of appropriate subsets, and the semidifferential sets (\Cref{def:sub_grad_diff_SM,def:super_grad_diff_SM}) that contain them constitute a polyhedral partitioning of $\mathbb{R}^{m}$ \cite{Iyer_Bilmes_2015_polyhedral}.

Our efforts utilizing the MM principle differ from the approaches summarized above and  perhaps to a certain degree from how MM algorithms are generally thought of. The techniques in \cite{IyerJegelkaBilmes2012_mirror,IyerJegBil2013,IyerBilmes2012_diff2SM} are applicable for fairly general constraints and can be best understood as an iterative framework where one continues until local convergence is achieved.  The algorithms we consider, however, are sequential in a `bonafide' sense, meaning an individual element or a batch of elements are selected at every step and appended to the previously chosen set of elements. Our focus is restricted to cardinality-constrained problems.
We begin by providing a reinterpretation of the classical greedy heuristic.

\subsection{Reinterpreting the classical greedy heuristic for maximization} \label{subsec:greedy_as_mm}

 The definitions of the submodularity and supermodularity ratios allow us to write the following bounds for the incremental gain $\rho_{\mathscr{A}}(\mathscr{B}) $,
\begin{equation}
	 \eta  \sum_{\nu \in \mathscr{A}} \rho_{\nu}(\mathscr{B}) \leq \rho_{\mathscr{A}}(\mathscr{B})  \leq \frac{1}{\gamma} \sum_{\nu \in \mathscr{A}}\rho_{\nu}(\mathscr{B}).
\end{equation}
If we view $\rho_{\mathscr{A}}(\mathscr{B})$ as a function of $\mathscr{A}$, then what we have above are modular bounds on $\rho_{\mathscr{A}}(\mathscr{B}) $ defined using the incremental gains $ \rho_{\nu}(\mathscr{B})$, $\nu \in \mathscr{A}$. Alternatively if we view the set $\mathscr{B}$ as one individual entity and the elements of $\mathscr{A}$  as  distinct entities, we can write modular bounds on $ F( \mathscr{A} \cup  \mathscr{B} )$ in terms of $F(\mathscr{B})$ and $ \rho_{\nu}(\mathscr{B})$, $\nu \in \mathscr{A}$:
\begin{equation} \label{eqn:modular_bound_for_FAuB_using_incremental_gain}
	F(\mathscr{B}) + \eta \sum_{\nu \in \mathscr{A}} \rho_{\nu}(\mathscr{B}) \leq F( \mathscr{A} \cup  \mathscr{B} )  \leq F(\mathscr{B}) + \frac{1}{\gamma} \sum_{\nu \in \mathscr{A}}\rho_{\nu}(\mathscr{B}).
\end{equation}
Thus we can view the submodularity and supermodularity ratios as parameters that allow us to define the tightest possible modular bounds of the above form for any $\mathscr{A},\mathscr{B} \subseteq \mathscr{V}$. Note that the bounds are also tight in the sense that if $\mathscr{A} \setminus \mathscr{B} = \emptyset$ then \cref{eqn:modular_bound_for_FAuB_using_incremental_gain} reduces to a trivial statement. Viewed through the lens of MM algorithms, the modular lower/upper bound serves as the minorizing/majorizing counterpart to $ F( \mathscr{A} \cup  \mathscr{B} )$.

With these perspectives, the greedy heuristic for maximization in \Cref{alg:batch_std_greedy} can be easily paraphrased in the language of MM algorithms. Having selected the set $\mathscr{A}_{j-1}$ after $j-1$ steps, we  seek $ \mathscr{A}_{j-1 \rightarrow j}  \subseteq \mathscr{V} \setminus \mathscr{A}_{j-1}$, $\abs{\mathscr{A}_{j-1 \rightarrow j} } = q_j$ that maximizes $F( \mathscr{A}_{j-1} \cup \mathscr{A}_{j-1 \rightarrow j} )$. We achieve this by maximizing the minorizing counterpart: the modular lower bound as in \cref{eqn:modular_bound_for_FAuB_using_incremental_gain} defined using the incremental gains $\rho_{\nu}(\mathscr{A}_{j-1})$, $\nu \in \mathscr{V} \setminus \mathscr{A}_{j-1} $.

Incremental gains associated with individual elements, coupled with the submodularity or  supermodularity ratios, are an obvious combination for defining modular bounds for a function. Many problems, however, may have additional attributes that enable other ways of defining modular bounds. The greedy heuristic can be adapted appropriately to utilize these special modular bounds. Such bounds could be easier to compute and perhaps perform better empirically. In \Cref{alg:greedy_ascent} we outline a greedy procedure built on the ansatz of an abstract modular lower  bound $\mathcal{M}_{\uparrow}\left[ \cdot \right]$ and modular upper bound  $\mathcal{M}_{\downarrow}\left[ \cdot \right]$ for the  incremental gain $\rho_{\mathscr{A}}(\mathscr{B}) $ associated with any $\mathscr{A}$, $\mathscr{B} \subseteq \mathscr{V}$:
\begin{equation}
	\mathcal{M}_{\uparrow}\left[ \rho_{\mathscr{A}}(\mathscr{B}) \right] \leq \rho_{\mathscr{A}}(\mathscr{B}) \leq \mathcal{M}_{\downarrow}\left[ \rho_{\mathscr{A}}(\mathscr{B}) \right].
\end{equation}
The symbols $\downarrow,\uparrow$ are a visual cue to pinpoint whether the bound is from above or below.

\begin{algorithm}
\begin{algorithmic}[1]
\caption{Greedy algorithm using modular lower bounds}  \label{alg:greedy_ascent}
\State {Input  $F,\mathscr{V},l,\{q_1,\ldots,q_l\}$}
\State {Initialize $\mathscr{A}=\emptyset$}
 \For {$i = 1 \text{ to }  l$}
  \State {Determine $\mathcal{M}_{\uparrow}\left[\rho_{\mathscr{V} \setminus \mathscr{A}}(\mathscr{A}) \right]$.}
  \State {Find $\mathscr{Q} \subseteq \mathscr{V} \setminus \mathscr{A}, \abs{\mathscr{Q}} = q_i$ that maximizes $\mathcal{M}_{\uparrow}\left[\rho_{\mathscr{Q}}(\mathscr{A}) \right]$}
  \State {$\mathscr{A} \leftarrow \mathscr{A} \cup \mathscr{Q}$}
\EndFor

\Return {Index set $\mathscr{A}$}
\end{algorithmic}
\end{algorithm}

Now we give performance bounds for the abstract batch greedy approach of \Cref{alg:greedy_ascent}.
\begin{theorem} \label{thm:greedy_ascent}
Let $F$ be a non-decreasing  function. \Cref{alg:greedy_ascent} for maximizing $F(\mathscr{A})$ subject to $\abs{\mathscr{A}} \leq k$ outputs a set $\mathscr{A}$ such that
\begin{displaymath}
	F(\mathscr{A}) \geq \lr{ 1 - \prod_{i=1}^{l} \lr{ 1 - \frac{q_i }{k \lr{1+\tau_i}} }} \max_{\mathscr{B} \subset \mathscr{V}, \abs{\mathscr{B}} \leq k} F(\mathscr{B})
\end{displaymath}
where $\tau_i > 0$ is a parameter that encapsulates the effectiveness of the modular lower bound $\mathcal{M}_{\uparrow}\left[ \cdot \right] $ in locally describing the function.
\end{theorem}
\hyperref[proof:theorem_greedy_ascent]{The proof is given in \Cref{appendix_subsec:greedy_stuff}.}\medskip

The analysis of \Cref{alg:greedy_ascent} is along the same lines as that of \Cref{alg:batch_std_greedy}. The effectiveness of the modular lower bound in locally describing the function is baked into the approximation guarantee via the parameter $\tau_i$. If $\mathscr{A}^{*}$ is the optimal set of the maximization problem, then for the $i^{\text{th}}$ step, $\tau_i$ is defined as the smallest scalar satisfying
\begin{equation} \label{eqn:tau_i_def}
  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{i-1}} -  \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{i-1}} \right] \leq  \frac{ \tau_i k \rho_{\mathscr{A}_{i}} \lr{ \mathscr{A}_{i-1}}}{q_i}.
\end{equation}
The dependence of $\tau_i$ is strictly on the  modular lower bound, but in many cases estimating it is easier when it is defined as the smallest scalar satisfying
\begin{equation} \label{eqn:tau_i_def_looser}
   \mathcal{M}_{\downarrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{i-1}} \right] -  \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{i-1}} \right] \leq  \frac{ \tau_i  k  \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}_{i}} \lr{ \mathscr{A}_{i-1}} \right]}{q_i}.
\end{equation}
Notice that $\tau_i$ estimated using the definition in \cref{eqn:tau_i_def_looser}  is always larger than what is necessary to satisfy \cref{eqn:tau_i_def}.

One instance of $\tau_i$ which we have previously seen, indirectly, is when the modular bounds are defined using incremental gains and submodularity/supermodularity ratios. In that case, with a little effort it is easy to see that $\tau_i$ according to \cref{eqn:tau_i_def_looser} will be
 $\frac{1 - \gamma_{\mathscr{V},k} \eta_{\mathscr{V},k} }{\gamma_{\mathscr{V},k} \eta_{\mathscr{V},q_i} }$. But this value is sub-optimal when compared to the $\tau_i $ one can implicitly infer from the result in \Cref{thm:batch_std_greedy}, which is $\frac{1 - \gamma_{\mathscr{V},k} \eta_{\mathscr{V},q_i} }{\gamma_{\mathscr{V},k} \eta_{\mathscr{V},q_i} }$. The sub-optimality stems from the fact that $\eta_{\mathscr{V},q_i} \geq \eta_{\mathscr{V},k}$, $\forall q_i \leq k$. The discrepancy is easily explained since in the proof of \Cref{thm:greedy_ascent} we allow for the modular lower bound $\mathcal{M}_{\uparrow}\left[ \cdot \right] $ to be negative. If we assume non-negativity of the modular lower bound, the proof can be accordingly modified to obtain the optimal result.

config: arxiv


TITLE: Velocity of a photon according to a stationary observer in Schwarzschild metric
QUESTION [2 upvotes]: Consider the Schwarzschild metric
$$ \left(1-\frac{2M}{r}\right)dt^2-\left(1-\frac{2M}{r}\right)^{-1}dr^2-r^2\left(d\theta^2+\sin^2\theta\, d\phi^2\right)$$
Final goal: calculate the observed velocity of a photon on a radial geodesic according to an observer that's stationary at some $r>2M$ above the singularity.
Such a stationary observer must have a wordline $$\gamma(\tau)=\left(t,r,0,0\right)$$
such that $\dot r=0$ and $\dot\gamma^\mu\dot\gamma_\mu=1$, this yields
$$\frac{\mathrm{d}t}{\mathrm{d}\tau}=\frac{1}{\sqrt{1-\frac{2M}{r}}} $$
The wordline for an observer stationary at some height $h$ is thus
$$ \gamma(\tau)=\left(\frac{\tau}{\sqrt{1-\frac{2M}{h}}},h,0,0\right)$$
Now, a photon geodesic must obey
$$ \frac{\mathrm{d}r}{\mathrm{d}\lambda}=\left(1-\frac{2M}{r}\right)\frac{\mathrm{d}t}{\mathrm{d}\lambda}\implies\frac{\mathrm{d}r}{\mathrm{d}t}=1-\frac{2M}{r}$$
The velocity of the photon according to the observer is
$$ \frac{\mathrm{d}r}{\mathrm{d}\tau}=\frac{\mathrm{d}r}{\mathrm{d}t}\frac{\mathrm{d}t}{\mathrm{d}\tau}=\frac{1-\frac{2M}{r}}{\sqrt{1-\frac{2M}{h}}}$$
The problem: if I plug in $r=h$ I would expect to obtain $1$, as the photon is supposed to move at the speed of light near the observer. What happened?

REPLY [3 votes]: If we want to be precise, your calculations seem correct but it is just the coordinates you are using that are not locally inertial and that is why you are not getting what you would like. Just a comment, do not set $\theta = 0$ that is a coordinate singularity of spherical coordinates and there fore of the metric in these coordinates. Instead, take $\theta = \frac{\pi}{2}$ which is the equator.
In general relativity, locally inertial coordinates means the following: given some coordinates in a neighborhood of a world-line $\gamma(\lambda)$, these coordinates are called locally inertial if the metric written in these coordinates at each point $\gamma(\lambda)$ of the world-line is the Minkowski metric. However, away from the world-line the metric in these coordinates is not Minkowski!
Your coordinates are $(t, r, \phi, \theta)$  and the world-line (a non-geodesic one by the way) is let's say $$\gamma(\tau) = \left(\, \frac{\tau}{\sqrt{1-\frac{2M}{h}\,}},\, \, h,\,\, 0,\,\, \frac{\pi}{2} \,\right)$$ parametrized with respect to proper time.
The tangent coordinate vectors along the coordinate $t-$lines, $r-$lines, $\phi-$lines and $\theta-$lines are
$$\frac{\partial}{\partial t} = \begin{bmatrix}1\\0\\0\\0 \end{bmatrix}, \,\,\,
\frac{\partial}{\partial r} = \begin{bmatrix}0\\1\\0\\0 \end{bmatrix}, \,\,\,
\frac{\partial}{\partial \phi} = \begin{bmatrix}0\\0\\1\\0 \end{bmatrix} \,\,\, \text{ and } \,\,\,
\frac{\partial}{\partial \theta} = \begin{bmatrix}0\\0\\0\\1 \end{bmatrix} \,\,\,$$ respectively. They are Schwarzschild orthogonal, but their Schwarzschild length is not unit ($+1$ for the time-like vector and $-1$ for the three space-like vectors) along the world line $\gamma(\tau)$. If you rescale these vectors, however, you can achieve normalization
$$\frac{\partial}{\partial \tau} = \frac{1}{\sqrt{1-\frac{2M}{h}}}\, \frac{\partial}{\partial t} =  \begin{bmatrix}\frac{1}{\sqrt{1-\frac{2M}{h}}}\\0\\0\\0\end{bmatrix} , \,\,\,
\frac{\partial}{\partial \rho} = {\sqrt{1-\frac{2M}{h}}}\, \frac{\partial}{\partial r} = \begin{bmatrix}0\\ \sqrt{1-\frac{2M}{h}} \\0\\0 \end{bmatrix}, \,\,\,$$
$$
\frac{\partial}{\partial u} =  \frac{1}{h\,\sin(\frac{\pi}{2})}\,\frac{\partial}{\partial \phi} =\frac{1}{h}\,\frac{\partial}{\partial \phi} = \begin{bmatrix}0\\0\\\frac{1}{h}\\0 \end{bmatrix}, \,\,\,\,\,
\frac{\partial}{\partial w} = \frac{1}{h}\,\frac{\partial}{\partial \theta} =  \begin{bmatrix}0\\0\\0\\\frac{1}{h} \end{bmatrix} \,\,\,$$
Now, you can perform the linear change of variables from $(t, r, \phi, \theta)$ to $(\tau, \rho, u, w)$ as follows
\begin{align}
&t = \frac{\tau}{\sqrt{\, 1 - \frac{2M}{h}\,}}\\
&r  = \left(\sqrt{\, 1 - \frac{2M}{h}\,} \right)\, \rho \,+ \, h\\
&\phi = \frac{u}{h}\\
&\theta = \frac{w}{h} + \frac{\pi}{2}
\end{align}
and the the inverse relations are
\begin{align}
&\tau = \left({\sqrt{\, 1 - \frac{2M}{h}\,}}\right)\, t \\
&\rho  = \frac{r \, - \, h}{\sqrt{1 - \frac{2M}{h}}} \\
&u = h\,\phi\\
&w =  h\,\theta \, - \, \frac{h\,\pi}{2}
\end{align}
The world line $\gamma(\tau)$ in the new coordinates is
$$\gamma(\tau) = \big(\tau,\, 0, \, 0, 0 \big)$$
The light-like radial geodesic in the original $(t, r, \phi, \theta)$ coordinates is
$$g(t) = \Big(\,t, \, r(t), \, 0, \, \frac{\pi}{2}\,\Big)$$  where
$$\frac{dr}{dt} = 1 - \frac{2M}{r}$$ In the new coordinates it is
$$g(\tau) = \Big(\,\tau, \, \rho(\tau), \, 0, \, 0\,\Big)$$ where we can find the function $\rho(\tau)$ by changing the coordinates in the differential equation for $r(t)$, i.e.
\begin{align}
\frac{d\rho}{d\tau} &= \frac{\frac{dr}{\sqrt{1-\frac{2M}{h}}}}{\sqrt{1-\frac{2M}{h}}\, dt} = \left(1 - \frac{2M}{h}\right)^{-1}\, \frac{dr}{dt} =  \left(1 - \frac{2M}{h}\right)^{-1}\, \left(1 - \frac{2M}{r}\right)\\
& = \left(1 - \frac{2M}{h}\right)^{-1}\, \left(1 - \frac{2M}{h + \rho \, \sqrt{1-\frac{2M}{h}}}\right)
\end{align} Observe that in the new coordinates the Schwarzschild metric is the Minkowski metric for each point on the world-line $\gamma(\tau)$. Now, when the light-like geodesic $g(\tau)$ intersects the world-line $\gamma(\tau)$, i.e. the photon reaches the observer, then $\rho = 0$ and from the differential equation for $\rho(\tau)$ we see that
$$\frac{d\rho}{d\tau} = 1$$ i.e. in this locally inertial coordinate system, the speed of light is still $1$ as expected.


TITLE: Infinite sum of asymptotic expansions
QUESTION [2 upvotes]: I have a question about an infinite sum of asymptotic expansions:
Assume that $f_k(x)\sim a_{0k}+\dfrac{a_{1k}}{x}+\dfrac{a_{2k}}{x^2}+\cdots$
with $a_{0k}\leq \dfrac{1}{k^2}$, $a_{1k}\leq \dfrac{1}{k^3}$, $a_{2k}\leq \dfrac{1}{k^4}$, $\cdots$.
Does it follow that $\sum_{k=1}^{\infty}f_k(x)\sim \sum_{k=1}^{\infty}a_{0k}+\dfrac{\sum_{k=1}^{\infty}a_{1k}}{x}+\dfrac{\sum_{k=1}^{\infty}a_{2k}}{x^2}+\cdots$?
By the way, could you please suggest me materials to learn asymptotic expansions like this? Thanks

REPLY [3 votes]: Of course it is possible, but much caution is required because we don't know
about uniformity in $k$ for the estimates corresponding to the $\sim$
statements.  Counterexamples are very easy to construct, where e.g.
$f_k(x)$ doesn't start behaving "nicely" until $x > k$.


TITLE: Given three chords on a circle which form an interior triangle what is the area of the triangle formed?
QUESTION [6 upvotes]: Using an argument similar to this one, the probability of a triangle being formed is $\frac{1}{15}$ since the number of ways six points on the circumference of a circle can be grouped into three sets of two is $\frac{6!}{2!^33!}=15$ and only one of these ways to group forms a triangle. Another way to think about this is forming all chords from six points and looking at $\triangle GKL$, the interior triangle formed.

Given a triangle is formed by three chords of a circle, what is the area of the triangle in terms of the location of the six points on the circle? I am looking run a simulation of the expected area given three random chords but having a hard time simply solving for the area of the triangle.
For simplicity I think we can assume that the circle is a unit circle of radius one?

REPLY [3 votes]: While I think it is probably possible to compute the expected area exactly, it hardly seems worthwhile.  We can choose $6$ angles uniformly between $0$ and $2\pi$ and order them so that $$0\leq \theta_0 < \theta_i < \cdots < \theta_5 < 2\pi$$  WLOG we can take $\theta_0=0.$  Then the expected value is
$$\frac{1}{32\pi^5}\int_0^{2\pi}\mathrm{d}\theta_1
\int_{\theta_1}^{2\pi}\mathrm{d}\theta_2
\int_{\theta_2}^{2\pi}\mathrm{d}\theta_3
\int_{\theta_3}^{2\pi}\mathrm{d}\theta_4
\int_{\theta_4}^{2\pi}A(\theta_1,\theta_2,\theta_3,\theta_4,\theta_5)\mathrm{d}\theta_5
$$
where $A$ is a rational function of sines and cosines.  Presumably this can be integrated in closed form by making the Weierstrass substitution on each of $\theta_5, \theta_4, \dots$ in turn. I shudder at the thought, but maybe a CAS can do it.
Following Βασίλης's lead, I wrote a simulation, using a circle of radius $1$.  I consistently get a value around $.083.$  The code is given below.  I just used Βασίλης's formulas, without checking them.  You ought to do that, as well as checking my code for errors.  I used the understanding I made in the comments.  If the angles are $\theta_0, \theta_1, \dots, \theta_5$ in cyclic order, then the chords connect $\theta_i$ and $\theta_{i+3}$ for $i=1,2,3.$
from math import sin, cos, pi, sqrt
from random import random
import numpy as np

trials = 100000

def area():
    theta = sorted(2*pi*random() for _ in range(6))
    A = [sin(theta[i]) - sin(theta[i+3]) for i in range(3)]
    B = [cos(theta[i+3]) - cos(theta[i]) for i in range(3)]
    C = [-sin(theta[i])*B[i]-cos(theta[i])*A[i] for i in range(3)]
    D = [A[i]*B[(i+1)%3]-A[(i+1)%3]*B[i] for i in range(3)]
    Dx = [-B[i]*C[(i+1)%3]+B[(i+1)%3]*C[i] for i in range(3)]
    Dy = [-A[i]*C[(i+1)%3]+A[(i+1)%3]*C[i] for i in range(3)]
    x = [Dx[i]/D[i] for i in range(3)]
    y =  [Dy[i]/D[i] for i in range(3)]
    M = np.ones((3,3))
    M[0,:] = x
    M[1,:] = y
    return .5*abs(np.linalg.det(M))

total = 0
squares = 0
for _ in range(trials):
    a = area()
    total += a
    squares += a*a
mean = total/trials
var = squares/trials - mean*mean
print(f'{trials} trials')
print(f'Mean: {mean}')
print(f'Std deviation {sqrt(var)}')

Typical output:
100000 trials
Mean: 0.08274184243163976
Std deviation 0.12692829789994378


TITLE: The number of permutations of $\mathbb{N}$
QUESTION [1 upvotes]: Let $\mathbb{N}!$ be the set of permutations of the natural numbers.
With $\aleph_0 = \text{card}\ \mathbb{N}$ you need two facts of cardinal arithmetic to show that the number of permutations of $ \mathbb{N}$ ($\aleph_0! = \text{card}\ \mathbb{N}!$) equals the cardinality of the continuum ($ 2^{\aleph_0} = \text{card}\ \mathbb{R}$):

$\aleph_0\ ! = \aleph_0^{\aleph_0}$ because $\aleph_0 = \aleph_0 -k$ for each $k \in \mathbb{N}$
$\aleph_0^{\aleph_0} = 2^{\aleph_0}$It's easy to see that $\aleph_0^{\aleph_0} \geq 2^{\aleph_0}$ but why is $\aleph_0^{\aleph_0} \leq 2^{\aleph_0}$? (Find the answer below in user egreg's comment.)

I wonder if the following proof – which is more constructive – is valid and interesting. (If it's a well-known proof, please give me a hint, I did not find a reference.) It assumes that you have a representation of the natural numbers (as Cantor did in his diagonalization proofs). For the sake of specificity let's choose the binary representation.
Let $\mathcal{N}$ be the set of normal numbers starting with 1, i.e. $n = 0.1d_2d_3d_4d_5\dots$. It is known that $\text{card}\ \mathcal{N} = \text{card}\ \mathbb{R}$. It is also known that each normal number contains every sequence of digits infinitely often.
Now the proof goes like this:

There is an injective function from $\mathbb{N}!$ to $\mathcal{N}$ which sends each permutation $\pi$ of $\mathbb{N}$ to the unique number $n(\pi) = 0.\pi(1)\pi(10)\pi(11)\pi(100)\pi(101)\dots$ which is normal.Added: The last claim ("which is normal") is just an assumption, which makes the proof conditional. Even for the identity permutation $\pi_1$ with $\pi_1[k] = k$ and $n(\pi_1) = 0.1\ 10\ 11\ 100\ 101\dots$ it took a proof of its own to show that $n(\pi_1)$ is normal!
There is an injective function from $\mathcal{N}$ to $\mathbb{N}!$ which sends each normal number $n = 0.1d_2d_3d_4d_5\dots$ to the unique permutation $\pi(n)$ as explained in this example for  $n = 0.10101101011\dots$, written more suggestive as  $n = 0.10\ 101\ 1010\ 11\dots$:

Start with the first digit and go to the right until $d_3 = 1$ which yields $\pi(1)=10$.
Do the same with $d_3$: Go to the right until $d_5 = 1$. While the next candidate ($10$) has already been created take one more digit, which yields $\pi(2) = 101$
$\pi(3) = 1010$
$\pi(4) = 11, \dots$.

This way you will eventually find and create all numbers, since normal numbers contain each sequence of digits infinitely often.
So we have

$\text{card}\ \mathbb{N}! \leq  \text{card}\ \mathcal{N}$
$\text{card}\ \mathcal{N} \leq  \text{card}\ \mathbb{N}!$
$\text{card}\ \mathcal{N} =  \text{card}\ \mathbb{N}!$ (by the Schröder-Bernstein theorem)
$\text{card}\ \mathcal{N} =  \text{card}\ \mathbb{R}$

from which it follows that $\text{card}\ \mathbb{N}! =  \text{card}\ \mathbb{R}$.
It's not surprising to see, that you could define a group on $\mathcal{N}$ by $x \circ y = n(\pi(x) \circ \pi(y))$ (if the above proof was correct). Note that the identity element $e$ of this group is the Champernowne constant $C_2 = 0.11011100101110111\dots = 0.862240\dots$. (Note, that it is not obvious that $C_2$ is a normal number: it had to be proved (1992))

REPLY [1 votes]: The number you construct in step 2 is not necessarily normal. We can generate a non-normal number of this form explicitly by:

When $n=2k$ let $\pi(n)$ be $2^k$.
When $n=2k+1$ is odd, let $\pi(n)$ be the smallest number not yet used that is not a power of $2$.

The length of $\pi(n)$ for even $n$ grows much quicker than the length of $\pi(n)$ for odd $n$, which means that the limiting density of $1$ bits is $0$. However this density must, by definition, be $1/2$ for the number to be normal.

Also, the $\pi$ you produce in step 2 is not necessarily surjective, so it may not be a permutation. Even though the binary representation of of the input contains any bit string infinitely many times, it may be that all of its appearances come at a point in the binary expansion where you're not starting a new number (because what comes immediately before it has already been used).
For example you can make an example of this by taking the Champernowne constant and insert an 1 bit each time you would otherwise be about to read out 10 as the next number:
$$ 0.1\;\underline{1}10\;11\;\underline{1}100\; \underline{1}101\; 11011\; 11000 \; \underline{1} 1001\; \ldots  $$
producing the sequence
$$ 1, 6, 3, 12, 13, 27, 24, 25, \ldots $$
which by construction never hits $2$. Since the numbers become longer and longer, the inserted $1$s will eventually be so rare that the limiting densities of anything stays what it ought to be, so the modified number is still normal (in base 2).


TITLE: Bounding the number of integer solutions of the following inequality
QUESTION [2 upvotes]: Let $r\geq 1$ be a real number, $-1\leq x\leq 1$ a real number and $y>2$ a real number. We consider this data to be fixed.
How can I obtain an upper bound on the number of $(a,b,c,d)\in \mathbf{Z}^4$ such that
$$\left(c(x^2-y^2) +(d-a)x-b\right)^2+y^2(2cx+d-a)^2 \leq 2(r-1)y^2; $$ $$ad-bc = 1;$$ $$ (a,b,c,d) = (1,0,0,1) \mod 2.$$
To be clear, the quadruple $(a,b,c,d)$ is supposed to satisfy all three conditions. (I edited the question and added the last two conditions.)
Are there any computer packages that can help me do this?
I expanded the entire expression using Maple, but this didn't look very pleasant.
The motivation lies in the bounding the number of matrices $A$ in $\mathrm{SL}_2(\mathbf{Z})$ such that the geodesic distance between the point $x+iy$ and $A\cdot (x+iy)$ is bounded by $r$.

REPLY [1 votes]: There is no upper bound.  With $a=d$ and $b=c=0$ you have infinitely many lattice points where the left side is $0$.


TITLE: Simplify ratio of Gamma Functions
QUESTION [0 upvotes]: Is it possible to simplify the following ratio of Gamma functions:
$$
r\equiv-\frac{\Gamma \left(-\frac{2}{7}\right) \Gamma \left(\frac{6}{7}\right) \Gamma \left(\frac{10}{7}\right)}{\Gamma \left(-\frac{3}{7}\right) \Gamma \left(\frac{1}{7}\right) \Gamma    \left(\frac{16}{7}\right)}
$$
?
I managed to reduce it to a somehow more symmetric expression of the form
$$
r=\frac{49}{36}\frac{\Gamma \left(-\frac{2}{7}\right)}{\Gamma(\frac{2}{7})}\frac{\Gamma\left(\frac{3}{7}\right)}{\Gamma\left(-\frac{3}{7}\right)}\frac{\Gamma\left(\frac{6}{7}\right)}{\Gamma\left(-\frac{6}{7}\right)}
$$
but I haven't managed to simplify it further.
Thanks in advance for any help!

REPLY [1 votes]: I can't see my way through to something nice. Using the recurrence relation for the Gamma function I get
$$-\frac{\operatorname{\Gamma}\left(-\frac27\right)\operatorname{\Gamma}\left(\frac67\right)\operatorname{\Gamma}\left(\frac{10}7\right)}{\operatorname{\Gamma}\left(-\frac37\right)\operatorname{\Gamma}\left(\frac17\right)\operatorname{\Gamma}\left(\frac{16}7\right)}=-\frac74\frac{\operatorname{\Gamma}\left(\frac57\right)\operatorname{\Gamma}\left(\frac67\right)\operatorname{\Gamma}\left(\frac37\right)}{\operatorname{\Gamma}\left(\frac47\right)\operatorname{\Gamma}\left(\frac17\right)\operatorname{\Gamma}\left(\frac27\right)}$$
Quadratic nonresidues $\pmod{7}$ on top and residues on the bottom. You could multiply numerator and denominator by what is now the numerator and use the multiplication formula for the Gamma function to get
$$-\frac{\operatorname{\Gamma}\left(-\frac27\right)\operatorname{\Gamma}\left(\frac67\right)\operatorname{\Gamma}\left(\frac{10}7\right)}{\operatorname{\Gamma}\left(-\frac37\right)\operatorname{\Gamma}\left(\frac17\right)\operatorname{\Gamma}\left(\frac{16}7\right)}=-\frac{7\sqrt7}{32\pi^3}\left(\operatorname{\Gamma}\left(\frac57\right)\operatorname{\Gamma}\left(\frac67\right)\operatorname{\Gamma}\left(\frac37\right)\right)^2$$
But if you got a pretty result one might anticipate an even prettier one for $\operatorname{\Gamma}\left(\frac13\right)$ and there is something with a complete elliptic integral of the first kind but it's not very encouraging.


TITLE: Increasing value, decreasing amount
QUESTION [0 upvotes]: So I really only came here for one question, since I have no idea what it's called.
Let's use a comparison to make it a bit easier.

I have two coins of the value '1'.
When I add those together, I get one coin that is worth '2'.
When I add two of those(2) together, I get a coin that is worth '3'
Ect. Ect.

I realize it might not be the greatest question ever, but what is counting/adding like this called? And is there a formula to easily calculate how many of the coins worth '1' I need to make a coin worth 'X'?
Thanks in advance, and forgive me for asking a possibly easy to answer question.

REPLY [1 votes]: In this instance it takes $2^{n-1}$ coins of value 1 to get a coin of value $n$. You might say that the coin values combine logarithmically, but that wouldn't be totally clear unless you give the explanation you already did.


text:
\section{Rule of Material Equivalence}
Tags: Rule of Material Equivalence, Biconditional, Implication, Conjunction

\begin{theorem}
==== [[Rule of Material Equivalence/Formulation 1|Formulation 1]] ====
{{:Rule of Material Equivalence/Formulation 1}}
==== [[Rule of Material Equivalence/Formulation 2|Formulation 2]] ====
{{:Rule of Material Equivalence/Formulation 2}}
\end{theorem}

config: wiki


TITLE: Real Analysis: $c^n \lt a$, there exists $\epsilon \gt 0$ s.t. $(c+\epsilon)^n \lt a$
QUESTION [0 upvotes]: I have a question about a task I don't quite understand.
Let $c \gt 0$, $a \in \mathbb {R}$ and $n \in \mathbb {N}$.
If $c^n \lt a$, there exists $\epsilon \gt 0$,  s.t. $(c+\epsilon)^n \lt a$
If $c^n \gt a$, there exists $\epsilon \gt 0$,  s.t. $(c-\epsilon)^n \gt a$
I don't really understand where they're coming from. I guess it says that if $c^n \lt a$, there is always space for an $\epsilon \gt 0$ and the result will still be smaller than $a$. But that's where I'm stuck. Is there a simple way to put this?

REPLY [1 votes]: Since $f:[0,\infty)\to\mathbb{R},$ $x\mapsto x^{1/n}$ is increasing, if $c^n < a$ then $c< a^{1/n}$. Surely you can find some real number between $c$ and $a^{1/n}$, call it $b$; take $\varepsilon=b-c$. Do a similar trick for the other side.


TITLE: Show that $X^2 \cap \le_X $ is a well ordered set.
QUESTION [1 upvotes]: Prove that if $X \subset \Bbb{N},$ then the order induced by $\le$ in $X$ is a well-ordered set. By induced order I mean $X^2 \cap \le_X .$
The excercise cites this other problem: If $R$ is an order in $A,$ and $B \subset A$, then $B^2 \cap R $ is an order in B. It is called the induced order.
My main issue is that I don't know what $X^2 \cap \le_X $ means. It could be that the set refers to the pairs $\{(k,k), (k+1, k+1), ... , (k+m, k+m)\} $ where $k+i, i\in \Bbb{N} $. Or maybe the set are the ordered pairs $(m,n)$ with $(m,n)$ in the cartesian product $X^2$. And as $(\Bbb{N}, \le)$ is a well-ordered set, $(a,a)$ could be a least element. But I guess It would all depend in how the actual order is defined.
Thanks in advance

REPLY [2 votes]: The set-theoretic definition of a binary relation on a set $X$ is a subset of $X\times X.$ So $a\leq b$ means there is a set called $\leq,$ and the ordered pair $(a,b)$ belongs to $\leq.$ In set-theory, if $R$ is a binary relation on the set $X$ then  the set which in non-set-theoretic notation is denoted by $\{(a,b)\in X^2: aRb\}$ is denoted by $R.$
What  you meant to ask ( after you fix the typos) was to show that $X^2\cap \leq_{\mathbb N}$ is a well-order on $X\subset \mathbb N$ where $\leq_{\mathbb N}$ is the usual order on $\mathbb N.$ In non-set theoretic language, to prove that if $X\subset \mathbb N$ then the usual order $\leq$ of $\mathbb N,$ restricted to $X,$ is a well-order on $X.$
BTW. The method of proof applies to any well-order on any set $N'$ and any $X\subset N'.$
Remark:This kind of notation in set-theory is also seen with regard to functions: In set-theory a function is the same thing as "its graph".


TITLE: Shine a beam of light horizontally, drop a stone from same height - would both hit the ground at the same time?
QUESTION [38 upvotes]: If a beam of light was shone horizontally, and simultaneously a stone was dropped from the same height, would they both hit the ground a the same time?
Of course on Earth they would not, but let's imagine a land mass large enough for the light not to fire off into space and away from the pull of the land's gravity.

REPLY [0 votes]: At the same time with writing my answer about black holes and other mumbo jumbo, I am also intuitively feeling that something must be wrong with it. There must be a way to visualize the equivalence principle also applying for light and it should not involve us falling in a black hole...
If we assume uniform gravity and a perfectly flat surface, we can decrease the height we run our experiment from so the time it takes the stone to fall is smaller and smaller, thus also limiting how far the light can go, so obviously we do not need a surface as huge as to create a black hole or even make its curvature obvious...
Well, it seems we have to get really precise, but it is a thought experiment anyway, so why not?
A micro-meter height gives us a 135km distance, a nanometer gets it down to 4.3 km (see formula).
(You can play around with the calculation in google :p or maybe wolfram alpha if you are less lazy than me.)
Those distances may seem small enough, but a planet's curvature over them is still huge... the vertical displacement of our "ground" if it were not flat but had a radius like our earth at those 4.3km away for the nanometer height test is almost 3 meters.
(see formula)
In the end, if we had some super flat surface and a super-uniform gravity field so it looked like it was perpendicular to it over a sufficient length, I guess we could see a light ray falling to the surface same as a stone. But then we could also say that we have an infinitely massive gravity source an infinite distance away from us, or who knows what... is that just like if we are at a black hole event horizon again?
I never imagined a thought experiment could fail before, but here we are, folks.


TITLE: Old childhood game
QUESTION [0 upvotes]: Well couple of days ago I saw my nephews playing a game that I played as a child (back then there was no computers and we had to play outside :)) And it got me thinking. Game revolves around coupple of simple rules and starts by throwing a rock on a $3$X$3$ square drawn on a sidewalk (filled with numbers $1-9$) Once the first player throws a rock and the rock falls on, let say number $2$ square  that that player "moves" two steps forward and then decides how it will proceed  to reach the "goal" which is $10$ steps from its starting point (I am simplifying the rules and objectives a bit). The decision is, he/she can then move by $2$ steps at the time to reach $10$ or $1$ step at the time or mix his/hers decisions but cannot go higher that $2$. However, once he/she decides to use lower number he/she cannot take the higher one again, so:
2+2+2+2+2+2 = 10
or
2+2+2+1+1+1+1 = 10
or
2+1+1+1+1+1+1+1+1 = 10

but not:
2+2+1+2+1+2 = 10 - no,no

Next, once the decision has been made and the player reaches $10$ (let say the $2+2+2+2+2+2$ = $10$ was the choice) all other players cannot make more than $6$ moves to reach the same goal ($10$) and the number of steps they start with has to be higher than $2$, so the next player throws a rock and gets $3$ thus his/hers options are:
3+2+2+2+1 =10 (5 moves)
3+3+3+1=10 (4 moves)
3+3+2+2+1=10 (6 moves)
...

also in each case player cannot move more than the initial number of steps he/she chose (got by throwing a rock if it got $3$ then $3$ steps is highest he/she can do per move) but can decide to change the numbers to $2$ or $1$ obeying the above rules (no going back)
After reflecting on the game I started wondering how many possible strategies there are in any given particular case and how would i compute that?  So for numbers $3, 4, 5, 6, 7, 8$ and $9$ how many possible strategies there are in total?
Can anyone help with this ??
Thank you.

REPLY [1 votes]: Generalizing to forming a number $N$ as a sum of a sequence of non-increasing numbers each not more that $V$, we have the following recurrence formula:
$$
\begin{align*}
f(x,y) =
\begin{cases}
0 & (y < 0)\\
1 & (y = 0)\\
\sum_{i=1}^{x} f(i,y-i)
\end{cases}
\end{align*}
$$
Where $x$ represents the largest integer available at that point in time and $y$ is the remaining number of steps. Drawing the table of values in your case, we get:
|y / x|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
-------------------------------------------------------------
|  0  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
-------------------------------------------------------------
|  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
-------------------------------------------------------------
|  2  |  1  |  2  |  2  |  2  |  2  |  2  |  2  |  2  |  2  |
-------------------------------------------------------------
|  3  |  1  |  2  |  3  |  3  |  3  |  3  |  3  |  3  |  3  |
-------------------------------------------------------------
|  4  |  1  |  3  |  4  |  5  |  5  |  5  |  5  |  5  |  5  |
-------------------------------------------------------------
|  5  |  1  |  3  |  5  |  6  |  7  |  7  |  7  |  7  |  7  |
-------------------------------------------------------------
|  6  |  1  |  4  |  7  |  9  |  10 |  11 |  11 |  11 |  11 |
-------------------------------------------------------------
|  7  |  1  |  4  |  8  |  11 |  13 |  14 |  15 |  15 |  15 |
-------------------------------------------------------------
|  8  |  1  |  5  |  10 |  15 |  18 |  20 |  21 |  22 |  22 |
-------------------------------------------------------------
|  9  |  1  |  5  |  12 |  18 |  23 |  26 |  28 |  29 |  30 |
-------------------------------------------------------------
|  10 |  1  |  6  |  14 |  23 |  30 |  35 |  38 |  40 |  41 |
-------------------------------------------------------------

Then the total number of ways is the sum of the numbers on the bottom row, which is $1 + 6 + 14 + 23 + 30 + 35 + 38 + 40 + 41 = 228$
At the moment I am not sure if there is a closed form formula for $f(x,y)$.


TITLE: Iterations of the radical of an integer
QUESTION [4 upvotes]: We denote for an integer $n>1$ its square-free kernel as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p,\tag{0}$$
with the definition $\operatorname{rad}(1)=1$. You can see this definition and the properties of this arithmetic function from the Wikipedia Radical of an integer. Then I wondered about a variant of two problems showed in last paragraphs of section B 41 of Guy's book [1].
Definition. For each fixed integer $n\geq 1$, I consider the arithmetic function $$f(n)=f^1(n):=\operatorname{rad}(n)+1,\tag{1}$$
and we create the iterated $$f^{k+1}=f(f^{k}(n))\tag{2}$$
until $f^{T}(n)$ reaches a prime number, here thus $T=T(n)$ is a function depending on $n$ (that is the number of steps in our iteration that we need to wait until the sequence of iterated $f^{k}(n)$ reaches a prime number
for the first time). We can call stopping time to the arithmetic function $T(n)$ (defined thus for integers $n\geq 1$ and taking positive values).
Example 1. Let $n=1$, then in a step the sequence of iterations reaches a prime number since $f(1)=f^1(1)=\operatorname{rad}(1)+1=1+1=2$ is a prime number. The same argument works with the composite number $n=8$, because $f(8)=f^1(8)=\operatorname{rad}(8)+1=2+1=3$ a prime number. Thus in our table $T(1)=1$ iteration, and also in this example we've seen that the corresponding  sequence defined for the integer $8$ has stopping time $T(8)=1$.
Example 2. We work about the calculation of $T(33)$. We iterate while the result is a composite integer. Here $\operatorname{rad}(33)=33$, thus $f(33)=34$ and since $34=2\cdot 17$ is also square-free then $f^2(33)=f(f(33))=34+1=35$. Again our last iterated, that is $35=5\cdot 7$ has no repeated prime factors, thus we write $f^3(33)=f(35)=36$. Finally $f^4(33)=\operatorname{rad}(36)+1=6+1=7$ that results a prime number. Thus we conclude that $T(33)=4$.
Computational fact. I did few experiments/calculations and seems that the arithmetic function $T(n)$ is erratic, thus it makes sense to study averages of consecutive values of this stopping time.

Question. I would like to know if it is possible to deduce a tighter upper bound for $$\frac{1}{N}\sum_{1\leq n\leq N}T(n)\tag{3}$$
  as $N$ grows (if you are able to provide an elaborated statement about the asymptotic behaviour of $(3)$ as $N\to\infty$ feel free to do it). Many thanks.

Final remarks. My motivation was to propose a similar variant of the mentioned problems in Guy's book, now for other interesting arithmetic function $\operatorname{rad}(n)$. I've no idea about a strategy to attack the problem to get idea about the size of the average means of the $T(n)$.
References:
[1]  Richard K. Guy, Unsolved Problems in Number Theory, Volume I, Second Edition, Springer (1994).

REPLY [2 votes]: Note that $f(n)=n+1$ if $n$ is square-free, which can happen at most three times in a row when iterating $f$, namely one of $n,n+1,n+2,n+3$ must be a multiple of $4$. And if $n$ is not square-free, then $2\le f(n)\le \frac n2+1$. Thus it takes up to four iterations to take $n$ to a number $\le \frac{n+3}2+1$. Thus if we start with $n\le 5+2^m$, we arrive at a number $\le 5+2^{m-1}$ after at most $4$ iterations.
Thus after at most $4\log_2(n-5)$ we are at a prime or at $4$ or $6$.
This gives the (correct, but probably very pessimistic) upper bound
$$ T(n)\le 1+4\log_2(n-5)\sim \frac 4{\ln2}\cdot \ln n\approx 5.77\ln n$$
(which then holds in similar form for the averaged $T$).

A more heuristic appoach is that the probability of $n$ beinf squarefree is $\frac 6{\pi^2}$, hence on average, we should be able to replace the factor $4$ above with $\frac{\pi^2}6\approx1.64$. We might also note that when $n$ is a multiple of $4$, its is a multiple of $8$ or higher about half the time etc. Thus we should then not step from $\sim 2^m$ to $\sim 2^{m-1}$, but on average more like to $2^{m-1-\frac12-\frac14-\ldots}=2^{m-2}$. Boldly combining both ideas, we get a heuristic estimate of $\sim \frac{\pi^2}6\log_4n\approx 1.19\ln n$. And there is still room for impovement by stopping t other primes than $2,3,5,7$.


text:
\section{Conclusion}
Starting from the stiff differential equation $y'=\fs(y) + \ff(y)$, where $\ff$ represents a few severely stiff, but cheap, ``fast'' components, we have proposed a modified equation \cref{eq:odemod} whose stiffness no longer
depends on $\ff$.  It involves an averaged force $\fe$ of $f = \fs+\ff$, evaluated by solving the stiff, but cheap, auxiliary problem \cref{eq:defu} over short time and thus forms the basis of the following multirate strategy:
Solve \cref{eq:odemod} with an explicit numerical method whose stability conditions are determined by the mildly stiff, but expensive, ``slow'' components $\fs$,
while solving \cref{eq:defu} with a separate explicit method whose stability conditions are determined by $\ff$, whenever an evaluation of $\fe$ is needed.
In Theorems \ref{thm:fecontr} and \ref{thm:erryeta}, we have proved that the modified equation \eqref{eq:odemod} approximates the original problem to first-order accuracy while preserving its contractivity properties. The stability analysis of the multirate test equation \cref{eq:modtesteq} underpins the reduced stiffness of the modified equation, which no longer depends on the fastest components $\ff$ for $\eta$ sufficiently large -- see \Cref{thm:stifflinscamod}.

By discretizing \eqref{eq:odemod} with an $s$-stage (explicit) Runge-Kutta-Chebyshev (RKC) method while
evaluating $\fe$ with one step of a separate $m$-stage RKC method, we have devised a new
multirate RKC method. The resulting mRKC method, given by \eqref{eq:defsmeta}--\eqref{eq:defbue},
is fully explicit, stable, and first-order accurate, as proved in \cref{thm:stab_mrkc,thm:firstorder}, without
the need for interpolation or extrapolation of missing stage values. Thanks to the reduced stiffness in  \eqref{eq:odemod}, the number of expensive $\fs$ evaluations is greatly reduced and independent of
the severe stiffness induced by just a few degrees of freedom in $\ff$, without any assumption about scale separation.

For semi-discrete parabolic problems, where $\fs$ and $\ff$ correspond to discretized diffusion operators
in the coarse and locally refined regions of the mesh, respectively,
the mRKC method permits to overcome the crippling effect on explicit time integrators
due to a few tiny elements or grid cells.
In particular, for diffusion dominated problems in complex geometry, the mRKC method is up to forty times faster than a standard first-order RKC method; it is also up to seventy times cheaper than a second-order RKC2 \cite{SSV98,VHS90} method for moderately high error tolerances.
Thus, the  mRKC method recovers
the well-known efficiency of RKC methods for large-scale, possibly nonlinear, parabolic problems
without sacrificing explicitness, even in the presence of local mesh refinement. When compared to the implicit Euler method, the mRKC scheme's performance depends on the degree of stiffness, problem size and nonlinearity. In all our numerical experiments, mRKC performed similarly, or even better, than IE, without the need for solving any linear systems. Moreover, our numerical experiments suggest that with increasing problem size, the efficiency of IE rapidly decreases, whereas mRKC remains only marginally affected.

The multirate strategy introduced here also paves the way for higher order extensions and for developing explicit stabilized multirate methods for stiff stochastic differential equations \cite{AbR22b}.


TITLE: limit law and product of matrices
QUESTION [3 upvotes]: Are there two $ n\times n $ matrices $A$ and $B$ such that $ \lim_{m\to\infty} A^m$  and $ \lim_{m\to\infty} B^m  $ both exists but $ \lim_{m\to\infty} (A \cdot B)^m  $ doesn't ?

REPLY [3 votes]: It's not true for $n=2$, take $A=\pmatrix{0&1\\ 0&0}$ and $B=\pmatrix{0&0\\\ -1&0}$. Then for $m\geq 2$ $A^m=B^m=0$ but $AB=\pmatrix{-1&0\\\ 0&0}$ so $\lim_{m}(AB)^m$ doesn't exists.
For a general $n\geq 2$, just take $A$ and $B$ with other entries $0$.


TITLE: For sets of reals $A$ and $B$, is it true that $(A + B)' = (\overline{A} + B') \cup (A' + \overline{B})$?
QUESTION [0 upvotes]: If $A, B \subset \mathbb{R}$ are bounded sets then I want to prove that $(A + B)' = (\overline{A} + B') \cup (A' + \overline{B})$. I'm stuck in both directions and I believe that is not true.
Any help will be appreciated.

REPLY [1 votes]: It seems the following
I shall understand $C'$ as the set of all non-isolated points of the space $C$.
Put $A=\Bbb Z$, $B=\sqrt{2}\Bbb Z$. Then both sets $A$ and $B$ are closed discrete subsets of the space $\Bbb R$, so $A'=B'=\varnothing$, $A+B$ is dense in $\Bbb R$, so $$(A+B)'=A+B\ne \varnothing=(\overline{A} + B') \cup (A' + \overline{B}).$$
The opposite inclusion also fails. Put $A=B=\Bbb Q$. Then
$(A+B)'=\Bbb Q'=\Bbb Q$ but both $\overline{A} + B'$ and $A' + \overline{B}$ equals $\Bbb R$.
Update. If you understand $C′$ as the set of all non-isolated points of the space $\overline{C}$ then the claim holds. Indeed, put $D=(\overline{A} + B')\cup (A' + \overline{B})$. Then $D\subset \overline{A}+\overline{B}\subset\overline{A+B}$. Let $c\in \overline{A} + B'$. There exists a point $a\in \overline{A}$ and a non-isolated point $b\in \overline{B}$ such that $c=a+b$. Since $b$ is a non-isolated of the set $\overline{B}$, there exists a sequence $\{b_n\}\subset\overline{ B}\setminus\{b\}$, convergent to the point $b$. Then a sequence $\{a+b_n\}\subset \overline{A+B}\setminus\{a+b\}$ converges to the point $a+b=c$. So $c$ is a non-isolated point of the set $\overline{A+B}$. The inclusion   $(A' + \overline{B})\subset (A+B)’$ can be proved similarly.
To show the opposite inclusion we use the boundedness of the set $A$. Let $c\in (A+B)’$. Then there exists a sequence $\{c_n\}\subset\overline{A+B}\setminus\{c\}$ such that $|c_n-c|<1/n$ for each $n$. Since $c_n\in \overline{A+B}$, there exist points $a_n\in A$ and $b_n\in b$ such that $|a_n+b_n-c_n|<1/n$. Since the set $A$ is bounded, a sequence $\{a_n\}$ has a subsequence $\{a_{n_k}\}$ convergent to a point $a\in\overline{A}$. Then the sequence $\{b_{n_k}\}$ converges to a point $c-a=b\in\overline{B}$. If $a\in A’$ or $b\in B’$ then $c\in D$. In the opposite case $a$ is an isolated point of the set $A$ and $b$ is an isolated point of the set $B$. Then both sequences $\{a_{n_k}\}$ and $\{b_{n_k}\}$ stabilize (that is, are eventually constant), so the sequence $\{c_{n_k}\}$ stabilizes too, a contradiction.


TITLE: 4 people apply for 3 jobs; what's the probability that I will get a job?
QUESTION [0 upvotes]: There are 4 people being interviewed for a job, one of them being me. There are 3 jobs. What is the probability of me getting a job? I think it's 75%.

REPLY [0 votes]: I think OP wants to know if they’re hiring 3 people and 4 people apply what’s his or her probability..
Applicants that can fill the 3 spots when all spots are still open:
1,2,3
1,2,4
1,3,4
2,3,4
Each number appears 3 times in 4 different arrangements. 3/4. 75%
Say the first spot is filled by applicant 1.. (you are number 4)
2 openings left and 3 applicants to choose from.
Arrangements of applicants for the number 2 spot:
2,3
2,4
3,4
Each number appears 2 times in the 3 arrangements. 2/3. 66 percent chance you fill the second slot.
Obviously it’s 50 percent for the last slot.
I don’t know if you can average probability outcomes?? Lemme know because if you can, your overall probability to get a job in this situation would be 63.6%


TITLE: How to calculate shortest distance in polar coordinates when approaching a pole
QUESTION [0 upvotes]: Given a distance (generally, a large one, say of 850km), a polar coordinate on the earth, and a bearing (with respect to the north pole), I'm using the Haversine formula to calculate a second coordinate. However, as I approach a pole, the shortest distance becomes tangential to that pole (at least I think so--correct me if I'm wrong). I'm not a mathematician, but a programmer, so bear with me while I lay out my formula and the results:
φ2 = arcsin(sin(φ1) * cos(850000/6371000) + cos(φ1) * sin(850000/6371000) * cos(bearing)) * (180 / π)
λ2 = (λ1 + arctan(sin(bearing) * sin(850000/6371000) * cos(φ1), cos(850000/6371000) - sin(φ1) * sin(φ2))) * (λ2 - π) * (180 / π)

I also have a formula that resets the coordinates to 180/-180 degrees when they cross either threshold, but I'm not entirely sure how to represent that mathematically.
Given a starting latitude and longitude (83.8047036171331, -27.8616033804678), I convert to radians and iterate from -180 degrees bearing to 180 degrees bearing, finding coordinates at 850km from my starting coordinate. I'm hoping to have a polygon as an end result. Here are my numbers divided by quadrant with respect to bearing:
-180.0 : 76.1604699668239, -27.8616033804677
-165.0 : 76.2781247730064, -36.2069893102399
-150.0 : 76.6289215559029, -44.5762730745583
-135.0 : 77.2063944341844, -52.9975787393726
-120.0 : 77.9998819868466, -61.5087265207167
-105.0 : 78.994667035189, -70.1659285755627

-90.0 : 80.1720895006312, -79.0598803856636
-75.0 : 81.5094837735314, -88.3495571649968
-60.0 : 82.9795366250911, -98.3431131407785
-45.0 : 84.5477083040733, -109.725327457386
-30.0 : 86.1617477729691, -124.353651321838
-15.0 : 87.6953134517602, -148.975376057487

0.0 : 88.5510627325576, 152.138396619532
15.0 : 87.6953134517602, 93.2521692965516
30.0 : 86.1617477729691, 68.6304445609022
45.0 : 84.5477083040733, 54.0021206964505
60.0 : 82.9795366250911, 42.619906379843
75.0 : 81.5094837735314, 32.6263504040613

90.0 : 80.1720895006312, 23.3366736247281
105.0 : 78.994667035189, 14.4427218146272
120.0 : 77.9998819868466, 5.7855197597812
135.0 : 77.2063944341844, -2.72562802156294
150.0 : 76.6289215559029, -11.1469336863772
165.0 : 76.2781247730064, -19.5162174506955
180.0 : 76.1604699668239, -27.8616033804677

As you can see, once I get to about 85 degrees N, the numbers start to increase precipitously. Now I understand in a very basic sense that the curve of a great circle has to do with its relationship to a pole and that a pole is a kind of coordinate singularity. Now my question is, how do I calculate a point that should, reasonably it seems, transverse a pole? Is the haversine formula inadequate in this regard and if so, is there another methodology for calculating a transpolar location? I apologize in advance if some of my vocab is off! Like I said I'm an amateur with interest in Mathematics but without much of a formal education!

REPLY [2 votes]: I haven't checked the formula, but you have ${850000 \over 6371000}$ instead of
either ${8500000 \over 6371000}$ or ${8500 \over 6371}$.
The point for the -180 bearing in the data above is about 750 km south of the center location.
(I believe the correct coordinates are about $(-96.1953,    -75.7800)$.)
It is not clear to me how you are computing your new coordinates. The Haversine formula is used to compute the distance given two sets of coordinates and does
not have a trivial inverse. Perhaps you can provide a link?
Here is one way to do it, I am sure there must be better ways:
I am performing the computations in the x-y-z plane rather than using
latitude/longitude. The mapping between the two is straightforward.
Given a point $p \in \mathbb{R}^3$ on the surface of the earth excluding the poles, a bearing $\beta$ (measured clockwise from north) and a distance $L$,
compute a new point $p'$ a distance $L$ away from $p$ at bearing $\beta$ (from $p$).
Note that the poles are excluded so that the bearing makes sense, at either pole a bearing to/from North makes no sense.
I am assuming a perfectly spherical Earth. To reduce notational clutter,
 define
$u: \mathbb{R}^3 \setminus \{0\} \to \mathbb{R}^3$ by $u(x) = {1 \over \|x\|} x$ (that is, normalise $x$).
Let $R= \|p\|$, be the radius (of the idealised Earth), and let $N=(0,0,R)$ be the porth pole.
Note that a distance $L$ corresponds to an angle (at the Earth's center) of
$\alpha = {L \over R}$ (radians).
Compute a 'local north direction' $\nu = u(N-{1 \over R^2}\langle p, N \rangle p)$. This is a direction contained in the intersection of the tangent plane at $p$ with the subspace containing $p$ and $N$.
Compute a 'local east direction' $e = u(\nu \times p)$. This is a
direction perpendicular to both $\nu$ and $e$ with the appropriate
orientation.
(Note that $\nu, p, e$ are mutually orthogonal.)
Compute a 'local direction' $d = (\sin \beta) e + (\cos \beta) \nu$.
This is a unit vector in the direction we want to go in on the tangent
plane at $p$.
Then we have the new point $p' = (\cos \alpha) p + (\sin \alpha) R d$.


TITLE: Problems about cadlag functions.
QUESTION [1 upvotes]: $f$ is a cadlag function on $[0,1]$,i.e. right continuous and has left limits for all $x\in[0,1]$.
How to prove:
for all $\epsilon>0$
$\{x_0\in[0,1]|f \text{ has a jump on }x_0 \text{ larger than }\epsilon\}$ is a finite set.

REPLY [0 votes]: Let $A = \{x_0\in[0,1] : f \text{ has a jump on }x_0 \text{ larger than }\epsilon\}$. If $A$ contains infinite number of points, then there exists $\{x_n\} \subset A$ such that $x_n \to x \in [0,1]$
If $x_n$ converge to $x$ from the right side, then since $f$ is cadlag we have $$f(x_n) \to f(x)$$ But at the same time $|f(x_n) - f(x_n-)| > \epsilon$, which means for any $n$ we can find $k_n$ such that $x_n - \frac{1}{k_n} > x$ and $$|f(x_n) - f(x_n - \frac{1}{k_n})| \geq \frac{\epsilon}{2}$$  But $x_n - \frac{1}{k_n}$ also convergs to $x$ from the right side, so we should have $$f(x_n -\frac{1}{k_n}) \to f(x)$$
Now we get an obvious contradiction.
Similarly we can find contradiction when $x_n$ coverges to $x$ from the left side.


text:
\begin{document}

	\title{Positioning Data-Rate Trade-off in mm-Wave Small Cells and Service Differentiation for 5G Networks}
	\author{$^*$Gourab Ghatak$^{1,2}$, $^*$Remun Koirala$^{1,3,4}$, Antonio De Domenico$^1$, Benoit Denis$^1$, Davide Dardari$^4$, and Bernard Uguen$^3$
     \\ \small{ $^1$CEA, LETI, MINATEC, F-38054 Grenoble,
France; $^2$LTCI, Telecom ParisTech, Universit\'e Paris Saclay, France; $^3$University of Rennes 1-IETR (CNRS UMR 6164), Rennes, France; $^4$DEI, University of Bologna, Cesena (FC), Italy}
\vspace*{-0.0cm}}
		\maketitle

	\begin{abstract}
We analyze a millimeter wave network, deployed along the streets of a city, in terms of positioning and downlink data-rate performance, respectively. First, we present a transmission scheme where the base stations provide jointly positioning and data-communication functionalities. Accordingly, we study the trade-off between the localization and the data rate performance based on theoretical bounds. Then, we obtain an upper bound on the probability of beam misalignment based on the derived localization error bound. Finally, we prescribe the network operator a scheme to select the beamwidth and the power splitting factor between the localization and communication functions to address different quality of service requirements, while limiting cellular outage.
	\end{abstract}
    \vspace*{-0.0cm}
\section{Introduction}
{\let\thefootnote\relax\footnote{{$^*$These authors have equal contribution in the work.\\
The research leading to these results has received funding from European Union under grant n. 723247 and supported by the Institute for Information \& communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No.B0115-16-0001, 5GCHAMPION).}}}
To address the multi-fold increase in the demand for data rates, exploitation of higher frequency spectrum in the millimeter wave (mm-wave) range is gaining popularity~\cite{rappaport2013millimeter}. However, mm-wave communication is characterized by high path loss and sensitivity to blockages. To solve these problems, beam-forming techniques are utilized with the help of highly directional antennas, which result in new issues in terms of coverage and initial access~\cite{li2016initial}. Moreover, beam-alignment errors between the base stations (BSs) and the user equipments (UEs) degrade the communication performance.
One solution to this problem consists of enabling UEs to simultaneously receive signals in the mm-wave and in the sub-6GHz band, and to use the latter to support the initial access on the mm-wave band~\cite{ghatak2017coverage}.
Another approach exploits positioning algorithms to support the UE cell discovery and access to mm-wave BSs. On the one hand, with fine-tuned positioning, the beam-alignment procedure is quickened, and beamforming and user tracking are improved~\cite{garcia2016location}. On the other hand, improved mm-wave beam-forming can be used for more accurate localization and orientation of nodes~\cite{Destino2017on}.

In addition to the high speed data rates, the fifth generation (5G) cellular networks anticipate an explosion of new services, characterized by heterogeneous requirements.
We investigate a mm-wave network deployed for supporting positioning and broadband functionalities simultaneously, e.g., in vehicle-to-infrastructure communication. Specifically, we study the trade-off between positioning efficiency and downlink data rates and accordingly, we prescribe the operator an algorithm to tune the mm-wave BS transmit power so as to meet specific quality of service (QoS) requirements of different services.

 \vspace*{-0.3cm}
\subsection{Related Work}
 \vspace*{-0.2cm}
In the context of sub-6GHz systems, Jeong et al.~\cite{jeong2015beamforming} have studied a distributed antenna system providing both data communication and positioning functionalities. The authors assumed that the UEs know the positions of the BSs and attempt to estimate their own positions based on the received signals. Lemic et al.~\cite{lemic2016localization} have shown that localization using mm-wave frequencies is efficient in terms of accuracy, even in the presence of a limited number of anchor nodes. In fact, mm-wave beam-forming allows for accurate localization and orientation of UEs with respect to the BSs~\cite{Destino2017on}. Garcia et al.~\cite{garcia2016location} have studied a location-aided initial access strategy for mm-wave networks, in which the information of UE locations enables to speed up the channel estimation and beam-forming procedures. Destino et al.~\cite{Destino2017on} have studied the trade-off between communication rate and positioning quality in a single user mm-wave link. Similarly Koirala et al.~\cite{koirala17localization} have studied the beamforming optimization and spectral power allocation based on theoretical localization bounds.

The downlink communication performance in random wireless networks is typically characterized by signal to interference and noise ratio (SINR) coverage probability and rate coverage probability, using stochastic geometry~\cite{bai2015coverage}. For this, the positions of the BSs are modeled using homogeneous Poisson point process (PPP)~\cite{elshaer2016downlink} or using repulsive point processes~\cite{chun2015modeling}. Recently, Ghatak et.al.~\cite{8254855} investigated a more realistic scenario, where mm-wave BSs are deployed along the roads of a city. We use this model in this paper, and accordingly we study a one dimensional setting where the BSs and the served users are assumed to be on the same street.

Specifically, leveraging on the tools of stochastic geometry, we present an average characterization of the localization and communication performance of this network, by exploiting the a-priori knowledge about the distribution of the distances of the users from the BSs. We analyze the positioning and data communication trade-off, and provide the operator with a power control scheme designed to satisfy distinct QoS requirements of the positioning and the communication functions.
 \vspace*{-0.2cm}
\subsection{Contributions and Organization}
The main contributions of this paper are:
\begin{itemize}
\item We characterize a noise-limited mm-wave system designed to support positioning and broadband services simultaneously by partitioning the BS transmit power. First, we obtain the Cramer-Rao lower bound (CRLB) for the estimation of the distance of a typical UE from its serving BS. Subsequently, we obtain the signal to noise ratio (SNR) and rate coverage probability of the typical user, as a function of the power splitting factor.
\item Leveraging on the derived CRLB for the estimation of the distance, we obtain an upper bound on the probability of beam-misalignment. Based on this, we compute the minimum antenna beamwidth that limits the beam-misalignment.
\item Finally, we analyze the trade-off between the positioning and the data rate performance of the typical user. Accordingly, we prescribe the operator with a scheme to select the proper power splitting factor to support different QoS requirements. Specifically, we study our mm-wave system under different operating beamwidths, and analyze the distribution of the total transmit power for maximizing either the positioning efficiency or the UE data-rate.
\end{itemize}
The rest of the paper is organized as follows. In Section~\ref{sec:SM}, we introduce our system model and outline the performance objectives. In Section~\ref{sec:MR}, we derive our main results on the positioning error, the rate coverage, and the misalignment error. We provide some numerical results in Section~\ref{sec:NRD}, and accordingly present our power partitioning scheme. Finally, the paper concludes in Section~\ref{sec:Con}.
\vspace*{-0.2cm}
\section{System Model}
\label{sec:SM}
We consider an urban scenario, with multi-storied buildings that result in a dense blocking environment. In this scenario we analyze a mm-wave network consisting of BSs deployed along the streets of the city.
\vspace*{-0.3cm}
\subsection{Network Geometry}
The positions of the BSs in each street are modeled as points of a one-dimensional Poisson point process (PPP) $\phi$, with intensity $\lambda$ [m$^{-1}$]. Each BS is assumed to be of known height $h_B$ and equipped with directional antennas with beamwidth $\theta$. Let the corresponding product of the directivity gains of the transmitting and receiving antennas be $G_0$. The transmit power of the BSs is assumed to be $P$. Without loss of generality we perform our analysis from the perspective of a typical user located at origin, which associates with the BS that provides the highest downlink power.
Accordingly, the distribution of the distance $d$ of the typical user from the serving BS is given by~\cite{chiu2013stochastic}:
\begin{align}
f_d(x) = 2\lambda\exp(-2\lambda x)
\label{eq:dist}
\end{align}
Furthermore, we assume that the network is equipped with efficient interference management capabilities (e.g., spatio-temporal frequency reuse), so that the performance of the users is noise-limited\footnote{Although the assumption of the network being noise-limited simplifies the analysis, Singh et al.~\cite{5733382} have shown the validity of this assumption in outdoor mm-Wave mesh networks. In a future work, we will extend the analysis by considering interfering BSs.}.
\vspace*{-0.2cm}
\subsection{Path-loss}
\vspace*{-0.1cm}
Due to the low local scattering, we consider a Nakagami fading for mm-wave communications~\cite{7593259} with parameter $n_0$ and variance equal to 1. Furthermore, we assume a path loss model where the power at the origin received from a BS located at a distance $d$ is given by $P_r = K\cdot P \cdot g \cdot G_0 \cdot (d^2 + h_B^2)^{\frac{-\alpha}{2}}$, where $K$ is the path loss coefficient, $g$ represents the fast-fading, and $\alpha$ is the path loss exponent. Thus, the average SNR can be written as $\frac{K\cdot P \cdot G_0 \cdot (d^2 + h_B^2)^{\frac{-\alpha}{2}}}{N_0 \cdot B}$. $N_0$ and $B$ are the noise power density and the operating bandwidth, respectively.
\vspace*{-0.5cm}
\subsection{Transmission Policy}
We assume a communication scheme where the transmit power of the BSs is divided into two parts: one associated with positioning and the other allotted for data communication. The power allocated for localization determines the number of control symbols used for this function, whereas the remaining power is utilized for control and data symbols of the communication phase. We acknowledge that it is possible to utilize the native communication signal for positioning services. However, we use dedicated waveforms designed for better localization performance (e.g., see \cite{damman16optimizing} for a discussion on localization specific waveforms). Hence, splitting of the transmit power becomes necessary to characterize and optimize the operating trade-off between communication and localization functionalities.

Accordingly, if the total transmit power is $P$, and $\beta$ is the fraction of power used for data services, the corresponding transmit power for localization is $P_L = (1 - \beta)P$. Consequently, the transmit power for data service is $P_D = \beta P$. Let the SNR for the distance estimation and the data communications phases be represented by $SNR_1$ and $SNR_2$, respectively.
\vspace*{-0.2cm}
\section{Positioning Error, Data Rate Coverage and Misalignment Error}
\label{sec:MR}
In this section, we first characterize the minimum variance of the error in the estimation of the distance of the typical user from the serving BS. Then, we derive the SNR coverage and the rate coverage probabilities.
\vspace*{-0.2cm}
\subsection{Distance Estimation Analysis}

To simplify our analysis, we only consider the effect of the distance on the power of the received signal (for instance, we consider Received Signal Strength Indicator (RSSI) based ranging algorithms), and ignore the effect of the distance on the phase~\cite{wu2012fila}. Accordingly, the received signal is:
\begin{equation}
	y(t) = \frac{\sqrt{KG_0P_L}}{(h_B^2+d^2)^{\frac{\alpha}{4}}} x\left(t\right) + n(t),
\end{equation}
where $n(t)$ is a zero mean additive white Gaussian noise resulting in estimation errors.

\begin{lemma}
The expected value of the Fisher information for the estimation of the distance ($d$) is calculated as:
\begin{align}
J_D = \frac{KG_0P_L  2 \lambda \bar{f^2}}{\sigma_N^2}  \int_1^\infty \frac{e^{-2 \lambda x}}{(h_B^2+x^2)^{\frac{\alpha}{2}}} d x,
\end{align}
where $\bar{f^2} = 1.25\pi^2B^2$.
Furthermore, the prior information is:

$J_p = \log\left(2\lambda \right) - 1$.

\label{lem:FIM}
\end{lemma}
\begin{proof}
The Fisher information for a given $d$ is~\cite{van2004detection}:

\begin{equation}
	J_d = \frac{KG_0P_L}{(h_B^2+ d^2)^{\frac{\alpha}{2}} \sigma_N^2} \bar{f^2},
\end{equation}
where $\bar{f^2}= \frac{\int_{-\infty}^{\infty} (2 \pi f)^2 |X(f)|^2 df}{\int_{-\infty}^{\infty} |X(f)|^2 df}$ is the effective bandwidth of the signal. In our case, we assume that the signal has a flat spectrum~\cite{Destino2017on}, and accordingly, we have $\bar{f^2} = 1.25\pi^2B^2$.
Now using the distribution of $d$ from~\eqref{eq:dist}, the expectation of the Fisher information is calculated as:
 \begin{eqnarray}
 	J_D = \mathbb{E}_d \left[ J_d \right] = \frac{KG_0P_L  2 \lambda \bar{f^2}}{\sigma_N^2}  \int_1^\infty \frac{e^{-2 \lambda x}}{(h_B^2+x^2)^{\frac{\alpha}{2}}} d x.

 \end{eqnarray}
 Finally, the prior information can be calculated as:
\begin{align}
J_p &= \mathbb{E} \left[\log(f_d(x))\right] = \int_0^{\infty}   \log\left(f_d(x)\right)f_d(x) d x \nonumber \\
& = \int_0^{\infty} \log\left(2 \lambda  \exp\left(-2  \lambda x\right)\right) 2 \lambda \exp\left(-2 \lambda  x\right) dx \nonumber \\

& = \log\left(2\lambda \right) - 1\nonumber
\end{align}
This completes the proof.
\end{proof}
\begin{corollary}
For the special case of path loss exponent $\alpha = 2$, $J_D$ evaluates to~\eqref{eq:J_tau},
where $Ei$ is the exponential integral~\cite{pagurova1961tables}.
\begin{figure*}
\small
\begin{equation}
	J_D =  \frac{KG_0P_L  2 \lambda \bar{f^2}}{\sigma_N^2} \frac{i ( e^{-i 2 \lambda h} Ei(i 2 \lambda h) -e^{i 2 \lambda h} Ei(-i 2 \lambda h ) )}{2h} + 2\lambda \log\left(2\lambda \right) - 1
    \label{eq:J_tau}
\end{equation}
\hrule
\end{figure*}
\end{corollary}
\vspace*{-0.4cm}

Finally, the Bayesian information can be obtained as $J_B = J_D + J_P$. Consequently, the Bayesian CRLB (BCRLB) and Jeffrey's prior corresponding to the Bayesian information are calculated as $\frac{1}{J_B}$ and $\sqrt{J_B}$, respectively.
\begin{rmk}
Intuitively, higher the Jeffrey's prior (or lower the BCRLB) is, better the estimation efficiency will be. From \eqref{eq:J_tau}, we see that a higher Jeffrey's prior is facilitated by a larger value of $P_L$, i.e., a smaller $\beta$.
\end{rmk}

\vspace*{-0.4cm}
\subsection{Coverage and Rate Analysis}
Based on the path-loss model of Section II-B, the SNR for the communication phase is:
\begin{align}
SNR_2  = \frac{P_D K g G_0}{\sigma_N^2}  ({d^2 + h_B^2})^{-\frac{\alpha}{2}}. \nonumber
\end{align}
Accordingly, let us define the SNR coverage probability of the typical user at a threshold $\gamma$, as the probability that the SNR is greater than $\gamma$. It represents the fraction of the users under coverage in the network.
\begin{lemma}
The SNR coverage probability at a threshold of $\gamma$ is calculated as~\eqref{eq:CovP}.
\begin{figure*}
\small
\begin{align}
&\mathcal{P}_C(\gamma) = \sum_{n = 1}^{n_0}\left(-1\right)^{n+1} \binom {n_0}n2\lambda \exp\left(2\lambda - \frac{h_B^2 n\gamma \sigma_N^2}{P_DKG_0}\right) \left[\frac{\sqrt{\pi}}{2}\left(\sqrt{\frac{P_DKG_0}{n\gamma \sigma_N^2}} - \frac{P_DKG_0}{n\gamma \sigma_N^2}\text{erf}\left(\frac{h_B^2 n\gamma \sigma_N^2}{P_DKG_0}\right)\right)\right]
\label{eq:CovP}
\end{align}
\hrule
\end{figure*}
\end{lemma}
\begin{proof}
The SNR coverage probability is computed as follows:
\begin{align}
&\mathbb{P}\left(SNR_2 \geq \gamma \right) = \mathbb{P}\left(\frac{P_D g K G_0}{\sigma_N^2}  (\sqrt{d^2 + h_B^2})^{-\alpha}  \geq \gamma \right)\nonumber \\
& = \mathbb{P}\left(g \geq \frac{\gamma \sigma_N^2}{P_DKG_0 ({x^2 + h_B^2})^{-\frac{\alpha}{2}}}\right) \nonumber \\
& = \sum_{n = 1}^{n_0}\left(-1\right)^{n+1} \binom {n_0}n\mathbb{E}\left[\exp\left(-\frac{n\gamma \sigma_N^2}{P_DKG_0 ({x^2 + h_B^2})^{-\frac{\alpha}{2}}}\right)\right] \nonumber \\
& = \sum_{n = 1}^{n_0}\left(-1\right)^{n+1} \binom {n_0}n2\lambda \int_0^{\infty}\exp\left(-\frac{n\gamma \sigma_N^2 ({x^2 + h_B^2})^{\frac{\alpha}{2}}}{P_DKG_0}\right) \cdot \nonumber \\
& \hspace*{4cm}\exp\left(-2\lambda x\right) dx \nonumber
\end{align}
Evaluating this integral completes the proof.
\end{proof}
Similar to the SNR coverage probability, the rate coverage probability at a threshold $r_0$ is defined as the probability that the downlink data rate of the typical user is greater than $r_0$.
\begin{corollary}
The rate coverage probability can be computed as:
\begin{align}
\mathcal{P}_R(r_0) = \mathbb{P}\left(R \geq r_0\right) &= \mathbb{P} \left(SNR_2 \geq 2^{\frac{r_0}{B}} -1\right) \nonumber\nonumber \\ & =  P_C\left( 2^{\frac{r_0}{B}} -1\right)
\end{align}
\end{corollary}

\vspace*{-0.7cm}
\subsection{Beam Misalignment Error}
A BS with an antenna beamwith $\theta$, serving a user located at distance $d$, covers a region of length $D_0$ on the ground (see Figure 1). Using simple trigonometric calculations, we have:
\begin{align}
D_0 = \frac{2\tan\left(\frac{\theta}{2}\right)\left[1 + \frac{d^2}{h_B^2}\right]}{1 - \frac{d^2}{h_B^2}\tan^2\frac{\theta}{2}}. \nonumber
\end{align}
Once the localization procedure and the corresponding exchange of user-BS control signals is performed, beam-misalignment can occur in the absence of dynamic beam-alignment on both sides of the radio link. Assuming that the user's antenna is always oriented towards the BS, or equivalently, in case the user is operating with an omni-directional antenna, beam-misalignment will occur in case the distance of the user on the ground is more than $\frac{D_0}{2}$ from the estimated position.

Let us assume that the estimation error for the UE localization is symmetric about its mean. Consequently, we bound the probability of the beam-misalignment as follows:
\begin{lemma}
The probability of beam-misalignment for a user located at a distance $d$ from the serving BS is bounded as $\frac{\text{BCRLB}}{D_0}$.
\begin{proof}
\begin{align}
\vspace*{-0.4cm}
\mathcal{P}_{MA}(d) = \mathbb{P}\left(|d - \hat{d}| \geq \frac{D_0}{2}\right) \stackrel{(a)}{\leq} \frac{2\sigma^2}{D_0} \stackrel{(b)}{=} \frac{2 \cdot \text{BCRLB}}{D_0},
\end{align}
where $\hat{d}$ is the estimated distance of the user. Here (a) follows from Markov's inequality assuming $\sigma^2$ as the variance of the positioning error. The step (b) occurs for an minimum-variance unbiased estimator (MVUE).
\vspace*{-0.3cm}
\end{proof}
\label{lem:missalignment}
\end{lemma}
\begin{corollary}
The mean misalignment error is then bounded by taking the expectation over d, i.e., $\bar{\mathcal{P}}_{MA} = \mathbb{E}_d\left[\mathcal{P}_{MA}(d)\right] \leq \mathbb{E}_d\left[\frac{2 \cdot \text{BCRLB}}{D_0}\right]$.
\end{corollary}
In the next section, we prescribe guidelines for an operator to choose an operating beamwidth for limiting this error.

\vspace*{-0.2cm}
\section{Numerical Results and Discussion}
\label{sec:NRD}
In this section, we present some numerical results based on the analytical framework presented in this paper. First, we show how the SNR coverage probability changes with the power splitting factor ($\beta$). Subsequently, we study the trade-off between localization and data rate as a function of $\beta$. Then, with the help of two examples, we describe our power partitioning scheme. In the following analysis, we assume $G_0 = 10$ dB and $n_0 = 3$.
\vspace*{-0.3cm}
\subsection{SINR Coverage Probability}
In Figure~\ref{fig:SINR} we plot the SNR coverage probability with respect to $\beta$ at a threshold of $\gamma = -10$ dB. As $\beta$ increases, the SINR coverage probability increases due to more power allocated to the data transmission phase. This provides a guideline to select a minimum operating $\beta$ for a given deployment density, such that the outage is limited. As an example, to limit a service outage below 20$\%$, with a BS deployment of 1 km$^{-1}$ and a power budget of $P = 25$ dBm, the minimum $\beta$ is 0.15, whereas with a power budget of $P = 20$ dBm, the minimum $\beta$ is 0.5.

More interestingly, this analysis provides the operator dimensioning rules in terms of the deployment density of the BSs for a given power budget. For example, in order to support services with an outage tolerance of 10$\%$, with a power budget of 20 dBm, a deployment density of 1 km$^{-1}$ does not suffice, and the operator must necessarily deploy more BSs.
\begin{figure}
\centering
\includegraphics[width = 8 cm, height = 4cm]{SNR.eps}
\caption{SNR coverage probabilities for a threshold of $\gamma = -10$ dB vs the fractional power split for different $\lambda$.}
\label{fig:SINR}
\vspace*{-0.5cm}
\end{figure}
\vspace*{-0.2cm}
\subsection{Misalignment Error}
In Figure~\ref{fig:miss} we plot the mean beam-misalignment bound with respect to the beamwidth of the transmit antenna of the BSs. As expected, the larger the beamwidth and the higher the SNR, the lower the misalignment. For example, for a tolerable misalignment of 0.02$\%$ with SNR = -15 dB and $\lambda = 5$ km$^{-1}$, the minimum antenna beamwidth should be 8 degrees.
\begin{figure}
\centering
\includegraphics[width = 8 cm, height = 4cm]{miss.eps}
\caption{Beam misalignment error with respect to beamwidth of the transmit antenna.}
\label{fig:miss}
\vspace*{-0.5cm}
\end{figure}
\vspace*{-0.5cm}
\subsection{Distance Estimation-Data Rate Trade-off}
In Figure~\ref{fig:FIM_Thru_diff_P} we plot the trade-off between the efficiency of the distance estimation of the user, represented by its Jeffrey's prior\footnote{The estimation error is calculated as the inverse of the Jeffrey's prior.} and the rate coverage probability at a rate threshold of 500 Mbps. Each position in the plot for a given deployment parameter corresponds to a particular $\beta$. Thus for a given power budget, deployment density, and operating beamwidth, the performance of the system is determined by a particular operating characteristic, i.e., a trade-off between the positioning efficiency and data rate performance. For a particular operating characteristic, as we increase $\beta$, we improve the rate coverage probability at the cost of degrading the localization efficiency; whereas, decreasing $\beta$ has the opposite effect. Accordingly, there exists a trade-off between the distance estimation and the data rate performance of the system. In the next subsection, we propose a scheme for selecting $\beta$ based on a given operating beamwidth.
\begin{figure}
\centering
\includegraphics[width = 8 cm, height = 4cm]{TO.eps}
\caption{Distance estimation error vs physical data rate for different power budget.}
\label{fig:FIM_Thru_diff_P}
\vspace*{-0.5cm}
\end{figure}
\begin{figure}
\centering
\includegraphics[width = 8 cm, height = 4cm]{FIN.eps}
\caption{Power allocation for the two services for different operating beamwidths.}
\label{fig:final}
\vspace*{-0.5cm}
\end{figure}
\vspace*{-0.4cm}
\subsection{QoS Aware Network Parameter Setting}
We propose the following scheme for setting the network parameters. First, for a given power budget, deployment density and operating beamwidth, the corresponding operating characteristic (i.e., a trade-off curve from Figure~\ref{fig:FIM_Thru_diff_P}) is selected. Next, for the chosen operating characteristic, the minimum $\beta_{min}$ is chosen to satisfy the required outage constraint. Then, for a given positioning error constraint, the maximum value of $\beta$, i.e., $\beta_{max}$ is selected. Finally, the operating $\beta_{min} \leq \beta \leq \beta_{max}$ is selected to address the specific QoS requirements. Accordingly, the misalignment error varies for the chosen $\beta$ and the operating $\theta$.

  In what follows, we explain the total power distribution based on the QoS requirements, for a varying degree of misalignment. We assume a network with $\lambda$ = 2 km$^{-1}$ and a BS power budget of $P = 20$ dBm providing two services:
\begin{itemize}
\item Service 1 requires maximum positioning efficiency and a tolerable outage of 10$\%$.
\item Service 2 requires maximum data-rate and a tolerable positioning error of 5e-4 m.
\end{itemize}
We study the power partitioning scheme under different operating beamwidths. In practice, the operating beamwidth may be a system requirement for the first generation mm-wave networks. Intuitively, for a less stringent misalignment requirement, the operating beamwidth can be smaller. This can either be exploited to improve the positioning or enhance the data-rate, as per the required QoS.

For service 1, the operator should set $\beta$ equal to the $\beta_{min}$ corresponding to the $\theta$ that satisfies the misalignment requirement. Then, if the operating $\theta$ can be decreased, more power can be allotted for positioning and the one used for data communication $P\beta_{min}$ is reduced, accordingly.
On the other hand, the operator should set $\beta$ equal to the $\beta_{max}$ corresponding to the $\theta$ that satisfies the misalignment requirement. Therefore, a thinner beamwidth facilitates larger power allocation for data communication ($P_D$ increases).
The stark difference in the two examples lies in the fact that the advantage of operating with a thinner beamwidth is exploited differently. With decreasing $\theta$, for a positioning service, $P_L$ increases and $P_D$ decreases, whereas the opposite is true for the high data-rate services (see Figure.~\ref{fig:final}).

It is worth mentioning that the inter-dependence of $\beta$ and $\theta$ for controlling the positioning performance and the misalignment error is not trivial. As an example, for a required misalignment constraint or for a required positioning error constraint, there exist non-unique $\left(\theta, \beta\right)$ pairs.

Furthermore, it may happen that for a given $\theta$ and $P$, no feasible $\beta$ exists that satisfies the positioning and misalignment constraints simultaneously, thereby necessitating a higher BS power budget. This interesting trade-off and the associated optimization problem will be treated in a future work.
\vspace*{-0.2cm}
\section{Conclusion}
In this paper we characterized a mm-wave system deployed to support positioning and broadband services simultaneously. Specifically, we introduced a power-partitioning based mechanism that enables the mm-wave BS to satisfy different localization and data-rate requirements. In this context, we derived dimensioning rules in terms of the density of BSs required to limit outage probability. Then we provided the operator with a beamwidth selection guideline to limit the misalignment probability. Finally, we studied the trade-off between the localization efficiency and the downlink data rate, and consequently, presented a scheme for partitioning the transmit power depending on the service requirements.
\label{sec:Con}
\vspace*{-0.35cm}
	\bibliography{refer.bib}
	\bibliographystyle{IEEEtran}

\end{document}


TITLE: What is the average rate of growth for the following set of data?
QUESTION [1 upvotes]: The chart shows the losses and gains in an investment over the course of five years. What was the average growth rate over the course of the five years?
Year$\space\space\space$    Percent Growth
1$\space\space\space\space\space\space\space+10\%$
2$\space\space\space\space\space\space\space-3\%$
3$\space\space\space\space\space\space\space-8\%$
4$\space\space\space\space\space\space\space+4\%$
5$\space\space\space\space\space\space\space+6\%$
I thought that this would mean that if you start with a value of $x$, then the each percentage represents an increase in the previous amount.
This would mean that the final amount after 5 years is
$x\times1.10\times.97\times.92\times1.04\times1.06$ or $1.0822x$
This would mean that the percent increase is $8.22\%$, but the real answer is $1.59\%$. How would this "average" work and how is my work wrong in the first place?

REPLY [3 votes]: You are correct that at the end of year five the amount is $1.0822$ times larger than the start value.  If you want the average annual growth rate, you take the $1/5$ power of this, as this will be the annual growth that when repeated fve times gives a factor $1.0822$.  In fact $1.0822^{1/5} \approx 1.01592$