text:
The main purpose of this thesis is to analyze and propose new improvements in the field of Automatic Keyphrase Extraction, i.e., the field of automatically detecting the key concepts in a document. We will discuss, in particular, supervised machine learning algorithms for keyphrase extraction, by first identifying their shortcomings and then proposing new techniques which exploit contextual information to overcome them. Keyphrase extraction requires that the key concepts, or \emph{keyphrases}, appear verbatim in the body of the document. We will identify the fact that current algorithms do not use contextual information when detecting keyphrases as one of the main shortcomings of supervised keyphrase extraction. Instead, statistical and positional cues, like the frequency of the candidate keyphrase or its first appearance in the document, are mainly used to determine if a phrase appearing in a document is a keyphrase or not. For this reason, we will prove that a supervised keyphrase extraction algorithm, by using only statistical and positional features, is actually able to extract good keyphrases from documents written in languages that it has never seen. The algorithm will be trained over a common dataset for the English language, a purpose-collected dataset for the Arabic language, and evaluated on the Italian, Romanian and Portuguese languages as well. This result is then used as a starting point to develop new algorithms that use contextual information to increase the performance in automatic keyphrase extraction. The first algorithm that we present uses new linguistics features based on anaphora resolution, which is a field of natural language processing that exploits the relations between elements of the discourse as, e.g., pronouns. We evaluate several supervised AKE pipelines based on these features on the well-known SEMEVAL 2010 dataset, and we show that the performance increases when we add such features to a model that employs statistical and positional knowledge only. Finally, we investigate the possibilities offered by the field of Deep Learning, by proposing six different deep neural networks that perform automatic keyphrase extraction. Such networks are based on bidirectional long-short term memory networks, or on convolutional neural networks, or on a combination of both of them, and on a neural language model which creates a vector representation of each word of the document. These networks are able to learn new features using the the whole document when extracting keyphrases, and they have the advantage of not needing a corpus after being trained to extract keyphrases from new documents. We show that with deep learning based architectures we are able to outperform several other keyphrase extraction algorithms, both supervised and not supervised, used in literature and that the best performances are obtained when we build an additional neural representation of the input document and we append it to the neural language model. Both the anaphora-based and the deep-learning based approaches show that using contextual information, the performance in supervised algorithms for automatic keyphrase extraction improves. In fact, in the methods presented in this thesis, the algorithms which obtained the best performance are the ones receiving more contextual information, both about the relations of the potential keyphrase with other parts of the document, as in the anaphora based approach, and in the shape of a neural representation of the input document, as in the deep learning approach. In contrast, the approach of using statistical and positional knowledge only allows the building of language agnostic keyphrase extraction algorithms, at the cost of decreased precision and recall.

Advances in Automatic Keyphrase Extraction / Marco Basaldella - : . , 2018 Feb 26. ((30. ciclo, Anno Accademico 2016/2017.

### Advances in Automatic Keyphrase Extraction

#### Abstract

The main purpose of this thesis is to analyze and propose new improvements in the field of Automatic Keyphrase Extraction, i.e., the field of automatically detecting the key concepts in a document. We will discuss, in particular, supervised machine learning algorithms for keyphrase extraction, by first identifying their shortcomings and then proposing new techniques which exploit contextual information to overcome them. Keyphrase extraction requires that the key concepts, or \emph{keyphrases}, appear verbatim in the body of the document. We will identify the fact that current algorithms do not use contextual information when detecting keyphrases as one of the main shortcomings of supervised keyphrase extraction. Instead, statistical and positional cues, like the frequency of the candidate keyphrase or its first appearance in the document, are mainly used to determine if a phrase appearing in a document is a keyphrase or not. For this reason, we will prove that a supervised keyphrase extraction algorithm, by using only statistical and positional features, is actually able to extract good keyphrases from documents written in languages that it has never seen. The algorithm will be trained over a common dataset for the English language, a purpose-collected dataset for the Arabic language, and evaluated on the Italian, Romanian and Portuguese languages as well. This result is then used as a starting point to develop new algorithms that use contextual information to increase the performance in automatic keyphrase extraction. The first algorithm that we present uses new linguistics features based on anaphora resolution, which is a field of natural language processing that exploits the relations between elements of the discourse as, e.g., pronouns. We evaluate several supervised AKE pipelines based on these features on the well-known SEMEVAL 2010 dataset, and we show that the performance increases when we add such features to a model that employs statistical and positional knowledge only. Finally, we investigate the possibilities offered by the field of Deep Learning, by proposing six different deep neural networks that perform automatic keyphrase extraction. Such networks are based on bidirectional long-short term memory networks, or on convolutional neural networks, or on a combination of both of them, and on a neural language model which creates a vector representation of each word of the document. These networks are able to learn new features using the the whole document when extracting keyphrases, and they have the advantage of not needing a corpus after being trained to extract keyphrases from new documents. We show that with deep learning based architectures we are able to outperform several other keyphrase extraction algorithms, both supervised and not supervised, used in literature and that the best performances are obtained when we build an additional neural representation of the input document and we append it to the neural language model. Both the anaphora-based and the deep-learning based approaches show that using contextual information, the performance in supervised algorithms for automatic keyphrase extraction improves. In fact, in the methods presented in this thesis, the algorithms which obtained the best performance are the ones receiving more contextual information, both about the relations of the potential keyphrase with other parts of the document, as in the anaphora based approach, and in the shape of a neural representation of the input document, as in the deep learning approach. In contrast, the approach of using statistical and positional knowledge only allows the building of language agnostic keyphrase extraction algorithms, at the cost of decreased precision and recall.
##### Scheda breve Scheda completa Scheda completa (DC)
automatic; keyphrase; extraction; machine; learning
automatic; keyphrase; extraction; machine; learning
Advances in Automatic Keyphrase Extraction / Marco Basaldella - : . , 2018 Feb 26. ((30. ciclo, Anno Accademico 2016/2017.
File in questo prodotto:
File
Basaldella_tesi definitiva.pdf

accesso aperto

Descrizione: tesi di dottorato
Dimensione 2.89 MB
Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/1143008


text:
# rational fractions?

• May 24th 2011, 07:49 PM
whit221
rational fractions?
I am a little unsure about this question, as I have found an answer that may suggest the one in the book has a mistake or I am not understanding correctly how to do it.
Write each expression as a single power with positive exponents.
a) $\frac{6^\frac{3}{2} \times 6^5}{6} = \frac{6^\frac{13}{2}}{6^\frac{2}{2}} = 6^\frac{11}{2}
$

The answer in the text is:
$16^\frac{11}{2}$

• May 24th 2011, 07:50 PM
TheEmptySet
Quote:

Originally Posted by whit221
I am a little unsure about this question, as I have found an answer that may suggest the one in the book has a mistake or I am not understanding correctly how to do it.
Write each expression as a single power with positive exponents.
a) $\frac{6^\frac{3}{2} \times 6^5}{6} = \frac{6^\frac{13}{2}}{6^\frac{2}{2}} = 6^\frac{11}{2}
$

The answer in the text is:
$16^\frac{11}{2}$

format: plain


text:
## Institute of Mathematical Statistics Lecture Notes - Monograph Series

### Weighted FWE-controlling methods in high-dimensional situations

#### Abstract

With high dimensionality, standard Bonferroni-style procedures can suffer from loss of power, since the significance level $\alpha$ must be divided by $k$ to declare significance. Kropf and Läuter (KL) show that certain data-dependent quadratic forms can be used to "pre-specify hypotheses, which can then be tested in a fixed, data-dependent order, without multiplicity adjustment. In this article we extend the KL procedure to a class of weighted procedures, using the same quadratic forms. The class includes the KL method, the Bonferroni-Holm method, and other, new procedures. We establish strong FWE control for all procedures, and compare power and level of various weighting methods using analytical and simulation results. The method is applied using a high-dimensional mixture model that is suggested by the analysis of real gene expression data.

#### Chapter information

Source
Y. Benjamini, F. Bretz and S. Sarkar, eds., Recent Developments in Multiple Comparison Procedures (Beachwood, Ohio, USA: Institute of Mathematical Statistics, 2004), 143-154

Dates
First available in Project Euclid: 28 November 2007

https://projecteuclid.org/euclid.lnms/1196285632

Digital Object Identifier
doi:10.1214/lnms/1196285632

Mathematical Reviews number (MathSciNet)
MR2118598

Rights


text:
# Plotting the DTFT using the output of fft6

Posted by Steve Eddins,

In my Fourier transform series I've been trying to address some of the common points of confusion surrounding this topic. For today's espisode I want to look at how to use the fft function to produce discrete-time Fourier transform (DTFT) magnitude plots in the form you might see in a textbook. Recall that the fft computes the discrete Fourier transform (DFT). I described the relationship between the DFT and the DTFT in my March 15 post.

For my example I'll work with a sequence that equals 1 for and equals 0 elsewhere.

Here's a plot of the DTFT magnitude of this sequence:

Now let's see what get using fft.

x = ones(1, 5)
x =

1     1     1     1     1

X = fft(x);
plot(abs(X))

Wow, that's not anywhere close to the DTFT magnitude plot above. And why does it look like it's only got two points? Well, take a look at the actual values of X:

X
X =

5     0     0     0     0

We have a 5 and four 0s. What's going on? I explained this back in my March 15 post when I discussed the relationship between the DFT and the DTFT. The outputs of the DFT are samples of the DTFT, and in this case the sample locations just happen to align with the locations of four zeros in the DTFT.

You can get a finer sampling (and a much nicer-looking DTFT plot) by zero-padding. Here I'll use the zero-padding syntax of fft.

N = 256;
X = fft(x, N);
plot(abs(X))

That's a smoother-looking curve, but it still looks quite a bit different than the DTFT magnitude plot above. To explain the MATLAB output we're looking at, let me show a DTFT magnitude plot that shows three periods instead of just one.

You can see that the output from MATLAB is one period of the DTFT, but it's not the period normally plotted, which is from to . Instead, it's the period from 0 to . To get a plot from to , use the fftshift function.

plot(abs(fftshift(X)))

That leaves us with the question of labeling the frequency axis. We want a plot in radians from to .

The way I always remember the frequency scaling between the DFT and the DTFT is this: the length of the DFT corresponds to the frequency in the DTFT.

So the frequencies in radians corresponding to the output elements of fft are:

w = 2*pi * (0:(N-1)) / N;

But we're calling fftshift to plot the magnitude of the DTFT, so we have to perform a similar shift on our frequencies:

w2 = fftshift(w);
plot(w2)

Now our frequencies start at and have a discontinuity in the middle. Here's one way to fix that up:

w3 = unwrap(w2 - 2*pi);
plot(w3)

Now we can redo our magnitude DTFT plot with the x-axis labels.

plot(w3, abs(fftshift(X)))
xlabel('radians')

Often I like to see the multiples of more clearly along the x-axis. One way to accomplish this is to normalize the frequency variable by .

plot(w3/pi, abs(fftshift(X)))
xlabel('radians / \pi')

Another option is to try Alan's pilabels contribution on the MATLAB Central File Exchange.

For the next time, I'm thinking of tackling the question of why the following output is complex:

fft([1 2 3 2 1])
ans =

9.0000            -2.1180 - 1.5388i   0.1180 + 0.3633i   0.1180 - 0.3633i  -2.1180 + 1.5388i

Many people expect it to be real.

Get the MATLAB code

Published with MATLAB® 7.10

OysterEngineer replied on : 1 of 6

Steve,

Thanks for another well written column.

SanguineCat replied on : 2 of 6

I went through the Fourier articles yesterday, and they’re very helpful. Thanks Steve.

The following question may be due to my inability to understand the unwrap function correctly. Does anyone know why the unwrapping the following code does not produce a linear result?

Fs = 20;
N=100;
F=[0:N-1]/N*Fs;
plot(unwrap(fftshift(F)-Fs))

Steve replied on : 3 of 6

SanguineCat—The function unwrap is meant for correcting discontinuities of phase angles caused by a branch cut in the complex plane. It is looking for discontinuities of greater than pi, and your example doesn’t have any discontinuities that big. You could try reducing the “jump tolerance,” which is the optional second input argument to unwrap.

Steve replied on : 4 of 6

SanguineCat—Oops, I didn’t explain that quite right. The function unwrap “fixes” discontinuities by adding multiples of 2*pi. The thing you are trying to unwrap isn’t made up of phase angles and the discontinuity isn’t close to a multiple of 2*pi, so unwrap is the wrong thing to use.

Ding replied on : 5 of 6

Nice Post, Steve. I learned something from the use of unwrap function here.

Regarding to labeling the frequency axis of FFT spectrum output, there might be a much easy way like this:

w4=2*pi*(-N/2:N/2-1)/N;
figure
plot(w4/pi,abs(fftshift(x)));

Normally, N is chosen even in FFT zero padding…

Starstrike replied on : 6 of 6

My first introduction to the unwrap function – it’s one I use so often I’d created a subfunction of my own to do it, without discovering ‘unwrap’. I can at least console myself that my custom version is faster – but I rarely call it multiple times, so might just switch to the greater redundancy of unwrap.

Interesting to see that you can get the DTFT from the DFT; oddly – using DFTs all the time – I was looking for a fast way to calculate the DTFT recently.

Ding’s code, as implied, would need a separate definition of w4 in the case of odd N, eg for unpadded DFTs.

These postings are the author's and don't necessarily represent the opinions of MathWorks.


text:
# Riemann-Stieltjes Integral with respect to total variation

In this Inequality for Riemann-Stieltjes integral the following question came up. Suppose functions $f,g:[a,b] \to \mathbb{R}$ are such that $f$ is Riemann-Stieltjes integrable with respect to $g$. Suppose $g$ has bounded variation and $v_a^x(g)$ is the total variation on interval $[a,x]$.

Is it true that $f$ is integrable with respect to $v_a^x(g)$ (even if $f$ is not continuous)? If true how could this be proved?

The assertion is true.

To simplify notation let $$h(x) = v_a^x(g)$$. Given a partition $$P = (x_0,x_1,\ldots, x_n)$$ of $$[a,b]$$ consider the upper and lower sums,

$$U(P,f,h) = \sum_{j=1}^n M_j \, [h(x_j) - h(x_{j-1})], \\ L(P,f,h) = \sum_{j=1}^n m_j \, [h(x_j) - h(x_{j-1})],$$

where $$M_j = \sup_{x \in [x_{j-1},x_j]} f(x)$$ and $$m_j = \inf_{x \in [x_{j-1},x_j]} f(x).$$

To prove that the integral $$\int_a^b f \, dh$$ exists we can show that the difference $$U(P,f,h) - L(P,f,h)$$ can be made arbitrarily close to $$0$$ with a suitable choice for $$P$$.

Since $$f$$ is Riemann-Stieltjes integable with respect to $$g$$ it is bounded and $$|f(x)| \leqslant M$$ for all $$x \in [a,b].$$ Since $$g$$ has bounded variation, for any $$\epsilon > 0$$ there exists a partition $$P_\epsilon$$ such that for any refining partition $$P$$ we have

$$v_a^b(g) - \sum_{j=1}^n |g(x_j) - g(x_{j-1})| \leqslant \frac{\epsilon}{M}.$$

Since $$h(x_j) - h(x_{j-1}) = v_{x_{j-1}}^{x_j}(g) \geqslant |g(x_j) - g(x_{j-1})|$$, we have

$$U(P,f,h) - L(P,f,h) - \sum_{j=1}^n(M_j - m_j) |g(x_j) - g(x_{j-1})|\\ = \sum_{j=1}^n(M_j - m_j) [\,h(x_j) - h(x_{j-1}) - |g(x_j) - g(x_{j-1})|\,] \\ \leqslant 2M\sum_{j=1}^n [\,h(x_j) - h(x_{j-1}) - |g(x_j) - g(x_{j-1})|\,] \\ = 2M \left[ v_a^b(g) -\sum_{j=1}^n |g(x_j) - g(x_{j-1})|\,\right] \\ \leqslant 2 \epsilon.$$

Thus,

$$U(P,f,h) - L(P,f,h) < 2 \epsilon + \sum_{j=1}^n(M_j - m_j) |g(x_j) - g(x_{j-1})|.$$

If we can argue that the integrability of $$f$$ with respect to $$g$$ implies that sum on the RHS can be made smaller than $$\epsilon$$ for a suitable choice for $$P$$ (that refines $$P_\epsilon$$), then we are finished.

Unfortunately, this sum is not a difference of upper and lower sums due to the presence of the absolute value and the fact that, in general, $$g$$ may not be nonnegative.

Nevertheless, it is true that if $$P$$ is sufficiently fine, then

$$\sum_{j=1}^n (M_j - m_j)|g(x_j) - g(x_{j-1})| < \epsilon.$$

This can be shown by separately considering subintervals where $$g(x_j) - g(x_{j-1}) \geqslant 0$$ and where $$g(x_j) - g(x_{j-1}) < 0$$, and finding points $$\xi_j, \xi_j' \in [x_{j-1},x_j]$$ where, respectively, $$M_j - m_j < f(\xi_j) - f(\xi_j') + \epsilon/(2v_a^b(g))$$ and $$M_j - m_j < f(\xi_j') - f(\xi_j) + \epsilon/(2v_a^b(g)).$$

$$\sum_{j=1}^n (M_j - m_j)|g(x_j) - g(x_{j-1})| \\ \leqslant \sum_{j=1}^n [f(\xi_j) - f(\xi_j')] \, [g(x_j) - g(x_{j-1})] + \frac{\epsilon}{2 v_a^b(g)}\sum_{j=1}^n|g(x_j) - g(x_{j-1})| \\ \leqslant \sum_{j=1}^n [f(\xi_j) - f(\xi_j')] \, [g(x_j) - g(x_{j-1})] + \frac{\epsilon}{2}.$$
The first term on the RHS is a difference of Riemann-Stieltjes sums and is smaller that $$\epsilon/2$$ for $$P$$ sufficiently fine, completing the proof.
• Thanks. Can you explain further why the sum in the last inequality is smaller than $\epsilon/2$? – AlRacoon Jan 5 '18 at 17:43
• @AlRacoon: Note that $\sum_{j=1}^n [f(\xi_j) - f(\xi_j')] \, [g(x_j) - g(x_{j-1})] = S(P,f,g,T) - S(P,f,g,T')$ -- two different tagged sums corresponding to the same partition. So the absolute value of that sum is less than or equal to $|S(P,f,g,T) - \int_a^b f \, dg| + |S(P,f,g,T') - \int_a^b f \, dg| < \epsilon$, if $P$ is sufficiently fine since $f$ is integrable with respect to $g$. – RRL Jan 5 '18 at 20:18
• How do you make sure that $M_j-m_j$ is $\leq$ some value where $g(x_j)-g(x_{j-1})<0$ (see another answer here). – Paramanand Singh Oct 14 '18 at 21:25


text:
Capital Gain

Any capital asset when sold can give the seller a higher or lower price from its purchase price leading to a capital gain or capital loss. The time period of holding an asset is decided based on if it is a long term or short-term capital gain. On that basis, the rate of taxation is decided if it is 20%, 15% or according to the tax brackets. The rate of taxation differs in the case of equity or debt, whether long or short term. The capital gain can be adjusted from capital loss to arrive at a net capital gain. The amount of gains and the exemption has to be reported in the tax return filed in the financial year in which the asset was transferred. The tax return can be filed quarterly, monthly, semi-annually or annually.

What is Capital Gain?

It refers to an increase in the value of a capital asset and the amount that is realized when the asset is sold off. A capital gain may be short-term or a long-term depending on the tenure for which the asset is held. A capital loss generally occurs when the market value of an asset decreases over a period of time as compared to its purchase price.

What is Capital Gains Tax?

A capital gains tax is generally levied on the growth in the value of investments incurred when individuals and companies sell their investments in a certain period of time. When such assets are sold, the gains so made are referred to as having been realized. The capital gains tax doesn't apply to any unsold investments or unrealized capital gains, hence the shares that appreciate every year will not incur any capital gains taxes until they are sold, no matter how long it has been held. Types of capital asset and capital gains tax is applicable on it.

The capital gains tax is categorized into two.

Long Term Capital Asset

These are the assets that are held for more than a year. For example, if any house property is sold after holding it for more than 24 months, it will be termed as a long-term capital gain (LTCG).

Short Term Capital Asset

These are the assets that are held for one year or less. In the case of immovable properties such as house, land, or building, the criteria are of 24 months or less. In the case of the following assets, they are considered short-term when held for 12 months or less.

Conditions for Attracting Tax on Capital Gain.

• There must be a capital asset owned by the seller.
• There must be a transfer of capital assets in the financial year.
• There must have been gain on the transfer of capital assets.

Tax on the long term and short-term capital gain (STCG)

1. The tax rate on LTCG is normally 0%, 15%, or 20% depending on tax bracket.
2. The LTCG tax rate on the sale of equity shares is 10% over and above 1 lakh
3. Short term capital gain tax is taxed as ordinary income.

Calculation of Capital Gain

Below mentioned points need to be considered while calculating capital gain.

• Cost of acquisition: The price at which an asset was bought by the seller initially.
• Cost of improvement: Any expenses made in addition to any improvement in the asset.
• Full value consideration: Total amount received or to be received by the seller for transfer of property.

What is Net Capital Gain?

The "net capital gain" is defined as the difference between net long-term gain (long-term capital gains minus long-term losses and any unused capital losses carried over from prior years) and net short-term capital loss (short-term gain minus short-term loss). A net capital gain may be subject to a lower tax rate than the ordinary income tax rate.

Can Mutual Funds Lead to Capital Gains?

The mutual funds that have accumulated realized capital gains are generally distributed to the shareholders and often before the end of the calendar year. The shareholders receive the fund's capital gains distribution along with a 1099-DIV form detailing the amount of the capital gain distribution along with the details of the amount considered as short-term capital gain and long-term capital gain as of the fund's ex-dividend date. The distribution thus helps in reducing the mutual fund's net asset value (NAV) by the amount of the pay-out. However, it does not impact the fund's total return.

US Capital Gains Tax

It applies to profits from assets held for more than one year known as LTCG. There are three types of tax rates that apply depending upon the tax bracket, which are 0%, 15%, or 20%.

It applies to profits from assets held for less than one year known as STCG.  They are taxed as ordinary income. Tax on a capital gain can be reduced by capital losses in the same year. Capital loss happens when an asset is sold below its acquisition price.

Net capital gain= LTCG – Capital loss

The advantage of capital gains is that tax payments are generally deferred until the asset is sold. For example, a real-estate investor does not have to pay taxes on the equity gained in a property investment until the year in which he sells the property for a profit. The investors pay taxes only during the tax year when they realize gain. It is different from income taxes where it is mandatory to pay tax each time payment is received.

A disadvantage of owning capital assets is that if they are sold for profit, the internal revenue service requires an individual to report such gains as income. The disadvantage of this tax is that it can reduce the overall profits realized from the sale of the asset.

Ways to Reduce Capital Gains Tax

1. Waiting longer than a year before selling: In case where a company sells an asset, it generally makes a long-term or short-term gain. One of the advantages of gains that fall under the long-term status is that they attract lower capital gains tax rates which is one of the ways in which capital gains tax can be reduced.
2. Sell when the income is low: The disposing of long-term capital gain assets during “lean” years meaning in the year when the income is low, it can help in reducing the capital gains tax; and the situations that may cause a decline in an individual’s income include approaching retirement period, quitting, or loss of employment. Therefore, selling the assets during such times can minimize the amount of tax levied.
3. Timing capital loss with capital gains: The capital losses can be used to offset capital gains. For example, individual owns two types of stocks, A and B. When he sells stock A, he makes a profit of $90, but when he sells stock B, he makes a loss of$40. His net capital gain is the difference between his capital gain and loss, \$50. Therefore, using losses in the year where an individual makes gains on capital can help him to lower the amount of tax significantly. It is to be noted that even though individuals are required to report all their capital gains, the tax to be levied is computed only on the net capital gain.

Context and Application

It is used and forms an important topic when the income tax topics ae covered in under-graduate and post graduate courses like

• Bachelor of Commerce
• Master of Commerce

Want more help with your accounting homework?

We've got you covered with step-by-step solutions to millions of textbook problems, subject matter experts on standby 24/7 when you're stumped, and more.
Check out a sample accounting Q&A solution here!

*Response times may vary by subject and question complexity. Median response time is 34 minutes for paid subscribers and may be longer for promotional offers.

Search. Solve. Succeed!

Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.

Tagged in


text:
1. ## 45-45-90 Triangle

Hi

Principle 5: The length of a leg opposite a 45 degree angle equals one-half the length of the hypotenuse times the square root of 2.

$a=\tfrac{1}{2}c\sqrt{2}$

why is this so? when I solve for 'a' in $c^{2}=a^{2}+a^{2}$ I get $\frac{c}{\sqrt{2}}=a$

Thanks.

2. Originally Posted by norifurippu
Hi

Principle 5: The length of a leg opposite a 45 degree angle equals one-half the length of the hypotenuse times the square root of 2.

$a=\tfrac{1}{2}c\sqrt{2}$

why is this so? when I solve for 'a' in $c^{2}=a^{2}+a^{2}$ I get $\frac{c}{\sqrt{2}}=a$

Thanks.
When your final answer has a radical in the denominator, we must 'rationalize' the denominator. By that, I mean, remove the radical from the denominator. How do we do that? We simply mutiply both numerator and denominator by the radical. Same as multiplying by 1. Value doesn't change, just how the fraction looks. See:

$\frac{c}{\sqrt2}\cdot\frac{\sqrt2}{\sqrt2}=\frac{c \sqrt2}{2}=\frac{1}{2}c\sqrt2$

3. Thanks!


text:
# Tag Info

1

I think you want $$S_{n}=S_{n−1}+ (x_{n}−μ_{n−1})(x_{n}−μ_{n})$$ where S, x and μ are respectively the variance, value and mean. See https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf for explanation and derivation.

3

You're also scaling $y$, then of course you are getting lower error. That question was regarding scaling $X$. The same model will have very different error metrics when units on $y$ are changed: if I multiply all $y$ values by 100, the error will be 100 times larger, if I divide all $y$ values by 100 the error will be divided by 100.

4

Scaling doesn't affect the performance of any tree-based method, not for lightgbm, xgboost, catboost or even a decision tree. This post that elaborates on the topic, but mainly the issue is that decision trees split the feature space based on binary decisions like "is this feature bigger than this value?", and if you scale your data, the decisions ...

0

We scale data because certain algorithm will not work optimally esp. Gradient descent. You may check the internet for further detail. Coming to the exact question - I am assuming, you have done the analysis that the Oridinal feature will be used as a Continuous(Not Categorical) feature with its respective values. So, I will ignore this point Models don't see ...

0

In real life problems you may not not have the actual “test data” to fit on, for example in some time series forecasting problems. My recommendation if you want to keep safe and avoid data leakage is to fit on training data and transform on test.

0

If it is a classification problem, then you will use sigmoid or softmax to make the output value in (0,1) and all the value must sum to 1 as per the rule of probability.

2

You should not use Label Encoding for Categorical data unless there is a known ranking and that also in the specified ratio between the level values. In this case, the model will assume 10 as 2 times of 5. One-hot will add a lot of dimensions as I can see in your data. You must try other Categorical encoding techniques esp. Sum Coding Or Helmert. You ...

Top 50 recent answers are included


text:
# Only One Equation Given?

Algebra Level 2

For natural numbers $x,y$, how many solution are there for the equation $x+y+xy=20$?

×


text:
Arithmetic Aptitude :: QE Quiz 8
Home » Arithmetic Aptitude » QE Quiz 8 » General Questions

Description: Free Online Test questions and answers on Quadratic Equation with explanation for various competitive exams,entrance test. Solved examples with detailed answer test 8

Exercise

 "When ambition ends, happiness begins." - (Proverb)
1 . Directions (Q. 1-5): In each of these questions, two equations (I) and (II) are given. You have to solve both the equations and give answer
(1) if x > y
(2) if x $\geq$y
(3) if x < y
(4) if x $\leq$y
(5) if x = y or a relationship between x and y cannot be established.

$Q.$
I. $x^ 2$ + 3x = 28
II. $y^ 2$ + 16y + 63 = 0
 $x > y$ $x \geq y$ $x < y$ $x \leq y$
2 . I. x = $\sqrt[3]{2197}$
II. y$^2$ = 169
 $x > y$ $x \geq y$ $x < y$ $x \leq y$
3 . I. $8x^ 2$ - 49x + 45 = 0
II.$8y^ 2$ - y - 9 = 0
 $x > y$ $x \geq y$ $x < y$ $x \leq y$
4 . I. 42x - 17y = -67
II. 7x + 12y = -26
 $x > y$ $x \geq y$ $x < y$ $x \leq y$
5 . I. $x^ 2$ - 8x + 15 = 0
II. $2y^ 2$ - 21y + 55 = 0
 $x > y$ $x \geq y$ $x < y$ $x \leq y$
6 . Directions (Q. 6-10): In each of these questions two equations (I) and (II) are given. You have to solve both the equations and give answer
(1) if p > q
(2) if p $\geq$ q
(3) if p < q
(4) if p $\leq$ q
(5) if p = q or no relation can be established between p and q.

$Q.$
I. $2.3p - 20.01 = 0$
II. $2.9q - p = 0$
 $p > q$ $p \geq q$ $p < q$ $p \leq q$
7 . I. p = $\sqrt{1764}$
II. $q^2$ = 1764
 $p > q$ $p \geq q$ $p < q$ $p \leq q$
8 . I. $p^ 2$ - 26p + 168 = 0
II. $q^ 2$ - 25q + 156 = 0
 p = q or no relation can be established between ‘p’ and ‘q’. $p \leq q$ $p < q$ $p \geq q$
9 . I. $p^ 2$ - 13p + 42 = 0
II. $q^ 2$ + q - 42 = 0
 $p > q$ $p \geq q$ $p < q$ $p \leq q$
 $p > q$ $p \geq q$ $p < q$ $p \leq q$


text:
# Write two pages on your understanding how religion and culture can influence nation diet.

###### Question:

Write two pages on your understanding how religion and culture can influence nation diet.

#### Similar Solved Questions

##### Find the area of the ellipse $b^{2} x^{2}+a^{2} y^{2}=a^{2} b^{2}$
Find the area of the ellipse $b^{2} x^{2}+a^{2} y^{2}=a^{2} b^{2}$...
##### 29-46 Skelch the curve with the given polar equation by first sketching the graph of 48 4 function of 0 in Cartesian coordinales. 29. r = 2 sin 0 J0. r = [ cos 0 31. r = 201 + COs 0) 32. r = | + 2c0s 0 33. r = 0. 0 > 0 34. r = 0 . 27 < 0 <2T 35. r = 3 cos 30 36. T = sin 50 37. r = 2cos 40 38. ' = 2 sin 60 39. r = ] - 3cos 0 40. ! = | +5sin 0 41. r _ 9 sin 20 42 r' = cus 40 43. / = 2 sin 30 44. r 0 = 45. 1= sin (0/2) 46. c0s(0/J
29-46 Skelch the curve with the given polar equation by first sketching the graph of 48 4 function of 0 in Cartesian coordinales. 29. r = 2 sin 0 J0. r = [ cos 0 31. r = 201 + COs 0) 32. r = | + 2c0s 0 33. r = 0. 0 > 0 34. r = 0 . 27 < 0 <2T 35. r = 3 cos 30 36. T = sin 50 37. r = 2cos 40 3...
##### Physics - Airborne Diver
A diver is airborne in full extended position rotating with a clockwise angular velocity w = -5 rad/s. At time t=0 he begins to pull his legs towards his chest at arate of -pi rad/s. Determine the angular velocity of his trunk and that of the lower extremities. Assume the diver is composed of two sl...
##### Problem 10: 10 points Assume that the distribution of the lifetime of a certain appliance is...
Problem 10: 10 points Assume that the distribution of the lifetime of a certain appliance is given. Knowing that the device has served five years, find the chance that it will serve 5 more years 1. Assume that the lifetime, T, is exponentially distributed, with the mean equal to 25 years. 2. How wil...
##### A population of diploid organisms is in Hardy-WeinbergEquilibrium. At one gene that only has two different alleles(biallelic), the allele frequency of one allele is 0.2. What is theexpected proportion of individuals in the population that areheterozygotes?
A population of diploid organisms is in Hardy-Weinberg Equilibrium. At one gene that only has two different alleles (biallelic), the allele frequency of one allele is 0.2. What is the expected proportion of individuals in the population that are heterozygotes?...
##### The ratio of boys to girls in a school is 8 : 9. If there are 256 boys, how many girls are there?
The ratio of boys to girls in a school is 8 : 9. If there are 256 boys, how many girls are there?...
##### Do high school students prefer certain movie genres over others?A high school mathematics teacher asked the 40 students in herPrecalculus class whether they'd prefer watching a comedy, athriller, an action film, or a horror film. 17 of the 40 students(42.5%) said they'd prefer a comedy.Regardless of whether validity conditions are met, use anappropriate formula to calculate a theory-based standardizedstatistic. Round your final answer to 3 decimal places.
Do high school students prefer certain movie genres over others? A high school mathematics teacher asked the 40 students in her Precalculus class whether they'd prefer watching a comedy, a thriller, an action film, or a horror film. 17 of the 40 students (42.5%) said they'd prefer a comedy...
##### LLciUse substitution to find the indefinite integral fol? +4t)(9t8 4)dt: fie 4t )9t8 4)dt = (Use C as the arbitrary constant )
LLci Use substitution to find the indefinite integral fol? +4t)(9t8 4)dt: fie 4t )9t8 4)dt = (Use C as the arbitrary constant )...
##### Provide Ihe necessary reacion conditions (reagenls and solvents) transtormalion More Inan one sico may b0 necassan_ Synthesis transtormalion are not required. (5 points each; 20 points total)pertorm the indicated reagonts usod mn Ine
Provide Ihe necessary reacion conditions (reagenls and solvents) transtormalion More Inan one sico may b0 necassan_ Synthesis transtormalion are not required. (5 points each; 20 points total) pertorm the indicated reagonts usod mn Ine...
##### Font Paragraph Styles Editing Voice Case Study, Chapter 36, Disorders of Neuromuscular Function Mrs. S. aged...
Font Paragraph Styles Editing Voice Case Study, Chapter 36, Disorders of Neuromuscular Function Mrs. S. aged 35 years, reports numbness, tingling, and weakness in her lower extremities. She is extremely worried because she remembers that her mother had these symptoms prior to being diagnosed with mu...
##### Please answer all 3 correctly. The moral of the story of the Solow growth model is...
please answer all 3 correctly. The moral of the story of the Solow growth model is that: human capital growth does not lead to economic growth. capital accumulation alone cannot lead to sustainable economic growth. capital accumulation is the key to sustained economic growth. technological adva...
##### Vector Question Od) b = 3 two 0 =9 (90 =q (e ~ = of 8 (1 these 7i 3 correct magnitude of a Which the : following correct?
Vector Question Od) b = 3 two 0 =9 (90 =q (e ~ = of 8 (1 these 7i 3 correct magnitude of a Which the : following correct?...
##### Determine the classification of each substance below in its crystalline solid form a5 a molecular, ionoic; metallic, network covalent; or nonbonding atomic solid. (3.5 points) (a) Methanol(b) Cesium(c) Cesium Chloride(d) Argon(e) SiOz(6) LiF(8) ClzFor the crystalline solids in Problem 1, look up their melting point and provide justification for the overall magnitude of the numbers You find based on the structure of their crystals. (3.5 points) Which one is a better electrical conductor: diamo
Determine the classification of each substance below in its crystalline solid form a5 a molecular, ionoic; metallic, network covalent; or nonbonding atomic solid. (3.5 points) (a) Methanol (b) Cesium (c) Cesium Chloride (d) Argon (e) SiOz (6) LiF (8) Clz For the crystalline solids in Problem 1, lo...
##### QUESTION 53 ARDS contributes to hypoperfusion. True False
QUESTION 53 ARDS contributes to hypoperfusion. True False...
##### Using standard heats of formation, calculate the standard enthalpy change for the following reaction 2HBr(g) H2(g)...
Using standard heats of formation, calculate the standard enthalpy change for the following reaction 2HBr(g) H2(g) + Br2() ANSWER kJ Submit Answer Retry Entire Group 2 more group attempts remaining Given the standard enthalpy changes for the following two reactions: (1) Zn(s)+ Cl2(g) ZnCl2(s) AH°...
##### Goal: Create a worksheet that shows accounts receivable activity for a company. Scenario: You have a...
Goal: Create a worksheet that shows accounts receivable activity for a company. Scenario: You have a summer holiday job with Qantas headquarters in Sydney. Assume that shortly into your employment your supervisor asks you to prepare an Excel spreadsheet that breaks down the month's accounts rece...
##### Rer Programu In the ammonia (NH3) molecule of the figure, three hydrogen (H) atoms form an...
rer Programu In the ammonia (NH3) molecule of the figure, three hydrogen (H) atoms form an equilateral triangle, with the center of the triangle at distance - 9.40 x 10-11 m from each hydrogen atom. The nitrogen (N) atom is at the apex of a pyramid, with the three hydrogen atoms forming the base. Th...
##### Sketch the shape and orientation of the following types of orbitals: (a) $p_{x}$, (b) $d_{z^{2}}$,(c) $d_{x^{2}-y^{2}}$.
Sketch the shape and orientation of the following types of orbitals: (a) $p_{x}$, (b) $d_{z^{2}}$,(c) $d_{x^{2}-y^{2}}$....
##### Question 13 (1 point) Let's look at grades again. Let's say that the grades for a...
Question 13 (1 point) Let's look at grades again. Let's say that the grades for a particular test are Normally Distributed with mean=80 and standard deviation = 7. What's the probability that a random student scores a grade between 80 and 90? Op=.3154 p=.842 Op=.4234 Op=.67...
##### Calculate the mass per liter of solid lead (II) phosphate (Ksp = 1.00 x 10-54) that...
Calculate the mass per liter of solid lead (II) phosphate (Ksp = 1.00 x 10-54) that should dissolve in 0.510 M lead (II) nitrate solution....
Hoo HOO Hoped...
##### In a normal distribution,KKof the values in the data set lie at or above the S5th percentile:In a normal distributionof the values in the data set. lie at or below thel 97th percentile
In a normal distribution, KKof the values in the data set lie at or above the S5th percentile: In a normal distribution of the values in the data set. lie at or below thel 97th percentile...
##### Which of the following statements about digestion is false? 29. Which of the following statements about...
Which of the following statements about digestion is false? 29. Which of the following statements about digestion is FALSE? A. Enzymes that carry out the final step in the digestion of carbohydrates are produced by the intestinal epithelial cells. B. Enzymes that carry out the final step in the dige...
##### 1) Consider an RLC series AC circuit having resistance R, capacitance C and inductance L= 0.0300 H connected to an AC source having an amplitude Vo 10.0 The current phasor of this circuit has length of 2.00 and it rotates 100 times per second: The total voltage phasor leads_the current phasor by 309 ,0) Draw separate phasor diagrams corresponding to common value of time. The [st diagram should include two phasors (the current and total voltage). The 2nd diagram should include three phasors (volt
1) Consider an RLC series AC circuit having resistance R, capacitance C and inductance L= 0.0300 H connected to an AC source having an amplitude Vo 10.0 The current phasor of this circuit has length of 2.00 and it rotates 100 times per second: The total voltage phasor leads_the current phasor by 309...
##### [12 points total] For each of the following series Z ak correctly evaluate the limit limk-+o ak and then determine if the Divergence Test applies Or if the Divergence Test is incon- clusive _ Show all steps when computing limits! Note: You are ONLY being asked if the Divergence Test applies![6 points] k2 k_1Value of the Limit: lim k-co k2Circle Correct Answer: Divergence Test Applies Divergence Test Inconclusive
[12 points total] For each of the following series Z ak correctly evaluate the limit limk-+o ak and then determine if the Divergence Test applies Or if the Divergence Test is incon- clusive _ Show all steps when computing limits! Note: You are ONLY being asked if the Divergence Test applies! [6 poin...
##### How do you simplify ((-30a^14 b^8) /( 10a^17 b^-2))^3?
How do you simplify ((-30a^14 b^8) /( 10a^17 b^-2))^3?...
##### How can I report ""^13"C" NMR data?
How can I report ""^13"C" NMR data?...
##### Lullor 10417=SubretDetermine the molar mass of BaOH)glmolu
Lullor 10417= Subret Determine the molar mass of BaOH) glmol u...
##### E) The red protein at left can bind to Ca2+, change conformation and allow other compounds to move across the bilayer. How would you classify this type of receptor?e) Typically, cellular concentration of Cl- is ten times lower than extracellular concentrations. Assume that the red protein at left moves Cl ions_ Predict the overall effect of this pathway, assuming a signaling event occurred at the blue receptor at rightf) A compound called orthovanadate is a type of phosphatase inhibitor. Explain
e) The red protein at left can bind to Ca2+, change conformation and allow other compounds to move across the bilayer. How would you classify this type of receptor? e) Typically, cellular concentration of Cl- is ten times lower than extracellular concentrations. Assume that the red protein at left m...
##### Find each product, if possible. $\left[\begin{array}{rrr} 1 & -2 & -3 \\ 2 & 0 & 1 \end{array}\right]\left[\begin{array}{r} 4 \\ -5 \\ -6 \end{array}\right]$
Find each product, if possible. $\left[\begin{array}{rrr} 1 & -2 & -3 \\ 2 & 0 & 1 \end{array}\right]\left[\begin{array}{r} 4 \\ -5 \\ -6 \end{array}\right]$...


text:
# 15 Puzzle question - trying to understand reasoning here

1. row     A B C D
2. row     E F G H
3. row     I J K L
4. row     M O N

Where there is exactly one inversion (O and N).

I figured out some questions on my own:

a) Can a row move change the order of tiles?

My answer: A row move can change the index of the tile moved only my going left -1 or going right +1. As no other tile moves, the order of tiles overall doesn't change.

b) How many pairs of tiles will have their relative order changed by a column move.

My answer: In a column move we either move the tile down a column, sliding it after the next 3 tiles or up one column, sliding it before the previous 3 tiles. Thus a column move changes the relative order of exactly 3 tiles.

c) What effect does a row move have on the parity of inversions?

My answer: As described in a) the order of tiles doesn't change in a row move, therefore the parity of inversions stays unchanged for a row move.

d) What effect does a column move have on the parity of number of inversions

e) The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles (N and O, say). But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs!

I tried playing around and for d) I claim that: a column move changes the parity of the number of inversions $n$ by either +3 or -3, always flipping the parity $n$ to the opposite side (even $n$ becomes odd, odd $n$ becomes even after a column move.)

The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles

I don't understand this sentence. Why?

EDIT: After reading the problem again, and taking into account they talk about the start state which has an odd number (1) of inversions, it makes more sense now. We need to go to an even number of inversions (0) by making an odd number of column moves, as each column move flips the parity to the oppsite side, see d)

But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs!

Hm, why not? I still dont' get what they mean with So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs.

• The following article may be of help: The Fifteen Puzzle - A New Approach, Mathematics Magazine (Mathematical Association of America), Vol 90, No 1, February 2017, pp 48-57. – user348749 Jul 11 '17 at 10:22
• For your first question: what is the parity of the number of inversions due to an exchange of a single pair of tiles? – Tob Ernack Jul 11 '17 at 10:31
• @TobErnack If I exchange a single pair of tiles, like switching their position, I either create a new inversion if they have been in order before or I "fix" an inversion if they have been inverted before, no? So exchanging a single pair of tile switches the parity of the number of inversions to the opposite. – Max Jul 12 '17 at 5:20
• @TobErnack Oh I get it, if the number of inversions in the start state is odd, we must make an odd number of column moves to get to an even number of inversions. Can you give me a hint how to interpret So after an odd number of column moves, the blank can not pos- sibly be back in the last row, where it belongs!? – Max Jul 12 '17 at 5:26
• Ok, I think I get it now, in the desired state the blank square is in the bottom right in row 4 (where it also resides in the starting position). Each column move changes the row number of the blank square +1 or -1. So after an odd number of moves it can't be in an even row number. Sorry, I think I made the question much harder buy not realizing they were taking about this specific starting position and make observations based on that. I was thinking too far ahead. Maybe I should try to come up with an answer for my own question for future reference later. – Max Jul 12 '17 at 5:38

Theorem. No sequence of moves transforms the board below on the left into the board below on the right.

1. row     A B C D                 A B C D
2. row     E F G H                 E F G H
3. row     I J K L                 I J K L
4. row     M O N                   M N O

a) Can a row move change the order of the tiles?

A row move can change the position of a tile only +1 or -1, but the position of no other tile changes. So a row move can never change the order of tiles.

b) How many pairs of tiles will have their relative order changed by a column move?

A column move changes the order of a tile either -4 or +4. When the tile is moved down, it moves in front of the next 3 tiles. When the tile is moved up, it moves behind the previous 3 tiles. Hence a column move changes the relative order for 3 pairs of tiles.

c) We define an inversion to be a pair of letters L1 and L2 for which L1 precedes L2 in the alphabet, but L1 appears after L2 in the order of the tiles.. What effect does a row move have on the parity of the number of inversions??

As a row move doesn't change the order of tiles, a row move has no effect on the number of inversions, so the parity stays the same.

d) What effect does a column move have on the parity of the number of inversions? Prove your answer.

As a column move changes relative order of 3 tiles, the number of inversions is flipped to the opposite, from even to odd and from odd to even.

e) The previous problem part implies that we must make an odd number of column moves in order to exchange just one pair of tiles (N and O, say). But this is problematic, because each column move also knocks the blank square up or down one row. So after an odd number of column moves, the blank can not possibly be back in the last row, where it belongs! Now we can bundle up all these observations and state an invariant, a property of the puzzle that never changes, no matter how you slide the tiles around.

Lemma: In every configuration reachable from the position shown below, the parity of the number of inversions is different from the parity of the row containing the blank square.

1. row     A B C D
2. row     E F G H
3. row     I J K L
4. row     M O N

Proof of the lemma by induction:

Base case:

After 0 moves, there is exactly 1 inversion (odd) and the row number of the blank square is 4 (even).

Inductive step:

If a row move happens, the row number of the blank square doesn't change, neither does the number of inversions change.

If a column move happens, the parity of the number of inversions is flipped (+3 or -3). Also, the parity of the row number of the blank square is flipped (+1 or -1). Given the start state with odd number of inversions and even row number for the blank square, the parity of those two variables will continue to differ after flipping them both to the opposite side.

e) Prove the theorem that we originally set out to prove.

As per the lemma, the parity of the number of inversions will always be different from the parity of the the row number for the blank square. In the desired end state their parity is equal, which will never be possible given the start state where those two variables have different parity.


text:
# Super hard Euclidean Geometry

The triangle $ABC$ is right angld at $A$. A line through the midpoint $D$ of $BC$ meets $AB$ at $X$ and $AC$ at $Y$. The point $P$ is taken on this line so that $PD$ and $XY$ have the same midpoint $M$. The perpendicular from $P$ to $BC$ meets $BC$ at T.

Prove that $AM$ bisects $\angle TAD$.

I have puzzled over this problem from my book on innovative Euclidean Geometry for months.

The book doesn't have solutions, only hints so you can imagine how frustrating this can be.

I would REALLY appreciate this if someone could solve it or at least make headway on it.

If you would like the hint provided by my book just ask. Thanks.

-
Oh man! I posted the figure thinking it would be useful.;) –  Inceptio Apr 13 '13 at 8:26
don't worry, (thank goodness the book had a picture in it or I would have got nowhere). :-) –  John Marty Apr 13 '13 at 8:29
We would help you, anyway.:) –  Inceptio Apr 13 '13 at 8:31
Using coordinates, I find that $\angle TAM = \angle DAM = \angle DXA - \angle DBA$. Now to find an elegant proof of this fact ... –  Blue Apr 13 '13 at 9:22
Do you mean $DBA-DXA$, instead of the other way around? It looks a lot like, in general, $DBA>DXA$, namely. –  HSN Apr 13 '13 at 9:32

## 1 Answer

\begin{align*} \angle TDM &= \angle YDC \\ &= \angle DYA - \angle DCY \text{ (exterior angle = sum of opposite interior angles in triangle }DCY) \\ &= \angle MAY - \angle DCY \text{ ($M$ is centre of circle through $XAY$, so $\angle MYA = \angle MAY$)} \\ &= \angle MAY - \angle DAY \text{ ($D$ is centre of circle through $BAC$, so $\angle DCY = \angle DAY$)} \\ &= \angle MAD \end{align*}

But $\angle TDM = \angle MTD$ (because $M$ is centre of circle through $PTD$, so $MD = MT$). Thus $\angle MTD = \angle MAD$, and so $MTAD$ is a cyclic quadrilateral. And $MD = MT$. Hence $\angle TAM = \angle MAD$.

QED

-
Very Beautiful; thank you SO much. It's amazing how many clever little deductions you have to put together to reach such a result. Thanks again!!! –  John Marty Apr 13 '13 at 10:53


text:
## Zero-cycles and K-theory on singular varieties.(English)Zbl 0635.14007

Algebraic geometry, Proc. Summer. Res. Inst., Brunswick/Maine 1985, part. 2, Proc. Symp. Pure Math. 46, 451-462 (1987).
[For the entire collection see Zbl 0626.00011.]
A theorem of A. Rojtman [Ann. Math., II. Ser. 111, 553-569 (1980; Zbl 0504.14006)] says that for a smooth projective variety X over an algebraically closed field, the torsion subgroup of the group of zero- cycles modulo rational equivalence, $$CH_ 0(X)_{tors}$$, is naturally isomorphic to the torsion subgroup of the Albanese variety of X, $$Alb(X)_{tors}$$. This result was generalized by the author [Am. J. Math. 107, 737-757 (1985; Zbl 0579.14007)] for the case of a projective variety X, smooth in codimension one (modulo p-torsion in characteristic $$p,$$ $$p>0)$$, where $$CH_ 0(X)_{tors}$$ had to be replaced by the torsion part of $$CH_ 0(X,X_{\sin g})$$, the quotient of the free abelian group on the smooth points of X and the subgroup generated by cycles of the form $$i_{C\quad *}((f))$$ with C a closed reduced, irreducible curve on X, not meeting $$X_{\sin g}$$, and f a rational function on C.
In the general case one is led to define a relative Chow group $$CH_ 0(X,Y)$$, where Y is closed in X and contains $$X_{\sin g}$$. The definition was given in another article and is not repeated here. Now the main result of the paper under review is that for an affine variety X over an algebraically closed field $$CH_ 0(X,Y)$$ is torsion free (modulo p-torsion in characteristic $$p>0).$$
As a corollary one obtains an injective map $$CH_ 0(X,Y)\to K_ 0(X)$$, whose image is isomorphic to the subgroup of $$K_ 0$$(X) generated by the residue fields of the smooth points of X.
Reviewer: W.W.J.Hulsbergen

### MSC:

 14C15 (Equivariant) Chow groups and rings; motives 14B05 Singularities in algebraic geometry 14C35 Applications of methods of algebraic $$K$$-theory in algebraic geometry 14C25 Algebraic cycles

### Citations:

Zbl 0626.00011; Zbl 0504.14006; Zbl 0579.14007


text:
Today we aim to take a closer look at float, the ubiquitous data type we use whenever we’re forced to leave the discrete confines of integers. While a very flexible data type, it is not without its flaws, and we will explore a few of them further down.

We’ll start with a short crash course into the representation scheme of the floating point representation and then look at two real-world (but made up) scenarios any engineer may find himself or herself in one day.

Bear in mind this is not a definitive guide nor an in-depth analysis. Its only purpose is to open the door towards more complex topics.

## A primer into the floating point representation

The IEEE-754 standard defines a representation that has a wider range (domain) than integers, but can also store and operate on rational numbers.

The representation splits the word into three parts:

• the sign bit $$s$$
• the exponent $$e$$, stored internally as a $$b_e$$-bit unsigned integer
• the significand or coefficient $$c$$, stored internally as a $$b_c$$-bit unsigned integer

Depending on the word size, the coefficient and exponent may use various lengths; for example, $$32$$-bit floating point numbers have $$b_c=23$$ and $$b_e=8$$.

The mapping from state to value is:

$f(s, e, c) = (-1)^s \times 2^{e-2^{b_e-1}+1} \times (1 + c \times 2^{-b_c}) \\ \forall e \in \{ 1, 2, \dots 2^{b_e}-2 \} \text{, } c \in \{ 0, 1, 2, \dots 2^{b_c}-1 \}$

As you can guess, the term $$1 + c \times 2^{-b_c}$$ in the above formula is simply the binary number $$\overline{1.c_{22} c_{21} c_{20} … c_{0}}$$, where $$c_i$$ is the $$i$$-th bit of the coefficient $$c$$; this term has the domain $$[1.0, 2.0)$$.

There are two special cases:

• $$e = 0$$ codes subnormal numbers, values between $$\pm 0$$ and the smallest possible normal numbers $$\pm 2^{-2^{b_e-1}+2}$$
• $$e = 2^{b_e}-1$$ codes the values $$\pm \infty$$ and $$NaN$$

### The underlying difference between ints and floats

One of the most common misconceptions is that, for a given word size, the floating point representation has better precision than the integer representation. Overall both are coded into the same number of bits.

But how is this possible, since a float can store values as little as $$0.00001$$ and as large as $$10^{25}$$?

Let’s look at the distribution of values over a large domain:

We can see that, while the representable integer values are uniformly distributed across the domain, the representable floating point values are not.

Looking at the map $$f$$ it is obvious why. For any exponent $$e_k$$, the interval of representable values has a uniform distribution; in other words, for $$32$$-bit floats the distance between any two successive values is equal to $$2^{e_k-127} \times 2^{-23}=2^{e_k-150}$$.

However, once the coefficient is saturated, the successor of this value will take the exponent $$e=e_k+1$$ and coefficient $$c=0$$. The distance between all subsequent values will now be $$2^{e_k+1-150-23}=2^{e_k-149}$$.

In conclusion, the distance between representable values doubles every time the coefficient saturates (that is, every $$2^{b_c}$$ values). As a result, floats can have better precision and better range than integers, but it can’t do both at the same time.

Precision-wise, $$32$$-bit floats will outperform ints only between $$0$$ and $$10^7$$, which is less than $$1\%$$ of the $$32$$-bit integer domain.

### Representation error

Since we are mapping a continuous domain ($$\Bbb{R}$$) to the discrete domain of representable floating point numbers, it follows that there will be some sort of approximation involved. While the IEEE-754 standard specifies multiple rounding modes, the most common is round-to-nearest, which simply maps the real value to the nearest representable value.

In order to better understand the process, we must define two kinds of errors. The absolute error

$\Delta x = |\hat{x} - x|$

is simply the distance from the real (or true) value $$\hat{x}$$ to the representable value $$x$$. Hence, in round-to-nearest the representation function will output the $$x$$ for which $$\Delta x$$ is minimal.

But the absolute error is not a fitting metric for all scenarios; after all, it is much worse to be off by $$0.5m$$ when we’re measuring $$2m$$ than when we are measuring $$2km$$. Thus, the relative error is defined as

$\frac{\Delta x}{|\hat{x}|}$

and it measures how large the error is in comparison to the value being stored.

In order to see how $$\hat{x}$$ maps to $$x$$ and what the errors are, let’s write a positive $$\hat{x} \gt 0$$ in a friendlier form:

\begin{align} \hat{x} & = 2^{\lfloor log_2 \hat{x} \rfloor} \times \hat{x} \times 2^{- \lfloor log_2 \hat{x} \rfloor} \\ & = 2^{\lfloor log_2 \hat{x} \rfloor} \times (1 + \hat{x} \times 2^{- \lfloor log_2 \hat{x} \rfloor} - 1) \\ & = 2^{\lfloor log_2 \hat{x} \rfloor} \times \left ( 1 + \left (2^{23} \times ( \hat{x} \times 2^{- \lfloor log_2 \hat{x} \rfloor} - 1) \right ) \times 2^{-23} \right ) \end{align}

NOTE: $$\lfloor log_2 x \rfloor$$ was chosen because $$x \times 2^{-\lfloor log_2 x \rfloor} \in [1, 2)$$.

It is now easy to identify the integer exponent and coefficient of a $$32$$-bit floating point representation:

\begin{align} e & = \lfloor log_2 \hat{x} \rfloor + 127 \\ c & = \lfloor 2^{23} \times (\hat{x} \times 2^{- \lfloor log_2 \hat{x} \rfloor} - 1) \rceil \end{align}

So then the map will be

\begin{align} x & = 2^{e -127} \times (1 + c \times 2^{-23}) \\ & = 2^{\lfloor log_2 \hat{x} \rfloor} \times \left ( 1 + \lfloor 2^{23} \times (\hat{x} \times 2^{- \lfloor log_2 \hat{x} \rfloor} - 1) \rceil \times 2^{-23} \right) \\ & = 2^{\lfloor log_2 \hat{x} \rfloor} \times \left ( 1 + \lfloor \hat{x} \times 2^{23- \lfloor log_2 \hat{x} \rfloor} - 2^{23} \rceil \times 2^{-23} \right) \\ & = 2^{\lfloor log_2 \hat{x} \rfloor -23} \times \left \lfloor \hat{x} \times 2^{23- \lfloor log_2 \hat{x} \rfloor} \right \rceil \end{align}

and the representation absolute error

\begin{align} \Delta x & = |\hat{x} -x| \\ & = \left | \hat{x} - 2^{\lfloor log_2 \hat{x} \rfloor - 23} \times \left \lfloor \hat{x} \times 2^{23 - \lfloor log_2 \hat{x} \rfloor} \right \rceil \right | \\ & = 2^{\lfloor log_2 \hat{x} \rfloor - 23} \times \left ( \left | \hat{x} \times 2^{23 - \lfloor log_2 \hat{x} \rfloor} - \left \lfloor \hat{x} \times 2^{23 - \lfloor log_2 \hat{x} \rfloor} \right \rceil \right | \right ) \end{align}

Since

$| k - \lfloor k \rceil | \le 2^{-1} \text{, } \forall k \in \Bbb{R}\_{+}$

we can find the non-optimal (but good enough) representation absolute error upper bound

$\Delta x \le 2^{\lfloor log_2 \hat{x} \rfloor - 24} \le \hat{x} \times 2^{-24}$

and the representation relative error upper bound

$\frac{\Delta x}{|\hat{x}|} \le 2^{-24} \approx 6e-8$

which is also called the machine epsilon.

Thus, we can observe that the floating point representation has an absolute error fairly proportional to the value (which we could have guessed from the previous distribution plot), but more importantly has a fairly constant relative error.

In other words, any $$32$$-bit floating point value can’t be more than $$0.000006 \%$$ off from the true value.

### Floating point decimal precision

An important observation is that the floating point representation is a binary representation. As a result it guarantees storage of $$b_c$$ significant binary digits, which do not necessarily correlate to decimal digits.

For example:

• the number $$0.0078125$$ is perfectly representable (i.e. has zero representation error), since it can be written as $$2^{-7} \times 1.0$$
• the number $$0.1$$ is represented in $$32$$-bit floats as $$0.10000000149011612 \dots$$, since it cannot be written as a finite sum of powers of two

In conclusion, it is not a good idea to gauge the representation error by the number of significant decimal digits.

NOTE: The latest revision of the IEEE-754 standard actually defines new decimal floating point formats. Since hardware support for them is virtually non-existent we can safely ignore them for the time being.

## The problem of docking spacecrafts

Let’s say we’re writing the guidance software for a spacecraft that is to leave Earth orbit, inject into a Martian orbit and dock with another craft that is already there.

Since we’re dealing with more than one planet, we build a heliocentric model of our solar system, at the heart of which is the orbital prediction function $$O_p$$, which outputs the craft position relative to the primary body (i.e. Earth, Mars, Sun) given a set of orbital parameters and a time value.

Then, given the Martian orbital parameters $$\gamma_m$$, target craft’s orbital parameters $$\gamma_t$$, our craft’s primary body orbital parameters $$\gamma_{pri}$$, and our craft’s orbital parameters $$\gamma_s$$, we have the absolute position of the two crafts at some point in time $$t$$:

$p_t (t) = O_p(\gamma_m, t) + O_p(\gamma_t, t) \\ p_s (t) = O_p(\gamma_{pri}, t) + O_p(\gamma_s, t)$

Since docking is a fiddly operation, we want to compute ahead of time the moment of rendezvous, or the time when the distance between two spacecrafts is minimal. We define the distance between the two crafts:

$d(t) = \lVert p_t(t) - p_s(t) \rVert$

for which we need to find

$t_{r} = \arg \min_{t} d(t)$

for $$\gamma_{pri} = \gamma_m$$, which we compute numerically by evaluating $$d(t)$$ for sufficiently many $$t$$.

Our code might look like the following:

def Op(orbit_params, t):
# assume perfect implementation

def get_target_abs_position(t):
return Op(mars_orbit_params, t) + Op(target_orbit_params, t)

def get_spacecraft_abs_position(pri_orbit_params, t):
return Op(pri_orbit_params, t) + Op(spacecraft_orbit_params, t)

def get_abs_distance(pri_orbit_params, t):
return np.norm(get_target_abs_position(t)
- get_spacecraft_abs_position(pri_orbit_params, t))

def get_rendezvous_time():
d_min = +inf
for t in np.linspace(now(), now() + 2days, 1000000):
d = get_abs_distance(mars_orbit_params, t)
if d < d_min:
d_min = d
t_r = t
return t_r, d_min

Then the moment comes when we perform the final burn, we compute $$\gamma_s$$, make the call to get_rendezvous_time and observe that we will perfectly intercept the target spacecraft. We take out the champagne and celebrate!

Then $$t_r$$ comes and goes, and there’s no sign of the other craft.

### Loss of significance

What happened? We nervously start debugging the code, looking for the flaw that just lost us a few billion dollars.

It can’t be Op, we’ve used this code to compute sattelite positions for some time now.

It can’t be get_spacecraft_abs_position or get_target_abs_position, we’ve used them to compute communication round-trip-time, and it was always on point.

It can’t be the floating point representation, since we know it behaves well due to its very low relative error. Or does it?

The truth is all the code is correct, but we just suffered a case of loss of significance under subtraction, or (very fittingly) catastrophic cancellation.

The issue was our misunderstanding of the low relative error of the floating point representation. While individually each operation is safe in relation to it’s output, it may not be in relation to the target quantity.

Let’s look to a unidimensional scenario of our algorithm for some $$t$$. The table contains the actual result of the operation in $$32$$-bit floating point representation, the mathematical result of the operation (applied on operators), the relative error of the operation and the true result (evaluated in a perfect representation).

$\begin{array}{|c|c|c|c|c|} \hline \text{Operation} & \text{Operation} & \text{Mathematical} & \text{Relative} & \text{True} \\ x & \text{result }(x) & \text{result } (x^*) & \text{error} & \text {result } \hat{x} \\ \hline O_p(\gamma_m, t) & 227900000km & 227900000km & 0.0 & 227900000km \\ \hline O_p(\gamma_t, t) & 12334.595703km & 12334.596km & <10^{-7} & 12334.596km \\ \hline O_p(\gamma_s, t) & 12334.318359km & 12334.318km & <10^{-7} & 12334.318km \\ \hline p_t(t) & 227912336km & 227912334.595703km & <10^{-8} & 227912334.596km \\ \hline p_s(t) & 227912336km & 227912334.318359km & <10^{-8} & 227912334.318km \\ \hline d(t) & 0.0km & 0.0km & \text{N/A } (0) & 0.278km \\ \hline \end{array}$

We managed to compute the positions of the target $$O_p(\gamma_t, t)$$ and the spacecraft $$O_p(\gamma_s, t)$$ with absolute errors of less than a meter. However, the problem rears its head when we compute the absolute positions $$p_t(t)$$ and $$p_s(t)$$; while they have very low relative errors, the absolute errors are comparable to the quantity we are measuring (distance between crafts). Thus, while the evaluation of $$d$$ has zero error by itself, the error compounded in the operands has a destructive effect on our computation.

Obviously, any of the two computed distances would be perfectly fine if we were evaluating radio round-trip-time $$rtt = \frac{p_s(t)}{c}$$, since $$rtt$$ is the measured quantity and the relative error is computed with respect to it. In fact even $$d(t)$$ may have had a perfectly acceptable error had our spacecraft been orbiting Earth, since our focus would not have been docking, but some other metric at a planetary scale.

To summarize, our problem is that we are asking for too great a precision for the domain we are operating on.

In order to fix such problems, we always look at the mathematical model and find an equivalent form in which the discrepancy between the operand domains and measurement domain is reasonable. If we take the function $$d$$ that we minimize, and specialize it for $$\gamma_{pri} = \gamma_m$$ we get:

\begin{align} d(t) & = \lVert p_t(t) - p_s(t) \rVert \\ & = \lVert O_p(\gamma_m, t) + O_p(\gamma_t, t) - O_p(\gamma_{pri}, t) - O_p(\gamma_s, t) \rVert \\ & = \lVert O_p(\gamma_t, t) - O_p(\gamma_s, t) \rVert \end{align}

which is perfectly intuitive, since there is no need to compute the absolute positions of the crafts given they orbit the same body. In consequence, we now get a numerical result of $$d = 0.277344km$$, which is much closer to the true value of $$\hat{d} = 0.278km$$.

### Obfuscation by good coding practice

Not all scenarios are as nicely laid out for us as this tought experiment, and it is sometimes difficult to identify potential sources of loss of significance.

Mathematical models are often expressed in a form that is easiest for humans to comprehend, but which can otherwise be numerically unstable under finite representations.

Moreover, when working with implementations of such models, it is very tempting and often encouraged to use existing functionality (like the functions get_*_abs_position in our examples) instead of implementing a specialization for our use case.

But above all, it is not necessary to be a rocket scientist to feel the effects of numerical errors, as we will see in the next sections.

## The problem of the power meter

We’ve obviously been fired from our job as a rocket scientist, and we’re now demoted to writing firmware for power meters.

Our taks is to measure a household’s power consumption over a large period of time. In order to achieve this, we have a power transducer that measures the instantaneous power consumption and outputs a DC voltage in the $$0-5V$$ range, corresponding to the measurement domain of $$0-5kW$$. The DC voltage is translated by an ADC to a floating point number equal to the input voltage.

Since it is a trivial problem, we implement a trivial solution:

def power_meter_main_loop():
while True:
usage_kwh = usage / (reading_freq_hz * 3600)
display(usage_kwh)
save_usage_to_storage(usage)

We choose a sampling frequency of $$10Hz$$ for our device and, at each iteration, we read a value from the ADC and accumulate it to usage. Since usage is expressed in $$kW \cdot ds$$ (kilowatt-decisecond), we need to convert it to $$kW \cdot h$$ and display it on the power meter’s LCD. We also save our usage to a non-volatile memory so we can retrieve it in case of a power outage.

The power meter gets released into production, installed in many homes and everything looks great. We take out the champagne and celebrate!

Then one year later, the company stops making any money. Crap…

### Vanishing values

Weirdly enough, all power meters seem to have stopped at $$3728.27 \text{ } kW \cdot h$$, and all tests on the hardware indicate that it is working properly. It then must be a software bug.

Since the $$kW \cdot h$$ is only used for displaying the value, we compute the underlying accumulator value of $$134217728.0 \text{ } kW \cdot ds$$.

As it happens, this value is a power of two, $$2^{27}$$ to be precise. The question is now, why is this an upper bound for our accumulator?

Let’s consider two representable, positive, $$32$$-bit floating point values

$x_1 = 2^{e_1-127} (1 + 2^{-23}c_1) \\ x_2 = 2^{e_2-127} (1 + 2^{-23}c_2)$

where $$e_1, e_2, c_1, c_2 \in \Bbb{N} \text{, } c_1, c_2 \lt 2^{23}$$.

Let’s try to find the representation $$y = 2^{e_y-127} (1 + 2^{-23}c_y)$$ of $$x_1+x_2$$.

If $$x_1 \ge x_2$$ we can compute the true value as

\begin{align} \hat{y} & = x_1 + x_2 \\ & = 2^{e_1-127} (1 + 2^{-23}c_1) + 2^{e_2-127} (1 + 2^{-23}c_2) \\ & = 2^{e_1-127} \left ( 1 + 2^{-23}c_1 + 2^{e_2-e_1} (1 + 2^{-23}c_2) \right ) \\ & = 2^{e_1-127} \left ( 1 + 2^{-23}(c_1 + 2^{e_2-e_1}c_2 + 2^{23+e_2-e_1}) \right ) \end{align}

But since $$y$$ must also be representable, then it follows that $$c_y \in \Bbb{N}$$, so then

$c_y = \lfloor c_1 + 2^{e_2-e_1}c_2 + 2^{23+e_2-e_1} \rceil$

Interestingly enough, if $$e2-e1 \le -25$$, then

$2^{e_2-e_1}c_2 \lt 2^{-2} \\ 2^{23+e_2-e_1} \le 2^{-2}$

so it follows that

$2^{e_2-e_1}c_2 + 2^{23+e_2-e_1} \lt 2^{-1} \\ \lfloor 2^{e_2-e_1}c_2 + 2^{23+e_2-e_1} \rceil = 0$

Since $$c_1 \in \Bbb{N}$$ it follows that $$c_y = c_1$$, and since $$e_y = e_1$$ then $$y = x_1$$.

We can conclude that if there is a difference of more than 24 between the exponents of two values, then their sum will always evaluate to the larger of them. Or, if we translate to decimal, if there is a difference of about seven or more orders of magnitude between the two operands, the sum will evaluate to the larger of them.

Now let’s see what happened in our scenario; we have our accumulator $$2^{27}$$ with $$e_a = 27+127=154$$, and the maximum value of the sample $$5.0$$ with $$e_s = \lfloor \log_2 5 \rfloor + 127 = 2+127=129$$.

Since $$e_a - e_s \ge 25$$ we can conclude that it would be technically impossible for the power meter to overcome this value, since any possible summation would simply evaluate to the accumulator value.

### Manifestation of the same underlying issue

Intrinsically we have the same issue as with the spacecraft example, with the distinction that instead of the result having a much smaller domain than both operands, one of the operands has a much smaller domain the the other and the result.

In fact, the above scenario is an extreme manifestation of a loss of precision due to large domain discrepancies (where $$\frac{x_2}{x_1}$$ approaches machine epsilon). In actuality, the power meter’s performance started slowly degrading the moment it was turned on.

If we look at the sum’s representation, we see that

\begin{align} c_y & = \lfloor c_1 + 2^{e_2-e_1}c_2 + 2^{23+e_2-e_1} \rceil \\ & = c1 + \lfloor 2^{e_2-e_1}(c_2 + 2^{23}) \rceil \end{align}

Thus, the actual representable value we add to the accumulator during each summation is

$x_2' = 2^{e1-104} \lfloor 2^{e_2-e_1}(c_2 + 2^{23}) \rceil$

Then, the error relative to $$x_2$$ is

\begin{align} \frac{|x_2 - x_2'|}{|x_2|} & = \left | 1 - \frac{x_2'}{x_2} \right | \\ & = \left | 1 - \frac{2^{e1-104} \lfloor 2^{e_2-e_1}(c_2 + 2^{23}) \rceil}{2^{e_2-127} (1 + 2^{-23}c_2)} \right | \\ & = \left | 1 - \frac{2^{e1-104} \lfloor 2^{e_2-e_1}(c_2 + 2^{23}) \rceil}{2^{e1-104} \times 2^{e_2-e_1}(c_2 + 2^{23})} \right | \\ & = \left | 1 - \frac{\lfloor 2^{e_2-e_1}(c_2 + 2^{23}) \rceil}{2^{e_2-e_1}(c_2 + 2^{23})} \right | \end{align}

We can parametrize for $$\Delta e=e_1-e_2$$:

$\frac{|x_2 - x_2'|}{|x_2|} = \left | 1 - \frac{\lfloor 2^{-\Delta e}(c_2 + 2^{23}) \rceil}{2^{-\Delta e}(c_2 + 2^{23})} \right |$

and compute the mean error relative to $$x_2$$ for any $$\Delta e$$ as

$M_e(\Delta e) = \frac{1}{2^{23}} \sum_{c2 = 0}^{2^{23}-1} \left ( \left | 1 - \frac{\lfloor 2^{-\Delta e}(c_2 + 2^{23}) \rceil}{2^{-\Delta e}(c_2 + 2^{23})} \right | \right )$

Thus the value of $$M_e(\Delta e)$$ is the mean relative error of the information we are trying to inject into the accumulator for an exponent difference of $$\Delta e$$. Or in the general case, the mean error of the floating point addition relative to the smaller operand, for an exponent difference of $$\Delta e$$.

While the above can be computed analitically, we are interested only in its graph:

We can clearly see the behaviour we determined in the previous section, where all information is lost for $$\Delta e \ge 25$$.

But more relevant is the relationship between the above relative error and the accumulator iteration:

As we can see, the error relative to $$x_2$$ increases somewhat linearly with the iteration number, until $$\Delta e = 25$$ is reached. As a result, before the failure, the power meter functioned for more than $$80\%$$ of its life with an unacceptably high error.

### Fixes

A more fitting representation for an accumulator is the integer representation, since it has a constant absolute representation error and zero error over addition, subtraction and multiplication.

If for some reason there is a hard constraint for a floating point representation, then there are some solution’s like Kahan’s algorithm that mitigates this error.

## Epilogue

We’ve barely scratched the surface of the types of issues we can encounter when performing arithmetic on finite representations - there is actually a whole field of mathematics called numerical analysis that deals with this.

But what I hope we can take from this text is the intuition of where the important information is coded in our algorithm and how it is handled by the representation. We may not always have the time to find the optimal solution, nor to perform an exhaustive analysis on our model, but what is important is that we do not mess up too badly.


text:
# How to mentally flip a coin?

If you've ever played rock-paper-scissors, and you are reading this on math.stackexchange, you probably know that always playing $1$ of the $3$ choices at random (more precisely: uniformly at random and independently of previous choices) guarantees even chances of victory against any opponent.

But "playing at random" is harder than it looks, particularly if you have no tools - from old-fashioned dice to tech accessing thermal noise. In fact, I've seen a little piece of code that marginally, but consistently over time, beats most humans at rock-paper-scissors simply by looking at biases in how they've been playing so far, and predicting future throws accordingly. For example, humans tend to to play long sequences of identical throws with the "wrong" frequency.

I was wondering if anyone knows good ways to produce reasonably random bits without tools; say, enough to compete with even or as-even-as possible odds against a computer trying to predict one's choices. I realize "good" and "reasonably" (and even "tools") is a bit fuzzy, but I'm sure folks will understand the spirit of the question... I don't want to simulate a Mersenne Twister in my head (though a pseudorandom generator with a reasonable balance of randomness and simplicity would definitely be a possibility), nor use the painful method a friend of mine suggested: pull a random hair from one's head, and check if it's white (for most people it's a biased toss, but as long as one's hair is salt-and-pepper one can trade hair for fairness in the toss).

Buried in the comments below, there's a link to a web page allowing you to test any such scheme!

• Your middle paragraph is throwing me off. Are you trying to win at rock-paper-scissors, or are you trying to produce numbers out of your head uniformly at random and independently? If the latter—you might be able to do so, but you won't be able to prove it! :) – Wildcard Jan 12 '17 at 4:35
• @Razin the question is this: suppose I ask you to come up with a sequence of heads and tails that looks random, enough to ideally fool a computer. But you are not allowed to check your own computer, use dice and whatever. Just use your head. Can you do it? It's harder than it looks. – Anonymous Jan 12 '17 at 4:56
• Just wait 'till you're as old as I am and short-term memory is totally shot, then each thought that pops to mind is random and...what was the question again? – BruceET Jan 12 '17 at 7:55
• What I would suggest is to choose a sequence and a number $n$ at random (to the best of your ability). Then the bit produced is each number in the sequence module 2 until you reach the $n$th number. Rinse, lather, repeat. – Noah May Jan 19 '17 at 5:34
• You could precompute a long sequence of random numbers, then memorize them. Each time you need a random number use the next one in the sequence. People are able to memorize tens of thousands of digits of pi and e. You could do it once then be set for life – Nick Alger Jan 20 '17 at 7:33

1. I have freckles. I just encircle with thumb and forefinger a “random" portion of my arm, count the freckles, and take the parity. It takes about 3-5 seconds. I guess that someone who is fairly hairy could do the same counting hair.

2. Talking of counting hair, I take a small lock of my hair (I have long hair), and then try to split it as evenly as possible in two “half locks”, each with half the hair. I repeat the same process on one of the half locks, and then on one of the quarter locks, until I’m left with a single hair. The parity of the number of halvings is my random bit. It takes me about 5-10 seconds to produce it. I’ve found this to be quicker than the more obvious method of just counting the hairs and taking their parity.

3. I play a really fast paced word association game: I think of a word, the very first word associated to it, the second, third and fourth (using my hand’s fingers to count the five words helps). My random bit is the order of the third last letters of the last two words. It’s easier to do than to say, it takes no more than $3$ seconds.

4. This is somewhat general, though I guess everyone should make it specific to one’s interests in life. I let my mind wander and pick $3$ artists (musicians, bookwriters, painters, etc.) and think of how many of the pieces of each I’ve heard/read/seen. I add the numbers and take the parity. A programmer friend of mine says for him it works really well with examples of some obscure software categories I can’t quite remember. I guess a gourmet could use types of food: how many vegetable soups. omelettes, and bottles of red wine he’s had in the last two weeks.

5. I pick a number that strikes my fancy, and play the $3n+1$ game (halve it if even or triple it and add $1$ if odd, and then repeat) for $20$ steps, using the (parity of) the second last digit. I've not tried this extensively enough to detect any bias, which instead affects the last digit, but I guess one could correct it with the method the OP suggests for white hair counting. This is slowish (about $20-30$ seconds), but still a bit faster than the congruential generator another poster suggested, at least for me.

6. If you are good at remembering phone numbers of people, their least significant digits are a good source of randomness against people who know relatively little of your contacts. You can always scramble them a little, like reversing them and skipping every other digit.

• Wow, 6 answers :) And some of them are quite good, I have to say; the phone numbers one would work very well for me, for example (on koaning.io/human-entropy.html, taking the last 4 digits, discarding any that is 8 or 9, and using the the 3 bits of every other, I generated without much effort about 1 bit/second, and the result was undistinguishable from that of a pseudorandom generator). The 3n+1, on the other hand, seems to works terribly (I tried starting with 123); there's a lot of correlation between consecutive "second last" digits. – Anonymous Mar 2 '17 at 10:17
• It was not an easy choice, because I got a number of really good answers, but after thinking a lot about it, I decided to award the bounty to this one! – Anonymous Mar 2 '17 at 19:01

This is one strategy that seems to work for me (36). I talk to myself (11). And for every sentence, I just count the letters in my head (46). Then, I can use the least significant bit, or maybe two, as "random" bits (50). It's a game I used to play as a pasttime for its own sake ... (43) and if I add the numbers wrong, well, it doesn't really seem to affect the randomness (76)! The numbers in parentheses are, if you haven't guessed, the letter counts of each sentence (71).

• I don't really mind the downvote (in fact, I'd rather not have my answer as the top scoring one) but ... would anyone who downvoted care to explain why? Do you think it's an answer that does not work? Do you think it's wrong for me to provide an answer to my own question? – Anonymous Jan 23 '17 at 21:13

You could precompute a long sequence of random numbers, then memorize them. Each time you need a random number use the next one in the sequence.

People are able to memorize tens of thousands of digits of $\pi$ and $e$. You could do it once then be set for life.

(This is a conversion of a comment to an answer)

Think of a five digit number. Add its digits. If it produces an even number, say it counts for heads. If it produces an odd number, say it counts for tails.

I base this on the fact that while there might be some bias on the numbers you would chose on a smaller scale (of less digits), five-or if you can/or the situation allows, even more digits-provides a sufficient "random hedge". i.e-your brain will not pre-compute the result (even or odd).

It also looks much faster than other methods proposed, particularly if you are involved in some form of fast paced game.

• One problem is that mentally odd digits seem more "random" to many people and may be overrepresented. Then odd digit sums would also be overrepresented. Maybe take the congruence class mod 3 of the digit sum. That is unbiased with respect to even vs odd digit choice and still easy enough to do in your head. (Add the digits; if the result has multiple digits add them; when you get to the range 1..9 take congruence mod 3.) – q.t.f. Mar 2 '17 at 10:14

a pseudorandom generator with a reasonable balance of randomness and simplicity would definitely be a possibility

Well, then let's pick a small multiplicative linear congruential generator.

Let $m=251$ $a=33$

Starting from a initial random (well..) value x[0] in the range $1 \cdots 250$ in each iteration we do mentally the following (pseudocode):

x[n] := x[n-1] * 33 ;
x[n] := x[n] % 251 ;
y[n] := x[n] % 2 ;

Ok, the second statement is not very easy to do mentally, but it can be slightly easied by substracting, for example:

while ( x[n] >= 251) {
if(x[n] >= 2008) x[n] -= 2008;
else if(x[n] >= 1004) x[n] -= 1004;
else if(x[n] >= 502) x[n] -= 502;
else x[n] -= 251;
}

Possible ideas:

1. Look around you and identify an object that stands out to you (not the sky, clouds, etc.). Then, count the letters in one word (or words) you could use to describe that object. Based on the letters in that word (odd or even; 0,1,or 2 mod 3, etc) you can make your random decision. (I wasn't able to find the percentage of English words with an odd or even number of letters, but this should be somewhat random.)

2. Clear your throat. If the number of sounds you make is odd, flip heads. If the number of sounds you make is even, flip heads. The logic is that (at least for me) I clear my throat in two "coughs" and three "coughs" about half the time each. (I rarely clear my throat in one "cough" or in four "coughs".)

3. Jump (or even make a small hop) into the air. As you do, start counting integers from 1 as fast as possible inside your head. As soon as you land, stop counting. Then you can take the integer you ended on and take that mod 2, mod 3 etc. for whatever purpose you wish.

Hope this helped :)

• I like 1! Even if it does produce some bias in the number of letters being odd or even, one can always erase that with a few extra tosses. Thanks! – Anonymous Feb 26 '17 at 0:15
• Yes, that is true. The throat-clearing trick and the jump&count idea are probably even less random (I tried the jumping trick a few times and I was never able to get past 10 - but that may be just because I am no athlete to say the least). Glad you liked it! – Michael Wang Feb 26 '17 at 5:49

What I would suggest is to choose a sequence and a number $n$ at random (to the best of your ability). Then the bits produced is each number in the sequence module 2 until you reach the $n$th number. Rinse, lather, repeat. Then append the sequences together.

For example, we could start with the number of partitions (A000041) and $n=6$.

1, 2, 3, 5, 7, 11
1, 0, 1, 1, 1, 1  (mod 2)

Then move on to the Thue-Morse Sequence (A010060) with $n=18$.

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0 (already mod 2)

And so on.

Of course you should use relatively small integers for $n$ - say between 1 and 25 - and make sure to avoid or at least use sparingly "useless" sequences such as the even numbers (A005843 just in case you needed it).

• I don't see how to produce this sequence without using resources comparable to that needed to simulate a PRNG :). Also, a large part of this problem is probably the need to extract pure random bits from an entropic sequence. The partition function for instance has obvious biases in residue classes. – Erick Wong Jan 19 '17 at 20:40
• @Erik Wong, Look at Anonymous's first reply comment to Razin. As for the biases in sequences, I would assume that the majority of them would balance out. – Noah May Jan 19 '17 at 21:52
• I've looked at Anonymous's comments. It explicitly says that you are not allowed to check a computer, just mental calculation. How do you propose to implement this suggestion using just your head? If it requires precomputation and looking up web pages, I'm not sure how this works better than just browsing a web site that generates random bits. Anonymous requested making this into an answer, so I will refrain from downvoting. – Erick Wong Jan 20 '17 at 0:40
• Think of a 'random' color (does not need to be too random).
• Look in a 'random' direction (again ,, ,, ).
• Choose the first object that you notice with that color.
• Close your left eye, and open you right eye.
• Now open you left eye and close your right eye.

You have a slightly different perspective with both eyes. If the object is better visible with your right eye (covers a slightly larger solid angle) the answer is HEAD. Otherwise the answer is TAIL.

• I've tried this, but there seems to be a small but definite bias. Apparently I tend to centre my view on my left eye. However, one can correct this in the usual way (toss two coins, if HH or TT repeat, if HT declare H, if TH declare T), and it seems a fun and reasonably effective way to do it (though of course you need to be immersed in some scenery). Thanks! – Anonymous Feb 24 '17 at 14:08

If you can use the environment - that is, not strictly mentally only - there are a few things I often do. And a lot more similar you can figure

• Use the seconds from a nearby watch, modulo N - or minutes if low frequency or some correlation is OK. Great for N up to 6 (and 10 and 12 and... but those are rarer)
• If playing cards, memorise some of the cards from your previous hand. Use red/black, or face value.
• Pick a number/digit/letter from wherever you can. As in, 4th letter, 3rd word, 2nd line in this text: "o". Or, the first digit of the licence plate of the next red car. Or...

I have posted a very similar answer to a very similar question "Mentally generating a pseudo random $\{0,1\}$ sequence with uniform distribution"....

as per @Nick Alger's answer, When I was young I memorized the first 100 or so digits of π. I did it for a fun challenge at the time, and for many years (decades?), I did not encounter any 'useful' application of this.

However, as my career has moved away from physics/engineering and more towards statistics, I have found that this knowledge is extremely useful as a source of unbiased random sampling.

For example, given that π=3.1415926535897932384626433832795028841971693993751058209749...

if I need to find a random sample of coin flips $\{0,1\}$, I consider the successive digits (after the decimal point) of π modulo 2. That is, if the digit is even, the outcome is $0$, and if it is odd, the outcome is $1$. Thus, the sequence is: $$\{1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,0,1,0,…\}$$

One can also set a different ('random seed') by skipping the first $x$ digits.

It should be obvious that this technique works for sampling when 2, 5 or 10 options are required. However, what is awesome is that with only a minor modification it can works just a easily if 3,4,6,7,8 or 9 options are required.

For example, if you need to model a roll of a die where 6 options are required, go through the digits one at a time, and if the digits is 0,1,2,3,4, or 5 than 'accept' that as the outcome and if it is 6 or higher than 'reject' / skip that digit. This method of sampling is called rejection sampling.

Thus the sampling would be: $$\{1,4,1,5,x,2,x,5,3,5,x,x,x,x,3,2,3...\} \rightarrow \{1,4,1,5,2,5,3,5,3,2,3…\}$$


text:
## Section problems for configuration spaces of surfaces

20 May 2019  ·  Chen Lei ·

In this paper we give a close-to-sharp answer to the basic questions: When is there a continuous way to add a point to a configuration of $n$ ordered points on a surface $S$ of finite type so that all the points are still distinct? When this is possible, what are all the ways to do it?.. More precisely, let PConf$_n(S)$ be the space of ordered $n$-tuple of distinct points in $S$. Let $f_n(S): \text{PConf}_{n+1}(S) \to \text{PConf}_n(S)$ be the map given by $f_n(x_0,x_1,\ldots ,x_n):=(x_1,\ldots ,x_n)$. We classify all continuous sections of $f_n$ up to homotopy by proving the following. 1. If $S=\mathbb{R}^2$ and $n>3$, any section of $f_{n}(S)$ is either "adding a point at infinity" or "adding a point near $x_k$". (We define these two terms in Section 2.1; whether we can define "adding a point near $x_k$" or "adding a point at infinity" depends in a delicate way on properties of $S$. ) 2. If $S=S^2$ a $2$-sphere and $n>4$, any section of $f_{n}(S)$ is "adding a point near $x_k$"; if $S=S^2$ and $n=2$, the bundle $f_n(S)$ does not have a section. (We define this term in Section 3.2) 3. If $S=S_g$ a surface of genus $g>1$ and for $n>1$, we give an easy proof that the bundle $f_{n}(S)$ does not have a section. read more

PDF Abstract

# Code Add Remove Mark official

No code implementations yet. Submit your code now

# Categories

Geometric Topology


text:
# How do you solve the inequality abs(x-3)<8?

May 24, 2017

#### Answer:

Solution: $- 5 < x < 11$ . In interval notation : $\left(- 5 , 11\right)$

#### Explanation:

$| x - 3 | < 8 \mathmr{and} x - 3 < 8 \mathmr{and} x < 11$ OR

$| x - 3 | < 8 \mathmr{and} x - 3 > - 8 \mathmr{and} x > - 5$

Solution: $- 5 < x < 11$ . In interval notation: $\left(- 5 , 11\right)$ [Ans]


text:
# Prove that $\pi>3$ using geometry

I was asked this question today in an interview.

Question: Prove that $\pi>3$ using geometry.

They gave me hints about drawing a unit circle and then inscribing an equilateral triangle and then proceeding. But I could not follow. Can anyone help?

• How is pi defined? – miracle173 Nov 22 '15 at 12:09
• @miracle173 How does that help? – SchrodingersCat Nov 22 '15 at 12:13
• How do you want to show something about pi if you have not definition of it? – miracle173 Nov 22 '15 at 12:15
• Inscribe a regular hexagon! – Christian Blatter Nov 22 '15 at 12:16
• An equilateral triangle inscribed in a unit circle has perimeter $3\sqrt{3}$, which is not of itself obviously helpful. Offhand I'd guess the interviewer was trying to guide you toward the idea of inscribing a suitable polygon, in this case a regular hexagon. – Andrew D. Hwang Nov 22 '15 at 13:33

The inscribed hexagon in the unit circle has perimeter $6$. The perimeter of the circle is $2\pi$, hence $\pi > 3$.

• Shouldn't it be $>$ and not $\ge$? – SchrodingersCat Nov 22 '15 at 12:30
• imgur.com/IbOElsj – Paulistic Nov 22 '15 at 12:48
• Arguably this involves six equilateral triangles – Henry Nov 22 '15 at 15:06
• How do you prove that the perimeter of the hexagon is smaller than the perimeter of the circle (really "prove", not say "it is clear that...")? – Sebastien Nov 23 '15 at 8:25

The inscribed $12$-gon in the unit circle has area $\frac{12}{2}\sin (2\pi/12)=3$. The area of the unit circle is $\pi$. Hence $\pi\ge 3$.

• Thanks, But can you use the triangle and do so? – SchrodingersCat Nov 22 '15 at 12:20
• Shouldn't it be $>$ and not $\ge$? – SchrodingersCat Nov 22 '15 at 12:30
• I like this argument based on area than another one on this thread based on perimeter. – Kim Jong Un Nov 22 '15 at 12:38

I am not sure if this is redundant, but:

If an equilateral triangle is inscribed in a unit circle, and if, on each side of the inscribed triangle, an isosceles triangle is further inscribed in the circle, then an equilateral hexagon with each side of length $=1$ results; but then $6 < 2\pi$ implies $3 < \pi$.

So is this something you are after?

• Not really.. I just want the proof using a triangle.. without constructing a hexagon. – SchrodingersCat Nov 22 '15 at 12:53
• @Aniket I would say the hint just provides a starting point; by inscribing suitable triangles twice we arrives at something useful, is not it? :) – Megadeth Nov 22 '15 at 12:54
• In that case.. I mean if you look at it in that way... It is fine. – SchrodingersCat Nov 22 '15 at 12:56

With a little bit of cheating, you don't need the whole hexagon...

Let $O$ be the centre of the unit circle with equilateral $\triangle ABC$ inscribed in it. Extend $\vec {AO}$ to meet the circle at D.

As $BC$ and $OD$ are perpendicular bisectors of each other, $\triangle OBD$ is isosceles, and hence $|BD|=1$. But this must be smaller than the minor arc subtended, which has length $\dfrac{\pi}3$.

• Could the downvoter comment why? – Macavity Dec 29 '15 at 14:50