User anthony quas - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T11:02:18Z http://mathoverflow.net/feeds/user/11054 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/126546/american-put-option-pricing-by-binomial-trees American put option pricing by "binomial trees" Anthony Quas 2013-04-04T18:49:23Z 2013-06-05T09:18:34Z <p>Dear MO World,</p> <p>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.</p> <p>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$.</p> <p>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. </p> <p>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].</p> <p>Here is a graph of $V_{0,0}$ versus $n$: <img src="http://www.math.uvic.ca/faculty/aquas/usput.jpg"></p> <p>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...</p> http://mathoverflow.net/questions/132355/how-to-simulate-random-paths-of-a-non-homogeneous-continuous-time-markov-process/132376#132376 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? Anthony Quas 2013-05-30T22:40:34Z 2013-05-30T22:40:34Z <p>Suppose you're in state $i$. For each $j$, let $X_j$ be an independent Exponential random variable with mean 1.</p> <p>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$.</p> http://mathoverflow.net/questions/131963/a-notion-of-a-coarse-parametrized-dimension-of-an-object-where-the-parameter/131968#131968 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 Anthony Quas 2013-05-27T04:32:18Z 2013-05-27T04:32:18Z <p>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. </p> <p>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.</p> <p>This is basically $$\frac{dN_A(r)}{d\log r}.$$</p> <p>The only difficulty is that $N_A$ isn't a differentiable function. </p> http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 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. Anthony Quas 2013-05-01T00:21:30Z 2013-05-01T04:09:34Z <p>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). </p> <p>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. </p> <p>--- Added to answer ---</p> <p>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$.</p> http://mathoverflow.net/questions/129030/how-do-we-recognize-a-markov-partition/129049#129049 Answer by Anthony Quas for How do we recognize a Markov partition? Anthony Quas 2013-04-29T01:34:33Z 2013-04-29T10:57:54Z <p>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)&lt;\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$.</p> <p>If this latter condition is not satisfied, then condition 2 will not be satisfied anyway, so this is a necessary condition.</p> http://mathoverflow.net/questions/128937/order-of-convergence-of-the-conditional-entropy/128967#128967 Answer by Anthony Quas for order of convergence of the conditional entropy Anthony Quas 2013-04-27T23:46:35Z 2013-04-28T19:47:42Z <p>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)$. </p> <p>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.</p> <p>We have $$\begin{split} H(X)&amp;=-k(1/k-1/k^2)\log (1/k-1/k^2)-k^k/k^{k+1}\log (1/k^{k+1}) \cr &amp;= (1-1/k)(\log k-\log(1-1/k))+(1/k)(k+1)\log k\cr &amp;=2\log k+O(\log k/k), \end{split}$$ which converges to $\infty$ as required. </p> <p>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$. </p> <p>In particular, we have $$\frac{H(X|Y)}{H(X)}\to\frac 12.$$</p> http://mathoverflow.net/questions/125737/chain-recurrent-set-of-a-isometry/125758#125758 Answer by Anthony Quas for Chain Recurrent Set of a Isometry Anthony Quas 2013-03-27T19:35:15Z 2013-03-27T19:35:15Z <p>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$. </p> <p>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}&lt;\epsilon/2$ and $T^{-n}x=x^{2^{-n}} > 1-\epsilon/2$.</p> <p>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$.</p> http://mathoverflow.net/questions/123528/probability-that-a-random-distance-function-is-metric/123548#123548 Answer by Anthony Quas for Probability that a random distance function is metric Anthony Quas 2013-03-04T16:52:13Z 2013-03-04T16:52:13Z <p>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. </p> <p>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$.</p> <p>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}$.</p> <p>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.</p> http://mathoverflow.net/questions/123209/natural-density-of-a-set-of-positive-integers-not-in-certain-congruence-classes/123300#123300 Answer by Anthony Quas for Natural density of a set of positive integers not in certain congruence classes Anthony Quas 2013-03-01T06:25:11Z 2013-03-01T06:25:11Z <p>Here is an amplification of @Greg Martin's answer. </p> <p>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 &lt; a_2 &lt; \ldots$ be the increasing enumeration of $S^c$. Let $\delta&lt;\alpha-\beta$.</p> <p>Let $m_1 &lt; m_2 &lt; \ldots$ be a sequence satisfying the following:</p> <ul> <li> $m_i>a_i$; <li> $\sum_{i=1}^\infty 1/m_i \lt \delta$; <li> $S(m_i)/m_i\to\alpha$. </ul> <p>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 </p> <p>$$(S\setminus\tilde S) \cap [1,m_j] \subset \left(\bigcup_{i &lt; j} (a_i+m_i\mathbb N)\cap [1,m_j]\right),$$ where $\mathbb N$ is the set of <em>strictly positive</em> integers.</p> <p>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}) &lt; \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.</p> http://mathoverflow.net/questions/120771/first-hit-time-in-a-graph-setting/120785#120785 Answer by Anthony Quas for First hit time in a graph setting Anthony Quas 2013-02-04T17:01:42Z 2013-02-04T17:01:42Z <p>This circle of questions is known as first passage percolation. There's an extensive literature on the subject.</p> http://mathoverflow.net/questions/119799/sum-of-binomial-coefficient/119802#119802 Answer by Anthony Quas for Sum of binomial coefficient Anthony Quas 2013-01-25T01:41:46Z 2013-01-25T01:41:46Z <p>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. </p> <p>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$.</p> <p>If you solve $\Phi(x)=\epsilon$, then you can obtain a suitable value for $d$ is something like $n/2-\sqrt{-2n\log\epsilon}$.</p> http://mathoverflow.net/questions/118978/failure-of-the-pointwise-ergodic-theorem/118980#118980 Answer by Anthony Quas for Failure of the Pointwise Ergodic Theorem Anthony Quas 2013-01-15T15:15:46Z 2013-01-15T15:15:46Z <p>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. </p> http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118904#118904 Answer by Anthony Quas for Elementary applications of linear algebra over finite fields Anthony Quas 2013-01-14T17:14:51Z 2013-01-14T17:14:51Z <p>How about binary linear codes? You can "see" the Hamming distance between codewords, and use linear transformations to encode/decode</p> http://mathoverflow.net/questions/118887/what-is-the-probability-that-a-random-subset-of-a-finite-group-is-generic/118901#118901 Answer by Anthony Quas for What is the probability that a random subset of a finite group is generic? Anthony Quas 2013-01-14T17:05:03Z 2013-01-14T17:05:03Z <p>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.</p> <p>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$).</p> <p>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 &lt; 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 &lt; j$, then $g_j\in Bg_i$.</p> <p>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$.</p> http://mathoverflow.net/questions/118177/minimal-period-of-arithmetic-progressions-occurring-in-sets-of-positive-density/118186#118186 Answer by Anthony Quas for Minimal period of arithmetic progressions occurring in sets of positive density. Anthony Quas 2013-01-06T07:18:32Z 2013-01-06T07:18:32Z <p>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.$$</p> <p>This has positive upper density (in fact positive density), because what you're removing has density $\sum_{n\ge 5}n/2^{n+1}&lt;1$.</p> <p>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.</p> http://mathoverflow.net/questions/118016/power-of-adjacency-matrix/118020#118020 Answer by Anthony Quas for power of adjacency matrix Anthony Quas 2013-01-04T04:01:02Z 2013-01-04T04:01:02Z <p>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. </p> <p>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.</p> <p>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}$.</p> <p>Of course, this is absolutely not a practical way to compute anything...</p> http://mathoverflow.net/questions/117912/faces-in-the-discrete-cube/117916#117916 Answer by Anthony Quas for faces in the discrete cube Anthony Quas 2013-01-02T23:45:25Z 2013-01-02T23:45:25Z <p>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).</p> <p>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.</p> <p>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}$.</p> <p>Now what is the probability that a random subset has density at least 90% in a given 0.5$n$-face?</p> <p>I'll compute the probability that a random subset has density <em>exactly</em> 90% in a given 0.5$n$-face, since as you increase the density, the probability decays geometrically, so the first term dominates.</p> <p>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}$.</p> <p>Since $0.1^{0.1}0.9^{0.9}>\frac12$, this decays fast (even when multiplied by $2^{2n}$). </p> http://mathoverflow.net/questions/117415/old-books-still-used/117479#117479 Answer by Anthony Quas for Old books still used Anthony Quas 2012-12-29T05:49:11Z 2012-12-29T05:49:11Z <p>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.</p> <p>The most recent (6th) edition includes a chapter on elliptic curves.</p> http://mathoverflow.net/questions/117242/estimates-for-the-mixing-time-of-a-markov-chain-with-biased-initiation/117271#117271 Answer by Anthony Quas for Estimates for the mixing time of a Markov Chain with biased initiation Anthony Quas 2012-12-26T18:38:56Z 2012-12-26T18:38:56Z <p>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&lt;\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).</p> <p>Even if the second particle starts at $N$, you expect a $\Theta(N)$ time.</p> <p>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$)</p> <p>See <a href="http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf" rel="nofollow">Levin, Peres and Wilmer's book</a> for lots more information.</p> http://mathoverflow.net/questions/116739/generating-spatially-aware-degree-preserving-random-graphs/116746#116746 Answer by Anthony Quas for Generating spatially-aware degree-preserving random graphs? Anthony Quas 2012-12-19T01:50:09Z 2012-12-20T01:40:49Z <p>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$.</p> <p>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}$. </p> <p>Doing the undirected case seems a bit more subtle...</p> <p>EDIT: Let me expand/change this a bit. For a mathematically interesting model, where you <em>might</em> 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.</p> <p>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')$.</p> http://mathoverflow.net/questions/116214/strange-pattern-in-rounding-errors/116248#116248 Answer by Anthony Quas for Strange pattern in rounding errors? Anthony Quas 2012-12-13T06:47:39Z 2012-12-13T06:47:39Z <p>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):</p> <p><img src="http://www.math.uvic.ca/faculty/aquas/errors.jpg"></p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116129#116129 Answer by Anthony Quas for how to find/define eigenvectors as a continuous function of matrix? Anthony Quas 2012-12-11T23:57:23Z 2012-12-11T23:57:23Z <p>Unfortunately it can get worse than your example. There can be no continuously choosable eigenvectors at all.</p> <p>Here's an example: Consider the family of matrices $$g(t)=\begin{cases} \begin{pmatrix}1+t&amp;0\cr 0&amp;1-t\end{pmatrix}&amp;\text{for t&lt;0}; \cr \begin{pmatrix}1&amp;t\cr t&amp;1\end{pmatrix}&amp;\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&lt;0$ and $\begin{pmatrix}1\cr1\end{pmatrix}$ and $\begin{pmatrix}1\cr-1\end{pmatrix}$ for $t>0$.</p> <p>Obviously there's no continuous selection possible.</p> http://mathoverflow.net/questions/115452/average-orders-of-multiplicative-functions/115666#115666 Answer by Anthony Quas for Average orders of multiplicative functions Anthony Quas 2012-12-07T01:50:17Z 2012-12-07T01:50:17Z <p>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.</p> <p>Here's an outline of why: It suffices to show that for all $\epsilon>0$, for all sufficiently large $N$ one has $$\sum_{N &lt; 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$.</p> <p>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.</p> <p>If you prefer your multiplicative functions to be integer-valued, of course, you can just take the floor of everything.</p> http://mathoverflow.net/questions/109106/upper-bound-on-expectation-value-of-the-product-of-two-random-variables/109110#109110 Answer by Anthony Quas for Upper bound on expectation value of the product of two random variables Anthony Quas 2012-10-08T03:22:23Z 2012-10-08T03:22:23Z <p>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$. </p> <p>In your notation, probably $F_X(t)=\int_0^t p(s)\,ds$ and $F_Y(y)=\int_0^t q(t)\,dt$.</p> <p>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 <i>increasing rearrangements</i> 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)$. </p> <p>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. </p> http://mathoverflow.net/questions/106104/cyclotomic-polynomials-evaluated-at-roots-of-unity Cyclotomic polynomials evaluated at roots of unity Anthony Quas 2012-09-01T08:24:23Z 2012-09-03T20:59:37Z <p>Dear MO_World,</p> <p>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. </p> <p>The question is this:</p> <blockquote> 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$? </blockquote> <p>Here $\Phi_n$ denotes the $n$th cyclotomic polynomial.</p> <p>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.</p> <p>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$...</p> <p>Not surprisingly it seems to be easiest for the condition to hold for small $p$. </p> <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$.</p> <p>Thanks for any more systematic suggestions...</p> http://mathoverflow.net/questions/103565/orbits-of-the-projective-special-linear-group-on-mathbfq-cup-infty/103568#103568 Answer by Anthony Quas for Orbits of the projective special linear group on $\mathbf{Q} \cup \{\infty\}$ Anthony Quas 2012-07-31T00:36:48Z 2012-07-31T00:36:48Z <p>Consider the matrix $A=\begin{pmatrix}a&amp;b \cr c&amp;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: </p> <p>$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. </p> <p>$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</p> <p>Similarly if $A$ is hyperbolic, there are two possible limit directions.</p> <p>This rules out the transitivity you were looking for.</p> http://mathoverflow.net/questions/103111/prescribed-values-for-the-uniform-density/103127#103127 Answer by Anthony Quas for Prescribed values for the uniform density Anthony Quas 2012-07-25T22:11:45Z 2012-07-25T23:18:42Z <p>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 <a href="http://en.wikipedia.org/wiki/Sturmian_word" rel="nofollow">Sturmian sequence</a> with parameter $\alpha$ has the property that sub-blocks of length $N$ have density converging to $\alpha$ uniformly in $N$.</p> <p>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.</p> <p>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$). </p> <p>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$). </p> <p>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.</p> <p>And <a href="http://en.wikipedia.org/wiki/Bob%27s_your_uncle" rel="nofollow">Bob's your mother's brother</a>.</p> http://mathoverflow.net/questions/103044/question-on-sums-of-squares/103045#103045 Answer by Anthony Quas for Question on Sums of Squares Anthony Quas 2012-07-24T20:09:12Z 2012-07-24T20:09:12Z <p>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.</p> <p>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}.$$</p> http://mathoverflow.net/questions/102299/computations-on-bollobas-proof-of-the-chign-p-for-constant-p/102427#102427 Answer by Anthony Quas for Computations on Bollobas' proof of the $\chi(G(n,p))$ for constant $p$ Anthony Quas 2012-07-17T05:43:58Z 2012-07-17T15:47:25Z <p>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]$.</p> <p>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$)$. </p> <p>Hence the solution to the equation satisfies$b^{r(r-1)/2}=An^r/r!$for some$1/2 &lt; A &lt; 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).$$</p> <p>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). </p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/102270/combinatorics-of-folding-digit-strings/102271#102271 Answer by Anthony Quas for Combinatorics of folding digit strings Anthony Quas 2012-07-15T04:50:04Z 2012-07-15T04:50:04Z <p>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). </p> <p>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))$. </p> http://mathoverflow.net/questions/134117/which-real-analytic-functions-of-two-variables-locally-are-magnitudes-of-complex Comment by Anthony Quas Anthony Quas 2013-06-19T08:33:03Z 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 http://mathoverflow.net/questions/132388/intuition-of-law-of-iterated-logarithm Comment by Anthony Quas Anthony Quas 2013-05-31T06:09:31Z 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&gt;\sqrt{2\log\log n})$is on the cusp of summability. So that$\mathbb P(N&gt;\sqrt{2.000001\log\log n})$is summable, so happens finitely many times (this is the easier part), whereas$\mathbb P(N&gt;\sqrt{1.999999\log\log n})$is not summable and so [quite a lot of annoying technical details skipped] happens infinitely often. http://mathoverflow.net/questions/132355/how-to-simulate-random-paths-of-a-non-homogeneous-continuous-time-markov-process/132376#132376 Comment by Anthony Quas Anthony Quas 2013-05-31T06:04:01Z 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. http://mathoverflow.net/questions/132221/quasicompactness-of-transfer-operators-associated-to-iid-matrix-products Comment by Anthony Quas Anthony Quas 2013-05-29T23:52:05Z 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? http://mathoverflow.net/questions/132221/quasicompactness-of-transfer-operators-associated-to-iid-matrix-products Comment by Anthony Quas Anthony Quas 2013-05-29T18:56:31Z 2013-05-29T18:56:31Z Interesting question. Do you know if in your case the Lyapunov exponents of the action are distinct? http://mathoverflow.net/questions/132167/family-of-random-sets-represent-all-integers-a-s Comment by Anthony Quas Anthony Quas 2013-05-29T00:39:28Z 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). http://mathoverflow.net/questions/129983/discrete-disjoint-covering-of-integer-lattices Comment by Anthony Quas Anthony Quas 2013-05-08T08:34:41Z 2013-05-08T08:34:41Z I did something related in$\mathbb R^d$and found a family of tilings there (see &lt;a href=&quot;<a href="http://mathoverflow.net/questions/77952/name-this-periodic-tiling&quot;&gt;this" rel="nofollow" title="name this periodic tiling%26quot%3b%26gt%3bthis">mathoverflow.net/questions/77952/&hellip;</a> question&lt;/a&gt;). It turned out that the tilings had been previously studied under the name &lt;i&gt;notched cube tilings&lt;/i&gt;. It's quite plausible that some version of Stein's ideas can be applied in your situation. http://mathoverflow.net/questions/129995/is-it-difficult-to-prove-that-nature-is-chaotic Comment by Anthony Quas Anthony Quas 2013-05-08T08:26:54Z 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. http://mathoverflow.net/questions/129957/is-the-sequence-omegan-alpha-uniformly-distributed-in-0-1 Comment by Anthony Quas Anthony Quas 2013-05-07T15:45:28Z 2013-05-07T15:45:28Z If the Erd&amp;ouml;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. http://mathoverflow.net/questions/129483/longest-run-of-heads Comment by Anthony Quas Anthony Quas 2013-05-03T03:24:32Z 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)&lt;(1-epsilon)\log n$with an arbitrary$y$in the part where$R_n(y)&gt;= (1-\epsilon)\log n$. When this is done, pair the remaining stuff arbitrarily. http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 Comment by Anthony Quas Anthony Quas 2013-05-03T00:59:51Z 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... http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 Comment by Anthony Quas Anthony Quas 2013-05-03T00:58:21Z 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. http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 Comment by Anthony Quas Anthony Quas 2013-05-01T07:19:04Z 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. http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 Comment by Anthony Quas Anthony Quas 2013-05-01T03:51:06Z 2013-05-01T03:51:06Z Pairwise independence is not enough; But there is <i>much</i> more independence than that here. This kind of argument shows up all over the place in The Probabilistic Method. http://mathoverflow.net/questions/129263/variant-of-an-expander-graph-probability-that-s-random-points-cast-a-shadow-proj/129266#129266 Comment by Anthony Quas Anthony Quas 2013-05-01T02:13:25Z 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.