User anthony quas - MathOverflow

American put option pricing by "binomial trees"

2013-04-04T18:49:23Z

Dear MO World,

I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar.

I'll try and give a description of what it means followed by a self-contained description of what I'm doing. First of all: an American put option is a product that gives the right to sell a share for a price $K$ (agreed at the outset) at any time up to the expiry time, $t$, of the option. It's assumed that the underlying share is moving according to a geometric Brownian motion (GBM) with known volatility parameter $\sigma$. The interest rate is $r$ and the initial share price is $s$.

The basic idea is to discretize the GBM to a multiplicative random walk on the "binomial tree" with depth $n$. That is: one assumes that at each of the $n$ stages the price multiplies by $u=\exp(\sigma\sqrt{t/n})$ or $d=1/u$. In this derivation, the "risk-neutral measure" is the measure on the multiplicative random walk where up steps occur independently with probability $p=(\exp(rt/n)-d)/(u-d)$ and down steps occur with probability $q=1-p$. One can then define $V_{j,i}$ to be the value of the option if unexercised by time $jt/n$ and the current share price is $su^id^{j-i}$. The approximate arbitrage-free cost of the option is $V_{0,0}$. The scaling of the multipliers guarantees that the multiplicative random walk converges to a geometric Brownian motion in the appropriate sense. It is assumed (and probably proved somewhere) that this converges to the true arbitrage free cost (computed using the GBM rather than the discrete approximation) as $n\to\infty$. I am interested in the dependence of $V_{0,0}$ on $n$, the number of time steps.

Here is the actual calculation that I'm doing: define $V_{n,i}=(K-su^id^{n-i})^+$. One then does a backwards recursion to populate previous levels of the "tree": $V_{j,i}=\max\big(K-su^id^{j-i},e^{-rt/n}(pV_{j+1,i+1}+qV_{j+1,i})\big)$. [The max here corresponds to either exercising the option now or holding it].

Here is a graph of $V_{0,0}$ versus $n$:

It seems that for odd $n$, the function roughly follows one curve, while for even $n$ it roughly follows another. I have no idea why the graph should look like this...

Answer by Anthony Quas for How to simulate random paths of a non-homogeneous continuous-time Markov process with discrete state space for a given infinitesimal generator matrix?

2013-05-30T22:40:34Z

Suppose you're in state $i$. For each $j$, let $X_j$ be an independent Exponential random variable with mean 1.

Now solve $\int_{0}^{T_j}\alpha_{i,j}(t)\ dt=X_j$ for each $i$. Whichever of the $T_j$'s is smallest, you jump from state $i$ to state $j$ at time $T_j$.

Answer by Anthony Quas for A notion of a 'coarse', parametrized dimension of an object, where the parameter determines how finely we can distinguish (say) a very thin rod from a line

2013-05-27T04:32:18Z

Something like $f(r)=\log_2 N_A(r)/\log_2 N_A(r/2)$, where $N_A(r)$ denotes the smallest number of $r$-balls that covers $A$ might work.

If you had a wire $W$ of cross-sectional radius $\delta$ and length 1, then for $r\gg\delta$, $N_W(r)\approx 1/\delta$, while for $r\ll\delta$, $N_W(r)\approx \delta^2/r^3$. When you compute the $f$, you get roughly what you need.

This is basically $$ \frac{dN_A(r)}{d\log r}. $$

The only difficulty is that $N_A$ isn't a differentiable function.

Answer by Anthony Quas for Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

2013-05-01T00:21:30Z

You're essentially asking if you drop $k$ objects each into one of $k$ bins, what is the probability that only $k/2$ bins are occupied. (You can forget the extra dimension and only think about the dimensions you're looking at).

If you let $E_i$ be the event that the $i$th bin is empty, this has probability $((k-1)/k)^k\approx 1/e$. The events $E_i$ are approximately independent. Letting $N=\sum_{i=1}^k \mathbf 1_{E_i}$, $N$ has expectation $k/e$. The probability that there are $k/2$ unoccupied bins will decay as $e^{-\alpha k}$ using large deviation estimates.

--- Added to answer ---

If you want to pick a subset of size $\alpha k$ of the set of size $k$, it's obvious how to do it: take the boxes with the most elements first. You expect the distribution of elements in each box to be approximately Poisson with parameter 1. This means that approximately $(1-2/e)k$ of the boxes have two or more elements. As long as $\alpha$ is less than $1-2/e$, there's a high probability that you can find a subset $S$ of size $\alpha k$ whose shadow has size at most $|S|/2$.

Answer by Anthony Quas for How do we recognize a Markov partition?

2013-04-29T01:34:33Z

If you can prove something like: $d(\phi^n(x),\phi^n(y))>(1+\delta)d(x,y)$ for all $x$ and $y$ such that $d(x,y)<\epsilon$, then it would suffice to show that there exists a $k$ such that for all sequences $i_0,i_1,\ldots,i_{nk-1}$, $\bigcap_{j=0}^{nk-1}\phi^{-j}\overline{U_{i_j}}$ has diameter at most $\epsilon$.

If this latter condition is not satisfied, then condition 2 will not be satisfied anyway, so this is a necessary condition.

Answer by Anthony Quas for order of convergence of the conditional entropy

2013-04-27T23:46:35Z

Let $n=k+k^k$ and let $X$ take each element $1\le j\le k$ with probability $1/k-1/k^2$. Let the remaining $k^k$ elements have probability $1/k^{k+1}$. Let $g(i)=\min(k+1,i)$.

We now have $\mathbb P(X\ne Y)=\mathbb P(X>k)=k^k/k^{k+1}=1/k$, which converges to 0 as required.

We have $$ \begin{split} H(X)&=-k(1/k-1/k^2)\log (1/k-1/k^2)-k^k/k^{k+1}\log (1/k^{k+1}) \cr &= (1-1/k)(\log k-\log(1-1/k))+(1/k)(k+1)\log k\cr &=2\log k+O(\log k/k), \end{split} $$ which converges to $\infty$ as required.

Finally, given $Y$, $X$ is known if $Y$ is in the range $\{1,\ldots,k\}$. But if $Y$ takes the value $k+1$ (which occurs with probability $1/k$), then $X$ takes one of $k^k$ values with equal probability. Hence $H(X|Y)=(1/k)\log k^k=\log k$.

In particular, we have $$\frac{H(X|Y)}{H(X)}\to\frac 12. $$

Answer by Anthony Quas for Chain Recurrent Set of a Isometry

2013-03-27T19:35:15Z

An example of the type you're asking for is given by the following transformation of the circle (considered as the set $[0,1]/\sim$, where $\sim$ identifies 0 and 1: $T(x)=x^2$.

The only periodic point is 0. On the other hand, every point is chain recurrent, because given $x\in(0,1)$, and $\epsilon > 0$, there exist $m$ and $n$ such that $T^m(x)=x^{2^m}<\epsilon/2$ and $T^{-n}x=x^{2^{-n}} > 1-\epsilon/2$.

Now the orbit $\overline{(x,Tx,\ldots,T^mx,T^{-n}x,\ldots,T^{-1}x)}$ is $\epsilon$-chain recurrent and includes the point $x$.

Answer by Anthony Quas for Probability that a random distance function is metric

2013-03-04T16:52:13Z

Since you haven't given a distribution, let me make an observation giving the right form of the answer in the case where the $D_{xy}$ are independent uniform $[0,1]$ random variables.

I want to claim that the probability, $p$, that the matrix defines a metric satisfies $\alpha^{n^2}\le p\le \beta^{n^2}$ for constants $\alpha$ and $\beta$.

First, notice that if all the $\binom n2$ edge lengths are in $[\frac12,1]$, then the triangle inequality is satisfied, so that $p\ge 2^{-\binom n2}$.

Conversely, consider the triples $(b,b+a,b+2a)$ where $a$ is an odd number in the range $1$ to $\frac n4$ and $1\le b\le a$. Notice that no two of these triples contain two elements in common. There are $\Theta(n^2)$ such triples. For such a triple, consider the event $E_{a,b}$ that $D_{b,b+2a}\le D_{b,b+a}+D_{b+a,b+2a}$. These events all have the same probability that is strictly less than 1. They are also independent, since no edge occurs in two events. Hence we obtain the upper bound.

Answer by Anthony Quas for Natural density of a set of positive integers not in certain congruence classes

2013-03-01T06:25:11Z

Here is an amplification of @Greg Martin's answer.

Let $S$ be any set whose upper density and lower density differ. Let the upper and lower densities be $\alpha$ and $\beta$ respectively. Write $S(N)$ for $|S\cap[1,N]|$. Let $a_1 < a_2 < \ldots $ be the increasing enumeration of $S^c$. Let $\delta<\alpha-\beta$.

Let $m_1 < m_2 < \ldots$ be a sequence satisfying the following:

$m_i>a_i$;
$\sum_{i=1}^\infty 1/m_i \lt \delta $;
$S(m_i)/m_i\to\alpha$.

Set $N_{m_i}=\{a_i\}$. Let $\tilde S$ be the set of integers $n$ such that $n\bmod m_i\not\in N_{m_i}$ for each $i$. Clearly $\tilde S\subset S$, so that the lower density of $\tilde S$ is at most $\beta$. On the other hand

$$ (S\setminus\tilde S) \cap [1,m_j] \subset \left(\bigcup_{i < j} (a_i+m_i\mathbb N)\cap [1,m_j]\right), $$ where $\mathbb N$ is the set of strictly positive integers.

Hence we see that $(S\setminus\tilde S) \cap [1,m_j]$ has at most $m_j(1/m_1+\ldots+1/m_{j-1}) < \delta m_j$ elements. So $\limsup_{j\to\infty}\tilde S(m_j)/m_j \gt \alpha-\delta > \beta $, and $\tilde S$ does not have a density.

Answer by Anthony Quas for First hit time in a graph setting

2013-02-04T17:01:42Z

This circle of questions is known as first passage percolation. There's an extensive literature on the subject.

Answer by Anthony Quas for Sum of binomial coefficient

2013-01-25T01:41:46Z

There's no clean answer, but you need to use the Central Limit Theorem. If $X_1,\ldots, X_n$ are independent random variables taking values 0 and 1 with probability $1/2$, then you're asking for a $d$ such that $\mathbb P(S_n\le d)\ge \epsilon$. By the Central limit theorem, for large $n$, you have $S_n$ is well approximated by a normal distribution with mean $n/2$ and variance $n/4$. That is $S_n$ has approximately the same distribution as $n/2+\sqrt n/2 N$ where $N$ is a Normal(0,1) random variable.

In this language, you are now asking for $d$ such that $\mathbb P(N\le (2d-n)/\sqrt n)\approx\epsilon$, or $\Phi((2d-n)/\sqrt n)\approx\epsilon$.

If you solve $\Phi(x)=\epsilon$, then you can obtain a suitable value for $d$ is something like $n/2-\sqrt{-2n\log\epsilon}$.

Answer by Anthony Quas for Failure of the Pointwise Ergodic Theorem

2013-01-15T15:15:46Z

Bellow, Alexandra(1-NW); Jones, Roger(1-DPL); Rosenblatt, Joseph(1-OHS) Convergence for moving averages. Ergodic Theory Dynam. Systems 10 (1990), no. 1, 43–62.

Answer by Anthony Quas for Elementary applications of linear algebra over finite fields

2013-01-14T17:14:51Z

How about binary linear codes? You can "see" the Hamming distance between codewords, and use linear transformations to encode/decode

Answer by Anthony Quas for What is the probability that a random subset of a finite group is generic?

2013-01-14T17:05:03Z

I think your conjecture is right. I hadn't heard of this fact before, so can't provide a reference. Here is my attempt at a proof.

The idea is that I want to reverse things: Fix a set $A=\{a_i\}$ with $|A|=k$ and show that the probability that a set $X$ is $A$-generic (i.e. $AX=G$) is exponentially small in $n$ (uniformly in $A$). On the other hand, there are only polynomially many ($\approx n^k$) $A$'s, so the probability that $X$ is $k$-generic is bounded above by $n^k\times$(exponentially small in $n$).

Let's do this in detail. Let $B=AA^{-1}$ (i.e. $\{a{a'}^{-1}\colon a,a'\in A\}$), so that $|B|\le k^2$. Now I claim that you can pick in $G$ elements $g_1,\ldots,g_m$, where $m=n/k^2$ such that $g_j\not\in\bigcup_{i < j}Bg_i$ (at the $j$th stage, there are at least $|G|-|B|(j-1)$ choices). The $A^{-1}g_i$ are now disjoint: if $A^{-1}g_i\cap A^{-1}g_j\ne\emptyset$ for $i < j$, then $g_j\in Bg_i$.

Now we compute for a random subset $X$: what is the probability that $AX\supset\{g_1,\ldots,g_m\}$? Note that $AX$ contains $g_i$ if $X$ contains an element of $A^{-1}g_i$. The probability of this is $1-2^{-k}$. Since the sets $A^{-1}g_i$ are disjoint, the probability that $AX$ contains each of the $g_i$ is $(1-2^{-k})^m=(1-2^{-k})^{n/k^2}$. Hence the probability that $X$ is $k$-generic is at most $n^k(1-2^{-k})^{n/k^2}$, which tends to 0 as $n\to\infty$ for fixed $k$.

Answer by Anthony Quas for Minimal period of arithmetic progressions occurring in sets of positive density.

2013-01-06T07:18:32Z

Let $$ S=\mathbb N\setminus\bigcup_{n\ge 5}\bigcup_k\lbrace 2^n(2k+1),2^n(2k+1)+1,\ldots,2^n(2k+1)+(n-1)\rbrace. $$

This has positive upper density (in fact positive density), because what you're removing has density $\sum_{n\ge 5}n/2^{n+1}<1$.

If you want to find an arithmetic progression with length $2^{n+1}$, it must have difference at least $n+1$ because it can't fit entirely between two blocks that are removed at the $n$th level, and hence must "jump over" at least one of those blocks. In particular, the common difference has to be at larger than the length of the block that it jumped over.

Answer by Anthony Quas for power of adjacency matrix

2013-01-04T04:01:02Z

You can certainly do this by cheating and making an outrageous expansion of the set of vertices. Let the vertices of the original graph by $V$. Now you form a new directed graph with vertices $V\times \mathcal P(V)$ (where $\mathcal P$ denotes power set). For each edge $i\to j$ in the original graph, and for each set $S$ containing $i$ but not $j$, define an edge $(i,S)\to (j,S\cup\lbrace j\rbrace)$. This new monster graph keeps track of all the places you've been and only lets you visit new vertices.

Let $\bar A$ be the adjacency matrix of this new directed graph. Finally, let $B$ be the $|V|\cdot 2^{|V|}\times |V|$ matrix with $B_{j\times S,j}=1$ for each $S$, and 0 and equal to 0 for all other entries.

The number of walks from $i$ to $j$ in the original graph of length $l$ is given by $(A^lB)_{(i,\lbrace i\rbrace),j}$.

Of course, this is absolutely not a practical way to compute anything...

Answer by Anthony Quas for faces in the discrete cube

2013-01-02T23:45:25Z

No. The typical set doesn't contain anything like a 0.6n face. Some similar questions are considered in "The Probabilistic Method" by Alon and Spencer (which I thoroughly recommend).

Here is the calculation. Let's just deal with 0.5n faces. I want to make a crude estimate of the probability that a subset (chosen uniformly) contains 90% of a 0.5n face.

The bound I'll use is the union bound: there are $\binom{n}{0.5n} 2^{n/2}$ $0.5n$-faces (choose which indices you want to restrict, and then decide the values you want to give them). This is considerably less than $2^{2n}$.

Now what is the probability that a random subset has density at least 90% in a given 0.5$n$-face?

I'll compute the probability that a random subset has density exactly 90% in a given 0.5$n$-face, since as you increase the density, the probability decays geometrically, so the first term dominates.

Since there are $2^{n/2}$ elements in the face, we're now asking for $$ \binom{2^{n/2}}{0.1\times 2^{n/2}}2^{-2^{n/2}}. $$ This is the number of ways of having exactly $0.9\times 2^{n/2}$ ones out of the $2^{n/2}$ possibilities (assume all numbers are integers by taking floors). A liberal dose of Stirling's formula shows that the binomial coefficient is $(0.1^{0.1}0.9^{0.9})^{-2^{n/2}}/2^{n/4}$ up to multiplicative constants, so that the number of configurations we're looking for is essentially $(0.1^{0.1}0.9^{0.9}\times 2)^{-2^{n/2}}/2^{n/4}$.

Since $0.1^{0.1}0.9^{0.9}>\frac12$, this decays fast (even when multiplied by $2^{2n}$).

Answer by Anthony Quas for Old books still used

2012-12-29T05:49:11Z

I'm amazed no one has mentioned Hardy and Wright's wonderful Introduction to the Theory of Numbers. It was first published in 1938 and is absolutely delightful.

The most recent (6th) edition includes a chapter on elliptic curves.

Answer by Anthony Quas for Estimates for the mixing time of a Markov Chain with biased initiation

2012-12-26T18:38:56Z

For the biased random walk, you can use a grand coupling: take two copies of the walk and make them move the same way (staying put if they can't move in their respective directions). I'll assume $p$ was meant to be the probability of moving to the right, and that $p<\frac12$. For a fixed $i$ (independent of $N$), you should expect a $\Theta(1)$ mixing time (as the expected time to hit 0 from some stationarily chosen initial point is $\Theta(1)$ and each time you hit 0, you expect to get a reduction in distance).

Even if the second particle starts at $N$, you expect a $\Theta(N)$ time.

For the chain with a hurdle, I think you get a similar $\Theta(1)$ time (I'm assuming you're not allowed to vary $\epsilon$)

See Levin, Peres and Wilmer's book for lots more information.

Answer by Anthony Quas for Generating spatially-aware degree-preserving random graphs?

2012-12-19T01:50:09Z

I can make you a directed model! Let's specify the out-degree of each vertex: $o_x$ is the out-degree of vertex $x$.

Choose yourself an increasing function $F(d)$ that encodes a distance penalty. For each pair of vertices $x$ and $y$, let $A_{xy}=F(\|x-y\|)U_{xy}$. The edges leaving vertex $x$ are then the $\vec{xy}$ corresponding to the $o_x$ smallest values of $A_{xy}$.

Doing the undirected case seems a bit more subtle...

EDIT: Let me expand/change this a bit. For a mathematically interesting model, where you might be able to prove something, you could look at a Gibbs probability distribution. You define an "energy" for each legal configuration (i.e. subgraph of $G$ satisfying the degree constraints). Then, based on the hypothesis that high energy states are unlikely, you assign them low probability.

More specifically, a reasonable approach would be to define the energy of a configuration $\xi$ to be $\Phi(\xi)=\sum_{e\in E(\xi)}F(\|e\|)$. If you let $\Lambda$ be the set of all legal configurations, then the Gibbs measure is defined by $\mathbb P(\xi)=e^{-\Phi(\xi)}/\sum_{\zeta\in\Lambda}e^{-\Phi(\zeta)}$. (The normalization, which is sometimes called the partition function, $Z(\Lambda)$, there makes this a probability measure). The reason that Gibbs measures are nice is that the multiplicative properties of the exponential function ($e^{a+b}=e^ae^b$) lead to some independence properties of the measure you've constructed. For example it's easy to see that if $\xi$ and $\xi'$ are 2 configurations that agree except that $\xi$ contains edges $ab$ and $cd$, while $\xi'$ contains edges $ac$ and $bd$, there's an easily calculated relationship between $\mathbb P(\xi)$ and $\mathbb P(\xi')$.

Answer by Anthony Quas for Strange pattern in rounding errors?

2012-12-13T06:47:39Z

For what it's worth, if you do the same computation on Mathematica, you see something quite different (and very much like what @Henry Cohn predicted):

Answer by Anthony Quas for how to find/define eigenvectors as a continuous function of matrix?

2012-12-11T23:57:23Z

Unfortunately it can get worse than your example. There can be no continuously choosable eigenvectors at all.

Here's an example: Consider the family of matrices $$ g(t)=\begin{cases} \begin{pmatrix}1+t&0\cr 0&1-t\end{pmatrix}&\text{for $t<0$}; \cr \begin{pmatrix}1&t\cr t&1\end{pmatrix}&\text{for $t\ge 0$.} \end{cases} $$ Then the eigenvectors are $\begin{pmatrix}1\cr 0\end{pmatrix}$ and $\begin{pmatrix}0\cr1\end{pmatrix}$ for $t<0$ and $\begin{pmatrix}1\cr1\end{pmatrix}$ and $\begin{pmatrix}1\cr-1\end{pmatrix}$ for $t>0$.

Obviously there's no continuous selection possible.

Answer by Anthony Quas for Average orders of multiplicative functions

2012-12-07T01:50:17Z

I think an explicit multiplicative function that should do the job for you is this one: $f(2^n)=2^n/\big((n+1)\sqrt{\log(n+e)}\big)$, $f(3^n)=3^n/\big((n+1)\sqrt{\log(n+e)}\big)$, $f(p^n)=0$ for $n\ge 1$ and primes $p\ge 5$. The $+1$'s and $+e$'s are just there to make the formula make sense for $n=0$ also.

Here's an outline of why: It suffices to show that for all $\epsilon>0$, for all sufficiently large $N$ one has $$ \sum_{N < 2^k3^l\le (1+\epsilon) N} \frac{1}{(k+1)\sqrt{\log(k+e)}}\cdot \frac{1}{(l+1)\sqrt{\log(l+e)}}\sim c\epsilon /\log N $$ Taking logs, the summation range is essentially $\log N\le k\log 2+l\log 3\le \log N+\epsilon$. For large $N$, there are approximately $\epsilon\log N/(\log 2\log 3)$ pairs $(k,l)$ in the range. These are reasonably uniformly distributed in the band of $\mathbb R^2$, $x\log 2+y\log 3\in [\log N,\log N+\epsilon]$. Hence (with a bit of work making sure the ends of the integral don't dominate), the sum is close to $$ \frac{\epsilon}{\log 2}\int_{0}^{\log N/\log 3} \frac{1}{(y+1)\sqrt{\log (y+e)}}\frac{1}{(x+1)\sqrt{\log(x+e)}}\ dx, $$ where $y=(\log N-x\log 3)/\log 2$.

In the first half of the range, the integral is something like $$ \frac{\epsilon}{\log N\sqrt{\log\log N}} \int_0^{\log N/(2\log 3)} \frac{1}{(x+1)\sqrt{\log(x+e)}}\ dx $$ which is $\sim c\epsilon/\log N$. Similarly for the second half of the range.

If you prefer your multiplicative functions to be integer-valued, of course, you can just take the floor of everything.

Answer by Anthony Quas for Upper bound on expectation value of the product of two random variables

2012-10-08T03:22:23Z

I'll assume that $X$ and $Y$ are non-negative random variables. Let $F_X$ be the cumulative distribution function of $X$ (that is $F_X(t)=\mathbb P(X\le t)$) and $F_Y$ be the cumulative distribution function of $Y$.

In your notation, probably $F_X(t)=\int_0^t p(s)\,ds$ and $F_Y(y)=\int_0^t q(t)\,dt$.

Now define two functions on $[0,1]$: $g_X(x)=\sup\lbrace t\colon \mathbb P(X\le t)\le x\rbrace $ and similarly $g_Y(x)=\sup\lbrace t\colon \mathbb P(Y\le t)\le x\rbrace$. These functions are the increasing rearrangements of $X$ and $Y$. That is these are non-decreasing functions with the property that $m\lbrace x\colon g_X(x)\le t\rbrace =\mathbb P(X\le t)$ and $m\lbrace x\colon g_Y(x)\le t\rbrace = \mathbb P(Y\le t)$.

Now the largest possible value of $\mathbb E XY$ given the distributions is $\int_0^1 g_X(t)g_Y(t)\ dt$. Intuitively the reason for this is that the largest value for the expectation is obtained when the largest values of $X$ are multiplied by the largest values of $Y$. Slightly more precisely imagine you've arranged the $X$ values from largest to smallest. Think of these as "weights" for the $Y$ values. Obviously you get the biggest integral if you weight the big $Y$ values with the biggest weights.

Cyclotomic polynomials evaluated at roots of unity

2012-09-01T08:24:23Z

Dear MO_World,

I'm working on an ergodic theory question (about a generalization of eigenfunctions for measure-preserving transformations) and have run into a number theory question concerning cyclotomic polynomials that I'm unable to tackle.

The question is this:

Let $p$ be a prime and let $p|n$. When is it the case that $\Phi_n(e^{2\pi i/p})=\pm e^{2\pi ij/p}$ for some $j$?

Here $\Phi_n$ denotes the $n$th cyclotomic polynomial.

I've experimented with Mathematica and have found there are non-trivial cases in which the condition holds, whereas for most cases it does not seem to hold.

Letting $c(n,p)=\Phi_n(e^{2\pi i/p})$, we have $c(105,3)=1$, but $c(105,5)$ and $c(105,7)$ are not on the unit circle. None of $c(15,3)$, $c(21,3)$, $c(15,5)$, $c(35,5)$, $c(21,7)$, $c(35,7)$ are on the unit circle; $c(40,2)=1$, but $c(50,2)=5$...

Not surprisingly it seems to be easiest for the condition to hold for small $p$.

Also, using the relations $\Phi_{p^2n}(x)=\Phi_{pn}(x^p)$; and $\Phi_n(1)=q$ if $n=q^k$ for some prime $q$ and an integer $k$, but $\Phi_n(1)=1$ otherwise, it's not hard to see that the condition holds whenever $p^2|n$, but $n$ is not a power of $p$.

Thanks for any more systematic suggestions...

Answer by Anthony Quas for Orbits of the projective special linear group on $\mathbf{Q} \cup \{\infty\}$

2012-07-31T00:36:48Z

Consider the matrix $A=\begin{pmatrix}a&b \cr c&d\end{pmatrix}$ in $SL(2,\mathbb Z)$. Then you're asking if setting $\begin{pmatrix}p_n\cr q_n\end{pmatrix}=A^n\begin{pmatrix}p\cr q\end{pmatrix}$ all of $P\mathbb Q^2$. To see that it's not, notice that there are a handful of cases:

$A$ is elliptic if it has a pair of eigenvalues on the unit circle. These are necessarily roots of unity. In this case, $A$ has finite order, and so it's obvious that there are infinitely many orbits.

$A$ is parabolic if it has a repeated root of $\pm 1$. In this case, $A^n\begin{pmatrix}p\cr q\end{pmatrix}$ converges in $P\mathbb Q^2$ to a fixed direction (the generalized eigenvector) unless $\begin{pmatrix}p\cr q\end{pmatrix}$ was in the direction of the eigenvector

Similarly if $A$ is hyperbolic, there are two possible limit directions.

This rules out the transitivity you were looking for.

Answer by Anthony Quas for Prescribed values for the uniform density

2012-07-25T22:11:45Z

OK. I think you can do this pretty easily by hand. First you need a way to generate sequences with very uniform density. The Sturmian sequences are perfect for this. A Sturmian sequence with parameter $\alpha$ has the property that sub-blocks of length $N$ have density converging to $\alpha$ uniformly in $N$.

Now: start by interspersing a Sturmian with parameter $\underline\delta$ with one of parameter $\bar\delta$. How to do the interspersing? Have one from $2^{n!}$ to $2^{(n+1)!}$. Then switch to the other between $2^{(n+1)!}$ and $2^{(n+2)!}$ etc. This switching is slow enough to guarantee that the sequence that you obtain has the prescribed $\underline\delta$ and $\bar\delta$. These are also the upper and lower densities for the time being.

Next we'll modify the sequence to obtain densities $\underline d$ and $\bar d$. Alternately splice in segments of Sturmian parameter $\underline d$ and $\bar d$ between $2^{4^i}$ and $2^{4^i+2^i}$. This won't affect the upper and lower logarithmic densities (because $2^i/4^i\to 0$).

But looking at these segments, you obtain a sequence with upper and lower densities $\underline d$ and $\bar d$ (the upper and lower uniform densities are also $\underline d$ and $\bar d$).

Finally, we'll perturb things as in my comment to get the uniform densities we want. For the segments between $2^n$ and $2^n+n$, insert alternately segments of the Sturmian sequences with densities $\underline u$ and $\bar u$. These segments are so sparse, they will have no effect on the upper and lower densities or the logarithmic densities. They are enough to guarantee that you get the uniform densities you want.

And Bob's your mother's brother.

Answer by Anthony Quas for Question on Sums of Squares

2012-07-24T20:09:12Z

Yes. One way to see this is that there are more $n$-element subsets with terms up to $N$ than there are possible sums of squares, giving an answer by the pigeonhole principle.

A more beautiful answer was given by Prouhet in the 1850's, who exhibited for each $n$ an explicitly-defined pair of sets $A$ and $B$ of size $2^n$ such that $$\sum_{a\in A}a^k=\sum_{b\in B}b^k\text{ for each $1\le k\le n$}. $$

Answer by Anthony Quas for Computations on Bollobas' proof of the $\chi(G(n,p))$ for constant $p$

2012-07-17T05:43:58Z

Go back to the original equation: $\binom nr p^{r(r-1)/2}=1$ and rewrite it as $b^{r(r-1)/2}=n^r/r!\left[\binom nr/(n^r/r!)\right]$.

Notice that $b^{r(r-1)/2}$ becomes larger than $n^r$when $b^{(r-1)/2}>n$. That is when $r=O(\log n)$. Notice that the term in brackets is very close to 1 in that range (certainly between $1/2$ and 1 for large $n$)$.

Hence the solution to the equation satisfies $b^{r(r-1)/2}=An^r/r!$ for some $1/2 < A < 1$. Now take logs to base $b$: $r(r-1)/2=\log_b A+r\log_b n-r\log_b r+r\log_b e+O(1)$. Divide through by $r/2$ to get $r-1=2\log_b n-2\log_b r+2\log_b e+O(1/r)$ or $$r=2\log_b n-2\log_b r+2\log_b e+1+o(1).$$

A great way to solve equations like this (where the RHS changes much slower than the LHS) is iteratively. You start with a guess and plug it in to the right side of the equation to get an improved guess (this is just the Banach contraction mapping theorem in action).

Here start with $r=2\log_b n$. The first improved version is $r=2\log_b n-2\log_b(2\log_b n)+2\log_b e+1+o(1)$. This is exactly the expression you were looking for.

Notice that the approximate solution changed by approximately $2\log_b(\log_b n)$. If you were to compute the next iterate, it would change by the derivative of the RHS times this amount, which is $o(1)$. The subsequent changes decay like a geometric progression with ratio $\log\log n/\log n$, so can be incorporated in the $o(1)$ term.

Answer by Anthony Quas for Combinatorics of folding digit strings

2012-07-15T04:50:04Z

The exponential growth rate is greater than $2^{n/2}$. It's $2^{r_bn}$ where $r_b\to 1$ as $b\to\infty$. What you're essentially looking at is the number of random walks on $b+1$ vertices (you can see this in your picture).

From this, you see that $2^{r_b}$ is the leading eigenvalue of the adjacency matrix of a path on $b+1$ vertices, which is $2\cos(\pi/(b+2))$.

Comment by Anthony Quas

2013-06-19T08:33:03Z

Why aren't you done then? If $\ln f$ is harmonic, then you can add its harmonic conjugate, exponentiate et voila

Comment by Anthony Quas

2013-05-31T06:09:31Z

The proof goes via lots of Borel-Cantelli. Heuristically if you believe the central limit theorem, $S_n$ should be normal with mean 0 and variance $n$, so that $S_n/\sqrt n$ is approximately $N(0,1)$. The appearance of the $\sqrt{2\log\log n}$ is roughly because $\mathbb P(N>\sqrt{2\log\log n})$ is on the cusp of summability. So that $\mathbb P(N>\sqrt{2.000001\log\log n})$ is summable, so happens finitely many times (this is the easier part), whereas $\mathbb P(N>\sqrt{1.999999\log\log n})$ is not summable and so [quite a lot of annoying technical details skipped] happens infinitely often.

Comment by Anthony Quas

2013-05-31T06:04:01Z

No sorry I don't. Something like this has been in the back of my mind for a while. You can check it though: compute the probability that there's a transition from $i$ to $j$ in the time interval $(t,t+dt)$ conditioned that there has been no transition up to time t.

Comment by Anthony Quas

2013-05-29T23:52:05Z

Am I missing something here? If the matrices are all rotations, there's no finite union that's preserved, but still both exponents are 0?

Comment by Anthony Quas

2013-05-29T18:56:31Z

Interesting question. Do you know if in your case the Lyapunov exponents of the action are distinct?

Comment by Anthony Quas

2013-05-29T00:39:28Z

I think this works even if $|A_n|=2$ for each $n$ (or even if you just work with prime $n$). This would follow from the 2nd Borel-Cantelli lemma (the probability that $m$ is represented is at least $1/n$ and the representability by $A_n$ is independent of representability by other sets).

Comment by Anthony Quas

2013-05-08T08:34:41Z

I did something related in $\mathbb R^d$ and found a family of tilings there (see <a href="mathoverflow.net/questions/77952/… question</a>). It turned out that the tilings had been previously studied under the name <i>notched cube tilings</i>. It's quite plausible that some version of Stein's ideas can be applied in your situation.

Comment by Anthony Quas

2013-05-08T08:26:54Z

The proofs of chaotic behaviour tend to rely on hyperbolic behaviour (or at least non-uniformly hyperbolic behaviour). Proving that this holds in many real systems (or even in lots of toy models) is extremely hard / apparently beyond the reach of current technology.

Comment by Anthony Quas

2013-05-07T15:45:28Z

If the Erdös-Kac theorem existed in a more refined version, saying that if you look at the distribution of $\Omega(n)$ over a range of $n$'s, then $\Omega(n)−\log\log n$ is close in total variation distance to a normal random variable, then the answer would be yes.

Comment by Anthony Quas

2013-05-03T03:24:32Z

Yes. The longest run of heads is tightly concentrated. That means that almost all of the space has between $(1-epsilon)log n$ heads and $(1+epsilon)log n$ heads. All you have to do is pair the very small part of the space where $R_n(x)<(1-epsilon)\log n$ with an arbitrary $y$ in the part where $R_n(y)>= (1-\epsilon)\log n$. When this is done, pair the remaining stuff arbitrarily.

Comment by Anthony Quas

2013-05-03T00:59:51Z

Although this probability does decay exponentially in $k$ (as long as the large deviation methods are valid, which I'm sure they are), the exponential decay is slower than the increase in the number of choices of subsets. This means that something more subtle is needed to finish off the argument. BTW: Even the 2D version of this problem seems non-trivial...

Comment by Anthony Quas

2013-05-03T00:58:21Z

@codingTheorist: I've played with this some more. I'm sure you're right that it decays exponentially in $k$. I have tried to prove this making some assumptions that I have not justified (the applicability of large deviations techniques) together with some very crude bounds (union bounds), and have so far been unsuccessful. My idea was to pick subsets of each face of size $\alpha k$, and then to estimate the probability that for a fixed such triple, there were more than $2\alpha k$ points in the random set that project to the chosen subsets.

Comment by Anthony Quas

2013-05-01T07:19:04Z

Hmmm... it looks like I didn't read the question as well as I should have... I hadn't thought about the 3 different projections part of the story. To get the kind of independence you need for large deviations (at least when you're looking at projection onto one face), I think you can compare the ball dropping process with putting a Poisson number of balls (actually independently) into each bin. I see about the $2/3$ now.

Comment by Anthony Quas

2013-05-01T03:51:06Z

Pairwise independence is not enough; But there is much more independence than that here. This kind of argument shows up all over the place in The Probabilistic Method.

Comment by Anthony Quas

2013-05-01T02:13:25Z

I don't think they don't need to be $k$-fold independent for this kind of argument to work.