Friday, November 15, 2019

Riddler Classic 2019-11-15

The Riddler Classic problem this week asks what the expected value of your score would be in a game where digits accumulate but subsequent digits can never be larger than the previous digit (see the page for a better description, especially the example).

Figuring out the expected value for all scores is really hard. But we don't have to figure out all possible scores and the probability of their occurrence. We only need to figure out the expected value for each digit and then sum those expected values. What's the expected value for the most significant digit? What's the expected value for the second-most significant digit? etc. Then sum.

Pretend the game ended after just one roll. Then the expected value of our score is:
\begin{equation}
\sum_{d=0}^{9}\frac{d}{10}=0.45
\end{equation}

But the game continues (the value must go up) so we figure out the expected value of the next digit. Let's consider 9. What's the probability the second digit is a 9? In order for the second digit to be 9, the first must also be a 9. So $P(d_2=9)=0.1*0.1=0.01$. What about 0? If our first digit was 9, then there's still just a $\frac{1}{10}$ chance the next digit is a 0. But if our first digit was a 1, then the outcomes are either 0 or 1, so the probability is $\frac{1}{2}$. More generally:
\begin{equation}
P(d_{i+1}=n) = \sum_{m=0}^{9}P(d_{i+1}=n|d_i=m)*P(d_i=m)
\end{equation}
where
\begin{equation}
P(d_{i+1}=n|d_i=m) =
\begin{cases}
    \frac{1}{m+1},& \text{if } n\leq m\\
    0,              & \text{otherwise}
\end{cases}
\end{equation}
and
\begin{equation}
P(d_1=m)=0.1
\end{equation}

The conditional probabilities can be written as a 10 by 10, lower-triangular matrix. Then the initial probabilities as a row. Multiplying gives the sums above. You can iterate as many times as you'd like to figure out the probability any given digit appears at any place. Multiply by their values as you go and accumulate the expected score. To four places its final value is $0.4737$.

Friday, November 8, 2019

Riddler Classic 2019-11-08

We want to count all the ways we can raid the candy shop, choosing at least 1 and no more than 100 pieces among three options.

This is a combination with repetition. So we add up all of these multisets:

\begin{equation}
\sum_{k=1}^{100}\left(\!\!{3\choose k}\!\!\right)
\end{equation}

which is equivalent to:
\begin{equation}
\sum_{k=1}^{100}\binom{3+k-1}{k}
\end{equation}

And thanks to this nifty identity:
\begin{equation}
\sum_{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}
\end{equation}

We can simplify that sum to:
\begin{equation}
\binom{(3-1)+100+1}{100}-1
\end{equation}

The minus one comes from the original sum starting at 1 instead of 0, so we subtract the choose-zero case. This gives a final value of 176,850 ways.

Wednesday, May 24, 2017

Collaborating to Win a Superbowl Party Game

The approaching NBA Finals reminded me of a game my friends and I play during the Superbowl. It's a little "betting" game to add some interest to the football game. A form is made with several prop bets. Each attendant will choose between one of two choices, many being over-under types. No one has to pay to play. There is no house. It's just a friendly competition to see who can guess the most correctly. Whoever wins the most "bets" right gets a small prize provided by the party host.

Now the lines for these over-under bets are made by Vegas oddsmakers and we get them from the Internet. They don't necessarily represent 50/50 odds for the over/under events. The goal for the oddsmakers is to get 50/50 money on the bets to minimize their risk. So the line represents the average perceived 50/50 odds point of the people who place bets. For my purposes today I'll ignore that and assume the odds are actually 50/50.

At the last Superbowl I brought some family to the party and the five of us filled out our forms. If my goal is not to win but to have someone in my group of five win, what strategy could we use in filing out our forms to maximize the probability that one of us wins? Again, I'll assume every bet on the form has 50/50 odds. We, as a group, also all fill out our forms together. (Or, equivalently, I could enter the contest multiple times.)

This year there were 12 bets on the form. The winner ended up getting 10 correct. The majority of participants got 3 or 4 right. I knew most people going were football fans and would have strong biases when they placed their bets. I figured I probably would have biases, too. So I decided to just use random.org to make each betting decision for me. I ended up getting 6 right.

Suppose I tell my wife that I'll fill out her form. How should I fill it out? The exact opposite of my first form is what I would intuitively decide to do. Her score will be 12-MyScore. We'll come back to this strategy, later. For a group of five, however, it's not so simple.

Consider the outcome space. There are 2^12 or 4096 different ways the results could turn out. We would like the average "distance" from any of these outcomes to one of our five choices to be minimized. "Distance" would be defined as the hamming distance. So the optimal five choices will be placed in this outcome space to jointly minimize their average distance to all possible outcomes. (There's probably some prior research on this topic but I couldn't seem to find the right search term to find it.)

If we have only one choice, it turns out that any choice will do, i.e. any way you fill out the form will, on average, have the same average hamming distance to all possible outcomes. Since all outcomes are equally likely, this makes sense. The expected value of the number of correct bets will be, you guessed it, 6.

I wrote a simple simulator in C++ to find groups of choices (bit strings) that, as a group, minimize the average distance to all outcomes. I can't exhaustively go through all groups of five. That's because 4096 choose 5 is an enormous number (on the order of 10^15). Not so big that it couldn't be done by a super computer but it's too big for the computer and time that I have. So we'll sample the space randomly and find the best ones we can.

The first thing I found was that there are multiple groups-of-five that achieve optimality. This makes sense when you go back to the results of having just a single choice.

To introduce my next result, I would just like to remind you that the number of bits set (or number of bets that are over) follows a binomial distribution. It much more likely that between 5 and 7 bets will be over than that 2 or fewer will be. So when I looked at the number of bits set in each choice over many optimal groups, I found that the number of bits set for my optimal choices also followed a binomial distribution. This makes sense, too. If I can have multiple entries, I want the distribution of my entries to follow the distribution of the outcome space. (For five entries I have a pretty small sample size and perhaps just using the simulator to find an optimal group of five entries would be simpler than coming up with one on my own.)

For the future I'll have to take a look at the other extreme. What betting strategy results in the worst performance? What distribution does it follow? (The inverse of the binomial distribution?)

Also, how does the expected number of correct bets change with number of entries? Obviously this goes up with the number of entries but quantitatively how does it change? All for another day.

Friday, December 30, 2016

Two Games For One Light Strip

I saw a 1-D pong game on Hackaday some time ago. I thought it was just right for a project to work on in my spare time to give as a gift to my sister-in-law's family for Christmas. It was! It uses a PIC16F18855 microcontroller, a potentiometer to adjust brightness, big arcade buttons, and a WS2812b light strip (1 meter, 60 LEDs).

The linked project used an Atmel part but I wanted to try out a PIC part for a couple of reasons. First was because I had my free (to me) PIC programmer so... why not? Second was because of this Application Note (AN1606) from Microchip that describes using the Configurable Logic Cell (CLC) in a way to easily drive WS2811 LEDs. This was easily adapted to my use of the PIC16F18855 and WS2812b LEDs. Though instead of assembly I used the MPLAB Code Configurator to auto-generate my C code to configure the CLC and other peripherals.

The game is simple. Send the light over to your opponent. He must mash his button when the light is close to him (any of the 5 closest LEDs are lit) to return it back to you. You mash your button when the light comes close to you (again, the 5 closest LEDs) to return it to your opponent. If you don't press your button in time, you lose and your opponent gets a point. Depending on which of the 5 LEDs was lit when you pressed your button, the return speed of the light to your opponent will vary. The closer it was to the end of the strip, the faster the return speed; the further, the slower. So if you play well, it will make it difficult for your opponent to return your returns. If you hit too early, it will make it easier for opponent to send a fast one to you. Winning is first to 10 (win by 2) or first to 30. The score is shown after each point by lighting up the number of LEDs corresponding with each player's score. A green LED shows the "line," or the points the game is played to. This will move as the win-by-2 requirement comes into play. A dial on the side adjusts LED brightness.


But just one game? Surely there are more games you can play with two buttons and a strip of lights. There are! I also implemented (though not shown in the video) a "tug-of-war" game. There are two "lines" drawn using a red LED and a blue LED. Then a white LED starts in between these two. Every time you push your button, the white light moves forward. Every time your opponent presses his button, the white light moves backward. Where 1-D pong is about timing and precision, this one is about speed. It's just a button mashing game but it's pretty fun. I originally thought to use the entire strip but then you'd have to press your button as many times as your opponent plus 30. That's a lot. I changed it to be just 10 and sometimes that feels like a lot. The game typically stays in a deadlock until someone tires out. If you just won and are playing again with someone fresh, you'll probably lose. (Okay I'll probably lose. You could win 12 in a row, I'm sure.)

But just two games? Surely there are more games... Nope. That's it. Well, that's all I implemented, anyway. There probably are more but the creativity juice just isn't flowing right now. (But earlier you said "There are!" and not "There is!" I think you owe us another. (No.)) I thought about adding some sort of “secret” mode where you could use the brightness dial and the buttons to set the light strip to any color you wanted for “accent” lighting or something. I wasn’t really sure on it and I ran out of time so that didn’t happen.

My wife and I built the game using some poplar wood to mount it all to and to make boxes for the giant arcade buttons (they're so tall!). She's the better wood worker so I called on her for some help. I soldered it all together on some proto board but I'm pretty sure there was a short or something somewhere because once I put it all together (crammed it in the button box), the switch to change from 1-D pong to tug-of-war didn’t work. So my nephews and nieces only got 1-D pong and no tug-of-war. (Sad.) Making a PCB just for the game would help. It would definitely fit on a cheap-o 5cm x 5cm board that you can get for next to nothing nowadays. I also had some issues with crimp connectors. The far button’s LED wouldn’t light up (which it does when it’s that player’s turn to “serve”). It would work uncrammed from the box but would not after cramming. After attempting to fix both for some time, I gave up and shipped it as is. Lucky for me I have enough parts to make a second one. Time to start drawing up a PCB!

Look at all those wasted pins. The shame.

Ignore that I mixed red/white for power in one place... and reused red/white everywhere.
Another thing I would change was in the mounting of the light strip. We cut out a channel for the strip to sit in so the top was flush with the wood. Then we glued it down. I think that was a mistake. I’d use the plastic clips that are made just for these light strips and just screw down the clips. I hate glue.

The boxes for the buttons are very tall because the arcade buttons are tall. I’d like to find something with a lower profile next time. I figured arcade buttons ought to last a long time, though, and would be easy to repair if something were to happen. Tradeoffs (as always).

The rainbow animation at startup is okay but is kind of lame at lower levels of brightness. I should probably adjust the animation for maximum coolness (i.e. maximum wow-factor (i.e. maximum “take my money!”)) based on the set brightness level. (s/should probably/probably won’t/)

I used a PIC16F18855 because that was the chip used on my PIC programmer (the MPLAB Xpress board) and when I ordered chips I didn't want to find out my "something else" wasn't supported. This one I knew would work. Since ordering parts I've learned many more chips will work (see my previous post about that). I used less than half of the program memory and didn't come close to using all 28 pins. As is, I could use a PIC16F18324 (about 21 cents cheaper in quantity).

I even decided to be a grown up, get a GitHub account, and upload the code there. You can find it here. I don't expect anyone to improve it for me but I'm happy to collaborate.

Wednesday, October 19, 2016

(Almost) Free PIC Programmer (with limitations)

Microchip has made a $10 PIC board to showcase their online IDE, MPLAB Xpress. The board is called the... MPLAB Xpress Board. (Consequence: unhelpful search results!) How do you make it so an online IDE can program your PIC part? Make the programmer look like a USB mass storage device. Now you can (theoretically) use it on any computer the Internet.

I was lucky and was able to snag one of these board for free! They gave away 2000 of them. Free? I can't pass that up. I had never used PIC and never had any real interest. (8-bit? Pffft! But they do have DIP packages...) Did that stop me from getting something for free? No. No it did not. Well after playing with it and looking into all the neat peripherals that PIC parts have, I decided to make this board more useful. I would have put some pin headers on to be able to separate the programmer from the on-board target device but they didn't ask for my input (weird, right?). But they did put some breakout pads on the back of the board (which are pointed out in that linked-to Hackaday article). Obviously we can't have the programmer trying to program two chips at once. So I took the matter of cutting traces into my own knife-wielding hands. I just need to cut right here...

Oops. Wrong spot. (I may get a little impatient when I'm excited to try out an idea.) Actually right there would be better.



Too late now. Two of those five pads are disconnected because I didn't think twice. Luckily some current-limiting resistors provided a nice alternative place to solder some wires to. Crisis averted. A little hot glue to give some mechanical support to my wires and now I have a free PIC programmer!

The firmware for the programmer side is available on GitHub. Here's one drawback listed in the README: "The programming algorithm is currently supporting only the new 8-bit LVP-ICSP protocol common to the PIC16F188xx (5 digit) devices. It is also assuming a fixed row size of 32 words." So... that's a pretty small subset of devices you can program with this. (I count 7 parts that are PIC16F188xx. You want me to read datasheets to figure out if there's more? No thanks. (Okay. I looked at the PIC16F18325/45's datasheet. I'd guess it's compatible based on row size. But no more!)) But I got it for free so I'm not going to complain. And even if they update the firmware source, how am I supposed to update my programmer? (A PICKit 3. But if I had that...)

I even tried it out on a DIP packaged PIC16F18855. It works great! The programmer also has the necessary pull-up resistor for the MCLR line so you can program the chip all by itself in your breadboard.

It's not running in the picture but that LED will blink.
Those wires go to my hacked programmer.


Eventually I'm going to use my PIC16F18855 to drive a strip of WS2812B LEDs. That'll be for another post.

Other links:
MPLAB Xpress forum (for both the IDE and the board, I guess)
Board Schematic

Saturday, January 23, 2016

Running Asterisk with Google Voice on your Synology Diskstation

I run a Synology Diskstation network-attached storage (NAS) at home (specifically a model DS114). I use it primarily for backups but it is really a little server so you can do almost anything on it. This is especially true if you run packages written by the community (though Synology publishes very good ones, too). I run CrashPlan on it so things I store on it are backed up to "the cloud" automatically (see here and here for instructions). I've plugged in a cheap-o USB audio adapter, connected it to my stereo, and can run Shairport on it (originally I ran this but now run the SynoCommunity package). This lets me easily stream audio from my computer to my stereo (using TuneBlade). I also connect my USB printer to it so I can print wirelessly.

One thing I've often wanted to run on it was Asterisk. Asterisk is a program that manages telephone lines and services (especially VoIP lines). Synology officially provides an Asterisk package that even includes a web GUI (though Digium no longer recommends using it). The problem with this package, however, is that they don't include the chan_motif module, which is necessary for running Google Voice lines with it.

While ambitious me usually doesn't stick around too long when he shows up, he was around long enough to try to take the Asterisk source and Synology toolchains from the Synology Open Source Project and rebuild their package from source, this time including chan_motif. I remember getting stuck on building some dependencies for my platform and ended up stopping there.

Months later I decide to revisit this problem. Looking through SynoCommunity's repository for their spksrc tool, I was thinking that maybe this would allow me to more easily create my own Asterisk package. Further looking led me to find their basic instructions for using Debian Chroot (I liked these extended instructions, too). Oh, my. What is this?! It's running a second, parallel OS on your Diskstation. (I've run Optware on a PogoPlug v2 and on my Asus Router that had DD-WRT at the time (now Tomato) and I hated it. I can't remember why but I remember thinking it was such a pain in the neck. I have had zero desire to run it on my Diskstation from day one. That PogoPlug, by the way, lasted less than 18 months before I chucked it in the garbage. I don't miss it. Arch Linux. U-Boot. It all made me want to poke my eyeballs out. That was a long parenthetical.)

So?

Well Debian offers their own package of Asterisk that does include the chan_motif module! No rebuilding from source necessary. (Just a simple 'sudo apt-get install asterisk' is all you neeed.) Now we're cooking with induction.

Now I've seen how things like this go and I am telling you right now that I will not become the go-to guy for support when you want to get Google Voice on Asterisk going on your Diskstation. This is what worked for me in early 2016. May this page go into the rubbish bin of irrelevance and be deemed out-dated not far into the future. I don't care! I have a life to live here, people. (Okay. Okay. I think they get it. Lay off on the attitude a little. (Phrases like "lay off on" make me love English.))

If you want instructions for getting Google Voice going on your Asterisk installation, you can start with Digium's wiki but I would recommend the excellent book Asterisk: The Definitive Guide, 4th Edition which covers it in Chapter 18 (beg your library to get it or if you have a Safari subscription, it's there, too). It's a good book for all things Asterisk.


Wednesday, January 13, 2016

Printing Every Powerball Lottery Number

I think gambling is fascinating. I think it's tempting and I abstain from it. I think it's morally wrong. Value comes from work. You don't get something for nothing in life (there's always a loss to someone).

Tonight the Powerball will play for a world record \$1.5 billion. Billion! That's insane. The odds are also insane. Powerball is played by choosing 5 of 69 numbers and then choosing 1 of 26 "powerballs." How many ways can the Powerball numbers be chosen? That's easy:

\begin{equation}
\binom{69}{5} \binom{26}{1}
\end{equation}

which is:

\begin{equation}
\frac{69!}{5!(69-5)!} \cdot \frac{26!}{1!(26-1)!}
\end{equation}

which is 292,201,338. That's a very big number. I know 1.5 billion is 5 times bigger but it's still a big number. Well let's consider the title scenario of printing out every single Powerball combination possible. Just what would that look like?

When I made a quick test print of different font sizes from 1.5 to 5.5 in half-point increments, I thought 3.5-point Courier New made for a nice size. That's a little more than 1 mm in text height. Making some adjustments to line spacing, page margins, and using 15 columns allowed me to put 2970 Powerball combos on a sheet of paper. If we print double sided we get 5940 combos per sheet of paper (enough combos for 57 years of twice-weekly playing). That means we'll need 49193 sheets of paper or 99 reams of paper! That weighs in at 492 lb. After toner is applied it's sure to weigh more than a quarter of a ton (sorry planet earth). Between me and the paper, I'm pushing the limit of what my Toyota Yaris is rated to carry. (Despite my wife's objection to having 10 cases of useless paper sitting around our house, I think it would be cool to have a copy.)

Walter Hickey wrote an excellent analysis for Business Insider of the expected value of a lottery ticket (written in Sept. 2013). He takes into account the possibility of sharing the jackpot (because more people buy tickets as the jackpot goes up in value) and the loss in value due to taking a lump sum. He does not factor in taxes, though. The short answer is that after taxes, it's never worth playing the lottery. This is no surprise.

The jackpot didn't get to \$1.5 billion by magic. It gets that high because people lose! That \$1.5 billion represents hundreds of millions of \$2 tickets. More tickets than there are combos! The odds truly are terrible. People will often say, "You have to play to win." I would say that the odds are so bad that not playing is as good as winning \$2 (or more!) twice a week for the rest of your life.

Here's a fun simulator (play as much as you want!): http://graphics.latimes.com/powerball-simulator/