Yellowstone Stories

We saw more elk around human habitats
in Yellowstone than in the wild.

For our one-year anniversary, Simiao and I went hiking in Yellowstone.  I'd always wanted to visit this national park, and I've never seen so many alien landscapes in such close proximity to each other:  thermal features, beautiful canyons and waterfalls, wildlife, petrified trees, and black obsidian beaches. If you decide to go to Yellowstone, I highly recommend that you go in the first week of the off-season.  Lower prices notwithstanding, the size of the parking lots gave me an idea of what a zoo the park must be during the summer with traffic jams, impossible parking and screaming children.  When we went in the first week of October it felt like we had the whole park to ourselves.

These are a few of my favorite photos.  I do have more related to an awesome side project I've been working on for almost a year now, but it's still not ready and needs some more work.  It'll be awesome when it's ready, trust me!

A toothpick-like tree at the Grand Prismatic Spring.

Watching this spooting thermal feature at the Artist's Paint Pots was like watching a natural lava lamp.

A squirrel fattening up for the coming winter.

The obsidian beach at Yellowstone Lake, the world's highest alpine lake.

A trio of fluffy gray jays were stalking us around Yellowstone Lake.

A fiery sunset over Great Fountain Geyser, which declined to erupt for the occasion.

A tree grows on top of a petrified tree stump on an incredibly steep trail on Specimen Ridge.

A view of the Lamar Valley from Specimen Ridge.

Utah Stories

If you find yourself exploring a national park,
 please don't feed the wildlife.  Someone
further up the trail fed this
golden-mantled ground squirrel
a piece of hard candy.  It was eating
the wrapper along with the food.

Simiao and I recently took a vacation to Utah to explore Bryce Canyon and Zion National Park.  I've always loved the scenery of the American Southwest and I relished the opportunity to scramble around on some very photogenic sandstone.

My favorite hike was the Virgin River Narrows, and if you are considering doing this hike you should definitely rent neoprene socks, a pair of hiking sticks and water hiking shoes from one of the local outfitters.  You won't regret it.  I saw dozens of people struggling, slipping and falling along that trail.  My favorite scenery, however, was in Upper Coyote Butte, which I could have wandered around and explored for days.

The landscapes in Bryce Canyon, Zion, Coyote Butte and White Pocket are absolutely incredible.  I wish I could have taken a photo that would convey the beauty of the southwest.  Unfortunately, I don't consider myself a great landscape photographer, so I prefer to take pictures of things that perhaps not every single tourist that has ever passed through the park has seen.  I've included some favorites here.

Sunset over the hoodoos at Bryce Canyon.  Sadly, I forgot to bring my timer for this trip so I was unable to take star-trail pictures over the rock formations.

Plaintain Goldenweed over Bryce Canyon. 

I can't do landscapes, but I thought this tiny arch and bonsai-sized Juniper tree were a perfect microcosm of Upper Coyote Butte.  Note the Moqui marbles in the sandstone.

A Great Basin Spadefoot tadpole living in a puddle at Upper Coyote Butte.  Remarkably, there were also at least two kinds of shrimp living in this same pool, tadpole shrimp and clam shrimp.

We startled this Desert Spiny Lizard which preferred to glare at us from under a rock and behind a dead Juniper.

This Pallid-Winged Grasshopper didn't appreciate my picking it up for a photo, and repeatedly bit me until I shooed it off my finger.

The sandstone here resembled a tubular wave that was turned to stone by the gaze of a surfing Medusa.

A 3D Printable Model of Cloud Gate aka "The Bean"

There are few works of modern art as beloved as Chicago's Cloud Gate, aka "The Bean".  It is interactive without having any moving parts, and indeed without being mobile at all.  Nobody at any age can resist engaging with their reflection in its curiously curved surface.

I started playing with TinkerCad because I wanted to use the 3D printer at work, a Makerbot Replicator, to print custom enclosures for my other electronics projects.  I thought that printing a model of Cloud Gate would be an easy way to learn to use the system before building my enclosures.  It turns out that I had it completely backwards.  To print an enclosure out of basic shapes (cylinders and boxes) is many times easier than designing your own custom surface for printing, and it took me a very long time to finally get it right.

I learned a few things about Cloud Gate as I worked on this model:

• Cloud Gate as seen from above is not a perfect ellipse.
• Wikipedia and all other sources including Anish Kappor's own website as the dimensions of Cloud Gate wrong.  In particular, the height of the arch.  You only need to stand under the arch to see that there is no way that it is 12 feet high.  At most, it might be 10.
• It is not possible to continuously deform a sphere into Cloud Gate.  Its derivatives are discontinuous at certain points on the surface, so I had to resort to Bezier curves to model it.

I am 6' 1" tall.  There is no way that the arch is 12 feet tall.  If I put my hand straight up, I can come within a foot of touching the arch.

Once I finally got the right form for the equations that generate the model, it was simply a matter of tuning the constants that generate the surface to match Cloud Gate as closely as possible.  I'm confident that my current version of the model is close enough that, while certainly not an exact copy, nobody would be able to tell the difference even if I scaled mine to the size of the real thing and put them side-by-side.

The evolution of the model.  The earliest model was printed in 2 separate pieces connected with pegs before I realized that the model prints fine when it is printed upside-down with supports and a raft.

The underside of the models.  I think that they look better printed at standard resolution because the natural color PVA comes out shinier.

The model is well-balanced enough that it does not require a stand to sit normally.

End-on, Cloud Gate has an egg-like shape.

The underside of the model showing the omphalos, or navel.

I recommend printing the model upside-down using supports and rafts, 25% infill and standard quality.  The supports are straightforward to remove using a razor blade.  The higher infill is necessary because the flat surfaces have a tendency to sag a bit at lower infill, and the standard quality prints with a larger radius and gives a shinier result.

It's also pretty fun to take my shape generator on TinkerCad and play with your own variant of Cloud Gate by editing the parameters.  If I feel bold later, I may try having one 3D printed in steel then buffing it to a mirror finish for the ultimate desktop Cloud Gate.

Download the model or printable STL files here:

• Cloud Gate on TinkerCAD, with source code for the shape generator.
• Cloud Gate on Thingiverse, with instructions and downloadable STL file.

Bayesian Network Reconstruction Using Systems Genetics Data: Comparison of MCMC Methods

Several former colleagues and I collaborated on a paper that was finally published in Genetics on January 28.  You can read it for free online here.

I won't regurgitate the entire work here, but I did want to take a moment to say why this research is important for many fields, not just genetics.  In fact, the Bayesian network reconstruction problem arises in numerous places including finance, machine learning, and crystallography.  The premise of it is this:  suppose you had a black box that, based on some inputs that are supplied to it, would perform a possibly random calculation and then give some results back to you.  Now it is your job to figure out how the machine works.  How are the outputs related to the inputs, and more importantly what is the underlying calculation that happens to produce these outputs?  Keep in mind that this machine could be doing nearly anything under the hood:  performing entirely different calculations based on one input, rolling dice and giving a random result, or throwing your inputs out entirely.

To computational biologists right now, the cell is such a black box.  We are able to measure a lot of things about it and do a lot of things to it, but we are unable to actually look at all of the things that are happening inside a cell in real time.  Not only are they happening at really fast timescales, we don't have microscopes capable of watching all of the relevant interactions that happen inside a cell at once, for example DNA unwinding, RNA synthesis, ribosomes making proteins, protein folding, protein-protein and extra-cellular interactions.  As a result, we are left measuring things such as single-nucleotide polymorphism and expression data and then trying to infer how the genes in the cell worked after the fact.

How we reconstruct a cell's regulatory network is remarkably naive:   we construct a completely random network, tweak it to make it more plausible (e.g., simulated annealing or gradient descent), and then repeat this many many times.  Finally, we propose that the links in the resulting networks that appeared most often are likely to be the true connections in the real network.

This isn't a perfect approach, but it has yielded new insights in the past.  Perhaps someday someone will come up with a greatly improved approach to reconstructing Bayesian networks, and it will be a boon to technology and mankind worthy of a Nobel prize.

Nash Equilibrium in the Sealed-Bid Senior Auction

At work we've been thinking a lot about auction theory, and I was challenged to solve for the Nash equilibrium in the sealed-bid senior auction.  I found the solution and I think the result is pretty interesting, but before I get to that point I want to give some background about what an auction is and this scenario in particular.

An sealed-bid auction is in its purest sense a game played between a number of bidders who all would like an item and would like to pay as little as possible for it to maximize their profit.  Unlike an auction like eBay where the current hammer price is public knowledge, in the sealed-bid auction every bidder will write down how much they want to bid for the item.  The auctioneer will then collect all of these secret bids and select the highest bid to be the winner¹.  Nobody has a chance to change their bid after they pass the auctioneer their secret bid.

It's crucial to understand what a Nash Equilibrium is, and why it's important.  Simply put, a Nash equilibrium strategy is a strategy such that if it was known that all other bidders were following this strategy, then it would not be optimal to deviate from the strategy.  A kind of Nash equilibrium is a dominant strategy, where all bidders should follow the dominant strategy regardless of what the other players were doing.

Let's start with a familiar example of a dominant strategy:  the second-price auction.  In a second-price auction, the highest bidder wins but only pays as much as the second-highest bidder.  An example of this is an eBay auction.  In a second-price auction, the dominant strategy is to bid your valuation v of the item at auction.  In the case where you lose the auction, you pay nothing and gain nothing.  In the case where you win the auction, you get the item (with value v) and you pay the second-highest bidder's bid (which we will call b for now).  Your profit is then v - b, and is maximized because if you had bid less than b then you wouldn't have won the auction, if you bid between b and v then you are indifferent because you would have paid b and made profit v - b anyway, and if you had bid more than v you might have actually lost money because you would have paid more than the item is worth to you if the second bidder had bid higher than v.  Thus, no matter what, even if you knew that everyone else was going to bid zero, you would still bid your valuation of the item in the second-price auction.

The first-price sealed-bid auction, on the other hand, does not have a dominant strategy.  In a first-price sealed-bid auction, the highest bid wins the item and pays their bid exactly.  In this case, bidding my valuation v is actually not a good idea:  I will never make a profit!  If I lose, I get nothing, and if I win, my profit is my valuation v minus my bid v, which is zero!

In fact, in the first-price sealed-bid auction, the best strategy actually depends on the distribution of valuations of the item in question.  That is, if I thought everyone valued the item between $0 and $1 with a uniform distribution, then the optimal strategy would be different than if everyone valued the item in a normal distribution around $0.50.  It becomes even more complicated in the case where I am uncertain in my appraisal of the item, in which case I must consider the winner's curse!

I will sidestep all of this complexity by asserting that in every case I study below, the bidders all know that every bidder's valuation of the item is selected from a uniform distribution between 0 and 1, and that every bidder knows how many other bidders there are.  The solutions below are only applicable given this assertion.

In the first-price sealed-bid auction, the ideal bid would be only slightly higher than the second place bidder's bid.  Naively, I will make the zero-order guess that all bidders will actually bid their valuation except for the one who actually does the math.  Now I'd like to know the bid that maximizes this privileged bidder's profit, which is the maximum of the expectation value of profit given a particular bid b, valuation v and number of bidders N.  So,

Equation 1:  Expected profit in the uniform-distribution first-price sealed-bid auction assuming that all bidders except one privileged bidder bid their value.

The first term is the profit if the privileged bidder wins with bid b, and the second term is the probability that all other bidders had valuations and bids less than b.  The expected profit is maximized if the first derivative is zero²

Equation 2:  Solving for the the maximum expected profit in the uniform-distribution first-price sealed-bid auction, if all bidders but one bid their valuation

It is now straightforward to solve for the optimal bidding strategy.

Equation 3:  I will show that this is the Nash equilibrium strategy in the uniform-distribution first-price sealed-bid auction.

I made a crucial assumption above:  that every other player would bid their valuation.  A strategy is only a Nash equilibrium if the strategy would be optimal given that everyone else is using the strategy.  If everyone were using this bidding strategy, would it be worthwhile to deviate?  To find out, I can substitute this bidding strategy into the profit term in equation 1 and solve again.  Now, all of the other bidders are using the strategy in Equation 3.  Can our privileged bidder do better?  The first term in Equation 1 remains the same:  the profit will just be his value minus his bid.  However, the probability that a bidder wins with this bid has changed because everyone else's value could actually be somewhat higher, v = N b / (N - 1).

Equation 4:  Solving for the maximum profit in the uniform-distribution first-price sealed-bid auction, if all other players bid the Nash equilibrium.

Just like in equation 2, I can solve for the new optimal strategy.  It should be obvious that the optimal bid, which is just the solution to

is just the same as equation 3.  Therefore, equation 3 is the Nash equilibrium.


I can now calculate the winner's expected profit in equilibrium by substituting equation 3 into equation 4, yielding

Equation 5:  The expected profit given that all players bid rationally in the uniform-distribution first-price sealed-bid auction.

It turns out that equation 5 is something more universal than might be expected.  The Revenue Equivalence Theorem tells us that as long as we set the rules of the auction so that the highest bidder wins the item and a bidder with value 0 has an expected profit of 0, all sealed-bid uniform-distribution auctions will have the same expected profit as in equation 5!

For example, let's consider an all-pay auction.  In an all-pay auction, every bidder pays their bid but only the highest bidder goes home with the item.  Obviously, a bidder should bid less than in the first-price auction above because their risk is higher: a bidder will always pay his bid but may not actually get the item to show for it.  As long as a bidder's valuation is more than zero, then he should bid more than zero because there is a small chance that he could get a spectacular deal on the item!  How much, exactly, should a bidder bid?

I'll solve this with the revenue equivalence theorem.  The revenue equivalence theorem tells me that the expected profit must be the same as in Equation 5, because the highest bidder still wins the auction and a bidder with the lowest valuation, 0, will simply walk away from the auction neither profiting nor paying.  Therefore, equation to solve is:

The left hand side of the equation comes from the revenue equivalence theorem.  The right hand side is justified as follows:  if a bidder has the highest valuation v (and therefore the highest bid), then he gets the item and recovers value v.  All bidders always pay their bid, b, in the all-pay auction so that value is simply subtracted.   This is trivially solved:

Equation 6:  The Nash equilibrium bid in the uniform-distribution all-pay sealed-bid auction.

Now I am ready to tackle the original challenge:  the Senior Auction.  In the Senior Auction, the first-place and second-place bidders both pay, but nobody else does.  Like all other auctions discussed here, the highest bidder will still be the one who takes home the item.  A rational bidder should bid at least as much in the all-pay auction because their risk is lower, and should bid less than in the first-price auction because their risk is higher.  Let's find out exactly how much using the Revenue Equivalence Theorem.

This should be fairly straightforward to solve.  The profit for the highest bidder is v - b, and the cost for the second-highest bidder is their bid b.  Thus, I have:

Which is just

This is straightforward to solve for b in terms of v:

Equation 7:  The Nash equilibrium bid in the uniform-distribution sealed-bid senior auction.

For example, let's take a look at the Nash equilibrium bid in the first-price, all-pay and senior auction for 10 bidders.

Figure 1:  Nash equilibrium bid as a function of valuation in three different types of auction, given 10 bidders with uniform valuations on [0,1]. 

Figure 1 shows two things that give us confidence in the result from equation 7.  A rational bidder always bids at least as high in the senior auction as in the all pay auction, and never bids more than in the first price auction.  This makes sense because the bidder's risk in the senior auction is higher than in the first price auction, but lower than that in all pay.  Another comforting observation in equation 7 is that for N = 2, the result is exactly the same as in the all pay auction as would be expected.

I'd like to verify that this is actually a Nash equilibrium by inverting equation 7, substituting back into the expected profit function and taking the first derivative, but that is algebraically cumbersome.  Instead, I will employ a computer algebra system, wxMaxima, and verify that the solution is a Nash equilibrium for some chosen values.  In my Maxima notebook (download here), I require both bid(v, B), which is the putative equilibrium bid given valuation v and number of bidders B and value(b, B), which inverts bid(v, B) with respect to valuation. The function ExpectedWinnings(b, v, N, B) gives the expected winnings in a top-N-pay auction given bid b, valuation v, N the number of top bidders who pay their bid, and the number of bidders B.  The 
expression solve(diff(ExpectedWinningsAllPay(b, v, B), b), b) determines the optimal bid b by solving 

given that all other bidders engage in the strategy prescribed by bid and value.  If the result is the same as bid, then bid is a Nash equilibrium because there is nothing to be gained from deviating from this strategy given that everyone else is using it.

If you execute my wxMaxima notebook yourself, you will see that Equation 7 is indeed a Nash equilibrium for the chosen valuation and number of bidders, so it is empirically true that Equation 7 is the Nash equilibrium for the uniform-distribution sealed-bid senior auction.

¹ Not all kinds of sealed-bid auctions give the item to the highest bidder, and not all kinds of sealed-bid auctions require that each bidder places only one bid.  For all examples here, the highest bidder wins.  Interested parties might read about unique bid auctions.


² Actually, it may be maximized or minimized. A more thorough person would check the second derivative to determine whether he found a local maximum or a local minimum. This is an exercise left to the reader.