text:
# Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits

### Abstract

Consider the problem: given data pair $(\mathbf{x}, \mathbf{y})$ drawn from a population with $f_\star(x) = E[ \mathbf{y} | \mathbf{x} = x]$, specify a neural network and run gradient flow on the weights over time until any stationarity. How does $f_t$, the function computed by the neural network at time t, relate to $f_\star$, in terms of approximation and representation? What are the provable benefits of the adaptive representation by neural networks compared to the pre-specified fixed basis representation in the classical nonparametric literature? We answer the above questions via a dynamic reproducing kernel Hilbert space (RKHS) view indexed by the training process of neural networks. We show that when reaching any local stationarity, gradient flow learns an adaptive RKHS representation, and performs the global least squares projection onto the adaptive RKHS, simultaneously. In addition, we prove that as the RKHS is data-adaptive and task-specific, the residual for $f_\star$ lies in a subspace that is smaller than the orthogonal complement of the RKHS, formalizing the representation and approximation benefits of neural networks.

Type
Publication
arXiv:1901.07114
Date


text:
Quantum Bayesian Networks

November 20, 2008

Books on Bayesian Networks

Filed under: Uncategorized — rrtucci @ 6:36 pm

Two of the best books for teaching Bayesian networks are

• Michael Jordan, “Introduction to Graphical Models”, in preparation
• Daphne Koller and Nir Friedman, “Bayesian Networks and Beyond”, in preparation.

In preparation !@#. For eons now, these books have been “in preparation”. Civilizations have come and gone. Many courses in many universities have used these books in preliminary form as their primary text. Why are these authors so laid back! Do they live in Frank Capra’s Shangrila, where people live thousands of years, and don’t need to hurry much. Hmm, Jordan at Berkeley, Koller at Stanford. California…Shangrila. It seems that, for the time being, these gem books will be available only to surfer dudes, not to us hard working Yankees on the other coast.

Update (Sept 9, 2009)
Wow, 1200 pages! I take back all I said about Californian’s being laid back. Check out

Probabilistic Graphical Models
Principles and Techniques

Daphne Koller and Nir Friedman
(Aug 2009, MIT Press)

Quantum Simulated Annealing

Filed under: Uncategorized — rrtucci @ 5:40 am

In my youngest paper, I proposed a “quantum Metropolis-Hastings algorithm” (MH) that uses a quantum computer to sample probability distributions. (This is useful in AI applications of Bayesian networks, for example). Now I am expanding my horizons by studying simulated annealing. In particular, I am studying the work of Somma, et al, and Wocjan et al. These two researchers and their collaborators have proposed a “quantum simulated annealing algorithm” (SA) that uses a quantum computer to find a local minimum $x_0$ of an “energy” function $E(x)$. They have found that quantum computers can do this quadratically faster than classical computers.

MH and SA are closely related. In both MH and SA, we seek a sample of $x$ points that is distributed according to a probability distribution $\pi(x)$, where $\pi$ is the stationary distribution of a Markov Chain. But in MH, $\pi$ is fixed: it does not change with each iteration. In SA, on the other hand, $\pi$ is a moving target: it becomes spikier and spikier with each iteration, peaking at those points which are minima of $E(x)$.

This excellent website describes various optimization algorithms. In particular, it has a page with an applet that uses SA to solve an instance of the traveling salesman problem with 15 cities.

SA must have been invented by a group of Shakers 🙂 . So simple and beautiful, and yet so useful.

November 13, 2008

Books on Quantum Bayesian Networks

Filed under: Uncategorized — rrtucci @ 4:23 pm

Nope. None. Not yet. The field is a secret garden at present. A secret garden, having one is great solace from those aspects of life that make us inconsolably sad. For many years now, quantum bayesian networks has been one of my secret gardens. Which reminds me of the novel, “The Secret Garden”, by Frances Hodgson Burnett. Great book, very memorable plot. Usually considered children’s literature, like Treasure Island and the like, but still a fun read for an adult, even better if the adult is reading it to his/her children. The 1993 movie is very good too.

My new paper: sampling + quantum computers

Filed under: Uncategorized — rrtucci @ 12:30 am

My youngest paper, just published today at ArXiv, is entitled:

“Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network”

The paper (41 pages) is just as wordy as its title. I could have written a much leaner paper (claims he), but I opted to include lots of introductory material, to make life easier for newcomers to my secret garden.

My target audience are two clans of people, quantum computerists and Bayesian network users. These two clans have never talked to each other until now, no doubt because they have never been properly introduced. My hope is that I, like Mr. Robinson, can get them to talk to each other, for a while at least (at least until they find out about my unsavory character.) I am referring here to the Mr. Robinson in the humorous poem “Etiquette” by W.S. Gilbert (yes, the Gilbert of the Gilbert & Sullivan operettas).

November 2, 2008

Qubit Mixers

Filed under: Uncategorized — rrtucci @ 3:04 pm
Tags:

A qubit lives in a complex vector space spanned by two vectors

$|0\rangle= \left[\begin{array}{c}1\\ 0 \end{array}\right]\;\;,\;\;|1\rangle = \left[\begin{array}{c}0\\ 1\end{array}\right]\;.$

Define the following projection operators:

$\overline{n} = P_0 = |0\rangle\langle 0|=\left[\begin{array}{c}1\;\;0\\ 0\;\;0\end{array}\right]\;\;,\;\; n = P_1 = |1\rangle\langle 1| =\left[\begin{array}{c}0\;\;0\\ 0\;\;1\end{array}\right]\;.$

$n$ is called the number operator because $n|b\rangle = b|b\rangle$ for $b \in \{0,1\}$. Note $\overline{n} = 1 -n$.

The Pauli matrices are defined by:
$\sigma_X = \left[\begin{array}{c}0\;\;1\\1\;\;0\end{array}\right]\;\;,\;\;\sigma_Y =\left[\begin{array}{c}0\;-i\\i\;\;0\end{array}\right]\;\;,\;\;\sigma_Z = \left[\begin{array}{c}1\;\;0\\ 0\;-1\end{array}\right]\;.$
One also defines $\vec{\sigma} = (\sigma_X,\sigma_Y,\sigma_Z)$.

The lingua franca for expressing a sequence of quantum computer commands are quantum circuits with circuit elements of some basic types. Here are some circuit elements in order of increasing complexity: (in these figures, 0,1,2 are qubit labels)

Fig.1 (Pinwheel) Single-qubit rotation and Controlled Not (CNOT)

Fig.2 (Farm Windmill) Multiply Controlled Rotation

Fig.3 (Windfarm) Multiplexor

The pinwheel, farm windmill and wind farm are my poetic analogues.
One can generalize the operators of Figs.2 and 3 to have more controls (the dark dots in Fig.2 and the half-moon nodes of Fig.3) and more complicated targets (the square nodes in Figs.2 and 3).

Let $N_B$ be the number of bits and $N_S= 2^{N_B}$ the number of states. The operators in Fig.1 are a “universal” set: any matrix in $SU(N_S)$ can be constructed in terms of them. The operators in Figs. 2 and 3 can be expressed in terms of those in Fig.1.

The operators in Figs. 1 and 2 appear frequently in the quantum computing literature. The multiplexor operator of Fig.3 is much less common. Only I and a few other workers have used it in their papers. Multiplexors have some very useful properties. I’ve used them in the theory behind my quantum compiler, Qubiter ( a quantum compiler decomposes an input unitary matrix into a sequence of elementary operations (SEO), elementary operations such as single qubit rotations and CNOTs.) My next paper uses multiplexors heavily. As soon as the paper is in ArXiv, I will update this post with a link to it.

Update: The paper is now available here. It contains a whole section introducing multiplexors.

Create a free website or blog at WordPress.com.

format: plain


text:
# [ANN] stdio-0.2.0.0

Today I’m very happy to announce a new beta version of stdio is released on hackage, there’re some large additions in this version:

• Add UDP module.
• Add JSON module.
• Add ToText class to Std.Data.TextBuilder module.

The largest addition is a new JSON module, features full RFC 8259 compliance and 2~3x faster performance. Try to bring big improvements over a very mature library like aeson is not an easy task, parts of the improvements come from faster Parser and Builder infrastructures in stdio. But we also made a few other improvements:

• To improve building lookup table during JSON parsing(and many other formats as well), An ordered map module based on sorted vectors and binary-search is also added, there’re actually four modules providing similar functions to containers:

• Std.Data.Vector.FlatMap
• Std.Data.Vector.FlatIntMap
• Std.Data.Vector.FlatSet
• Std.Data.Vector.FlatIntSet

These data structures have different time and memory characteristics from tree-based ones, and suits some situations better, e.g. intermediate lookup table.

• To improve JSON string parsing, we made an UTF-8 validation state machine with JSON unescaping logic built-in written in C, combine with the ability to scan a whole chunk of input(provided by our new Parser, namely scanChunks), we now have faster JSON string parsing performance than some native code(JSON.parse from nodejs).

• Numeric parsing is also improved, e.g. we changed Integer decoding loop to use machine words if range permits, then covert the result to Integer rather than use Integer all the time.

There’re also lots of improvements and simplifications contribute to faster performance. Overall this is good proof that our new Parser and Builder infrastructures work well.

Besides the JSON module, another important addition is the ToText class in Std.Data.TextBuilder, which is also derivable via generics. The format is chosen to follow Show class as much as possible, this is a very handy class when you need to quickly turn something into a builder or text.

A UDP module is added quite easily since the IO manager part is in place. Due to the message based nature, the API is quite different from TCP, design suggestions are welcomed!

Happy hacking!
Cheers


text:
# Overview

At it’s most basic level, an operational amplifier (op-amp) is a discrete analogue integrated circuit which acts as a voltage-amplifier with very high gain.

Note that an op-amp’s gain can be adjusted with the appropriate external circuitry (the op-amp’s internal gain does not change, but the gain of the entire circuit does). It can also be converted into a current amplifier.

# Schematic Symbol

An op-amp is commonly drawn on schematics as:

You may see this symbol with or without the voltage supply pins $$V_{S+}$$ and $$V_{S-}$$. If they are not present, it is assumed that they are connected up to a power source which should be obvious from the design intent.

WARNING: Always take note of the position of the inverting (-) and non-inverting (+) input terminals. Sometimes they can be drawn swapped around relative to the symbol shown above.

# Uses

• Buffers
• Linear amplifiers, non-linear amplifiers
• Pre-amplifiers (amplifier’s with a input voltage of 10mV or less)
• Analogue mathematical operations (differentiators, integrators, summer, subtracters, e.t.c)
• Voltage to current (transconductance) and current to voltage conversions (transimpedence)

# Configurations

## Voltage Follower (aka Buffer)

A voltage follower (also known as a buffer) is one of the most basic circuits you can make with an op-amp.

As shown in the above diagram, the output voltage is the same as the input voltage ($$v_{o} = v_{i}$$). Well isn’t this pointless? No, the key point to a voltage follower/buffer is that it can convert a high-impedance input into a low impedance output. Practically, this means that you can now sink/source more current from the output without the voltage changing. Buffers are great for boosting signals that travel across long distances, or for signals which get split and go to many devices (this is called fan-out, and is common with digital clock signals).

A simulation schematic for a voltage-follower op-amp is shown below:

The results of the simulation:

## Non-Inverting Amplifier

A op-amp in the non-inverting amplifier configuration is shown below.

The equation for the gain of the non-inverting amplifier is:

$$v_o = (1 + \frac{R_f}{R_i} ) v_i$$

Notice the $$1$$ in the gain equation? This means that no matter what you set the resistors $$R_f$$ and $$R_i$$ to, you can never get a gain which is less than one. This is one of the disadvantages of the non-inverting amplifier (you can have a gain of less than one with an inverting amplifier).

Here is a simulation schematic (circuit) for a non-inverting op-amp amplifier running from a single-ended supply. Because R1 ($$R_f$$) and R2 ($$R_i$$) are both $$1k\Omega$$, the op-amp has a gain of:

$$G = 1 + \frac{R_f}{R_i} \\ G = 1 + \frac{1k\Omega}{1k\Omega} \\ G = 2$$

The results of the simulation are shown below. As you can see, the output voltage $$V_{out}$$ is exactly twice the input voltage $$V_{in}$$.

## Inverting Amplifier

A op-amp amplifier in the inverting configuration is shown below:

The equation for the gain of an inverting amplifier is:

$$v_o = – \frac{R_f}{R_i} v_i$$

The negative sign is to show that the output is the inverse polarity of the input. Notice that, unlike the non-inverting amplifier, an inverting amplifier lets you obtain a gain of less than 1.

Below is the schematic used for simulating the behaviour of an inverting op-amp. Note how is requires a negative voltage power supply.

And below are the simulation results for the above schematic:

## Differential Amplifier

A differential amplifier amplifies the difference between two electrical signals.

The output voltage is given by the equation:

$$v_o = \frac{R_4}{R_3 + R_4}(1 + \frac{R_2}{R_1})v_2 – \frac{R_2}{R_1}v_1$$

Below is a schematic for simulating the behaviour of a differential op-amp:

This schematic produces the following results:

## Integrator

It’s output voltage is proportional to the integral of the input voltage w.r.t. time. The figure below shows an ideal op-amp based integrator.

However, this circuit is normally not practical in real world situations. Any errors such as the output offset voltage and input bias current (which all op-amps invariably have), as well as a non-perfect input signal with small amounts of DC bias, will cause the output to drift, until it reaches saturation.

A way to fix this problem is to insert a high-valued feedback resistor, $$R_f$$, to limit the DC gain, as well as a resistor, $$R_{bias}$$, on the non-inverting input terminal to compensate for the input bias current.

## Transconductance Amplifier

A transconductance amplifier is an op-amp topology which is used to convert a voltage into a current. Coincidentally, it is also known as a voltage-to-current converter.

A basic transconductance amplifier can be built with an op-amp in a non-inverting configuration.

A transconductance amplifier is useful creating an industry standard 4-20mA (or 0-20mA) current-loop signal. The input voltage can come from something like a potentiometer or microcontroller (coupled with either using a VDAC peripheral or PWM/RC-filter technique to create a variable voltage).

One dis-advantage with this design is that the current output is not ground referenced, that is, ground is not used as the return path for the current. This complicates the wiring.

# Important Variables

Sorted alphabetically.

## Gain-Bandwidth (GBW) Product

The gain-bandwidth product can be initialised as GBWP, GBW, GBP or GB. It is an important parameter which basically puts a limit on the maximum gain and frequency. An op-amp’s maximum possible gain reduces as the frequency of the signal increases. The multiplication of the gain with the frequency gives the gain-bandwidth product, which is relatively constant for a particular op-amp.

Hence if the gain bandwidth of a particular op-amp is 1Mhz, and the gain is 10, the maximum frequency that the op-amp can operate linearly at (still provide a gain of 10) is at 100kHz. Or if the gain was set to 100, then the maximum frequency is 10kHz. This also means that an op-amp has a built-in low-pass filter, as the gain drops for very high frequencies.

An example of an ultra-high gain bandwidth is 1700MHz, which are present in ‘Wideband CFB” op-amps, designed for applications such as RGB line drivers (such as the OPA695). A ‘normal’ GBW can be anywhere between 100kHz and 10MHz. A low gain-bandwidth is around 1kHz (reminiscent of less advanced, older op-amps). Remember gain is unit-less (V/V), so gain bandwidth is expressed as a frequency only. Not realising this can be confusing! The GBW product is closely related to the slew rate (see below).

## Slew Rate

Slew rate is another op-amp parameter. It defines the maximum rate the voltage can change with respect to time. In an ideal op-amp, this would be infinite. It has the SI units V/s, and is commonly expressed in uV/s. It can be thought of as the slope of the output waveform if one of the inputs of the input was subjected to a step voltage change. This parameter usually increases as the GBW increases.

## Supply Current

The supply current is generally constant for any supply voltage. It is normally rated as the no-load current. Obviously, if there is a load on the op-amp, the current through the power pins will be the sum of the no load ‘supply current’ and the current going through the load.

Supply currents for standard op-amps are typically between 1.5-4mA. A ‘low-power’ op-amp has a typical supply current between 0.5-1.5mA (such as the LM258N). Then there are ultra-low power op-amps that only draw 5-20pA (such as the LMC6464). You normally sacrifice slew-rate and gain-bandwidth for ultra-low power.

## Input Impedance

The input impedance is the internal resistance to ground from the two input pins. In an ideal op-amp, this value is zero. For most op-amps, this value is somewhere between 1-10M.

## Output Voltage Range

This defines the voltage range at which the op-amp can drive the output. The LM324 is rumoured to only be able to drive the output near ground if it is sourcing current, but only to 0.5V minimum if sinking (see this EDA Forum post, LM324 Opamp Gain Instability).

Cascading op-amps is concept when the output of one op-amp is connected to the input of another. There can be an arbitrary number of op-amps in the cascade, but usual limits are 3-4.

For a fixed-gain, cascading op-amps can also be used to increase the bandwidth, as each individual op-amp now can operate at a lower gain and therefore has a larger bandwidth as defined by the gain-bandwidth product. Note though that each additional op-amp added to increase the bandwidth gives diminishing returns. Also important to note that op-amp bandwidth is defined as the -3dB gain points. Hence the bandwidth does not stay the same (total bandwidth gets smaller) when two identical op-amps are cascaded, as these will now the -6dB points. A practical limit for fixed-total-gain increased-bandwidth cascading is about 3-4 op-amps.

## The Gain

When cascading op-amps, the total gain is the product of all of the individual op-amps gains, i.e.:

$$A_{total} = A_0 A_1 A_2 … A_n$$

## The Bandwidth

The bandwidth of cascaded op-amps is not as simple to calculate as the gain.

If all of the op-amps are identical, then the following equation can be used:

$$BW_{tot} = BW \times \sqrt{2^{\frac{1}{N}} – 1}$$

where:
$$BW_{tot}$$ = the total bandwidth of the cascaded op-amp system
$$BW$$ = the bandwidth of the individual op-amps (remember, they have to be identical)
$$N$$ = the number of op-amps in the cascaded system

# Feedback Resistor Values

As a rule-of-thumb, you should use the lowest acceptable resistances in op-amp feedback paths to reduce instabilities.

# History

Op-amps have slowly gotten better over the last few decades. Newer op-amps have better gain bandwidth products, better noise rejection ratios, and far less input bias currents as well as power usage. As expected, all the newer ones are primarily released in SMD packages.

Check out Korg’s Monotron schematics for some good examples of how op-aps are used in commercial products.

# Rail-to-Rail Op-amps

What is a rail-to-rail op-amp? The manufacturers of single-supply op-amps (op-amps that can run from a single voltage supply, rather than requiring a dual positive/negative supply) market op-amps as rail-to-rail, and that the output of the op-amp can swing from ground to the positive rail. This is not exactly true. The op-amp’s output voltage will never get exactly to the rail, due to the finite voltage drop across the output-stage transistors. This voltage drop increases with the amount of current the op-amp is supplying to the load.

WARNING:Rail-to-rail” op-amps cannot really output either rail voltage. A negative power supply is always required if you want the op-amp to be able to output a true 0V.

To achieve a true ground output, you need a negative voltage supply. There are dedicated IC’s designed to provide a small negative power supply to op-amps so that they can output true ground. One such example is the Texas Instruments LM7705, a “Low Noise Negative Bias Generator“. This IC only generates -230mV, which allows the designer to use CMOS-based op-amps which usually have a maximum supply voltage of 5.5V.

# Examples

Below are some examples of op-amps that stand out from the crowd for some reason, be it popularity, years in service, or functionality wise.

Manufacturer Code: Description: Approximate Price (1 unit, US$): AD860x Good for high precision stuff! Awesome for photo-diode amplification (both current-to-voltage and voltage-to-voltage configurations).$3.50
LM324 A common op-amp that has been around for along time, this can operate of a single supply and can swing right to ground, but cannot swing to the rail voltage.
LM833 One of the cheapest ‘audio’ op-amps available (about US$0.20 as of 2011). Features a high GBW for it’s price. OPA695 This is a ultra-wideband, current-feedback op-amp. If you need an op-amp with a ridiculously high gain-bandwidth product, this is along the lines of what you want to use. It has a GBW of 1700Mhz and a maximum slew-rate of 4300V/us.$3.50

# Isolation Amplifiers

Isolation amplifiers provide galvanic isolation between the input (sensor) and output (measurement circuitry). They are used to protect the sensor measurement and recording circuitry (e.g. a microcontroller with on-board ADC) from dangerously high voltages at the sensor, and also the opposite, to protect the sensor environment from potentially dangerous voltages on the rest of the system.

A common application would be to isolate and amplify the voltage across a current-sense resistor on a high-power motor, or to protect humans with medical sensors connected to them from the measurement system.

Basic isolation amplifiers require two power supplies (one for each side of isolation), while others incorporate built-in transformers so that you only have to provide one power source.

Posted: September 5th, 2011 at 6:08 pm
Last Updated on: May 31st, 2016 at 2:40 pm


text:
# Behaviour of likelihood ratio test as sample size increases

I know that the log likelihood statistic, i.e. $$X^2=-2(LL_1 - LL_2)$$ where $$LL_1$$ and $$LL_2$$ are the maximum log likelihoods of two models, one nested in the other, is asymptotically distributed as a chi-squared variate with degrees of freedom equal to the difference in the number of free parameters between the two models as $$n \rightarrow \infty$$; $$n$$ is the sample size of the data.

My question: is the difference between the sampling distribution of $$X^2$$ and the theoretical chi-squared distribution always decreasing as n increases? If we compare the difference given two different sample sizes, is the approximation of a theoretical chi-square distribution always better at the larger sample size?

I ask because, in simulations of a rather complicated model, the sampling distribution of $$X^2$$ does come closer to the theoretical distribution as $$n$$ increases up to a point and then, as $$n$$ increases further, the fit between the two gets worse. I did not expect this behaviour and cannot find an explanation.

• For how many simulations (repeated samples) have you assessed the convergence to the Chi2? That is, you are evaluating the convergence at different n. Perfect. Then how many simulations/repeated samples for each n have you performed?
– Fr1
Sep 4 '19 at 15:49
• I have used 5000 independent simulations each time, and have varied the sample size (n) from 50, 100, 200, 500 and 1000 Sep 13 '19 at 14:22
• Could you include some more details of the model and simulations? Maybe show some plots? Mar 13 '21 at 8:07

It's not clear to me if this is implied in the original question, but if the data follow the alternate hypothesis rather than the null one, the statistic will tend asymptotically toward a noncentral, rather than standard, $$\chi^2$$. Also, there are circumstances in which the asymptotic result doesn't hold, eg https://stats.stackexchange.com/a/52855/163989. More information on the problem, including some plots, could help.


text:
# If 748x924 is divisible by 11, what is minimum value of x

1. 2
2. 0
3. 6
4. 4

Option 2 : 0

## Detailed Solution

Given:

748x924 is divisible by 11

Concept used:

Divisibility rule of 11 = If the sum of the digit at the odd place and even place are equal or differ by a number that is divisible by 11, the number is also divisible by 11

Calculation:

The sum of digit at odd place and even place of 748x924

⇒ Odd place digits sum = 7 + 8 + 9 + 4 = 28

⇒ Even place digits sum = 4 + x + 2 = 6 + x

Odd place digits sum - Even place digits sum

⇒ 28 – (6 + x)

⇒ 22 – x

Here, if we take the value of x 0 then the result is divisible by 11

The minimum value of x is 0


text:
# Showing that $f(4x) + 4f(2x) =8\cos^4(x)-3$, where $f(x) = \cos x$

It is given that $$f(x)= \sin(x+30^\circ) + \cos(x+60^\circ)$$

A) Show that $$f(x)= \cos(x)$$

B) Hence, show that $$f(4x) + 4f(2x) =8\cos^4(x)-3$$

I managed to prove $$f(x)$$ equals $$\cos(x)$$, but after that I'm stumped.

• Do you know how to expand $\cos 4x$ and $\cos 2x$ in terms of $\cos x$? Even easier if you know Euler's formula. – rogerl Jan 29 '19 at 20:38

You can use the property: $$cos(2x) = cos^2(x)-sin^2(x)$$
Since this will allow you to express $$cos(4x)$$ = $$cos^2(2x)-(1-cos^2(2x)) = 2cos^2(2x)-1$$
By substituting again $$cos(2x)$$ by the aforementioned expression you will be able to express $$4cos(2x)+cos(4x)$$ in terms of $$sin(x)$$ and $$cos(x)$$ raised to some powers. The sinus will cancell out and will obtained the desired result.
$$f(x)=\sin(30^{\circ}+x)+\sin(30^{\circ}-x)=2\sin30^{\circ}\cos{x}=\cos{x}.$$ Thus, $$f(4x)+4f(2x)=\cos4x+4\cos2x=8\cos^4x-8\cos^2x+1+8\cos^2x-4=8\cos^4x-3.$$


text:
Cooper Doyle

2022-07-08

If you are a voter in a state with a million other active voters, what is the probability that your vote will be pivotal in the next election?
Assuming a given voter is equally likely to vote for either party, it seems that the answer is $\left(\begin{array}{c}1,000,000\\ 500,000\end{array}\right)\ast \left(\frac{1}{2}{\right)}^{500,000}\ast \left(\frac{1}{2}{\right)}^{500,000}$ and when I plug it into a calculator it gives me 7.9788E-4, which doesn't seem plausible. Is there something wrong with my reasoning?

pampatsha

Expert

The probability that your vote will be pivotal in deciding this kind of perfect election can be calculated as the probability that 500,000 people will vote for one candidate and 5000,000 people will vote for the second candidate. Just as you calculated, this probability will be $\left(\genfrac{}{}{0}{}{1,000,000}{500,000}\right)×\left(\frac{1}{2}{\right)}^{1000000}=7.9788...×{10}^{-4}.$ This probability is somewhere around one in a thousand. You might have been expecting a probability closer to one in a million, but the probability is as high as it is because of the law of large numbers. The great majority of the time the final count for each side will fall somewhere in between $500,000±1000.$ In other words, the race will tend to be fairly close, so there is a relatively high probability that your vote (and everyone else's) will sway the election.