Stochastic Nonsense

Put something smart here.

Probability Problems Coin Flips 01

You have an urn with 10 coins in it: 9 fair, and one that is heads only. You draw a coin at random from the urn, then flip it 5 times. What is the probability that you get a head on the 6th flip given you observed head on each of the first 5 flips?

Let $H_i$ be the event we observe head on the $i$th flip, and let $C_i$ be the event we draw the $i$th coin, $i = 1,…,10$.

Then we wish to calculate (using range syntax for brevity) $$( P(H_6 | H_1 H_2 H_3 H_4 H_5) = P(H_6 | H_{1:5}) $$)

Conditioning on which coin we drew, and exploiting the symmetry between coins 1 to 9:

$$( \begin{align} P(H_6 | H_{1:5}) & = \sum_{i=1}^{10} P(H_6 | H_{1:5}, C_{i}) P(C_i | H_{1:5} ) \\ & = 9 \cdot P(H_6 | H_{1:5}, C_1) P(C_1 | H_{1:5}) + P(H_6 | H_{1:5}, C_{10}) P(C_{10} | H_{1:6} ) \end{align} $$)

So it just remains to calculate $P(C_i | H_{1:5})$. This can be done via bayes rule:

$$( P(C_i | H_{1:5}) = \frac{ P(H_{1:5} | C_i ) P(C_i) }{ P(H_{1:5}) } $$)

where, playing the same conditioning trick:

$$( \begin{align} P(H_{1:5}) &= \sum_{i=1}^{10} P(H_{1:5} | C_i ) P(C_i) \\ & = \sum_{i=1}^{9}P(H_{1:5} | C_i) P(C_i) + P(H_{1:5} | C_{10}) P(C_{10}) \\ & = 9 \cdot \left( \frac{1}{2} \right)^5 \frac{1}{10} + 1^5 \frac{1}{10} \end{align} $$)

Thus:

$$( \begin{align} P(C_1 | H_{1:5}) & = \frac{ P(H_{1:5} | C_1 ) P(C_1) }{ 9 \cdot \left( \frac{1}{2} \right)^5 \frac{1}{10} + 1^5 \frac{1}{10} } \\ & = \frac{ \left( \frac{1}{2} \right)^5 \frac{1}{10} }{ 9 \cdot \left( \frac{1}{2} \right)^5 \frac{1}{10} + 1^5 \frac{1}{10} } \\ & = \frac{1}{9 + 2^5} \\ & = \frac{1}{41} \\ & \\ P(C_{10} | H_{1:5}) & = \frac{ P(H_{1:5} | C_{10} ) P(C_{10}) }{ 9 \cdot \left( \frac{1}{2} \right)^5 \frac{1}{10} + 1^5 \frac{1}{10} } \\ & = \frac{ 1^5 \frac{1}{10} }{ 9 \cdot \left( \frac{1}{2} \right)^5 \frac{1}{10} + 1^5 \frac{1}{10} } \\ & = \frac{32}{9 + 32} \\ & = \frac{32}{41} \\ \end{align} $$)

Note that we can quickly self-test and verify $ \sum_{i=1}^{10} P(C_i) = 1 $.

Returning to eqn (2)

$$( \begin{align} P(H_6 | H_{1:5}) & = 9 \cdot P(H_6 | H_{1:5}, C_1) P(C_1 | H_{1:5}) + P(H_6 | H_{1:5}, C_{10}) P(C_{10} | H_{1:6} ) \\ & = 9 \cdot \frac{1}{2} \frac{1}{41} + 1 \cdot \frac{32}{41} \\ & = \frac{73}{82} \end{align} $$)

Alternatively, you can use R to calculate the probability via brute force by repeatedly sampling according to our problem and counting the number of heads observed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
max_itrs <- 5*1e6
used_itrs <- 0
skipped_itrs <- 0
num_H <- 0

for(itr in 1:max_itrs){
  coin <- sample(1:10, 1)

  if( coin <= 9 ){
    if( !all( runif(5) <= 0.5)){
      skipped_itrs <- skipped_itrs + 1
      next
    }
    num_H <- num_H + ifelse( runif(1) <= 0.5, 1, 0)
  } else {
    num_H <- num_H + 1
  }
  used_itrs <- used_itrs + 1
}

num_H / used_itrs

# vs 73/82
num_H / used_itrs - 73/82

my sample run produced

1
2
3
4
5
6
> num_H / used_itrs
[1] 0.8901657
> 
> # vs 73/82
> num_H / used_itrs - 73/82
[1] -7.821522e-05

C++ and Const. Sigh.

well known benefits of constness.

1
2
3
4
5
6
7
8
// function:
bool learn_tree(const float** target, unsigned int num_classes);

// and I'm attempting to call with:
float** residuals;

// compiling produces:
error: cannot initialize a parameter of type 'const float **' with an lvalue of type 'float **'

what on earth? It turns out the winner is this beautiful bit of syntax:

1
bool learn_tree(const float* const* target, unsigned int num_classes);

beautiful.

So for all future googlers, this is how you declare const double arrays or const multidimensional arrays in c++.

Splitting Files With Awk

To split files (eg for test / train splits or k-folds) without having to load into R or python, awk will do a fine job.

For example, to crack into 16 equal parts using modulus to assign rows to files:

split files into equal parts with awk
1
$ cat LARGE_FILE | awk '{print $0 >("part_" int(NR%16))}'

Or to crack a file into a 80/20 test/train split:

create test/train split using awk
1
awk '{if( NR % 10 <= 1){ print $0 > "data.test.20"} else {print $0 > "data.train.80"}}'

And finally, if your data file has a header that you don’t want to end up in a random file, you can dump the header row into both files, then tell your awk script to append (and use tail to skip the header row)

create test/train split with proper header handling
1
2
3
head -1 LARGE_FILE > data.test.20
head -1 LARGE_FILE > data.train.80
tail -n+2 LARGE_FILE | awk '{if( NR % 10 <= 1){ print $0 >> "data.test.20"} else {print $0 >> "data.train.80"}}'

Wordpress to Octopress Migration

As mentioned, I’m moving my blog to octopress. I got tired of php, php-cgi, wordpress, security holes, constant updates that broke random plugins, 5 second page loads, fragile caching plugins, and all the various nonsense that wordpress brings to the table.

An aside: php-cgi is so fragile and crashes so often I ran a screen session as root that just attempted to restart it every 5 seconds (attached below for any poor souls stuck using this tech.)

1
2
# run as root inside screen
for (( ; ; )); do /usr/bin/spawn-fcgi -u nginx -g nginx -f /usr/bin/php-cgi -a 127.0.0.1 -p 53217 -P /var/run/fastcgi-php.pid; sleep 5; done

For googlers who want to move from wordpress to octopress, here’s how I moved 70-odd posts with minimal pain.

1 – Get thomasf’s excellent python script (accurately named exitwp) that converts wordpress posts to octopress posts. This will create one octopress post per wordpress post in the source directory.

2 – I simultaneously moved urls from blog.earlh.com to earlh.com/blog so I needed to 301 all the old posts. I did that by getting this awesome wordpress post exporter script contributed by Mike Schinkel. I curled that to create a list of urls to forward, then built a tsv of pairs of old url\tnewurl. Then the below awk script will print nginx forward rules:

1
cat posts.tsv | awk -F"\t" '{print "\tlocation " $2 "{\n\t\treturn 301 " $1 ";\n\t\tbreak;\t}"'} | sed "s/http:\/\/blog.earlh.com//"

The rules look like:

1
2
3
4
location /index.php/2009/06/cleaning-data-in-r-csv-files {
        return 301 http://earlh.com/blog/2009/06/29/cleaning-data-in-r-csv-files/;
        break;
}

Add them to your site nginx.conf file inside the server configuration block.

I’ll update with solutions for better image embedding.

C++ Is Horrific

I’m poking at some c++ after not touching it for a decade. c++11 has apparently gotten roughly as capable as java pre 2000; it now can create threads! But the error messages. Oh, the error messages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
$ clang++ -std=c++11 -stdlib=libc++ src/test.cpp
In file included from src/test.cpp:4:
In file included from /usr/bin/../lib/c++/v1/thread:93:
In file included from /usr/bin/../lib/c++/v1/functional:465:
/usr/bin/../lib/c++/v1/memory:1677:31: error: calling a private constructor of class 'std::__1::thread'
            ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
                              ^
/usr/bin/../lib/c++/v1/memory:1604:18: note: in instantiation of function template specialization
      'std::__1::allocator<std::__1::thread>::construct<std::__1::thread, const std::__1::thread &>' requested here
            {__a.construct(__p, _VSTD::forward<_Args>(__args)...);}
                 ^
/usr/bin/../lib/c++/v1/memory:1488:14: note: in instantiation of function template specialization
      'std::__1::allocator_traits<std::__1::allocator<std::__1::thread> >::__construct<std::__1::thread, const std::__1::thread &>' requested here
            {__construct(__has_construct<allocator_type, pointer, _Args...>(),
             ^
/usr/bin/../lib/c++/v1/vector:1471:25: note: in instantiation of function template specialization
      'std::__1::allocator_traits<std::__1::allocator<std::__1::thread> >::construct<std::__1::thread, const std::__1::thread &>' requested here
        __alloc_traits::construct(this->__alloc(),
                        ^
src/test.cpp:36:13: note: in instantiation of member function 'std::__1::vector<std::__1::thread, std::__1::allocator<std::__1::thread> >::push_back'
      requested here
    threads.push_back(t);
            ^
/usr/bin/../lib/c++/v1/thread:261:5: note: implicitly declared private here
    thread(const thread&);
    ^
1 error generated.

what was the cause of this monstrosity?

1
2
3
4
std::vector< std::thread > threads;
// [...]
std::thread t(thread_func, i);
threads.push_back(t);

so yeah, you can’t copy thread objects, enforced by having a private constructor. Still, the amount of knowledge it takes to translate from the error message to the error is pretty amazing.

Replacing Sort | Uniq

A code snippet: when poking at columnar data in the shell, you’ll often find yourself asking questions like what are the unique values of a particular column, or the unique values and their counts. R would accomplish this via unique or table, but if your data is largish it may be quite annoying to load into R. I often use bash to quickly pick out a column, ala

pick out a column
1
$ cat data.csv | awk -F, '{print $8}' | sort | uniq -c | sort -r -n

In order: bash cats my data, tells awk to print just column 8 using , as the separator field, sorts all the data so that I can use uniq, asks uniq to print the counts and then the unique strings, then sorts by the counts descending (-n interprets as a number and -r sorts descending). The obvious inefficiency here is if your data is a couple of gb, you have to sort in order for uniq to work. Instead, you can add the script below to your path and replace the above with:

pick out a column
1
$ cat data.csv | awk -F, '{print $8'} | count

not only is this a lot less typing, but it will be significantly faster since you don’t have to hold all the data in ram and sort it.

replace sort | uniq
1
2
3
4
5
6
7
8
9
10
#!/usr/bin/ruby

# replaces sort | uniq -c
cnts={}
$stdin.each{ |i|
  cnts[i] = 1 + (cnts[i] || 0)
}

cnts.sort_by{ |word, cnt| -1*cnt }.
    each{ |word, cnt| puts "#{cnt}\t#{word}" }

Hiring Software Engineers

I perpetually see employers, on hacker news and elsewhere, complaining about difficulty hiring. I haven’t had such issues, so a (perhaps bold) guide to hiring software engineers:

  1. are you paying market salaries?
    1. are you really paying market salaries, or are employees supposed to join your company because you’re a special snowflake?
    2. even if you are paying market, why should an employee go to your firm? What is the upside to them for leaving a boss and company that they know? Because it would be really convenient for you, the hirer, is not a good answer.
  2. do you make the interviewing process decent, or do you scatter caltrops in front of potential employees?
    1. good employees do not need to crash study then regurgitate graph algorithms that your company never uses on the whiteboard. They also have jobs and value their vacation time and don’t care to spend a week consulting for you.
    2. how long does it take you to respond to resumes that come in? You should be able to say yes/no/maybe within 2 business days. Do your recruiters / interviewers actually read the cover letters / resumes? Last time I changed job a big sf / yc startup let my first interviewer roll into the interview room just shy of 20 minutes late without having read my resume. That’s a complete dick move, and it’s part of why I turned them down.
    3. when potential employees send you github links, do you have an engineer actually bloody look at them (almost never in my experience)?
    4. do you actually expend effort to meet potential employees and grow a bunch of warm leads, or do you wait until 3 weeks before you want someone to start then gripe because you can’t convert cold leads in 1 week plus a 2 week resignation period for their current employer?
    5. do you use shit software like that jobvite bullshit that badly ocrs then expects me to hand proof their shitty ocr job, or do you directly accept pdf resumes?
    6. for the love of god, I do not have a copy of ms word and wouldn’t take one if it were free. I will not put my resume into word format.
  3. do you take some pains to grow employees?
    1. do you hire people out of university? Take a chance on people?
    2. Like one of my former employers, do you do a good job hiring new grads from schools besides stanford / berkeley / mit / cmu, but then 18 months in after employees have demonstrated their value refuse to bring them up to market rates and lose them?
  4. when you send out offers, do you actually put out a good offer or do you throw numbers out that are 10% or more under your ceiling then expect employees to negotiate hard with you? I just turned down an sf startup because they did this; the ceo who successfully hired me said, “Earl: when I was an employee I hated negotiating, so I’m going to make you a great offer. This also means I’m not going to negotiate.” And you know what? It was a great offer, and I said yes the next morning. It also avoids starting your new job after a confrontational exercise.
  5. if you have recruiters contacting people, do you have them make clear they’re internal not external?
    1. do your recruiters actually read peoples’ linkedin profiles before contacting them? I used rails a bit 3 employers ago and had to remove that word from my profile because I got spammed with rails stuff.
  6. do your job postings on linkedin, craigslist, message boards, and your website tell potential employees why he or she should work for you, or like the vast majority, is it simply a long list of desiderata?
  7. just like the easiest sale is an upsell to a customer you have, the easiest recruit is the good employee you already have that you keep happy and prevent from leaving
    1. like Rand says, do you know off the top of your head the career goals of your employees? What are you doing to help them get there?
    2. do you give your employees raises to keep them at or above market, or can they get a $20k raise by swapping companies? If that raise is on offer, exactly why should they continue to work for you?
    3. on that note… 0.2% of an A round company isn’t golden handcuffs. It’s more like paper handcuffs.

Moving to Octopress

I finally got tired of wordpress, and I’m trying out octopress. If you have a blog, I think you would probably also be happier using octopress.

Reasons to switch:

  • wordpress doesn’t just work; it takes endless supervision. This is complicated by the seeming inability to get only security related updates, so I always feel forced to stay on the version treadmill for security reasons. This frequently breaks plugins.
  • wordpress treats security as an afterthought. For instance, the first thing you may think of is locking down the wp-admin directory to your home ip, but last time I tried this breaks the site.
  • php is security-hole ridden junk. This seems to have improved over the years but I’m still a little uneasy about using it, whereas only serving static html should be very secure and only require a single serving program making it much easier to keep up with security.
  • serving php with nginx is fragile; there’s multiple ways to set it up and none of them seem to work particularly reliably
  • there’s always 10 plugins to do any given task, none of which fully work or fully integrate with wordpress. I tried to get markdown working with wordpress last weekend and it was a nightmare
  • wordpress is slow, and caching plugins are brittle; serving static html from octopress should be lightning fast.
  • octopress comes with a bunch of nice features like syntax highlighting that doesn’t require loading 15 different javascript files ala the syntax highlighter I’m using

Reasons I want to switch:

  • I really like the idea of serving a static site and deploying with rsync
  • I like using git to version my site and vim to write posts

I will miss comments, but I hope people will email instead. That said, of the nearly 20,000 comments my site has received I believe fewer than thirty weren’t spam. In fact, wordpress has a whole cottage industry selling a comment spam control tool called Akismet created to fix how easy wordpress makes comment spam.