savoy082

Pt En An obvious way of creating rational approximations for irrational numbers is by truncating its decimal expansion. For example, $3$, $3.1$ and $3.14$ are all rational approximations of $\pi $; as fractions, those approximations would be written $3$, $\frac{31}{10}$ and $\frac{314}{100} $. Notice how $\frac{314}{100}$ has $100$ as the denominator and yet only produces an approximation correct up to two decimal places. Claim: by using continued fractions one can obtain better rational approximations for irrational numbers. Method: if $x $ is an irrational number, instead of truncating its decimal expansion, we can truncate its continued fraction. Taking $\pi $ as an example, we have $$\pi = 3 + \frac1{7 + \frac1{15 + \cdots}} $$ and by taking $$\pi \approx 3 + \frac17 = \frac{22}{7} $$ we get the approximation $\pi \approx 3.14285\cdots$: it is correct up to two decimal places just as $\frac{314}{100} $, but $7$ is a much smaller denominator than $100$. (And all in all, $\frac...

Pt En In this twitter proof we will have a look at a rather curious, yet simple, property of real polynomials. Claim: if $p(x) = \sum_{i=0}^n a_ix^i $ is a polynomial with real coefficients, then for all complex numbers $z $, $$p(z) = 0 \iff p(\bar{z}) = 0$$ which means that the complex roots of $p(x) $ come in conjugate pairs. Twitter proof: it suffices to show that $p(z) = 0 \implies p(\bar{z}) = 0$. Assume that $p(z) = 0$ and recall that $a_i = \bar{a_i} $: $$\begin{align} p(\bar{z}) &= \sum_{i=0}^n a_i\bar{z}^i \\ &= \sum_{i=0}^n \overline{a_iz^i} \\ &= \overline{\sum_{i=0}^n a_iz^i} = \overline{p(z)} = 0 \end {align} $$ Neste post vamos dar uma olhadela a uma propriedade curiosa, mas simples, dos polinómios com coeficientes reais. Proposição: se $p(x) = \sum_{i=0}^n a_ix^i $ é um polinómio com coeficientes reais, então para qualquer número complexo $z $ vem $$p(z) = 0 \iff p(\bar{z}) = 0$$ o que significa que as raízes complexas de $p(x) $ vêm em pares conjuga...

Pt En In this post I will show the existence of a family of polynomials that are very useful for interpolation. For that I will use what are known as Lagrange polynomials. Claim: given $n+1$ pairs $(x_i, y_i) $ with $0\leq i \leq n $ and with $x_i \neq x_j $ whenever $i\neq j $, there exists a polynomial $p(x) $ of degree at most $n $ such that $$p(x_i) = y_i,\ i = 0, \cdots, n $$ Twitter proof: consider the polynomial $$l_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} $$ with $l_i(x_i) = 1$ and $l_i(x_j) = 0$ whenever $j \neq i$. Define $p(x) $ to be $$p(x) = \sum_{i=0}^{n} y_i l_i(x) $$ $p(x) $ has degree at most $n $ because so do the $l_i(x) $ and $p(x_k) = \sum_i y_i l_i(x_k) = y_k $. In a future post I will show the uniqueness of the polynomial satisfying the constraints in the claim. Neste post vou mostrar a existência de uma família interessante de polinómios, muito útil em interpolação. Para isso vou usar uns polinómios chamados polinómios de Lagrange. Proposição: d...

Pt En In this twitter proof we will see that no polynomial grows faster than the exponential function. Claim: the ratio $\frac{x^p}{e^x}$ tends to $0$ as $x $ tends to infinity. Twitter proof: recall that by the Taylor expansion of $e^x $ we have $$e^x = \sum_{i=0}^\infty \frac{x^i}{i!}$$ and for $x > 0$ we have $$\frac{x^p}{e^x} \leq \frac{x^p}{\sum_{i=0}^{p+1} a_ix^i} \to 0 $$ where $a_{p+1} \neq 0$ thus proving our claim. The way I like to look at this is "if the exponential has a bit of every polynomial inside, then it will grow faster than any fixed polynomial $p(x)$" (because, in particular, the exponential "has a bit" of all other polynomials that have degree higher than that of $p(x) $. Neste post vamos ver que a função exponencial cresce mais depressa que qualquer função polinomial. Proposição: o rácio $\frac{x^p}{e^x}$ tende para $0$ quando $x $ tende para infinito. Prova num tweet: sabemos pela expansão de Taylor de $e^x $ que $$e^x = \sum...

Pt En For this twitter proof we will be using a piece of mathematics straight from the 17th century. Claim: the number $\sqrt[n]{2} $ is irrational for $n \geq 3$. Twitter proof: suppose that $n \geq 3$ and $\sqrt[n]{2}$ is rational, i.e. $\sqrt[n]{2} = \frac{a}{b}$ for some integers $a, b $. Then taking the $n $-th power of both sides we get $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contradicting the well-known Fermat's Last Theorem . Para esta prova num tweet vamos usar um pedaço de matemática do século 17. Proposição: o número $\sqrt[n]{2} $ é irracional para $n \geq 3$. Prova num tweet: suponhamos que $n\geq 3$ e que $\sqrt[n]{2} $ é racional, i.e. $\sqrt[n]{2} = \frac{a}{b} $ para alguns inteiros $a, b $. Se for esse o caso, elevando os dois lados da igualdade a $n $, obtemos $2 = \frac{a^n}{b^n} \iff b^n + b^n = a^n $, contrariando o famoso Último Teorema de Fermat . &nbsp&nbsp- RGS join the mathspp mailing list

Pt En In this post I will share with you my favourite proof that the series of the inverses diverges: $\sum_{i=1}^\infty \frac1i = \infty $. Claim : the series $\sum_i \frac1i$ diverges. Twitter proof : consider the series $$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\frac14 + 4\times \frac18 + \cdots = \\ &\frac12 + \frac14 + \frac14 + \frac18 + \cdots \leq \\ &\frac12 + \frac13 + \frac14 + \frac15 + \cdots \end{align}$$ that clearly diverges because it is a series of a constant nonzero term. By the comparison test, the series of the inverses also diverges. Comment with your favourite way to prove this fact!! Neste post quero partilhar com todos a minha prova preferida de que a série dos inversos dos naturais diverge: $\sum_{i=1}^\infty \frac1i = \infty $. Proposição : a série $\sum_i \frac1i$ diverge. Prova num tweet : considere-se a série$$ \begin{align} &\frac12 + \frac12 + \frac12 + \cdots = \\ &\frac12 + 2 \times\fr...

Pt En In this post we prove what the minimum number of moves to solve the problem of the Tower of Hanoi is! Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$. Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$. If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ dis...

Pt En This post is going to follow up what was discussed here , and I will show you how changing the value of the discount factor may affect what the optimal policy is. For that, consider the MDP defined below: This MDP is inspired in the example I have been using; I added an extra state and stripped the MDP of the majority of the transitions so we can focus on what is essential here. From the MDP above there is a clear contender for the title of optimal policy: $$\begin{align} &\pi(H) = E\\ &\pi(T) = D\\ &\pi(TU) = D\end{align}$$ Assume that when we enter the MDP there is a $50\%$ chance we start Hungry and a $50\%$ chance we start Thirsty. If we use the policy $\pi$ then the expected reward is $$E[R | \pi] = 0.5E[R_T | \pi] + 0.5E[R_H | \pi]$$ where $E[R_s | \pi]$ is the expected reward we get by following policy $\pi$ starting from state $s$. From my previous post we know that $E[R_T | \pi] = E[R_H | \pi] = \frac{1}{1-\gamma}$ and hence $$E[R | \pi] = \frac{1}{1-\g...

Pt En In this previous post I defined a Markov Decision Process and explained all of its components; now, we will be exploring what the discount factor $\gamma$ really is and how it influences the MDP. Let us start with the complete example of last post: In this MDP the states are Hungry and Thirsty (which we will represent with $H$ and $T$) and the actions are Eat and Drink (which we will represent with $E$ and $D$). The transition probabilities are specified by the numbers on top of the arrows. In the previous post we put forward that the best policy for this MDP was defined as $$\begin{cases} \pi(H) = E\\ \pi(T) = D\end{cases}$$ but I didn't really prove that. I will do that in a second, but first what are all the other possible policies? Well, recall that the policy $\pi$ is the "best strategy" to be followed, and $\pi$ is formally seen as a function from the states to the actions, i.e. $\pi: S \to A$. Because of that, we must know what $\pi(H)$ and $\pi(T)$ a...

Pt En In this post I will introduce Markov Decision Processes, a common tool used in Reinforcement Learning, a branch of Machine Learning. By the end of the post you will be able to make some sense of the figure above! I will couple the formal details, definitions and maths with an intuitive example that will accompany us throughout this post. In later posts we will make our example more complete and use other examples to explain other properties and characteristics of the MDPs. Let me introduce the context of the example: From a simplistic point of view, I only have two moods: " hungry " and " thirsty ". Thankfully, my parents taught me how to eat and how to drink, so that I can fulfill the needs I mentioned earlier. Of course that eating when I am hungry makes me happy, just as drinking when I am thirsty makes me happy! Not only that, but eating when I am hungry usually satisfies me, much like drinking when I am thirsty usually satisfies me. Suppose that, g...

Pt En In this twitter proof we will see how the exponential function can mess up with objects from our daily lives!.. Claim: with less than $50$ folds, a piece of paper will be so thick that it will cover the distance from the Earth to the Moon. Twitter proof: a common sheet of paper is $0.1$mm thick. If we fold it once, it becomes $0.2$mm thick. Folding twice, $0.4$mm. Folding $49$ times, the paper becomes $2^{49}\times 0.1$mm thick, which is around $5.63\times 10^{13} $mm or $5.63\times10^7$km, $141$ times the distance from the Earth to the Moon ($398818$km). Neste post vamos ver como a função exponencial pode interagir com objetos do nosso quotidiano e criar resultados inesperados. Proposição: com menos de $50$ dobras, uma folha de papel fica com uma grossura superior à distância da Terra à Lua. Prova num tweet: uma folha de papel normal tem $0.1$mm de grossura. Se a dobrarmos uma vez, fica com $0.2$mm de grossura. Dobrando de novo, fica com $0.4$mm. Dobrando $49$ vezes,...

Pt En In this post we will see why it is not helpful to have two consecutive layers of neurons with linear activation functions in neural networks. With just a bit of maths we can conclude that $n$ consecutive linear layers compute the exact same functions as $1$ single layer. Claim: having two fully connected layers of neurons using linear activation functions is the same as having just one layer with a linear activation function. We just have to lay down some notation in order for the maths to be doable. Assume the two consecutive layers of linear neurons are preceded by a layer with $n_0$ neurons, whose outpus are $o_1, o_2, \cdots, o_{n_0}$. Let us say that after that layer, there is a layer of $n_1$ neurons with linear activation functions $f_i(x) = a_ix + b_i$; the weight from neuron $t$ of the previous layer to the neuron $i$ of this layer is $w_{t,i}$. The second layer of neurons has $n_2$ neurons, with linear activation functions $f_i'(x) = a_i'x+b_i'$ and the...

Pt En After watching this video from Siraj Raval, I decided to jump right on board of the #100daysofMLcode initiative! (even though I am something like 73 days late...) The goal here is to devote (at least) 1h every day, for the next 100 days, to studying ML or writing code! According to the rules posted by Siraj, I must: Make a public pledge for this, which this post is; Make a log of everything, which this post will also be; Whenever I see something related to this #100DaysofMLCode, be supportive! Progress log For the day $0$ I wrote this post and spent quite some time thinking about what I will do throughout. I am thinking of studying several topics about ML and then writing educative posts here, for the blog. For today I wrote this twitter proof , tackling a mathematical property of neural networks with linear activation functions. Started reading about Reinforcement Learning and Markov Decision Processes; already imagined a nice example I will be using when writing about th...