Saturday, December 18, 2010

Probability problem


There's a famous problem in probability: find a probability distribution such that two such independent random variables have a sum that is uniformly distributed from 0 to 1.

That turns out to be impossible. One way to prove it is by considering the expected value of exp(2*pi*i*x). Because the distribution of the sum has to have this quantity be 0, each part also has to have the same property. The only distribution with support between 0 and .5 with this property is 0 w.p .5, and 0.5 w.p. 0.5. That distribution doesn't work.

A related problem is: find a probability distribution such that two such independent random variables x1, and x2 satisfy x1 + 2*x2 is uniformly distributed from 0 to 1.

Can you do it?


Thursday, December 02, 2010



package main

func main(){
stat := make([][][]int, 9)
for i := 0; i < 9; i++ {
stat[i] = make([][]int, 9)
for j := 0; j < 9; j++ {
stat[i][j] = make([]int, 9)
}
}
rule := make([][]*int, 324)
for i := 0; i < 324; i++ {
rule[i] = make([]*int, 9)
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
rule[i*9+j][k] = &stat[i][j][k]
rule[81+i*9+j][k] = &stat[i][k][j]
rule[162+i*9+j][k] = &stat[k][j][i]
rule[243+i*9+j][k] = &stat[3*(i/3)+(k/3)][3*(i%3)+(k%3)][j]
}
}
}
input := "96..1.7.4..1....2....2.59....3......59.....76......1....98.3....7....2..1.8.7..69"
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
if input[9*i+j] == '1'+byte(k){
stat[i][j][k] = 1
}
}
}
}
for iter := 0; iter < 100; iter++ {
for i := 0; i < 324; i++ {
sum := 0
for j := 0; j < 9; j++ {
sum += *rule[i][j]
}
if sum&1 == 1 {
for j := 0; j < 9; j++ {
if *rule[i][j] == 0 {
*rule[i][j] = 2
}
}
}
if sum == 16 {
for j := 0; j < 9; j++ {
if *rule[i][j] == 0 {
*rule[i][j] = 1
}
}
}
}
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
for k := 0; k < 9; k++ {
if stat[i][j][k] == 1 {
print(k+1)
}
}
}
println()
}
}