Russell O’Connor’s Blog2017-06-16T11:45:46ZRussell O’Connorhttp://r6.ca/http://r6.ca/blog/http://r6.ca/blog/20170616T114546Z.htmlSome Random Thoughts of an Advanced Haskeller2017-06-16T11:45:46Z2017-06-16T11:45:46Z
<p>Recently I was thinking about a programming problem that would need access to random values.
I thought it might be fun to write up my though process as an advanced Haskeller while working through this particular problem.
</p><p>In Haskell, one would write such a program by using a random monad to access an oracle providing random numbers.
The traditional way to implement <code>MonadRandom</code> is using the state monad.
The <code>Gen</code> type holds the state of the (pseudo-)random number generator, and the <code>randomInt</code> function returns a new random number and updates the state of the generator.
</p><pre>type Random a = State Gen a
randomInt :: Gen -> (Int,Gen)
randomOracle :: MonadRandom Int
randomOracle = state random</pre>
<p>Then I write my program inside the Random monad, making calls to the <code>randomOracle</code> as needed
</p><pre>myProg :: Random Result
myProg = do
{- ... -}
x <- randomOracle
{- ... -}
y <- randomOracle
{- ... -}</pre>
<p>In order to run my program, I need to provide it with a random seed.
</p><pre>evalRandom :: Random result -> Gen -> result
evalRandom = evalState</pre>
<p>For deterministic testing, we can pass fixed generators to <code>evalRandom</code>.
If we use <code>StdGen</code>, we can map our <code>Random</code> program to <code>IO</code> and use the system random number generator.
</p><pre>type Gen = System.Random.StdGen
randomInt = System.Random.random
evalRandomIO :: Random result -> IO result
evalRandomIO = getStdRandom . runState</pre>
<p>For the most general possible random number generator, the type for the generator state is simply an infinite stream of random values.
</p><pre>data Stream a = Cons a (Stream a)
unfoldStream :: (g -> (a, g)) -> g -> Stream a
unfoldStream next = go
where
go seed = Cons value (go nextSeed)
where
(value, nextSeed) = next seed
type Gen = Stream Int
randomInt (Cons hd tl) = (hd, tl)
evalRandomStdGen :: Random result -> StdGen -> result
evalRandomStdGen rr = evalRandom rr . unfoldStream System.Random.random
evalRandomIO :: Random result -> IO result
evalRandomIO rr = evalRandomStdGen rr <$> newStdGen</pre>
<p>Before, when I was an intermediate Haskeller, I would probably stop at this point pretty satisfied with this.
And let me be clear that this is a fine solution.
However, now that I am an advanced Haskeller, I cannot help but feel a little dissatisfied with this solution.
The problem with this implementation of the <code>Random</code> monad is that the type is too broad.
Since the <code>Random</code> type is the <code>State</code> monad, there are operations allowed by the type that should not be allowed for a <code>Random</code> program.
For instance, within the <code>Random</code> type, someone could store the state of the generator and restore it later causing random values to be replayed, or someone might completely replace the state of the generator with their own value.
</p><p>One way to solve this problem is to use Haskell’s module system to abstract the monad and only expose the <code>randomOracle</code> operation.
While this is a reasonable solution (in fact it is a very good solution as we will see), it would be nicer if we could instead use the type system to create a monad that is only capable of representing the programs we want to allow, and disallows other programs that would try manipulate the generator state in ways we do not want.
Essentially we want our <code>Random</code> programs to only be able to query the random oracle, and that is it.
After reflecting on this problem and the various kinds of monads I know about, I realized that the a suitable free monad captures exactly this notion of providing only an operation to query the random oracle.
Specifically we want <code>Control.Monad.Free.Free (Reader Int)</code> or more directly (but more obtusely written) as <code>Control.Monad.Free.Free ((->) Int)</code>.
We truly want a free monad because any sequence of responses from the random oracle is valid.
</p><p>One problem with this <code>Free</code> monad is that the bind operation can be slow because it needs to traverse through a, possibly long, data structure.
There are several solutions to this, but for this particular free monad, I happen to know that the <a title="van Laarhoven Free Monad" href="20140210T181244Z.html">Van Laarhoven free monad representation</a> is possible:
The type <code>forall m. Monad m => m Int -> m a</code> is isomorphic to <code>Control.Monad.Free.Free ((->) Int) a</code>.
</p><pre>newtype Random a = Random { instantiateRandom :: forall m. Monad m => m Int -> m a }
instance Monad Random where
return a = Random $ \_ -> return a
ma >>= mf = Random . runReaderT
$ ReaderT (instantiateRandom ma) >>= ReaderT . instantiateRandom . mf
instance Applicative Random where
pure = return
(<*>) = ap
instance Functor Random where
fmap = liftM</pre>
<p>In this representation, the random oracle function just fetches the argument.
</p><pre>randomOracle :: Random Int
randomOracle = Random id</pre>
<p>For deterministic testing purposes we can evaluate the random monad by instantiating it with our state monad from before.
</p><pre>evalRandom :: Random result -> Stream Int -> result
evalRandom rr = evalState . instantiateRandom rr . state $ \(Cons hd tl) -> (hd, tl)</pre>
<p>However, we can also directly instantiate it with the <code>IO</code> monad for production purposes.
</p><pre>evalRandomIO :: Random result -> IO result
evalRandomIO rr = instantiateRandom rr evalRandomIO</pre>
<p>This is all very good; however, the advanced Haskeller in me still thinks that I ought to be able to write <code>evalRandom</code> without the need to invoke the <code>State</code> monad.
This is because if we were actually using the <code>Free ((->) Int</code> monad, I would be writing <code>evalRandom</code> using <code>iterA</code>.
</p><pre>iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a
evalFreeRandom :: Free ((->) Int) result -> Stream Int -> result
evalFreeRandom = iterA (\fpa (Cons hd tl) -> fpa hd tl)</pre>
<p>No need for any state monad business in <code>evalFreeRandom</code>.
How can I get that elegant solution with the Van Laarhoven free monad?
One way would be to convert to the <code>Free ((->) Int)</code> representation
</p><pre>freeRandom :: Random result -> Free ((->) Int) result
freeRandom rr = instantiateRandom rr (liftF id)
evalRandom :: Random result -> Stream Int -> result
evalRandom = evalFreeRandom . freeRandom</pre>
<p>Surely there must be a way to do this directly?
</p><p>Before solving this I turned to another interesting problem.
The <code>iterA</code> function recurses over the free monad structure to do its evaluation.
The <code>Free</code> monad comes with its own general recursive elimination function called <code>foldFree</code>
</p><pre>foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a</pre>
<p>This <code>foldFree</code> function is captures everything about the free monad, so it should be possible to write <code>iterA</code> by using <code>foldFree</code> to do all the recursion.
But how is that even possible?
The types of <code>foldFree</code> and <code>iterA</code> look too far apart.
<code>foldFree</code> requires an natural transformation as input, and the arguments to <code>iterA</code> provide nothing resembling that.
</p><p>To solve this I turned to the <kbd>#haskell</kbd> IRC channel for help.
With assistance from glguy, ReinH, and byorgey, I turned the well known idea that if you want turn something to or from a natural transformation you use some sort of Yoneda / continuation like construction.
In this particular case, the <code>Cont (p a)</code> monad seems to capture what we need.
Following the types (and forgetting about the semantics) we end up the following.
</p><pre>iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a
iterA h ff = runCont (foldFree (\fx -> Cont $ \k -> h (k <$> fx)) ff) pure</pre>
<p>As an aside, <a title="myIterA" href="http://lpaste.net/356001">glguy has a more “natural” solution</a>, but it technically has a less general type, so I will not talk about here, even if I do feel it is better.
</p><p>Turning back to our original problem of directly writing <code>evalRandom</code> without using the state monad, we can try to see if <code>Cont</code> will solve our problem.
</p><pre>evalRandom :: Random result -> Stream Int -> result
evalRandom rr = runCont (instantiateRandom rr (Cont $ \k (Cons hd tl) -> k hd tl)) const</pre>
<p>We can compare the <code>Cont</code> solution to the <code>State</code> solution and see that the code is pretty similar.
</p><pre>evalRandom :: Random result -> Stream Int -> result
evalRandom rr = evalState (instantiateRandom rr (state $ \(Cons hd tl) -> (hd, tl)))</pre>
<p>The inner <code>Cont</code> construction looks very similar to the inner <code>state</code> construction.
The outer call to <code>const</code> in the <code>Cont</code> solution discards the final "state" which captures the same functionality that <code>evalState</code> has for the <code>State</code> solution.
Now we can ask, which has better performance, the <code>State</code> solution, with its tupling and untupling of values, or the <code>Cont</code> solution which uses continuations instead?
I will leave it to the GHC experts to figure that one out.
</p><p>Arguably most of this is an exercise in academics, but it only took me a hour or three to go through this whole thought process.
As an advanced Haskeller, I have slowly gathered, over many years, experience with these sorts of abstractions so that it starts becoming easy to do this sort of reasoning.
While it may or may not matter much for my particular application, eventually this kind of reasoning becomes important.
For example, the modern stream fusion in GHC exploits constructions that resemble this kind of reasoning, and that has had a big impact on performance.
</p><p>For the non-advanced Haskellers out there, do not be deterred.
Keep practicing your craft; keep reading about new abstractions, even if you do not fully get it; keep looking out for potential applications of those abstractions to solidify your understanding.
Eventually you will have lots of very powerful problem solving tools at your disposal for making safe software.
</p>http://r6.ca/blog/20151210T033709Z.htmlBell’s Casino Solution2015-12-10T03:37:09Z2015-12-10T03:37:09Z
<blockquote>
<p><a href="20150816T185621Z.html">Bell’s Casino Problem</a></p>
<p>A new casino has opened up in town named “Bell’s Casino”. They are offering a coin game. The game works as follows.
</p>
<p>The house will commit two coins on the table, oriented heads or tails each, and keep them covered. The player calls what the faces of the each of the coins are, either HH, HT, TH, or TT. The
casino reveals the coins and if the player is correct, they win $1, and otherwise they lose $1.
</p>
<dl>
<dt>Problem 1.</dt>
<dd>Prove that there is no strategy that can beat the casino.</dd>
</dl>
</blockquote>
<p>Solution to problem 1.
</p><p>Let <var>p</var><sub>HH</sub> be the probability that the casino orients the coins as HH, and similarly for <var>p</var><sub>HT</sub>, <var>p</var><sub>TH</sub>, and <var>p</var><sub>TT</sub>.
We have <var>p</var><sub>HH</sub> + <var>p</var><sub>HT</sub> + <var>p</var><sub>TH</sub> + <var>p</var><sub>TT</sub> = 1.
If the player calls the orientations <var>X</var><var>Y</var>, the they win $1 with probability <var>p</var><sub><var>X</var><var>Y</var></sub>, and lose $1 with probability 1-<var>p</var><sub><var>X</var><var>Y</var></sub>.
This means the total expected value is 2*<var>p</var><sub><var>X</var><var>Y</var></sub> - 1 dollars.
The casino can minimize the players expected value by choosing each of the four possible orientations with equal proability of 25%.
In the case the players expected value is $-0.50 no matter what orientation they choose to call.
</p><blockquote>
<p>After opening the customers stop coming by to play this boring game, so to boost attendance the casino modifies the game as follows.
</p>
<p>The house will commit two coins on the table, oriented heads or tails each, and keep them covered. The player calls what the faces of each of the two coins are, either HH, HT, TH, or TT. The
casino reveals one coin, of the players choice. After seeing revealed coin, the player can elect to back out of the game and neither win nor lose, or keep going, and see the second coin.
If the player’s call is correct, they win $1, and otherwise they lose $1.
</p>
<dl>
<dt>Problem 2.</dt>
<dd>Prove that there is no strategy that can beat the casino.</dd>
</dl>
</blockquote>
<p>Solution to problem 2.</p><p>Without loss of generality, suppose the player calls HH and they ask for the first coin to be revealed.
With probability <var>p</var><sub>TH</sub> + <var>p</var><sub>TT</sub> the first coin is tails.
At this point the player’s best option is to elect to back out of the game as it is now impossible for them to win.
With probability <var>p</var><sub>HH</sub> + <var>p</var><sub>HT</sub> the first coin is heads.
At this point the player can back out or continue.
If the player always continues then they win $1 with probability <var>p</var><sub>HH</sub> and they lose $1 with probability <var>p</var><sub>HT</sub>.
Their total expected value is <var>p</var><sub>HH</sub> - <var>p</var><sub>HT</sub> dollars.
As before, the casino can choose each of the four possible orientations with equal proability of 25%.
In the case the players expected value is $0 if they chose to continue if the revealed coin is correct, and it is also $0 if they chose to always back out of the game.
No matter what strategy the player chooses, they cannot beat the casino as long as the casino chooses each of the four possible orientations with equal proability.
</p><blockquote>
<p>Even with the new, more fair, game, attendance at the casino starts dropping off again. The casino decides to offer a couples game.
</p>
<p>The house will commit two coins on two tables, oriented heads or tails each, and keep them covered. The couple, together, calls what the the faces of each of the two coins are, either HH, HT, TH, or
TT. Then, each player in the couple gets to see one coin each. Collectively they get to decide whether they are going to back out of the game or not by the following method. After seeing
their revealed coin, each player will raise either a black flag or a red flag. If both players raise the different colour flags, the game ends and no one wins or loses. If both players raise the
same colour flag, the game keeps going. If the couples original call was right, they win $1, and otherwise, they lose $1. To ensure that the couple cannot cheat, the two tables
are places far enough apart such that each player’s decision on which flag to raise is <a title="Space-like interval" href="https://en.wikipedia.org/wiki/Spacetime#Space-like_interval">space-like separated</a>. Specifically the tables are placed 179 875 475 km apart and
each player has 1 minute to decide which flag to raise otherwise a black flag will be raised on their behalf (or, more realistically, the tables are placed 400 m apart and each player has
100 nanoseconds to decide which flag to raise).
</p>
<dl>
<dt>Problem 3.</dt>
<dd>Prove that there is no strategy for the couple that can beat the casino.</dd>
</dl>
</blockquote>
<p>Solution to problem 3.
</p><p>Alice and Bob enter the casino together.
The casino covers two coins, and Alice and Bob call a random choice for the orientation of the coins.
Without loss of generality let us assume they call HH.
</p><p>Alice and Bob are separated by 179,875,475 km so they cannot communicate and simutaneously each of them see the value of one of the coins.
If Alice sees heads on her coin, she can raise a black flag with probability <var>a</var>, and a red flag with probability 1-<var>a</var>.
If she sees tails she can raise a black flag with probability <var>b</var>, and a red flag with probability 1-<var>b</var>.
The pair (<var>a</var>, <var>b</var>) characterizes any strategy that Alice could employ.
Similarly, if Bob sees heads on his coin can raise a black flag with probability <var>c</var>, and a red flag with probability 1-<var>c</var>,
and if he sees tails he can raise a black flag with probability <var>d</var>, and a red flag with probability (1-<var>d</var>).
So the quadruple (<var>a</var>,<var>b</var>,<var>c</var>,<var>d</var>) parameterizes all possible strategies that Alice and Bob can employ together.
</p><p>Given the strategy parameterized by (<var>a</var>,<var>b</var>,<var>c</var>,<var>d</var>) they win $1 if they raise the same colour flag if the coins are both heads.
The probability of this happening is <var>a</var><var>c</var> + (1-<var>a</var>)(1-<var>c</var>).
They lose $1 if they raise the same colour flag if any of the coins are tails.
The probability of that happening is <var>b</var><var>c</var> + (1-<var>b</var>)(1-<var>c</var>), <var>a</var><var>d</var> + (1-<var>a</var>)(1-<var>d</var>), <var>b</var><var>d</var> + (1-<var>b</var>)(1-<var>d</var>)
if only the first coin is tails, or if the second coin is tails, or if both coins are tails, respectively.
If the casino chooses the coins orientations with equal proability, their total expected winnings with their strategy is
</p><p><var>E</var> = (<var>a</var><var>c</var> + (1-<var>a</var>)(1-<var>c</var>) - <var>b</var><var>c</var> - (1-<var>b</var>)(1-<var>c</var>) - <var>a</var><var>d</var> - (1-<var>a</var>)(1-<var>d</var>) - <var>b</var><var>d</var> - (1-<var>b</var>)(1-<var>d</var>))/4.
</p><p>Theorem. If 0 ≤ <var>a</var> ≤ 1, 0 ≤ <var>b</var> ≤ 1, 0 ≤ <var>c</var> ≤ 1, 0 ≤ <var>d</var> ≤ 1, and we
let <var>E</var> = (<var>a</var><var>c</var> + (1-<var>a</var>)(1-<var>c</var>) - <var>b</var><var>c</var> - (1-<var>b</var>)(1-<var>c</var>) - <var>a</var><var>d</var> - (1-<var>a</var>)(1-<var>d</var>) - <var>b</var><var>d</var> - (1-<var>b</var>)(1-<var>d</var>))/4,
then <var>E</var> ≤ 0.
</p><p><a href="data:text/plain;base64,UmVxdWlyZSBJbXBvcnQgUHNhdHouDQpSZXF1aXJlIEltcG9ydCBSZWFscy4NCg0KT3BlbiBTY29wZSBSLg0KDQpHb2FsIGZvcmFsbCBhIGIgYyBkOlIsIDAgPD0gYSA8PSAxIC0%2BIDAgPD0gYiA8PSAxIC0%2BIDAgPD0gYyA8PSAxIC0%2BIDAgPD0gZCA8PSAxIC0%2BDQogIChhKmMgKyAoMS1hKSooMS1jKSAtIGIqYyAtICgxLWIpKigxLWMpIC0gYSpkIC0gKDEtYSkqKDEtZCkgLSBiKmQgLSAoMS1iKSooMS1kKSkvNCA8PSAwLg0KUHJvb2YuDQppbnRyb3MuDQphcHBseSAoUm11bHRfbGVfcmVnX2wgNCk7IFtscmF8XS4NCnVuZm9sZCBSZGl2Lg0KcmV3cml0ZSA8LSBSbXVsdF9hc3NvYy4NCnJld3JpdGUgUmludl9yX3NpbXBsX207IFt8bHJhXS4NCnBzYXR6IFIuDQpRZWQuDQo%3D">Proof by positivstellensatz</a>
</p><p>Let <var>G</var> = <var>b</var><var>c</var><var>d</var> + (1-<var>b</var>)(1-<var>c</var>)(1-<var>d</var>)
+ <var>a</var><var>b</var><var>d</var> + (1-<var>a</var>)(1-<var>b</var>)(1-<var>d</var>)
+ <var>a</var>(1-<var>c</var>)<var>d</var> + (1-<var>a</var>)<var>c</var>(1-<var>d</var>)
+ <var>a</var>(1-<var>b</var>)(1-<var>c</var>) + (1-<var>a</var>)<var>b</var><var>c</var>.
0 ≤ <var>G</var> because <var>G</var> is the sum of products of non-negative numbers.
But <var>E</var> = -<var>G</var>/4, so <var>E</var> ≤ 0.
QED.
</p><p>Thus no matter what strategy Alice and Bob use, they cannot expect to beat the casino.
At least that is what the casino thinks.
</p><blockquote>
<dl>
<dt>Problem 4.</dt>
<dd>Devise a physical procedure that a couple can follow to beat the casino on average at this last game without cheating.</dd>
</dl>
</blockquote>
<p>Solution to problem 4.</p><p>Alice and Bob enter the casino together.
Each of them have one of a pair of maximally entangled qbits.
For concreteness let say they are a pair of entangled photons, even though realistically they will use a different physical realization of their qbits.
</p><p>The casino covers two coins, and Alice and Bob call a random choice for the orientation of the coins.
Without loss of generality assume they call HH.
Currently they only have a 25% chance of being right. In order to shift the odds in their favour they need to substantially increase their odds of
dropping out of the game if they are wrong, but avoid dropping out if they are right.
</p><p>Alice and Bob are separated by 179,875,475 km so they cannot communicate and simutaneously each of them see the value of one of the coins.
Alice follows the following procedure.
If she see an H, she measures the polarization of her qbit at an angle of 0°.
If she sees a T, she measures the polarization of her qbit at an angle of -45°.
In either case, if her measurement is positive she raises a black flag and if her measurement is negative she raises a red flag.
In both cases she has a 50% chance of raising either flag.
</p><p>Bob follows the following procedure.
If he sees an H, he measures the polarization of his qbit at an angle of +22.5°.
If he sees a T, he measures the polarization of his qbit at an angle of +67.5°.
In either case, if his measurement is positive he raises a black flag and if his measurement is negative he raises a red flag.
In either case he has a 50% chance of raising either flag.
</p><p>Because their qbits are entangled, the flags they raise are correlated.
The probability of Alice and Bob raising the same colour flag is cos²(<var>θ</var>), where <var>θ</var> is the difference between their measurement angles.
</p><p>If both coins are heads, then the difference between their measurement angle is 22.5°, and the probability of them raising the same colour flag is
cos²(22.5°) = (2 + √2)/4 ≅ 85.4%.
</p><p>If one coin is heads and the other is tails, then the difference between their measurement angle is 67.5°, and the probability of them raising the same colour flag is
cos²(67.5°) = (2 - √2)/4 ≅ 14.6%.
</p><p>If both coins are tails, then the difference between their measurement angle is 112.5°, and the probability of them raising the same colour flag is
cos²(112.5°) = (2 - √2)/4 ≅ 14.6%.
</p><p>If the casino randomly selects the orientation of their coins with equal probability then Alice and Bob’s expected winnings is
((√2 + 2) - 3*(2 - √2))/16 ≅ $0.103, which is a positive amount.
</p><blockquote>
<p>The casino cannot figure out how they keep losing money on this game and, soon, Bell’s Casino goes bankrupt.</p>
</blockquote>
<p>This physical property that allows Alice and Bob to correlate their flags without communicating is called <dfn>quantum pseudo-telepathy</dfn>.
What surprised me the most is that Bob measurements are not quite aligned with Alice’ measurments.
I would have thought it was better that for Bob to measure at angles 0° and +45°.
</p><div class="figure"><img alt="graph of (cos²(θ) - 2×cos²(θ+45°) - cos²(θ+90°))/4" src="images/988c6064f2b5adf014bef7324c7ab700405aaec9ea2d5334d42d53e9ede06aee.svg"/><br/>Graph of expected value vs angle of Bob’s measurements.</div>
<p>If Bob measures at these angles then when the coins are HH, they are guarenteed to raise the same flag, and when the coins are TT, they are guarenteed to raise opposite flags, which is perfect.
However, when one is tails and one is heads, then they have a 50% chance of raising the same flag.
This makes their expected value 0.25*1 - 0.5*0.5 = $0, and they do not come out ahead.
But by having Bob rotate his measurements by a small amount, Bob can increase the chances of raising the different flags in case of HT or TH, while decreasing the chances of correctly staying or leaving the game in case of HH or TT.
Because of the geometry of the circle, Bob increases the chances of raising different flags in case of HT or TH faster than he decreases the chances of raising the correct flags in case of HH or TT.
If Bob makes measurements at angle φ and φ + 45°, then the optimal expected value occurs at φ = 22.5°.
</p>http://r6.ca/blog/20151116T042026Z.htmlStochastic Elections Canada 2015 Results2015-11-16T04:20:26Z2015-11-16T04:20:26Z
<p>It is time to announce the results from Stochastic Elections Canada for the 42<sup>st</sup> General Election.</p><p>Every vote counts with the <a href="20040603T005300Z.html">stochastic election process</a>, so we had to wait until all election results were validated and <a href="http://enr.elections.ca/JudicialRecount_e.aspx">certified</a> before we could announce our results.
However, stochastic election results are not very sensitive to small changes to the number of votes counted. The distributions for each candidate are typically only slightly adjusted.</p><p>Now that the last judicial recount has been completed, we can announce our <abbr title="member of parliament">MP</abbr> selection.</p><table class="election" summary="This table lists the number of seats each party could receive if the 2015 election used the stochastic election method">
<caption>2015 Stochastic Election Simulation Results</caption>
<thead>
<tr>
<th>Party</th>
<th>Seats</th>
<th>Seat Percentage</th>
<th>Vote Percentage</th>
</tr>
</thead>
<tbody>
<tr>
<td>Liberal</td>
<td class="number">139</td>
<td class="number">41.1%</td>
<td class="number">39.5%</td>
</tr>
<tr>
<td>Conservative</td>
<td class="number">105</td>
<td class="number">31.1%</td>
<td class="number">31.9%</td>
</tr>
<tr>
<td>NDP-New Democratic Party</td>
<td class="number">63</td>
<td class="number">18.6%</td>
<td class="number">19.7%</td>
</tr>
<tr>
<td>Bloc Québécois</td>
<td class="number">19</td>
<td class="number">5.62%</td>
<td class="number">4.66%</td>
</tr>
<tr>
<td>Green Party</td>
<td class="number">11</td>
<td class="number">3.25%</td>
<td class="number">3.45%</td>
</tr>
<tr>
<td>Christian Heritage Party</td>
<td class="number">1</td>
<td class="number">0.296%</td>
<td class="number">0.0870%</td>
</tr>
</tbody>
</table>
<p><a href="http://r6.ca/StochasticElection/2015Results.ods">Results by province and by riding are available (electoral districts on page 2).</a></p><p>The results were generated from <a href="http://enr.elections.ca/DownloadResults.aspx">Elections Canada data</a>. One hundred and seventy-four elected candidates differ from the actual 2015 election outcome.
</p><p>The Christian Heritage Party holds the balance of power in this parliament.
Assuming a Liberal party member becomes speaker of the house,
that means the Liberals together with the Bloc Québécois and Green Party have 168 votes and the Conservative and <abbr title="New Democratic Party">NDP</abbr> together have 168 votes.
In this case, it is the Christian Heritage Party vote that would break the tie.
</p><p>Unfortunately, Liberal leader Justin Trudeau with 52.0% of the vote in the riding of Papineau, still lost to Maxime Claveau of the Bloc Québécois with 12.2% of the vote.
Apparently it is now the Bloc Québécois’s turn to represent their support in Papineau.
If Justin Trudeau wants to be prime minister, his best bet is to try to be appointed to the Senate and rule from there.
Similarly <abbr title="New Democratic Party">NDP</abbr> leader Tom Mulcair lost to Liberal candidate Rachel Bendayan in the riding of Outremont.
Perhaps there is a deal to be struck between the Liberal and <abbr title="New Democratic Party">NDP</abbr> to get their leaders appointed to the Senate.
</p><p class="fine">This is only one example of the results of a stochastic election. Because of the stochastic nature of the election process, actual results may differ.
</p><p class="fine">In Canada’s election process, it is sometimes advantageous to not vote for one’s preferred candidate. The stochastic election system is the only system in which it always best to vote for your preferred candidate. Therefore, if the 2015 election were actually using a stochastic election system, people would be allowed to vote for their true preferences. The outcome could be somewhat different than what this simulation illustrates.</p><p>Related info</p><ul>
<li><a href="20151021T015605Z.html">2015 stochastic election expected results</a></li>
<li><a href="20110530T170250Z.html">2011 stochastic election results</a></li>
<li><a href="20081107T061447Z.html">2008 stochastic election results</a></li>
<li><a href="20060217T201200Z.html">2006 stochastic election results</a></li>
<li><a href="20060122T172700Z.html">2004 stochastic election results</a></li>
</ul>
http://r6.ca/blog/20151021T015605Z.htmlStochastic Elections Canada 2015 Update2015-10-21T01:56:05Z2015-10-21T01:56:05Z
<blockquote>
<p>The rule of the people has the fairest name of all, isonomia, and does none of the things that a monarch does. The lot determines offices, power is held accountable, and deliberation is conducted in public. — Herodotus</p>
</blockquote>
<p>In Athenian democracy, sortition was used to select their magistrates in order to avoid the oligarchs buying their way into the office. What would happen if we used a form of sortition to to select our parliament? Since most people are too busy and unprepared to sit in parliament, I propose the next best thing: the drawing of lots in a riding to select a person to chose the representative for the riding. What would happen?
</p><p>The <a title="Voting System" href="20040603T005300Z.html">resulting system</a> is a unique system that provides local representation and approximately proportional representation. Each party gets a chance to represent a riding in roughly proportion to the amount of support they have in the riding. Democracy means “rule of people”, not “rule of the majority” (nor “rule of the plurality”). Not only is it perfectly democratic for the minority to get an opportunity to be represented in parliament, it is more democratic than what we have in Canada now.
</p><p>Of course, directly selecting a random person in a riding is fraught with difficulties, so instead one would vote, as we do now, for one’s preferred candidate. Then, once the votes are tallied, a candidate is selected randomly with probability proportional to the vote they received. In this system it is <em>always</em> best to vote for your preferred candidate. There will be no more strategic votes or vote splitting. Voting participation would go up since every vote increases the chances of your preferred candidate being selected. The resulting parliament will be close to the proportion of the number of votes received for each party without having MPs selected from a party list.
</p><p>Imagine a world where we have Stochastic Elections Canada. Stochastic Election law requires that all counts be validated and recounted, if requested, before seat selection takes place. Because in every vote influences the outcome, we must await the return of the writs, scheduled by electoral law for Monday, November 9, 2015. For now, we can bring you our seat expectation chart based on preliminary 2015 election results:
</p><table class="election" summary="This table lists the expected number of seats each party would receive if the 2015 election used the stochastic election method">
<caption>Expected Seat Distribution</caption>
<thead>
<tr>
<th>Party</th>
<th>Expected Number of Seats<br/>(95% confidence)</th>
<th>Distribution Shape</th>
</tr>
</thead>
<tbody>
<tr>
<td>Animal Alliance/Environment Voters</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=336033&chd=s:9CAAAAAAA"/></td>
</tr>
<tr>
<td>ATN</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9A"/></td>
</tr>
<tr>
<td>Bloc Québécois</td>
<td>9 – 22</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=87CEFA&chd=s:AAAAAABDHMVgr1895yoeUNIECBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Canada Party</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9A"/></td>
</tr>
<tr>
<td>CAP</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DC143C&chd=s:9AAA"/></td>
</tr>
<tr>
<td>Christian Heritage Party</td>
<td>0 – 2</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=cc6699&chd=s:9TDAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Communist</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=FF6347&chd=s:9FAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Conservative</td>
<td>91 – 122</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=6495ED&chd=s:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBCCDEGHKMPTXbfkpty157899752yuqlhcYUROLJHFEDCCBBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Democratic Advancement</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9CAAA"/></td>
</tr>
<tr>
<td>Forces et Démocratie - Allier les forces de nos régions</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=01af58&chd=s:9MBAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Green Party</td>
<td>5 – 18</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=99c955&chd=s:AAABEJRdp1895wmcTMHECBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Liberal</td>
<td>119 – 153</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=ea6d6a&chd=s:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBCDDEGHJMORVYchlptx1468998752yvrmieaWTQNKIHFEDCCBBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Libertarian</td>
<td>0 – 3</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=f2ba00&chd=s:9sPEBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Marxist-Leninist</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=CD5C5C&chd=s:9LBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>NDP-New Democratic Party</td>
<td>54 – 81</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=F4A460&chd=s:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBCDEGILOSWbgmrw14799863zvqlgbWSPLJHFEDCBBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>PACT</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9A"/></td>
</tr>
<tr>
<td>PC Party</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=6666cc&chd=s:9FAAAAAAA"/></td>
</tr>
<tr>
<td>Pirate</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=71079f&chd=s:9BAAAA"/></td>
</tr>
<tr>
<td>Radical Marijuana</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=D2B48C&chd=s:9CAAAAAAA"/></td>
</tr>
<tr>
<td>Rhinoceros</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=D8BFD8&chd=s:9JBAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>Seniors Party</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9A"/></td>
</tr>
<tr>
<td>The Bridge</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=9370DB&chd=s:9A"/></td>
</tr>
<tr>
<td>United Party</td>
<td>0</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=de3163&chd=s:9A"/></td>
</tr>
<tr>
<td>Independent</td>
<td>0 – 3</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:90TEBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"/></td>
</tr>
<tr>
<td>No Affiliation</td>
<td>0 – 1</td>
<td><img alt="" src="http://chart.apis.google.com/chart?cht=bvs&chs=311x20&chbh=1,0,0&chco=DCDCDC&chd=s:9PAAAAA"/></td>
</tr>
</tbody>
</table>
<p>Related info</p><ul>
<li><a href="20110530T170250Z.html">2011 stochastic election results</a></li>
<li><a href="20081107T061447Z.html">2008 stochastic election results</a></li>
<li><a href="20060217T201200Z.html">2006 stochastic election results</a></li>
<li><a href="20060122T172700Z.html">2004 stochastic election results</a></li>
</ul>
http://r6.ca/blog/20150827T020314Z.htmlClearing Up “Clearing Up Mysteries”2015-08-27T02:03:14Z2015-08-27T02:03:14Z
<p>I am a big fan of <a title="Jaynes on Entropy" href="20100802T005835Z.html">E. T. Jaynes</a>.
His book <cite>Probability Theory: The Logic of Science</cite> is the only book on statistics that I ever felt I could understand.
Therefore, when he appears to rail against the conclusions of Bell’s theorem in his paper
“<a href="http://bayes.wustl.edu/etj/articles/cmystery.ps.gz">Clearing up Mysteries—The Original Goal</a>”, I take him seriously.
He suggests that perhaps there could be a time-dependent hidden variable theory that could yield the outcomes that quantum mechanics predicts.</p><p>However, after reading Richard D. Gill’s paper,
“<a href="http://arxiv.org/abs/quant-ph/0301059v2">Time, Finite Statistics, and Bell’s Fifth Position</a>”
it is very clear that there can be nothing like a classical explanation that yields quantum predictions, time-dependent or otherwise.
In this paper Gill reintroduces Steve Gull’s computer network, where a pair of classical computers is tasked to recreate probabilities predicted in a <a title="CHSH inequality" href="https://en.wikipedia.org/w/index.php?tilte=CHSH_inequality&oldid=676806380">Bell-CHSH</a> delayed choice experiment.
The catch is that the challenger gets to choose the stream of bits sent to each of the two spatially separated computers in the network.
These bits represent the free choice an experimenter running a <a title="CHSH inequality" href="https://en.wikipedia.org/w/index.php?tilte=CHSH_inequality&oldid=676806380">Bell-CHSH</a> experiment has to choose which polarization measurements to make.
No matter what the classical computer does, no matter how much time-dependent fiddling you want to do, it can never produce correlations that will violate the <a title="CHSH inequality" href="https://en.wikipedia.org/w/index.php?tilte=CHSH_inequality&oldid=676806380">Bell-CHSH</a> inequality in the long run.
This is Gull’s “You can’t program two independently running computers to emulate the EPR experiment” theorem.</p><p>Gill presents a nice analogy with playing roulette in the casino.
Because of the rules of roulette, there is no computer algorithm can implement a strategy that will beat the house in roulette in the long run.
Gill goes on to quantify exactly how long the long run is in order to place a wager against other people who claim they can recreate the probabilities predicted by quantum mechanics using a classical local hidden variable theory.
Using the theory of supermartingales, one can bound the likelihood of seeing the <a title="CHSH inequality" href="https://en.wikipedia.org/w/index.php?tilte=CHSH_inequality&oldid=676806380">Bell-CHSH</a> inequality violated by chance by any classical algorithm in the same way that one can bound the likelihood of long winning streaks in roulette games.</p><p>I liked the casino analogy so much that I decided to rephrase Gull’s computer network as a coin guessing casino game I call <a title="Bell’s Casino Problem" href="20150816T185621Z.html">Bell’s Casino</a>.
We can prove that any classical strategy, time-dependent or otherwise, simply cannot beat the house at that particular game in the long run.
Yet, there is <a title="Bell’s Casino Solution" href="20151210T033709Z.html">a strategy</a> where the players employ entangled qubits and beat the house on average.
This implies there cannot be any classical phenomena that yields quantum outcomes.
Even if one proposes some classical oscollating (time-dependent) hidden variable vibrating at such a high rate that we could never practically measure it, this theory still could not yield quantum probabilities,
because such a theory implies we could simulate it with Gull’s computer network.
Even if our computer simulation was impractically slow, we could still, in principle, deploy it against Bell’s Casino to beat their coin game.
But no such computer algorithm exists, in exactly the same way that there is no computer algorithm that will beat a casino at a fair game of roulette.
The fact that we can beat the casino by using qubits clearly proves that qubits and quantum physics is something truly different.</p><p>You may have heard the saying that “correlation does not imply causation”.
The idea is that if outcomes <var>A</var> and <var>B</var> are correlated, the either <var>A</var> causes <var>B</var>, or <var>B</var> causes <var>A</var>, or there is some other <var>C</var> that causes <var>A</var> and <var>B</var>.
However, in quantum physics there is a fourth possibilty.
We can have correlation without causation.</p><p>In light of Gull and Gill’s iron clad argument, I went back to reread Jaynes’s “Clearing up Mysteries”.
I wanted to understand how Jaynes could have been so mistaken.
After rereading it I realized that I had misunderstood what he was trying to say about Bell’s theorem.
Jaynes just wanted to say two things.</p><p>Firstly, Jaynes wanted to say that Bell’s theorem does not necessarily imply action at a distance.
This is not actually a controversial statement.
The many-worlds interpretation is a local, non-realist (in the sense that experiments do not have unique definite outcomes) interpretation of quantum mechanics.
This interpretation does not invoke any action at a distance and is perfectly compatible with Bell’s theorem.
Jaynes spends some time noting that correlation does not imply causation in an attempt to clarify this point although he never talks about the many-worlds interpretation.</p><p>Secondly, Jaynes wanted to say that Bell’s theorem does not imply that quantum mechanics is the best possible physical theory that explains quantum outcomes.
Here his argument is half-right and half-wrong.
He spends some time suggesting that maybe there is a time-dependent hidden variable theory that could give more refined predictions than predicted by quantum theory.
However, the suggestion that any classical theory, time-dependent or otherwise, could underlie quantum mechanics is refuted by Bell’s theorem and this is clearly illustrated by Gull’s computer network or by Bell’s casino.
Jaynes learned about Gull’s computer network argument at the same conference that he presented “Clearing Up Mysteries”.
His writing suggests that he was surprised by the argument, but he did not want to rush to draw any conclusions to from it without time to get a deeper understanding of it.
Nevertheless, Jaynes larger point was still correct.
Bell’s theorem does not imply that there is not some, non-classical, refinement of quantum mechanics that might yield more informative predictions than quantum mechanics does and Jaynes was worried that people would not look for such a refinement.</p><p>Jaynes spent a lot of effort trying to separate epistemology, where probability theory rules how we reason in the face of imperfect knowledge, from ontology, which describes what happens in reality if we had perfect information.
Jaynes thought that quantum mechanics was mixing these two branches together into one theory and worried that if people were mistaking quantum mechanics for an ontological theory then they would never seek a more refined theory.</p><p>While Bell’s theorem does not rule out that there may be a non-classical hidden variable theory,
Colbeck and Renner’s paper “<a href="http://arxiv.org/abs/1005.5173v3">No extension of quantum theory can have improved predictive power</a>” all but eliminates that possibility
by proving that there is no quantum hidden variable theory.
This can be seen as a strengthening of Bell’s theorem, and they even address some of the same concerns that Jaynes had about Bell’s theorem.</p><blockquote>
<p>To quote Bell [2], <dfn>locality</dfn> is the requirement that “…the result of a measurement on one system [is] unaffected by
operations on a distant system with which it has interacted in the past…” Indeed, our non-signalling conditions reflect
this requirement and, in our language, the statement that P<sub>XYZ|ABC</sub> is non-signalling is equivalent to a statement that
the model is local (see also the discussion in [28]). (We remind the reader that we do not assume the non-signalling
conditions, but instead derive them from the free choice assumption.)
In spite of the above quote, Bell’s formal definition of locality is slightly more restrictive than these non-signalling
conditions. Bell considers extending the theory using hidden variables, here denoted by the variable Z. He requires
P<sub>XY|ABZ</sub> = P<sub>X|AZ</sub> × P<sub>Y|BZ</sub> (see e.g. [13]), which corresponds to assuming not only P<sub>X|ABZ</sub> = P<sub>X|AZ</sub> and P<sub>Y|ABZ</sub> =
P<sub>Y|BZ</sub> (the non-signalling constraints, also called parameter-independence in this context), but also P<sub>X|ABYZ</sub> =
P<sub>X|ABZ</sub> and P<sub>Y|ABXZ</sub> = P<sub>Y|ABZ</sub> (also called outcome-independence). These additional constraints do not follow
from our assumptions and are not used in this work.</p>
</blockquote>
<p>The probabilistic assumptions are weaker in Colbeck and Renner’s work than in Bell’s theorem, because they want to exclude quantum hidden variable theories in addition to classical
hidden variable theories.
Today, if one wants to advance a local hidden variable theory, it would have to be a theory that is even weirder than quantum mechanics, if such a thing is even logically possible.
It seems that quantum mechanics’s wave function is an ontological description after all.</p><p>I wonder what Jaynes would have thought about this result.
I suspect he would still be looking for an exotic hidden variable theory.
He seemed so convinced that probability theory was solely in the realm of epistemology and not ontology that he would not accept any probabilistic ontology at all.</p><p>I think Jaynes was wrong when he suggested that quantum mechanics was necessarily mixing up epistemology and ontology.
I believe the many-worlds interpretation is trying to make that distinction clear.
In this interpretation the wave-function and Schrödinger’s equation is ontology, but the Born rule that relates the norm-squared amplitude to probability ought to be epistemological.
However, there does remain an important mystery here:
Why do the observers within the many-worlds observe quantum probabilities that satisfy the Born rule?
I like to imagine Jaynes could solve this problem if he were still around.
I imagine that would say that something like, “Due to phase invariance of the wave-function … <i>something something</i> … transformation group … <i>something something</i> … thus the distribution must be in accordance with the Born rule.”
After all, Jaynes did manage to use transformation groups to solve the <a href="https://en.wikipedia.org/w/index.php?title=Bertrand_paradox_%28probability%29&oldid=674563212#Jaynes.27_solution_using_the_.22maximum_ignorance.22_principle">Bertrand paradox</a>, a problem widely regarded as being unsolvable due to being underspecified.
</p>http://r6.ca/blog/20150816T185621Z.htmlBell’s Casino Problem2015-08-16T18:56:21Z2015-08-16T18:56:21Z
<p>A new casino has opened up in town named “Bell’s Casino”. They are offering a coin game. The game works as follows.
</p><p>The house will commit two coins on the table, oriented heads or tails each, and keep them covered. The player calls what the faces of the each of the coins are, either HH, HT, TH, or TT. The
casino reveals the coins and if the player is correct, they win $1, and otherwise they lose $1.
</p><dl>
<dt>Problem 1.</dt>
<dd>Prove that there is no strategy that can beat the casino.</dd>
</dl>
<p>After opening the customers stop coming by to play this boring game, so to boost attendance the casino modifies the game as follows.
</p><p>The house will commit two coins on the table, oriented heads or tails each, and keep them covered. The player calls what the faces of each of the two coins are, either HH, HT, TH, or TT. The
casino reveals one coin, of the players choice. After seeing revealed coin, the player can elect to back out of the game and neither win nor lose, or keep going, and see the second coin.
If the player’s call is correct, they win $1, and otherwise they lose $1.
</p><dl>
<dt>Problem 2.</dt>
<dd>Prove that there is no strategy that can beat the casino.</dd>
</dl>
<p>Even with the new, more fair, game, attendance at the casino starts dropping off again. The casino decides to offer a couples game.
</p><p>The house will commit two coins on two tables, oriented heads or tails each, and keep them covered. The couple, together, calls what the the faces of each of the two coins are, either HH, HT, TH, or
TT. Then, each player in the couple gets to see one coin each. Collectively they get to decide whether they are going to back out of the game or not by the following method. After seeing
their revealed coin, each player will raise either a black flag or a red flag. If both players raise the different colour flags, the game ends and no one wins or loses. If both players raise the
same colour flag, the game keeps going. If the couples original call was right, they win $1, and otherwise, they lose $1. To ensure that the couple cannot cheat, the two tables
are places far enough apart such that each player’s decision on which flag to raise is <a title="Space-like interval" href="https://en.wikipedia.org/wiki/Spacetime#Space-like_interval">space-like separated</a>. Specifically the tables are placed 179 875 475 km apart and
each player has 1 minute to decide which flag to raise otherwise a black flag will be raised on their behalf (or, more realistically, the tables are placed 400 m apart and each player has
100 nanoseconds to decide which flag to raise).
</p><dl>
<dt>Problem 3.</dt>
<dd>Prove that there is no strategy for the couple that can beat the casino.</dd>
</dl>
<dl>
<dt>Problem 4.</dt>
<dd>Devise a physical procedure that a couple can follow to beat the casino on average at this last game without cheating.</dd>
</dl>
<p>The casino cannot figure out how they keep losing money on this game and, soon, Bell’s Casino goes bankrupt.
</p>http://r6.ca/blog/20150222T233125Z.htmlParallel Evaluation of the Typed Lambda Calculus2015-02-22T23:31:25Z2015-02-22T23:31:25Z
<p>There is much written about the <a title="Call-by-Value is Dual to Call-by-Name" href="http://homepages.inf.ed.ac.uk/wadler/papers/dual/dual.pdf">duality</a> between strict-order (call-by-value) evalutaion for the lambda calculus and the normal-order (call-by-need) evaluation (or semantic equivently, lazy evaluation).
In the simply typed lambda calculus, all evaluation eventually terminates, so both evaluation strategies result in the same values.
However, when general recursion is added to the simply typed lambda calculus (via a fixpoint operator, for example) then evaluation of some expressions does not terminate.
More expressions terminate with normal-order evaluation than with strict-order evaluation.
In fact, if evaluation terminates in any order, then it terminates with normal-order evaluation.
</p><p>I would like to discuss the possibility of a third, even laxer evaluation strategy available for the typed lambda calculus that allows for even more expressions to terminate.
I did just say that normal-order evaluation is, in some sense, a best possible evaluation order, so, in order to beat it, we will be adding more redexes that add the commuting conversions.
</p><p>The typed lambda calculus enjoys certain commuting conversions for case expressions that allow every elimination term to pass through the case expression.
For example, the commuting conversion for the <code>π₁</code> elimination term and the <code>case</code> experssion says that
</p><pre>π₁(case e₀ of σ₁ x. e₁ | σ₂ y. e₂)</pre>
<p>converts to
</p><pre>case e₀ of σ₁ x. π₁(e₁) | σ₂ y. π₁(e₂)</pre>
<p>These commuting conversions are required so that <a title="Proofs and Types" href="http://www.paultaylor.eu/stable/Proofs+Types.html">the subformula property holds</a>.
</p><p>My understanding is that a corollary of this says that
</p><pre>f(case e₀ of σ₁ x. e₁ | σ₂ y. e₂)</pre>
<p>and
</p><pre>case e₀ of σ₁ x. f(e₁) | σ₂ y. f(e₂)</pre>
<p>are denotationally equivalent whenever <code>f</code> is a strict function.
</p><p>I would like to develop a version of the lambda calculus that allows these two expressions to denote the same value for any <code>f</code>.
Call this, the unrestricted commuting conversion property.
A lambda calculus with this property would necessarily be parallel and thus will require a parallel evaluation strategy.
For example, the natural definition of <code>or</code> becomes the parallel-or operation.
</p><pre>or x y := if x then True else y</pre>
<p>This definition has the usual short-circuit property that <code>or True ⊥</code> is <code>True</code> where <code>⊥</code> is defined by
</p><pre>⊥ := fix id</pre>
<p>If we use the unrestricted commuting conversion property then we also have the that <code>or ⊥ True</code> is <code>True</code>:
</p><pre>or ⊥ True
= {definition of or}
if ⊥ then True else True
= {β-expansion}
if ⊥ then const True ⟨⟩ else const True ⟨⟩
= {commuting}
const True (if ⊥ then ⟨⟩ else ⟨⟩)
= {β-reduction}
True</pre>
<p>Hence <code>or</code> is parallel-or.
</p><p>Other parallel functions, such as the majority function, also follow from their natural definitions.
</p><pre>maj x y z := if x then (or y z) else (and y z)</pre>
<p>In this case <code>maj ⊥ True True</code> is <code>True</code>.
</p><pre>maj ⊥ True True
= {definition of maj}
if ⊥ then (or True True) else (and True True)
= {evaluation of (or True True) and (and True True)
if ⊥ then True else True
= {commuting}
True</pre>
<p>It is easy to verify that <code>maj True ⊥ True</code> and <code>maj True True ⊥</code> are also both <code>True</code>.
</p><p>My big question is whether we can devise some nice operational semantics for the lambda calculus that will have the unrestricted commuting conversions property that I desire.
Below I document my first attempt at such operational semantics, but, spoiler alert, it does not work.
</p><p>The usual rule for computing weak head normal form for the case expression <code>case e₀ of σ₁ x. e₁ | σ₂ y. e₂</code> says to first convert <code>e₀</code> to weak head normal form.
If it is <code>σ₁ e₀′</code> then return the weak head normal form of <code>e₁[x ↦ e₀′]</code>.
If it is <code>σ₂ e₀′</code> then return the weak head normal form of <code>e₂[y ↦ e₀′]</code>.
In addition to this rule, I want to add another rule for computing the weak head normal form for the case expression.
This alernative rules says that we compute the weak head normal forms of <code>e₁</code> and <code>e₂</code>.
If we get <code>C₁ e₁′</code> and <code>C₂ e₂′</code> respectively for introduction terms (<abbr title="also known as">a.k.a.</abbr> constructors) <code>C₁</code> and <code>C₂</code>, and
if additionally <code>C₁</code> = <code>C₂</code> then return the following as a weak head normal form, <code>C₁ (case e₀ of σ₁ x. e₁′ | σ₂ y. e₂′)</code>.
If <code>C₁</code> ≠ <code>C₂</code> or if we get stuck on a neutral term (e.g. a varaible), then this rule does not apply.
</p><p>This new rule is in addition to the usual rule for <code>case</code>. Any implementation must run these two rules in parallel because it is possible that either rule (or both) can result in non-termination when recursivly computing weak head normal forms of sub-terms.
I suppose that in case one has unlifted products then when computing the weak head normal form of a <code>case</code> expression having a product type or function type, one can immediately return
</p><pre>⟨case e₀ of σ₁ x. π₁ e₁ | σ₂ y. π₁ e₂, case e₀ of σ₁ x. π₂ e₁ | σ₂ y. π₂ e₂⟩</pre>
or
<pre>λz. case e₀ of σ₁ x. e₁ z | σ₂ y. e₂ z</pre>
<p>This amended computation of weak head normal form seems to work for computing <code>or</code> and <code>maj</code> functions above so that they are non-strict in every argument, but there is another example where even this method of computing weak head normal form is not sufficent.
Consider the functions that implements associativity for the sum type.
</p><pre>assocL : A + (B + C) -> (A + B) + C
assocL z := case z of σ₁ a. σ₁ (σ₁ a) | σ₂ bc. (case bc of σ₁ b. σ₁ (σ₂ b) | σ₂ c. σ₂ c)
assocR : (A + B) + C -> A + (B + C)
assocR z := case z of σ₁ ab. (case ab of σ₁ a. σ₁ a | σ₂ b. σ₂ (σ₁ b)) | σ₂ c. σ₂ (σ₂ c)</pre>
<p>Now let us use unrestricted commuting conversions to evaluate <code>assocR (assocL (σ₂ ⊥))</code>.
</p><pre>assocR (assocL (σ₂ ⊥))
= { definition of assocL and case evaluation }
assocR (case ⊥. σ₁ b. σ₁ (σ₂ b) | σ₂ c. σ₂ c)
= { commuting conversion }
case ⊥. σ₁ b. assocR (σ₁ (σ₂ b)) | σ₂ c. assocR (σ₂ c)
= { definition of assocR and case evaluations }
case ⊥. σ₁ b. σ₂ (σ₁ b) | σ₂ c. σ₂ (σ₂ c)
= { commuting conversion }
σ₂ (case ⊥. σ₁ b. σ₁ b | σ₂ c. σ₂ c)
= { η-contraction for case }
σ₂ ⊥</pre>
<p>Even if η-contraction is not a reduction rule used for computation, it is still the case that <code>t</code> and <code>case t. σ₁ b. σ₁ b | σ₂ c. σ₂ c</code> should always be dentotationally equivalent.
Anyhow, we see that by using commuting conversions that a weak head normal form of <code>assocR (assocL (σ₂ ⊥))</code> should expose the <code>σ₂</code> constructor.
However, if you apply even my ammended computation of weak head normal form, it will not produce any constructor.
</p><p>What I find particularly surprising is the domain semantics of <code>assocL</code> and <code>assocR</code>.
<code>assocL</code> seems to map <code>σ₂ ⊥</code> to <code>⊥</code> because no constructor can be exposed.
<code>assocR</code> maps <code>⊥</code> to <code>⊥</code>.
Therefore, according to the denotational semantics, the composition should map <code>σ₂ ⊥</code> to <code>⊥</code>, but as we saw, under parallel evaluation it does not.
It would seem that the naive denotational semantics appears to not capture the semantics of parallel evaluation.
The term <code>case ⊥. σ₁ b. σ₁ (σ₂ b) | σ₂ c. σ₂ c</code> seems to be more defined than ⊥, even though no constructor is available in the head position.
</p><p>Although my attempt at nice operational semantics failed, I am still confident some nice computation method exists.
At the very least, I believe a rewriting system will work which has all the usual rewriting rules plus a few extra new redexes that says that an elimination term applied to the <code>case</code> expression commutes the elimination term into all of the branches,
and another that says when all branches of a case expression contain the same introduction term, that introduction term is commuted to the outside of the case expression, and maybe also the rules I listed above for unlifted products.
I conjecture this rewriting system is confluent and unrestricted commuting conversions are convertable (probably requiring η-conversions as well).
</p><p>Without proofs of my conjectures I am a little concerned that this all does not actually work out.
There may be some bad interaction with fixpoints that I am not seeing.
If this does all work out then shouldn’t I have heard about it by now?
</p>http://r6.ca/blog/20150111T040537Z.htmlSecure diffie-hellman-group-exchange-sha2562015-01-11T04:05:37Z2015-01-11T04:05:37Z
<p>Recently I have been working on purging <abbr title="Digital Signature Algorithm">DSA</abbr> from my computer systems.
The problem with <abbr title="Digital Signature Algorithm">DSA</abbr> and <abbr title="Elliptic Curve Digital Signature Algorithm">ECDSA</abbr> is that they fail catastrophically with when nonces are accidentally reused, or if the randomly generated nonces are biased.
At about the same time, I was pleased to discover an article on <a title="Secure Secure Shell" href="https://stribika.github.io/2015/01/04/secure-secure-shell.html">securing <abbr title="Secure Shell">SSH</abbr></a>. It gives further advice in setting up <abbr title="Secure Shell">SSH</abbr> and I have proceeded to apply most of the recommendation listed there.
</p><p>For key exchange algorithms, <a title="Secure Secure Shell" href="https://stribika.github.io/2015/01/04/secure-secure-shell.html">the article</a> suggests using <code>curve25519-sha256</code> and falling back to <code>diffie-hellman-group-exchange-sha256</code> for compatibility purposes if you must.
The <code>diffie-hellman-group-exchange-sha256</code> protocol allows the client and server to negotiate a prime field to perform the key exchange in.
In order to avoid using the smaller prime fields, <a title="Secure Secure Shell" href="https://stribika.github.io/2015/01/04/secure-secure-shell.html">the article</a> suggests deleting prime numbers less than 2000 bits in size from <code>/etc/ssh/moduli</code>.
The problem with this advice is that only the <abbr title="Secure Shell">SSH</abbr> server reads <code>/etc/ssh/moduli</code>; touching this file does nothing to secure your <abbr title="Secure Shell">SSH</abbr> client from using small prime fields during key negotiation.
Securing the client is the important use case for <code>diffie-hellman-group-exchange-sha256</code>, because if you can control the server, then it means you will probably use <code>curve25519-sha256</code> instead.
</p><p>However, <a title="Diffie-Hellman Group Exchange for the Secure Shell (SSH) Transport Layer Protocol" href="https://www.ietf.org/rfc/rfc4419.txt">the protocol for <code>diffie-hellman-group-exchange-sha256</code></a> does allow the client to negotiate the field side.
The problem is that this ability is not exposed for configuration in <abbr title="Secure Shell">SSH</abbr>.
To address this, I created a <a href="data:text/plain;base64,QXV0aG9yOiBSdXNzZWxsIE8nQ29ubm9yIDxvY29ubm9yckBnb29nbGUuY29tPgpkaWZmIC11ciBvcGVuc3NoLTYuOHAxLm9yaWcvZGguaCBvcGVuc3NoLTYuOHAxL2RoLmgKLS0tIG9wZW5zc2gtNi44cDEub3JpZy9kaC5oICAgICAyMDE1LTA1LTA0IDExOjQ4OjA2LjYxODI3ODU0OCAtMDQwMAorKysgb3BlbnNzaC02LjhwMS9kaC5oICAyMDE1LTA1LTA0IDExOjQ4OjM1LjgyNTcwNDM1NSAtMDQwMApAQCAtNDMsOCArNDMsNyBAQAogCiB1X2ludCAgIGRoX2VzdGltYXRlKGludCk7CiAKLS8qIE1pbiBhbmQgbWF4IHZhbHVlcyBmcm9tIFJGQzQ0MTkuICovCi0jZGVmaW5lIERIX0dSUF9NSU4gICAgIDEwMjQKKyNkZWZpbmUgREhfR1JQX01JTiAgICAgMjA0OAogI2RlZmluZSBESF9HUlBfTUFYICAgICA4MTkyCiAKIC8qCmRpZmYgLXVyIG9wZW5zc2gtNi44cDEub3JpZy9rZXhnZXhjLmMgb3BlbnNzaC02LjhwMS9rZXhnZXhjLmMKLS0tIG9wZW5zc2gtNi44cDEub3JpZy9rZXhnZXhjLmMgICAgICAgIDIwMTUtMDUtMDQgMTE6NDg6MDYuNjIxMjc4NTkyIC0wNDAwCisrKyBvcGVuc3NoLTYuOHAxL2tleGdleGMuYyAgICAgMjAxNS0wNS0wNCAxMjowMjo1MS40NzcwMDA0MzAgLTA0MDAKQEAgLTYxLDYgKzYxLDggQEAKICAgICAgICB1X2ludCBuYml0czsKIAogICAgICAgIG5iaXRzID0gZGhfZXN0aW1hdGUoa2V4LT5kaF9uZWVkICogOCk7CisgICAgICAgIG5iaXRzID0gTUlOKERIX0dSUF9NQVgsIG5iaXRzKTsKKyAgICAgICAgbmJpdHMgPSBNQVgoREhfR1JQX01JTiwgbmJpdHMpOwogCiAgICAgICAga2V4LT5taW4gPSBESF9HUlBfTUlOOwogICAgICAgIGtleC0+bWF4ID0gREhfR1JQX01BWDsKZGlmZiAtdXIgb3BlbnNzaC02LjhwMS5vcmlnL2tleGdleHMuYyBvcGVuc3NoLTYuOHAxL2tleGdleHMuYwotLS0gb3BlbnNzaC02LjhwMS5vcmlnL2tleGdleHMuYyAgICAgICAgMjAxNS0wNS0wNCAxMTo0ODowNi42MjEyNzg1OTIgLTA0MDAKKysrIG9wZW5zc2gtNi44cDEva2V4Z2V4cy5jICAgICAyMDE1LTA1LTA0IDEyOjEwOjI1LjE0NTQyODk0NCAtMDQwMApAQCAtODcsMTAgKzg3LDYgQEAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGtleC0+bmJpdHMgPSBuYml0czsKICAgICAgICAgICAgICAgIGtleC0+bWluID0gbWluOwogICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXg7Ci0gICAgICAgICAgICAgICBtaW4gPSBNQVgoREhfR1JQX01JTiwgbWluKTsKLSAgICAgICAgICAgICAgIG1heCA9IE1JTihESF9HUlBfTUFYLCBtYXgpOwotICAgICAgICAgICAgICAgbmJpdHMgPSBNQVgoREhfR1JQX01JTiwgbmJpdHMpOwotICAgICAgICAgICAgICAgbmJpdHMgPSBNSU4oREhfR1JQX01BWCwgbmJpdHMpOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSBTU0gyX01TR19LRVhfREhfR0VYX1JFUVVFU1RfT0xEOgogICAgICAgICAgICAgICAgZGVidWcoIlNTSDJfTVNHX0tFWF9ESF9HRVhfUkVRVUVTVF9PTEQgcmVjZWl2ZWQiKTsKQEAgLTk5LDEzICs5NSwxNyBAQAogICAgICAgICAgICAgICAgICAgICAgICBnb3RvIG91dDsKICAgICAgICAgICAgICAgIGtleC0+bmJpdHMgPSBuYml0czsKICAgICAgICAgICAgICAgIC8qIHVudXNlZCBmb3Igb2xkIEdFWCAqLwotICAgICAgICAgICAgICAga2V4LT5taW4gPSBtaW4gPSBESF9HUlBfTUlOOwotICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXggPSBESF9HUlBfTUFYOworICAgICAgICAgICAgICAga2V4LT5taW4gPSBtaW4gPSAxMDI0OworICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXggPSA4MTkyOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgIHIgPSBTU0hfRVJSX0lOVkFMSURfQVJHVU1FTlQ7CiAgICAgICAgICAgICAgICBnb3RvIG91dDsKICAgICAgICB9CisgICAgICAgbWF4ID0gTUlOKERIX0dSUF9NQVgsIG1heCk7CisgICAgICAgbWluID0gTUFYKERIX0dSUF9NSU4sIG1pbik7CisgICAgICAgbmJpdHMgPSBNSU4oREhfR1JQX01BWCwgbmJpdHMpOworICAgICAgIG5iaXRzID0gTUFYKERIX0dSUF9NSU4sIG5iaXRzKTsKIAogICAgICAgIGlmIChrZXgtPm1heCA8IGtleC0+bWluIHx8IGtleC0+bmJpdHMgPCBrZXgtPm1pbiB8fAogICAgICAgICAgICBrZXgtPm1heCA8IGtleC0+bmJpdHMpIHsKCg%3D%3D">patch</a> for <a title="OpenSSH" href="http://www.openssh.com/">OpenSSH</a> that raises the minimum field size allowed for the <code>diffie-hellman-group-exchange-sha256</code> key exchange for both the client and server.
This means you do not need to edit the <code>/etc/ssh/moduli</code> file to increase the minimum field size for the server, but it will not hurt to do so either.
</p><p>If you are running <a title="NixOS Linux" href="https://nixos.org/">NixOS</a> you can download the patch and add it to your <code>/etc/nixos/configuration.nix</code> file with the following attribute.
</p><pre> nixpkgs.config.packageOverrides = oldpkgs: {
openssh = pkgs.lib.overrideDerivation oldpkgs.openssh (oldAttrs: {
patches = oldAttrs.patches ++ [ <a href="data:text/plain;base64,QXV0aG9yOiBSdXNzZWxsIE8nQ29ubm9yIDxvY29ubm9yckBnb29nbGUuY29tPgpkaWZmIC11ciBvcGVuc3NoLTYuOHAxLm9yaWcvZGguaCBvcGVuc3NoLTYuOHAxL2RoLmgKLS0tIG9wZW5zc2gtNi44cDEub3JpZy9kaC5oICAgICAyMDE1LTA1LTA0IDExOjQ4OjA2LjYxODI3ODU0OCAtMDQwMAorKysgb3BlbnNzaC02LjhwMS9kaC5oICAyMDE1LTA1LTA0IDExOjQ4OjM1LjgyNTcwNDM1NSAtMDQwMApAQCAtNDMsOCArNDMsNyBAQAogCiB1X2ludCAgIGRoX2VzdGltYXRlKGludCk7CiAKLS8qIE1pbiBhbmQgbWF4IHZhbHVlcyBmcm9tIFJGQzQ0MTkuICovCi0jZGVmaW5lIERIX0dSUF9NSU4gICAgIDEwMjQKKyNkZWZpbmUgREhfR1JQX01JTiAgICAgMjA0OAogI2RlZmluZSBESF9HUlBfTUFYICAgICA4MTkyCiAKIC8qCmRpZmYgLXVyIG9wZW5zc2gtNi44cDEub3JpZy9rZXhnZXhjLmMgb3BlbnNzaC02LjhwMS9rZXhnZXhjLmMKLS0tIG9wZW5zc2gtNi44cDEub3JpZy9rZXhnZXhjLmMgICAgICAgIDIwMTUtMDUtMDQgMTE6NDg6MDYuNjIxMjc4NTkyIC0wNDAwCisrKyBvcGVuc3NoLTYuOHAxL2tleGdleGMuYyAgICAgMjAxNS0wNS0wNCAxMjowMjo1MS40NzcwMDA0MzAgLTA0MDAKQEAgLTYxLDYgKzYxLDggQEAKICAgICAgICB1X2ludCBuYml0czsKIAogICAgICAgIG5iaXRzID0gZGhfZXN0aW1hdGUoa2V4LT5kaF9uZWVkICogOCk7CisgICAgICAgIG5iaXRzID0gTUlOKERIX0dSUF9NQVgsIG5iaXRzKTsKKyAgICAgICAgbmJpdHMgPSBNQVgoREhfR1JQX01JTiwgbmJpdHMpOwogCiAgICAgICAga2V4LT5taW4gPSBESF9HUlBfTUlOOwogICAgICAgIGtleC0+bWF4ID0gREhfR1JQX01BWDsKZGlmZiAtdXIgb3BlbnNzaC02LjhwMS5vcmlnL2tleGdleHMuYyBvcGVuc3NoLTYuOHAxL2tleGdleHMuYwotLS0gb3BlbnNzaC02LjhwMS5vcmlnL2tleGdleHMuYyAgICAgICAgMjAxNS0wNS0wNCAxMTo0ODowNi42MjEyNzg1OTIgLTA0MDAKKysrIG9wZW5zc2gtNi44cDEva2V4Z2V4cy5jICAgICAyMDE1LTA1LTA0IDEyOjEwOjI1LjE0NTQyODk0NCAtMDQwMApAQCAtODcsMTAgKzg3LDYgQEAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGtleC0+bmJpdHMgPSBuYml0czsKICAgICAgICAgICAgICAgIGtleC0+bWluID0gbWluOwogICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXg7Ci0gICAgICAgICAgICAgICBtaW4gPSBNQVgoREhfR1JQX01JTiwgbWluKTsKLSAgICAgICAgICAgICAgIG1heCA9IE1JTihESF9HUlBfTUFYLCBtYXgpOwotICAgICAgICAgICAgICAgbmJpdHMgPSBNQVgoREhfR1JQX01JTiwgbmJpdHMpOwotICAgICAgICAgICAgICAgbmJpdHMgPSBNSU4oREhfR1JQX01BWCwgbmJpdHMpOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgY2FzZSBTU0gyX01TR19LRVhfREhfR0VYX1JFUVVFU1RfT0xEOgogICAgICAgICAgICAgICAgZGVidWcoIlNTSDJfTVNHX0tFWF9ESF9HRVhfUkVRVUVTVF9PTEQgcmVjZWl2ZWQiKTsKQEAgLTk5LDEzICs5NSwxNyBAQAogICAgICAgICAgICAgICAgICAgICAgICBnb3RvIG91dDsKICAgICAgICAgICAgICAgIGtleC0+bmJpdHMgPSBuYml0czsKICAgICAgICAgICAgICAgIC8qIHVudXNlZCBmb3Igb2xkIEdFWCAqLwotICAgICAgICAgICAgICAga2V4LT5taW4gPSBtaW4gPSBESF9HUlBfTUlOOwotICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXggPSBESF9HUlBfTUFYOworICAgICAgICAgICAgICAga2V4LT5taW4gPSBtaW4gPSAxMDI0OworICAgICAgICAgICAgICAga2V4LT5tYXggPSBtYXggPSA4MTkyOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgIHIgPSBTU0hfRVJSX0lOVkFMSURfQVJHVU1FTlQ7CiAgICAgICAgICAgICAgICBnb3RvIG91dDsKICAgICAgICB9CisgICAgICAgbWF4ID0gTUlOKERIX0dSUF9NQVgsIG1heCk7CisgICAgICAgbWluID0gTUFYKERIX0dSUF9NSU4sIG1pbik7CisgICAgICAgbmJpdHMgPSBNSU4oREhfR1JQX01BWCwgbmJpdHMpOworICAgICAgIG5iaXRzID0gTUFYKERIX0dSUF9NSU4sIG5iaXRzKTsKIAogICAgICAgIGlmIChrZXgtPm1heCA8IGtleC0+bWluIHx8IGtleC0+bmJpdHMgPCBrZXgtPm1pbiB8fAogICAgICAgICAgICBrZXgtPm1heCA8IGtleC0+bmJpdHMpIHsKCg%3D%3D">./openssh-dh-grp-min.patch</a> ];
});
};</pre>
<p>As an aside, I noticed that <a title="Diffie-Hellman Group Exchange for the Secure Shell (SSH) Transport Layer Protocol" href="https://www.ietf.org/rfc/rfc4419.txt">this key exchange protocol</a> has a design flaw in it.
The hash signed by the server is the hash of <code>V_C || V_S || I_C || I_S || K_S || min || n || max || p || g || e || f || K</code>.
The details of what those variables stand for is not important.
What is important is that there is a older format of the protocol that is supported for backwards compatibility where the hash signed by the server is the hash of <code>V_C || V_S || I_C || I_S || K_S || n || p || g || e || f || K</code>.
In this older protocol, the client only requests a field size without specifying the minimum and maximum allowed bounds.
This is why the variables <code>min</code> and <code>max</code> are do not appear in the hash of the older protocol.
A short header is sent by the client to determine which of these two versions of this protocol it is using.
</p><p>The problem is that this header is not part of the hashed data.
This little crack has potential to be an exploit.
A <abbr title="Man in the Middle">MITM</abbr> attacker could replace the header the client sends with the old protocol header, and then try to manipulate the remaining communication between the client and server so that both the client and server hash the same serialized byte string allowing the server to appear to be authenticated to the client, but where the client and server are interpreting that serialized byte string in two different ways.
In particular the <abbr title="Man in the Middle">MITM</abbr> wants the client to not be doing computation modulo some safe prime, but instead do modular arithmetic over a different ring entirely.
</p><p>Fortunately this particular little crack does not appear to be wide enough to exploit.
The incidental properties of the serialization format do not allow a successful manipulation, at least not in practical SSH configurations.
</p><p>When one is signing a serialized blob of data, it is important that the data can be unambiguously parsed using only the contents of that data.
This principle is violated here because one cannot decide if one will parse <code>min</code> and <code>max</code> without knowing the header, which is not part of the serialized blob of data.
The reason this failure can so easily creep into the protocol is that neither the client nor the server actually have to parse that blob of data.
They both serialize the data and then create or verify the signature, but parsing is never done. Therefore, parsing is never implemented.
Since parsing is not implemented, it is easy to miss that the data serialization format is ambigous.
</p>http://r6.ca/blog/20140921T175644Z.htmlHard Drive Failure2014-09-22T19:22:01Z2014-09-21T17:56:44Z
<p>A few weeks ago my desktop computer suffered catastrophic hard drive failure.
Not only did it not boot, it soon got to the point where even the <abbr title="Basic Input/Output System">BIOS</abbr> would fail to recognise the device.
At first I did not worry too much.
Although I was not doing automatic backups, I was still doing irregular weekly manual backups of my home directory with <a title="Tarsnap - Online backups for the truly paranoid" href="https://www.tarsnap.com/">tarsnap</a> and I had performed one about three days prior.
I was not specifically making backups of my <a title="NixOS Linux" href="https://nixos.org/">NixOS</a> system and user configuration, but I had some old copies.
The configuration files do not change much and they are less important.
Importantly, I had backups of my <a title="Tarsnap - Online backups for the truly paranoid" href="https://www.tarsnap.com/">tarsnap</a> keys stored in other places, such as my shell account.
</p><p>While waiting for a replacement drive to arrive, I realized I had a serious problem.
My <a title="Tarsnap - Online backups for the truly paranoid" href="https://www.tarsnap.com/">tarsnap</a> keys were encrypted with my <abbr title="Pretty Good Privacy">PGP</abbr> key.
I had two specific places where I kept backup of my <abbr title="Pretty Good Privacy">PGP</abbr> keys.
One place was a USB drive in a safe deposit box.
However, at some point I had taken that one out to update it, and then misplaced it before putting it back.
Naturally, I had been meaning to get around to replacing that USB drive and the data on it, for some number of years.
Also, to my surprise, I had never actually placed my <abbr title="Pretty Good Privacy">PGP</abbr> key in my secondary spot.
</p><p>I was sunk.
I had some very old hard drive images with older versions of my <abbr title="Pretty Good Privacy">PGP</abbr> key on it, but because I rotate my encryption keys every five years, they were not useful.
Within the last five years I had started using full disk encryption.
I had some newer hard drive images that also have my <abbr title="Pretty Good Privacy">PGP</abbr> keys but I need the passphrases to decrypt these images.
I had copies of the passphrase around, but, of course, they were all encrypted with my <abbr title="Pretty Good Privacy">PGP</abbr> keys.
</p><p>After an emotional day and some meditation, slowly my old passphrase came back to me and I was able to decrypt one of my disk images.
I was able to rescue my <abbr title="Pretty Good Privacy">PGP</abbr> keys and from there I was able to recover everything I had.
</p><p>I plan to get a bit more serious about distributing copies of my <abbr title="Pretty Good Privacy">PGP</abbr> key since I use it so widely.
With my <abbr title="Pretty Good Privacy">PGP</abbr> key I should be able to always recover everything since I keep all my other key material encrypted with it.
Instead of a single USB drive in a safe deposit box, I want to keep two identical USB keys, one at home and one in the box.
When I want to update the data, I will update the one at home, swap it with the one in the box, and update the second one and keep it at home until the next update is needed.
</p><p>I have also gotten more serious about automatic backup.
Turns out that <a title="NixOS Linux" href="https://nixos.org/">NixOS</a> already comes with a <a title="Tarsnap - Online backups for the truly paranoid" href="https://www.tarsnap.com/">tarsnap</a> system service.
All that one has to do is place one’s write-only <a title="Tarsnap - Online backups for the truly paranoid" href="https://www.tarsnap.com/">tarsnap</a> key in the appropriate place and specify which directories to back up.
I am hoping to make system recovery even easier by also backing up my <del datetime="20140922T192201Z"><ins datetime="20140922T013824Z"><kbd>~/.nix-profile/manifest.nix</kbd>, <kbd>/root/.nix-profile/manifest.nix</kbd>,</ins></del><ins datetime="20140922T192201Z"><kbd>/nix/var/nix/profiles/default/manifest.nix</kbd>, <kbd>/nix/var/nix/profiles/per-user/*/profile/manifest.nix</kbd>,</ins> <kbd>/etc/nixos</kbd> and <kbd>/var/lib</kbd>.<del datetime="20140922T013824Z">There are probably a few more things I should back up, like my user profiles, but I am not yet sure how best to do that.</del>
</p><p>I also want to restart my programme of escrow for my passwords in case something happens to me.
I need to improve my documentation of password list to make it easier for others to use.
I will use <a title="Shamir's Secret Sharing Scheme" href="http://point-at-infinity.org/ssss/">ssss</a> to split my master password and distribute among my escrow agents.
The nice thing about public-key cryptography is that I can assign escrow agents without requiring anything from them beyond the fact that they already possess and use <abbr title="Pretty Good Privacy">PGP</abbr> keys.
I do not even need to inform them that they are my escrow agents.
The encrypted components will be stored on my USB drive in the safe deposit box.
</p><p>Overall, I am glad to have narrowly avoid disaster and have definitely learned some lessons.
Check your backup policy everyone!
</p>http://r6.ca/blog/20140803T030905Z.htmlICFP 2014 Post-Mortem2014-08-03T03:09:05Z2014-08-03T03:09:05Z
<p>I participated in the 2014 ICFP programming contest this year.
This year’s task was to write an <abbr title="artifical intelligence">AI</abbr> for a simplified Pac-Man game called Lambda-Man.
You could write the <abbr title="artifical intelligence">AI</abbr> in any language you wanted, as long as it complies to a specific <abbr title="Stack, Environment, Control, Dump">SECD</abbr> machine architecture invented for the contest.
At the end of the lightening round, it was announced that the final task included writing an <abbr title="artifical intelligence">AI</abbr> for the ghosts as well.
Again, the ghost <abbr title="artifical intelligence">AI</abbr> could be written in any language, as long as it compiles to a separate 8-bit architecture invented for the contest.
</p><p>I spent the first several hours implementing my own simulator of the arcade.
Eventually I realized that I would have to start working on the <abbr title="artifical intelligence">AI</abbr> if I was going to have an entry for the 24-hour lightening division.
It was at that point I realized that the provided on-line simulator was plenty adequate for my needs and I never completed my simulator.
</p><p>I have some previous experience writing assembler <abbr title="domain specific langauge">DSL</abbr>s in Haskell to handle linking.
After the 2006 ICFP contest, our team wrote a fake UM-DOS shell so that we could submit our solution in UM format.
This lead me to writing <a title="Assembly: Circular Programming with Recursive do" href="https://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf">an
article in The Monad Reader</a> about how to write an assembler using recursive do.
After that, I encountered a really elegant and simple formulation of an assembler monad on some paste site.
Unfortunately, I do not recall the author, but here is how the implementation looks.
</p><pre>newtype Label = Label { unLabel :: Int }
data ASMMonad w a = ASMMonad { runASM :: Label -> ([w],a) }
instance Monad (ASMMonad w) where
return a = ASMMonad $ \_ -> ([], a)
x >>= y = ASMMonad (\(Label i) -> let (o0, a) = runASM x (Label i)
(o1, b) = runASM (y a) (Label (i+length o0))
in (o0 ++ o1, b))
instance MonadFix (ASMMonad w) where
mfix f = ASMMonad (\i -> let (o0, a) = runASM (f a) i in (o0, a))
execASM :: ASMMonad w a -> [w]
execASM m = fst $ runASM m (Label 0)</pre>
<p>Next one adds two primitive operations.
The <code>tell</code> function is similar to the version for the writer monad.
The <code>label</code> function returns the current index of the output stream.
</p><pre>tell :: [w] -> ASMMonad w ()
tell l = ASMMonad $ \_ -> (l,())
label :: ASMMonad w Label
label = ASMMonad $ \i -> ([],i)</pre>
<p>Lastly one makes an <code>ASMMonad</code>ic value for each assembly instruction
</p><pre>data ASM = LDC Int32 -- load constant
| LD Int Int -- load variable
| LDF Label -- load function
| ADD
{- … -}
deriving Show
ldc x = tell [LDC x]
ld x y = tell [LD x y]
ldf x = tell [LDF x]
add = tell [ADD]
{- … -}</pre>
<p>At the risk of jumping ahead too far, my compiler can produce linked assembly code very simply.
The clause below compiles a lambda abstraction to linked <abbr title="Stack, Environment, Control, Dump">SECD</abbr> assembly using recursive do.
</p><pre>compileH env (Abs vars body) = mdo
jmp end
begin <- label
compileH (update env vars) body
rtn
end <- label
ldf begin</pre>
<p>Thanks to recursive do, the first line, <code>jmp end</code>, refers to the <code>end</code> label which is bound in the second last line.
</p><p>With a <abbr title="domain specific langauge">DSL</abbr> assembler written in Haskell, I turned to creating another <abbr title="domain specific langauge">DSL</abbr> language in Haskell to compile to this assembly language.
The <abbr title="Stack, Environment, Control, Dump">SECD</abbr> machine is designed for Lisp compilers, so I created a little Lisp language.
</p><pre>data Binding a = a := Lisp a
data Lisp a = Var a
| Const Int32
| Cons (Lisp a) (Lisp a)
| Abs [a] (Lisp a)
| Rec [Binding a] (Lisp a)
{- … -}</pre>
<p>The <code>Abs</code> constructor builds an <var>n</var>-ary lambda function.
The <code>Rec</code> constructor plays the role of <kbd>letrec</kbd> to build mutually recursive references.
With some abuse of the <code>Num</code> class and <code>OverloadedStrings</code>, this Lisp <abbr title="domain specific langauge">DSL</abbr> is barely tolerable to program with directly in Haskell.
</p><pre> Rec [ {- … -}
,"heapNew" := ["cmp"]! (Cons "cmp" 0) -- heap layout 0 = leaf | (Cons (Cons /heap is full/ /value/) (Cons /left tree/ /right tree/))
-- "cmp" @@ ["x","y"] returns true when "x" < "y"
,"heapIsFull" := ["h"]! If (Atom "h") 1 (caar "h")
,"heapInsert" := ["cmpHeap", "v"]! Rec ["cmp" := (car "cmpHeap")
,"insert" := ["heap", "v"]! -- returns (Cons /new heap is full/ /new heap/)
If (Atom "heap") (Cons (Cons 1 "v") (Cons 0 0))
(Rec ["root" := cdar "heap"
,"left" := cadr "heap"
,"right" := cddr "heap"
] $
Rec ["swap" := "cmp" @@ ["v", "root"]] $
Rec ["newRoot" := If "swap" "v" "root"
,"newV" := If "swap" "root" "v"
] $
If (caar "heap" `ou` Not ("heapIsFull" @@ ["left"]))
(Rec ["rec" := "insert" @@ ["left", "newV"]] $
Cons (Cons 0 "newRoot") (Cons "rec" "right"))
(Rec ["rec" := "insert" @@ ["right", "newV"]] $
Cons (Cons ("heapIsFull" @@ ["rec"]) "newRoot") (Cons "left" "rec")))
]
(Cons "cmp" ("insert" @@ [cdr "cmpHeap","v"]))
{- … -}</pre>
<p>The <code>@@</code> operator is infix application for the Lisp langauge and the <code>!</code> operator is infix lambda abstraction for the Lisp langauge.
</p><p>This Lisp language compiles to the <abbr title="Stack, Environment, Control, Dump">SECD</abbr> assembly and the assembly is printed out.
The compiler is very simple.
It does not even implement tail call optimization.
There is a bit of an annoying problem with the compiler; the assembly code is structured in exactly the same way that the original Lisp is structured.
In particular, lambda abstractions are compiled directly in place, and since lambda expressions are typically not executed in the location they are declared,
I have to jump over the compiled code.
You can see this happening in the snippet of my compiler above.
I would have preferred to write
</p><pre>compileH env (Abs vars body) = do
fun <- proc (compileH (update env vars) body)
ldf fun</pre>
where <code>proc</code> is some function that takes an <code>ASMMonad</code> value and sticks the assembly code “at the end” and returns a label
holding the location where the assembly code got stashed.
However, I could not figure out a clever and elegent way of modifing the assembly monad to support this new primitive.
This is something for you to ponder.
<p>My Lambda <abbr title="artifical intelligence">AI</abbr>, written in my Lisp variant, is fairly simple and similar to other entries.
Lambda-Man searches out the maze for the nearest edible object.
It searches down each path until it hits a junction and inserts the location of the junction into a binary heap.
It also inserts the junction into a binary tree of encountered junctions.
If the junction is already in the binary tree, it does not insert the junction into the heap because it has already considered it.
The closest junction is popped off the heap, and the search is resumed.
</p><p>There is at least one bit of surprising behaviour.
If there is more than one path from one junction to another, sometimes Lambda-Man ends up taking the longer path.
This behaviour did not seem to be bothersome enough to warrant fixing.
</p><p>This programming task has renewed my appreciation for typed languages.
The Lisp language I developed is untyped, and I made several type errors programming in it.
Although it is true that I did detect (all?) my errors at run-time, they were still frustrating to debug.
In a typed language, when an invariant enforced by the type system is violated, you get a compile time error that, more or less, points to the code location where the invariant is violated.
In an untyped language, when an invariant is violated, you get a run-time error that, more or less, points to some point in the code where missing invariant has caused a problem.
While this often is enough to determine what invariant was violated, I had little idea where the code breaking the invariant was located.
</p><p>With some effort I probably could have used GADTs to bring Haskell’s type checker to the Lisp <abbr title="domain specific langauge">DSL</abbr>, but I was not confident enough I could pull that off in time.
</p><p>I also needed to write some ghost <abbr title="artifical intelligence">AI</abbr>s.
The 8-bit machine that the ghosts run on is so constrained, 256 bytes of data memory; 256 code locations; 8 registers, that it seemed to make sense to write the code in raw assembly.
</p><p>The first thing I tried was to make the ghosts move randomly.
This meant I needed to write my own pseudo-random number generator.
Wikipedia lead me to a paper on how to write long period <a title="Xorshift RNGs" href="http://www.jstatsoft.org/v08/i14/paper">xorshift random number generators</a>.
The examples in that paper are all for 32-bit or 64-bit machines, but I had an 8-bit architecture.
I wrote a little Haskell program to find analogous random number generators for 8-bit machines.
It found 6 possibilities for 32-bit state random number generator composed of four 8-bit words that satisfied the xorshift constraints described in the paper.
Here is the assembly code for getting a 2 bit pseudo-random value.
</p><pre>mov a,[0]
div a,2
xor [0],a
mov a,[0]
mul a,2
xor a,[0]
mov [0],[1]
mov [1],[2]
mov [2],[3]
mul [3],8
xor [3],[2]
xor [3],a
; get 2 bits
mov a,[3]
div a,64</pre>
<p>The random seed is held in memory locations [0] through [3].
After moving to the successive the state, this code takes 2 pseudo-random bits from memory location [3] and puts it into register <code>a</code>.
</p><p>I did not check the quality of this random number generator beyond constructing it so that it has a period of 2<sup>32</sup>-1.
I expect the bit stream to appear to be quite random.
</p><p>My Lambda-Man performed reasonably well against my random ghosts, so I put some effort into making my random ghosts a little smarter.
I wrote a ghost <abbr title="artifical intelligence">AI</abbr> that tried to get above Lambda-man and attack him from above.
Then I made each other ghost try to attack Lambda-man from the other three directions in the same manner.
The idea is to try to trap Lambda-man between two ghosts.
</p><p>These smarter ghosts were quite a bit more successful against my simple Lambda-man <abbr title="artifical intelligence">AI</abbr>.
At this point I was out of contest time, so that was it for my <a href="http://r6.ca/icfp2014/icfp2014.tar.gz">2014 ICFP contest submission</a>.
</p><p>Thanks to the organizers for a terrific contest problem.
I am looking forward to see the final rankings.
</p>