Showing posts with label Maths. Show all posts
Showing posts with label Maths. Show all posts

Friday, April 17, 2026

There are 11064 Cars in Luxembourg

I was in Luxembourg recently and saw 4 cars when I was there. Their registration plates were 1396, 1871, 2383 and 8852





This made me wonder if I could estimate the total number of cars in Luxembourg. 

This is the German Tank problem where the British in WW2 found some serial numbers on German tanks in north Africa and wanted to use those to guess how many tanks had been produced. If you are sure the serial number on tanks goes up by one each time and they started with number 1. Then if you have seen the highest number 100 in looking at 3 tanks of after looking at 50 you can have a better estimate to the highest number of tank made.  Also if you see a tank with number 1000 you know at least 1000 have been made. 



A formula to estimate the total number based on seeing k serial (registration) numbers where m is the highest number seen is the MVUE (Minimum Variance Unbiased Estimator) N ≈ m + (m/k − 1)

Which gives an estimate of 11064 total cars in Luxembourg.


Monday, December 20, 2021

Calculus Made Easy and Memorable

I made a website to help people learn calculus. I have taken a 1910 book Calculus Made Easy by Silvanus P. Thompson that has already been digitized and put on the web in a nice format at https://calculusmadeeasy.org/. This was created by nadvornix and other volunteers. This edition has added some memorisation reminders to the text.

The book is famous for being accessible to teenagers. Some of the text has dated in the century since. Martin Gardner created a new edition in the 1980s with some of the text deolded and some extra background chapters. Making similar updates might improve this book some more.

Orbit is a tool that tests your knowledge of text you just read. And then retests you on a regular basis. This vastly increases the amount you remember for very little extra time or effort. Some of the evidence that timed repetition aids recall is given in this essay 

Calculus made Easy and Memorable is on the web at http://calculusmadememorable.org/ and the code is here

Why put a new more memorable calculus book online? ‘1 million students take a college-level Calculus 1 course in the United States, at an average cost of $2,500. And then 40% of them fail.’ That is 1 billion loss a year in one country from failing one course. Anything that helps reduce that rate could be a boon.







Wednesday, September 27, 2017

Pi Digits High Low Game

Suppose you take a long number and for each digit if it is bigger then the previous one increase a counter by one. If it is less then the previous number reduce the counter by one. You keep a running total and graph that total. Noting when it passes 0. This total number will go up and down and can get to zero many times. If you play this game with random numbers in a million digits on average the number of times you will have crossed 0 is 1594.4 and the standard deviation of the number of times crossed 0 is 1207.3. Though as the number of times zero is crossed cannot be less then 0 this is a bit odd.
       
import random

numcrossed=[]
j=0
while j < 200:
	i = 0
	last=0
	total=0
	x=[]
	y=[]
	crossed=0
	while i < 1000000:
		ran= random.randint(0, 10)
		if ran==last:
			total=total
		elif ran>last:
			total=total+1
		else:
			total=total-1
		if total==0:
			x.append(i)
			y.append(total)
			crossed=crossed+1        
		i=i+1        
		last=ran
	numcrossed.append(crossed)
	j=j+1
       
 
If instead of random numbers the digits of pi are used. This is what the path of total counts looks like
       
file = open("pi1000000.txt", "r") 
#3.14159265358979323846264338327950 pi2.txt
x = []
y = []
text=file.read() 

pi = list(text)
total =0
i = 0
crossed=0
i=0

while i < len(pi):
	if pi[i]>pi[i-1]:
		#print(pi[i])
		total=total+1
	if pi[i]
 

Pi has a 0 total 657 times. Which is more than 51 out of 200 random million long sequences did in my tests. None of this means anything. Going up or down based on digits in a base ten number but i like these pattern sort of sequences.

E crosses 0 1725 times

sqrt2 crosses 0 1300 times

and with 2 million digits


The python code for visualisation is 
       
import numpy as np
import matplotlib.pyplot as plt

plt.scatter(x, y, alpha=0.5, color='green')
plt.title('Sqrt 2 High Low Game')
plt.show()
       
 

Monday, November 05, 2012

Drawing the presidential Election

Finding all the ways the electoral college votes from each state can be added up to give both candidates 269 votes turns out to be really hard. Political pundits always bring up the spectre of a drawn presidential election.

What happens if the US election ends in a draw?

If There’s an Electoral College Tie, Things Will Get Even Crazier Than You May Know

Where both candidates get 269 of the electoral college votes.

The website 270towin calculates 32 practical combinations that could result in a tie and give the probability of one of these occuring given polling data at 0.2%.

The NYtimes here claims there are 5 practical ways a tie could result.

But how many possible drawing combinations are there in total, including implausible ones?

Elections are much closer than the set of all possible wins a candidate could have. Certain states are similar so tend to vote the same way so some divisions are far more likely than others. Also by the median voter theorem two competing parties will be as similar to each other as possible to get as much of the vote as they can. Roughly the Republicans will be as near the center as they can while getting all the right wing votes and the democrats as near the center while getting all the left wing votes.

But how many total ways are there that two candidates can win 50 states and one district? That is as, ColinTheMathmo pointed out, 2^51 as each state can go to either candidate. I want to find the number of allocations in this 2^51 that give each candidate 269 electoral college votes*.

2^51 is a big number. As Matthew Saltzman said the set partition is an NP-Complete problem and a 'Complete enum at 10M/sec, would take 7 years.'

But instead of complete enum we just want to see the cases where both candidates get 269. The code here calculates this. I took some Minizinc code from Hakan Kjellerstrand who pointed out an error in my previous reading of a result that would calculate all the allocations of states that give 269 electoral votes. The code is written in Minizinc as it can calculate all answers in a way GLPK** doesn't. Hakan also kindly pointed out some inefficiencies in my program so I am linking to his code.

Here are some of the many results it output

Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania 'South Dakota' Texas Utah 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Vermont 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Wyoming 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Nevada 'New York' 'North Dakota' Ohio Pennsylvania 'South Dakota' Texas Utah 
My mac is 2.16 gz and has 2 gigs of RAM so it is not a fast machine. Still after three hours of running it ground to a halt. This means I have no answer for you. If I find out how many of the state allocations result in 269 votes I will let you know.

It is interesting that these sorts of difficult NP-Complete problems pop up in real life and getting solutions for them is not always easy.

* Actually Maine and Nebraska can give out votes proportionately so the search space is even larger than this

**Just in case someone can use it here is GLPK code that will work out one answer

/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Pop {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function 
          z: sum{i in STATES} VotesTable[i,j]*x[i];
     
/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] == Need[j];

/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Need:=
Votes        269;

end;

Friday, November 02, 2012

What is the least amount of land that will make you President?

Matthew Yglesias in the slate calculates what he thinks is the smallest area of land a candidate could win and still win this presidential election. Densely populated states will have more electoral college votes per square kilometer and so you can win the election while winning a relatively small surface area of America.
His reasoning is 'I started with a list of states in order of population density. So you have DC, then New Jersey, then Rhode Island, then Massachusetts, and so forth. Eventually you get a set that wins you the electoral college. Except the bloc of the 18 densest states gives you 282 electoral votes—way more than you need. Eliminate Michigan, the 18th densest, and you have 266 electoral votes. So then you can round things out with little New Hampshire's four electoral votes and you have your winning map'.

I checked this allocation with the GLPK program below. I used the electoral votes listed here and the state areas listed on wikipedia This gets 270 votes with an area of 1625012km². US states + DC is an area of 9826630km² so 16.54% of the US could win an election.

The states are Delaware, District of Columbia, Hawaii, New Hampshire, Rhode Island, Connecticut, Maryland, Indiana, Massachusetts, Virginia, New Jersey, North Carolina, Ohio, Illinois, Pennsylvania, Florida, New York, California. My map is here

Matthew Yglesias' map is the same so he did find the optimal solution by hand.

/*code to find the least land area to get 270 votes. Run with 'glpsol -m election.mod -o out'
*/
/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Cost {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function */
      minimize z: sum{i in STATES} Cost[i]*x[i];

/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] >= Need[j];


/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Cost:=
 Alabama 135765
 Alaska 1717854
 Arizona 295254
 Arkansas 137732
 California 423970
 Colorado 269601
 Connecticut 14357
 Delaware 6447
 "District of Columbia" 177
 Florida 170304
 Georgia 153909
 Hawaii 28311
 Idaho 216446
 Illinois 149998
 Indiana 94321
 Iowa 145743
 Kansas 213096
 Kentucky 104659
 Louisiana 134264
 Maine 91646
 Maryland 32133
 Massachusetts 27336
 Michigan 250494
 Minnesota 225171
 Mississippi 125434
 Missouri 180533
 Montana 380838
 Nebraska 200345
 Nevada 286351
 "New Hampshire" 24216
 "New Jersey" 22588
 "New Mexico" 314915
 "New York" 141299
 "North Carolina" 139389
 "North Dakota" 183112
 Ohio 116096
 Oklahoma 181035
 Oregon 254805
 Pennsylvania 119283
 "Rhode Island" 4002
 "South Carolina" 82932
 "South Dakota" 199731
 Tennessee 109151
 Texas 695621
 Utah 219887
 Vermont 24901
 Virginia 110785
 Washington 184665
 "West Virginia" 62755
 Wisconsin 169639
 Wyoming 253336;

param Need:=
Votes        270;

end;

Tuesday, June 19, 2012

The Fairest Way to Pick a Team

What is the best way to pick a team? As kids we would always strictly alternate between teams so team 1 had first team 2 the second pick and then team 1 again etc.

Most things you can measure about people are on a bell curve. A small number of people are bad, most are in the middle and a few are good. There are a few good known metrics of ability. None are perfect, there is no one number that can sum up ability. The simpler the sport the more one metric can tell you, in cycling VO2 max is a very good indicator. Whereas in soccer VO2 max, kicking speed, vertical leap, number of keep me ups you can do etc could all measure some part of football ability.

So say there was one good metric for a task and teams were picked based on this. Is the standard strict alteration, where Team 1 picks then Team 2 alternating, fair? Fair here meaning both teams end up with a similar quality.

I wrote a program in R Package. Not because I know it but because it is perfect for this sort of problem. If you are picking 5 a side and the best player left is always picked by a team how much better is the first picker?

Strict Alteration the code is

players<-10
#create a vector
z <-0
#run 10000 simulations
for(i in 1:10000)
{
#rnorm generates a normally distributed dataset
# this one has 10 elements. A mean of 100 and a std of 12
#sort puts the biggest at the end
x <- c(sort(rnorm(players, mean=100, sd=12)))
# for each simulation take every second one and put it into a different team. 
# Give one team even and one odd 
z <- append(z, sum(x[c(1,3,5,7,9)]-x[c(2,4,6,8,10)]))
}
print(sd(z))
#get the average difference between the two teams
print(mean(z))

> print(sd(z))

[1] 8.794016

> print(mean(z))

[1] -22.59786

IQ has an average of 100 and a standard deviation of 12. IQ isn't used much to pick soccer teams but many things follow a similar pattern. In software development IQ wouldn't be the worst metric to pick a team on and agile teams are supposed to have between 5 and 9 members. So think of this as people picking teams of developers.

In this simulation Team 1 ends up with .225 of a person advantage. The more people on the team the greater advantage the first picker gets.

18 players

> print(sd(z))

[1] 8.287164

> print(mean(z))

[1] -25.52077

16 players

> print(sd(z))

[1] 8.20681

> print(mean(z))

[1] -25.00685

Would another way of picking the teams be fairer?

Balanced Alteration from the Win Win Solution by Brams and Taylor 'strict alteration can give a big boost to the first chooser when there are only two parties. What we need to do is reduce this advantage of the first chooser by amending strict alternation.'

The balanced alteration allows the captains to be first chooser in turn.

This is

Team 1 Team 2 Team 2 Team 1 Team 1 Team 2 Team 2 Team 1....

the code is

players<-10
#create a vector
z <-0
#run 10000 simulations
for(i in 1:10000)
{
#rnorm generates a normally distributed dataset
# this one has 10 elements. A mean of 100 and a std of 12
#sort puts the biggest at the end
x <- c(sort(rnorm(players, mean=100, sd=12)))
# for each simulation take every second one and put it into a different team. 
# Give one team even and one odd 
z <- append(z, sum(x[c(1,4,5,8,9)]-x[c(2,3,6,7,10)]))
}
print(sd(z))
print(mean(z))

> print(sd(z))

[1] 9.757417

> print(mean(z))

[1] -9.04198

This method looks better than the standard strict alteration.

Thinking about the bell curve though is would make sense if the team that got the best player got the worst, and the second best the second worst etc. This should even up the teams well. The code for this is

players<-10

#create a vector
z <-0
#run 10000 simulations
for(i in 1:10000)
{
#rnorm generates a normally distributed dataset
# this one has 10 elements. A mean of 100 and a std of 12
#sort puts the biggest at the end
x <- c(sort(rnorm(players, mean=100, sd=12)))
# for each simulation take every second one and put it into a different team. 
# Give one team even and one odd 
z <- append(z, sum(x[c(2,4,6,7,9)]-x[c(1,3,5,8,10)]))
}
print(sd(z))
print(mean(z))

> print(sd(z))

[1] 9.3498

> print(mean(z))

[1] 3.027536

This has a better average difference. The fact the difference is as high as it is makes me think I may have a bug in my code.

Kids to implement this method would have to alternate picking a player until they were about to pick the middle player in their team Then Team 2 would get a second pick. This sounds almost practical.

When you played a sport (particularly soccer) as a kid what rules did you pick teams by? Can you think of a better algorithm now?

Friday, April 13, 2012

Completing a Panini Sticker Album



When I was a kid my main ambition was to fill out the Panini Italia 90 sticker album. I promised myself when I was old and rich I would buy all the stickers I needed to fill out a championship sticker album. Some kids aim to play for Ireland, I aimed low. Turns out I am not rich but I am nerdy so at least I can work out how much it would cost to fill out the album.

This is called the Coupon Collector Problem.
"Given n coupons, how many coupons do you expect you would need to draw with replacement before having drawn each coupon at least once?"

There are 539 stickers in an album to collect. The first sticker you buy is going to be one you need, a 539/539 chance of getting one you need. The second has a 538/539 chance of being one you do not have as there is one it can clash with. This keeps going until for the last sticker every new sticker has a 1/539 of beng the right one. The formula for the number of attempts you would need to calculate the coupon collector number is 539*Harmonic Number of 539. Which according to Wolfram Alpha is 6.867858*539=3701.77. The stickers are sold in packs of five. Which means 740 packs.

On amazon a box of 100 packs cost £43.95. This would mean (assuming you could get .4 of a box at that same price) that filling the album would be expected to cost 325.23 pounds.

Panini sell the stickers at 14p each. So to buy the stickers individually would cost 539*.14=75.46 pounds.

Is there some kind of mixture of boxes of random stickers and individual ones that means you can fill in the album for as cheap as possible. Say the individual stickers can be bought at the price of a box. So thats 0.1162 pounds for each sticker. Which is not that much of a saving. It becomes more efficient to buy individual stickers than random packs at this price after about 90 stickers.

The last sticker takes on average 539 stickers to be bought to find it. So this last sticker costs 0.1162*539=62.63 pounds if you buy it in packets not individually.

But are the tickets independent? As in are some rarer than others and is each pack random? Some people studied this in the very cool paper 'Paninimania: sticker rarity and cost-ef fective strategy'
"We consider some issues related to the famous Panini stickers devoted to the football world cup. In particular, we address the following questions: is there a planned shortage of some stickers? What is a good cost-e ffective strategy to fill in an album?"
Which proves amongst other things I am not the only nerd that still wants to fill in a Panini album.

Tuesday, December 13, 2011

Eradication Game Theory


Can you crowdsource disease eradictaion?

I mentioned in this post on 2030 that I expect Polio and Guinea worm to be eradicated by then. It becomes a tricky issue when a disease gets really uncommon how you find and treat the last few cases? So far only smallpox and rinderpest have been eradicated. Eradication is great because once its done its done. You would not have to immunise every child for polio any more. Every polio vaccine has a small cost and risk and once thats gone you can go spend the money on something better


India has tried an interesting tack 'Cash awards for info on diseases'
Alert the government on the occurrence of new cases of certain ailments and you may get a cash award! The government has targeted vaccine preventable diseases such as diphtheria, pertussis, measles, tetanus, and leprosy for elimination by 2016. India is also on the verge of being declared polio-free.
District medical and health officer Dr G. Srinivasulu explains that even after being declared polio-free, there should not be a single new case for 14 consecutive months in the country. This is where the reward comes in. “If anybody succeeds in detecting a new polio case meanwhile, the government will give a cash award. Even in case of detection of new leprosy cases, ASHA health workers are given Rs 150-Rs 200,” he said.


There was a competition last year from DARPA to encourage new ways to pool information held my many people.
'MIT wins $40,000 prize in nationwide balloon-hunt contest'

A team from the Massachusetts Institute of Technology won $40,000 in a high-tech scavenger hunt on Saturday by discovering the location of 10 red weather balloons.

"We're giving $2,000 per balloon to the first person to send us the correct coordinates, but that's not all -- we're also giving $1,000 to the person who invited them. Then we're giving $500 whoever invited the inviter, and $250 to whoever invited them, and so on..." it said.

Some similar system that set up a chain of reward could be really useful in disease eradication. Many security protocols rely on a sort of iterative proof of trustworthiness. Something similar could be used to allow steps toward eradication without fear some other country is going to stop efforts.

Assurance contracts are another approach. It is possible that some regions are scared that once a disease is eradicated to their area they will lose funds. Some way to guarantee that funding will not reduce or to reward successful eradication might help here. Something like Dominant assurance contracts might help to change incentives to encourage eradication.



How about a guarantee fund for each of the remaining countries with polio and guinea worm that when who declares them free they get some cash bonus. You could imagine a kickstarter project that gave the minister of health in Nigeria money when polio was declared eradicated from the country.

Another good plan is not to have fake immunisation drives against polio



The juice of the carrot, the smile of the parrot
A little drop of claret - anything that rocks
Elvis and Scotty, days when I ain't spotty,
Sitting on the potty - curing smallpox


We want to discourage deliberately being lax about a disease so you have to be clever about incentives. Anyone have any good idea for how you could bribe people and governments to further incentivise disease eradication?

Thursday, September 15, 2011

A/B testing. Is Khan doing it wrong?

A/B testing is where you try an old way of doing things and a new way each with a sample of the users and see which one works better. It is frequently used by ads where you test two wordings "Buy new coke!" and "Buy improved coke!" to see which one gets more clicks.

If you ever write a book or need to name a shop you should spend a few quid buying google ads for the two names you are trying to pick "How to start a fight" and "How to win an argument" and see which one gets clicked on more. That one should be the name.

This is one of those embarrasing posts that is probably wrong. But I think the A/B testing used by the Khan academy makes a fairly fundamental mistake. The Khan acedemy has lessons in various subjects. So presumably they want to use A/B testing to see if kids taught "1+1=2" or "1 + 1 = 2" learn more quickly and such.

A/B testing is a useful way to see if little tweaks result in better user experience. In Khan's case learning. It does not substitute for good design vision but can help make some relatively small tweaks. Improving the Khan acedemy and kids education is really important so if there is a bug in their A/B testing they might be making the wrong choices about how to improve their teaching.

For this kind of testing you need to pick the number of test cases in advance. How not to run an A/B test explains why and the effects of looking before all the test is finished. This is an odd feature of frequentist statistics

'However, the significance calculation makes a critical assumption that you have probably violated without even realizing it: that the sample size was fixed in advance. If instead of deciding ahead of time, “this experiment will collect exactly 1,000 observations,” you say, “we’ll run it until we see a significant difference,” all the reported significance levels become meaningless. This result is completely counterintuitive and all the A/B testing packages out there ignore it'

The A/B testing used by Khan seems not to do this as the gae bingo system says

"Controlling and ending your experiments

Typically, ending an experiment will go something like this:

You'll notice a clear experiment winner and click "End experiment, picking this" on the dashboard. All users will now see your chosen alternative."



This seems to be saying that either you should notice what is statistically significant which you won't always or that something can be declared statistically significant before all the samples are tested. Think of it this way. If every test has a 5% chance of being wrong and you think of everytime you look at the A/B test as adding 5% to the chance of being wrong. It is not quite that bad but it gives you a feeling of the problem.

Now there are ways you can tell that something is statistically significant really early in a test. "Bayesian Statistics and the Efficiency and Ethics of Clinical Trials" deals with these. In medical trials you want to know as early as possible if a new treatement is better or worse than an old one. Giving someone the wrong ad wont kill anyone but the wrong cancer drug might. This paper goes through how you would figure this out using Bayesian methods. These methods are also described in chapter 37 of MacKay's 'Information Theory, Inference, and Learning Algorithms'

But looking at the code GAE bingo uses for A/B testing they do not seem to be using these methods. So it looks to me that they are making the mistake of letting you stop a test when you want to. Which in frequentist statistics can be an error.

Also I think Vanity another rails A/B testing framework makes the same assumption
"This experiment will conclude once it has 1000 participants for each alternative, or a leading alternative with probability of 95% or higher:"

The system used by the BBC is based on time and not numbers according to this article. "Example use
For 5 in 100 people to get a two-option test running for 24 hours the function is initialised like this:". Which is not nearly as bad. But it is assuming that at the end of the time period you have had enough users to make a good test.

There is a proper explanation as to what can happen if you stop a trial early in "How not to run A/B testing". But from my reading many of the A/B testing frameworks out there seem to be making this error. Please correct me in the comments.

Addition: Ben from gae bingo got back to me in a comment on their blog.
"You're right that this is an issue, and that's a great blog post. However, this is significantly mitigated by a) letting your experiments run long enough to get a large-ish sample size for your population and b) simply not checking your dashboard constantly and making snap decisions.

We could build stuff into the system to mandate that, but at the moment I believe we'll be able to get solid value out of the existing framework (just like most A/B systems)." This seems fair enough, Khan are going to have such a high volume of users that they will be able to get a large sample size quickly.

Allen Downey has a great review of the problem with simulations here

Friday, March 11, 2011

Think Different

I am fascinated by how people think differently from each other. I think there are big differences in the fundamental methods people use to think, but because we rarely talk about how we think these are not well known.

Feynman talks here about how he heard numbers in his head when he counted and his friend saw numbers visually.


He believed that such fundamental differences explained why we sometimes have such difficulties communicating with each other.

I 'see' numbers as a kind of line and I have heard other people describe other ways they 'see' numbers

Reading is another place people think differently. When I read I 'hear' the words as I read them. This is called subvocalisation and is normal but it slows down reading. "Subvocalization, or silent speech, is defined as the internal speech made when reading a word, thus allowing the reader to imagine the sound of the word as it is read". There are all sorts of online guides as to how to stop subvocalising. My wife does not subvocalise and never has. She describes seeing words as the actual word rather then hearing it and then understanding what it means.

Do left handed people who do that hook handed over the top writing have a fundamentally different view of writing? Do you know of any other basic cognitive tasks that people carry out in completely different ways?

Thursday, February 17, 2011

Watson is better off having a three way competition

It seems non intuitive but I think Watson is more likely to win because its competition are so good. If you look at how well it did on Jeopardy here it seems to show Watson is better having humans splitting the points on questions it cannot answer as it is so quick to answer the ones it can.

When the humans buzz in they are right 19/23 about 83% of the time. Suppose Jennings was up against watson and me and I got zero buzz ins. Jennings may have gotten 11 of the buzz ins that Rutter got. Watson seems so fast on the buzzer that it seems to buzz first for nearly every question it could answer 44/50 times it tries to answer it is first.

This means that Jennings could nearly have doubled the number of answers he had but because there are two people who are really good at the sorts of questions only humans could answer these points are divided amongst the humans. Of the 23 human answers only 6 did Watson try to buzz in on.

There is a similar probability puzzle that might help in a three way duel. "You're a cowboy, and get involved in a three way pistol duel with two other cowboys. You are a poor shot, with an accuracy of only 33%. The other two cowboys shoot with accuracies of 50% and 100%, respectively. The rules of the duel are one shot per cowboy per round. The shooting order is from worst shooter to best shooter, so you get to shoot first, the 50% guy goes second, and the 100% guy goes third, then repeat. If a cowboy is shot he's out for good, and his turn is skipped. Where or who should you shoot first?"

Theres another explanation of a three way duel here.

Sometimes having 2 really good competitors increases your chances of winning.

Sunday, September 26, 2010

A failed Mturk translation test

The Mturk is Amazon's platform where you can put up jobs for people to do. These tend to be things like translation or image categorisation that humans are good at but computers are not.

According to Panos Ipeirotis' research mturk workers seem to be highly educated. The majority having degrees and about 10% having postgraduate degrees. Much mturk work is boring and probably does not use the skills these well educated workers have.

A few days ago google announced sponsorship for projects they think are carrying out good work. One winner was

"The Khan Academy will receive $2 million toward funding its work on the "make educational content available online for free" theme. The academy does just that, with a library of over 1,800 videos with lessons on math, science, finance, and history.

Bill Gates is a big fan of the Khan academy "This guy is amazing," he wrote. "It is awesome how much he has done with very little in the way of resources."
.

I am also a huge fan of the Khan academy I think that these videos and other online education videos such as MIT's online courses have amazing potential to transform the education of millions of people.

How far could googles 2 million grant stretch? Obviously it is up to Mr Khan to decide how to use his resources but I thought it would be interesting to see if the mturk could be used to translate one of his mathematics videos. The languages with over 100 million speakers are Mandarin, Spanish, English, Hindi, Bengali, Cantonese, Arabic,Portuguese, Russian and Japanese. 10 languages for 2000 videos would be 20,000 video translations. If each video cost 100 dollars to translate that would spend the 2 million dollars google donated. If this cost can be reduced more languages could be added.

A mathematics video is not something the average person can translate. However we know a large number of turkers have degrees and many are from India where they would likely have an understanding of English and Hindi or Bengali.

I tried an experiment to see if I could get one of Khan's videos translated into Hindi using the mturk at a cost of 5 dollars. Unfortunately I failed. The first person who accepted the task dictated what Khan said into text. Which is useful but not what I was looking for. The second person posted up another video on Solving linear inequalities in English not a translation of Khan's video.



This small experiment tells me that you need to be very clear on the mturk how you ask for a task to be completed. It also says that it might be worthwhile once you find someone who understands and completes the task to encourage them to translate other videos rather than rely on the vagaries of who happens to accept your mturk task.

This experiment ignored the problem of copyright. Khan owns his videos and it is unfair for someone to come along and copy him. I was not trying to steal any glory from Mr Khan with this experiment just to see if the mturk could be used to translate his videos.

Other people have successfuly used mturk to reduce the cost of translations. 'How I reduced translation costs of 200 articles from $9000 to $46' is an interesting article on one successful usage. This tells me that the problem was more likely with my unclear instructions than with the mturk platform. You can even monitor translations taking place in the mturk here so I still think this method would be cost effective. However my simple experiment failed.

Monday, January 11, 2010

Analytics X Prize

There is a competition here to try and predict what proportion of murders in Philadelphia will occur in each of the cities 47 zip codes. Many people who are interested in these sorts of puzzles have started submitting predictions.

So how would you go about predicting the murder proportion in each zip code?
Well if nothing changes in Philadelphia you would expect each zip code to keep exactly the same proportion of murders, well with some random variation you could not predict. So my first guess is a repeat of exactly what happened last year.

But in the real world things do change. Say the population changes if every person had the same chance of being murdered then the proportion of murders in a zip code would change proportionate to the change in population. If this was the case the prediction problem would become to find out what changes in population will take place over the year.



The dataset I am using is here and some errors in it need to be removed. Each dot is a zip code. It looks like number of murders does roughly follow population but it is not nearly an exact match. So changes in population are important but they are far from the only thing we need to predict.

How expensive the house in an area are or the average income or the number of people per house might help indicate the murder rate. Here I am looking at number of (murders/population)*10000.





So it looks to me a bit like areas with crowded houses could be more likely to have murders.






House cost looks like it is not connected to murder rate. This could be because zip code is too rough grained for this to be a good judge. Maybe the average cost of a house in a block would be a better measure of risk. Philadelphia has even been broken down into 60ft squares here



Does household income look like it is related to murder rate?

So if the graph is a random scattering of dots then it looks like the independant variable on the x-axis has no relation to homicide rate the dependant variable on the y-axis. If the dots form a line (well not just a line but that is another story) then the homicide rate may be related to that independant variable. It really is not this simple but that's the basics.



As Siah pointed out here young black males seem to be murdered out of proportion. The graph above does seem to suggest that predicting changes in ethnicity of a zip code may improve predictions. Age is another important variable and I do not have data on that so that might be the next thing to get.

There are interesting posts already on this puzzle
"Evaluating Spatial Predictions" and "Second Pass at Analytics X Prize" and "Homicides as non homogeneous poisson processes" are very informative.

Thursday, December 10, 2009

Dublin pubs and the El Farol Bar problem

I was in town last night and i noticed how empty the superpubs were. these are the giant warehouse like pubs that need to be packed all the time to pay for the giant rents they have.

They also need to be full to make it look like they are not just giant warehouses. This is a version of the El Farol Bar problem. The game theory is this

* If less than X% of the population go to the bar, It will be too empty and they'll all have a worse time than if they stayed at home.
* If more than X% of the population go to the bar, they'll all have a better time than if they stayed at home.

People realise the pubs will be empty so no one goes. It is a positive feedback problem. Which means these big pubs are in big trouble.

Sunday, November 29, 2009

The Diet Problem

What is the cheapest way to feed yourself? This is not a minor issue our diets and health could be much better if they were optimised to provide the most needed nutrients at the smallest cost and also to provide the most palatable diet that is as healthy as possible.

Stigler in 1939 worked out a near optimal miminum price needed to supply a person with the nutrients they need for a year. The diet consists of five not very pleasant foods so is not intended to be realistic dietry advice.

Still given current knowledge of nutrition a list of prices from various supermarkets could you optimise you shopping basket to provide your family with groceries? Here we want to give people the nutrients they need in a form they will actually eat that is healthy and cheap.

We need a list of
1. What nutrients are needed by a person
2. Foods preferences of people.
3. A price list of foods
4. A Linear program to optimize a shopping basket based on these variables.

All of these requirements need some explanation. I think its best if each gets it's own post. So tomorrow I will have a post on what quantities of nutrients people require. If you have any suggestions please comment.

Sunday, November 15, 2009

215 is the first Wikipedia dull number

I have always wanted my own constant and now for a short period I have one. Imagine numbers were 'interesting' or 'dull'. The first dull number would be interesting because it was the first dull number so no dull number can exist. So all number are interesting.
Now you would think any interesting number would be notable enough to have its own wikipedia page. The first number without a wikipedia page is 215. This should be notable enough to deserve a wikipedia page. So as long as 215 has no wikipedia page it is dull and thus as the first non notable number it is notable. The paradoxes of wikipedia notability were brought up here.

Thursday, October 29, 2009

Matchbox Maths Games

There is a great article here on Matches on India. No really read it.
In fact, 97% of rural households purchase matches on a monthly basis. Matches are a unique product because of their high, constant demand and low price point.Their ubiquitous presence provides fascinating insights into India's rural distribution networks, and offer potential ways to inform and interact with India's relatively untouched market.

The article then suggests using the matchboxes to spread public health messages
What if that space was used to relay information? Imagine the possibilities of spreading new health/educational information or advertising to 97% of rural families on a monthly basis. Simple pictorial designs would pique interest and accommodate India's vast differences in literacy rates and languages. Awareness of important topics such as the installation of chimneys to reduce smoke inhalation or cleaning and covering water containers to prevent stomach ailments could be spread to households across India, and potentially save lives

I would recommend selling the glamor of flushing toilets and chimneys and such rather than nagging in your images. But i do not know enough about rural Indians and their diseases to advise on what health images to provide them. There are some interesting studies on what does kill these people here.

However what if all you put on the boxes was games? Many people have a ludic philosophy of life. You see a love of games in maths nerds in particular. This love of games I believe adds a cognitive richness that aids intellectual development.

There is a great book called "everything bad is good for you". That claims the increase in IQ in recent decades is due to increased complexity in our culture. I have not studied the Flynn effect enough to be sure it is not caused by nutrition or even to be sure it is important. But I will assume it is and that intellectual challenges improve general cognitive abilities. I will go further out on a limb and claim that such improvements in cognitive abilities would aid rural Indians. Never having been a rural Indian this really is a big assumption.

So what intellectual challenges could fit on a matchbox and be read by an illiterate farmer? How about puzzles and games?

There are some face meltingly brilliant match puzzles here(pdf). Other then puzzles there are games like NIM, dots and boxes, chomp and loads of others you can play with matches. I would imagine if a brand of matches has a game on it that keeps the kids from bothering you this would be a popular feature.

So can you think of some way to explain a puzzle or the rules of a game on a matchbox without using text? Do you think it really could be useful to put mathematical games and puzzles on matchboxes?

Wednesday, October 28, 2009

A work sceduling problem

I saw this problem recently
A city authority is considering placing a toll booth on its new bridge. The beginning
times for the shifts are 8am, noon, 4pm, 8pm, midnight and 4am. A collector
beginning a shift at one of the above times works for the next 8 hours.
The following staffing levels during each of the 24-hour periods have been estimated

Hour.................... Minimum Collectors Needed
8am - Noon.............. . 5
Noon – 4pm ................6
4pm – 8pm .................10
8pm - Midnight........... .7
Midnight – 4am ...........4
4am – 8am .................6

Find the minimum number of collectors that need to be hired to begin the 8 hour shifts
at each of the six times.


A GLPK program to calculate this is

var x1 >= 0, integer;
var x2 >= 0, integer;
var x3 >= 0, integer;
var x4 >= 0, integer;
var x5 >= 0, integer;
var x6 >= 0, integer;
/* objective function */
minimize z: x1+x2+x3+x4+x5+x6;

/* Constraints */
s.t. ctr1:x1 + x6 >= 5;
s.t. ctr2:x1+x2>= 6;
s.t. ctr3:x2+x3>= 10;
s.t. ctr4:x3+x4>= 7;
s.t. ctr5:x4+x5>= 4;
s.t. ctr6:x5+x6>= 6;
data;
end;

The answer is 19 and no one starts working at 8am.
This is a simplified version of the program described here. Not a major revelation or anything but always find these puzzle solving programs cool.

Sunday, October 18, 2009

Prediction with game theory

I am going to this talk on Thursday so I am reading the book Predictioneer by Bruce Bueno De Mesquita. He has a ted talk video on his prediction ideas.


The use of game theory in forecasting seems based on the axiom that people are rational. The problem is they are not, here is a list of the different ways they are not. If you know how they are going to be irrational you can alter your models to take this into account. However if you fail to do this you will end up with less accurate models.

In chapter 2 the book claims people are rational and particularly that we are transitive in our preferences. "to be rational.. their preferences must not go in circles. For instance if I like chocolate ice cream better then vanilla and vanilla better then strawberry i presumably like chocolate ice cream better than strawberry." So no rock paper scissors can exist in human preferences.

The problem is they do. There is loads of evidence that people can have intransitive preferences. For example May showed in 1952 that people can have intransitive preferences for wealth, looks and intelligence in a partner. So how can you have a mathematical system modeling the world where one of your axioms is false?

While on the subject of intransitive never play dice with Warren Buffet. There are loads of stories of how he tries to con people with a set of intransitive dice. Edward Thorpe for example. Or Bill Gates as described in Bill Gates Speaks: Insight from the World's Greatest Entrepreneur By Janet Lowe

Buffet once attempted to win a game of dice with Bill Gates using intransitive dice. "Buffet suggested each would choose one dice and discard the other two. They would bet on who would roll the highest number most often. Buffet offered to let Gates pick first. This suggestion instantly aroused Gates curiosity. He asked to examine the dice after which he demanded buffet choose first."

Wednesday, September 16, 2009

NAMA, how much is 54 billion euro?

Nama, the Irish governemts agency to take on bad loans, is paying 54 billion euro to buy property. How much money is that? There is a great visualisation here about how much is a trillion.

So lets picture Croke Park. Its pitch is 144.5 m x 88m. That is much bigger then a soccer or rugby pitch. A 20 euro note is 133 × 72 milimiters. So to pave Croke Park pitch with 20 euro notes requires. So that is 1087 notes long 1223 wide or 1,329,401 notes are needed to pave croke park pitch in 20 euro notes. So that is roughly 2 layers of 20 euro notes being 54 million and paving it two notes deep. A billion is a thousand million so 54 billion is 1000 times this. So 54 billion is paving Croke Park in 20 euro notes 2000 deep.

So if your looking at the game on Sunday imagine there is a 20,000 euro pile of cash on the pitch that you now owe. That is 54 billion divided among the people who pay tax. So you and the person sitting next to you owe a 2000 deep 20 euro sized chunk of the Croke Park pitch.

A comment vaguely asked how much euro coin is this? "Did you know its also enough Euros placed end to end to reach the moon". According to here a 2 euro coin has
Thickness (mm): 2.20
Weight (g): 8.50

So 27 billion 2 euro coins are needed. So in weight that is 229.5 million kilos.
"The maximum gross mass for a 20 ft (6.1 m) dry cargo container is 30,480 kg" so that is 7540 containers full of 2 euro coins.

How long would the stack be? 2.2 * 27 billion millimeters = 59 400 kilometers. Or enough to go around the earth one and a half times. But less than a fifth the distance to the moon.