Feb 8, 2011 - Expected Number Of Coin Tosses Until You Get Tail

Because of my interest in BitCoin I was confronted with the question of the expected number of attempts to achieve a specific result if the probability of achieving the result per attempt is fixed. In BitCoin mining, the miners test nonces for hashing a certain value, trying to find a nonce so that the sha256 hash of the nonce combined with the value is a number below a certain threshold. Every test of a nonce has a fixed probability of succeeding, so it is exactly this classic problem of the expected number of attempts.

A simpler variant of the problem is: what is the expected number of coin tosses until you receive head (or tail). Or how many dice rolls on average until you roll a six.

Anyway, my maths being a little rusty I did not know immediately how to calculate it. I remember how to calculate the expected "value" of some event: it is the sum of the values of the possible outcomes multiplied with the respective probabilities for the outcomes. But for the expected number of attempts until something happens, this yields an infinite sum: p*1+(1-p)*p*2+(1-p)^2*p*3+...+(1-p)^(n-1)*p*n+... if the probability for the desired result is p. That is because the probability to get the result after n attempts for the first time is the probability to not get it in the first n-1 attempts (1-p)^(n-1) multiplied by p. And we want to sum the probability for it taking one attempt+the prob. for it taking two attempts+... up to infinity.

On the internet I found some claims that the expected number of attempts is simply 1/p, but I could not find an explanation for it. Now in the meantime I found a really elegant and much more versatile solution to the problem, but I had already decided that I needed to tackle that "nasty" infinite sum. So while the solution mentioned above obliterates the need, I still want to show how to compute that infinite sum, as I could find no other explanation on the internet.

To compute the infinite sum, we'll look at the partial sums p*1+(1-p)*p*2+(1-p)^2*p*3+...+(1-p)^(n-1)*p*n. Thinking about progressions, one famous progression immediately comes to mind: the Geometric Progression p+p^2+p^3+...+p^n. It is memorable for the neat trick for computing it's value: multiply the whole thing by (1-p)/(1-p), then most terms in the numerator cancel each other out and we are left with (1-p^(n+1))/(1-p).

Our sum almost looks like the geometric progression, if only we could use the same trick to compute it. Luckily we can. First, let's say q = (1-p) and observe that we can factor out the p from the sum. So we are left with the problem to compute p(1+2q+3q^2+...+nq^(n-1)). If we multiply this with (1-q)/(1-q) we get

p(1+(2q-q)+(3q^2-2q^2)+...+(nq^(n-1)-(n-1)q(n-1)-nq^n)/(1-q) = (since p = 1-q)

= 1+q+q^2+...+q^(n-1)-nq^n

The first part of that is a geometric progression, so we know it is equal to

(1-q^n)/(1-q) - nq^n

Still not that pretty, but we are making progress. Rather than trying to make that partial sum more pretty, let's see what happens for n-> infinity: since q < 1 we have q^n -> 0 and I claim that nq^n -> 0 too (will show this later). Therefore lim_n_to_infinity((1-q^n)/(1-q) - nq^n) = 1/(1-q), or 1/p. So there we have it, the expected number of attempts until a result of probability p happens is 1/p.

For toin cosses p = 0.5, so the number of attempts is 2. For rolling a six with a die, it is 6.

As for the remaining step, nq^n -> 0 for q < 1, I admit I also had to Google for a hint. The (or one trick) is to write q as 1/(1+a) for some a > 0. Then the equation becomes n/(1+a)^n. Then we look at the Binomial Sum for (1+a)^n, which is

1+(1 out of n)a+(2 out of n)a^2+...+a^n <= n(n-1)*a^2/2 (since 2 out of n = n(n-1)/2).

Therefore n/(1+a)^n <= n/(n(n-1)*a^2/2) = 2/((n-1)a^2) which obviously goes to 0 for n -> infinity.

I am not sure who the audience for this blog post could be, but anyway, I am glad I found a small puzzle and managed to learn some simple new tricks while trying to solve it. I am excited about the solution I linked to above, which sets up equations for the expected value E = 1*p+(1-p)*(E+1). It is much simpler, and also more versatile, as you can use the same approach to answer questions like "how many coin tosses until you get three times head in a row". Somehow I have never encountered that approach before, as far as I remember.

Also I must admit I was a bit disappointed by the internet, namely the apparent willingness to accept the formula E(number of attempts) = 1/p without questioning how to derive it. This has to be explained somewhere else already, but if not, maybe I did my small part to plug an information hole in the internet. :-)

Sep 12, 2010 - Fixing WLAN Connectivity Issues On My MacBook

It is almost too simple to blog about, but on the other hand, it caused me some grief.

Short summary: fixing the WLAN channel fixed the WLAN performance. It had never occured to me to try switching the channel because signal strength had always be shown as excellent. However, apparently the external monitor somehow disturbed the connection on the default channel.

I had been experiencing really bad network problems on my home network for a while. It had gotten so bad that I even used Tethering on my Android phone as a fallback at times, and I did not even dare to play my beloved Carcassonne games on Brettspielwelt anymore, because they would be so painfully slow.

Disconnecting my MacBook from the external monitor and going next to the WLAN router with it seemed to yield big improvements. So it looked as if the signal strength simply was not good enough. I already thought about buying another router or even plugs for networking via the power grid. However, the signal strength indicator for the WLAN was always at 100%, which seemed strange.

As a last test, I remembered about the command line tool ping. pinging my router, ping told me I had 20 to 40% packet loss. Really bad. But then I disconnected the monitor and tried ping again - suddenly the packet loss was 0%. After some more trials, like connecting the monitor to another computer, it became clear that it is really when the external monitor is connected to my MacBook that the WLAN connection goes bad. Apart from ping, using some of the speed detection web sites also was informative. Download speeds quadrupled without the external monitor being plugged in. By googling I found that others experience this, too.

At first I was frustrated, expecting costly repairs or hardware replacements, but then I read somewhere that changing the WLAN channel might help. So I switched my router from automatic channel selection to channel 5 (before it was using 11), and since then, the WLAN connection seems to be fine. (Knock on Wood - it's only been 30 minutes since I changed it).

So that's it - switching the channel should have been the first thing to try when I experienced connectivity problems. However, it didn't occur to me because the network strength indicator always showed a strong signal. Only with ping was I able to see the packet loss despite of the good signal.

It's such a relief to have a snappy network connection again. Especially as I didn't have high hopes for finding a solution by myself, as I know next to nothing about optimizing WLAN networks.

Jun 20, 2010 - Mac Mini G4 Homeserver With Ubuntu Linux 10.04, WPA2

I finally got WPA2 to work on my old Mac Mini G4, which is running Ubuntu Linux 10.04 server edition for PowerPC (Update: WLAN worked for a while, but it seems to be very unstable. Could be the location where it sits, or the software - Update2: running it at another location, it seems to work fine and stable).

I wanted to use the old Mini as a homeserver for a long time, but my girl-friend had complained about the (faint) noise it makes. Without a wireless connection, I had to place it next to the router, which in turn is placed next to her room.

Now with wireless I put it on the fridge in the kitchen, which is already quite noisy. Unfortunately, my girl-friend still complains. But I hope she'll either get used to it, or I can still find a better place. With WLAN, there are more options.

Since I have installed Ubuntu Server and Samba for serving Windows shares months ago, I have forgotten the steps and can not talk about them now. I remember that the Ubuntu installation was really simple. Also I had apparently already configured the driver for the Mini's wireless card, so I am not sure how I got that working. For a long time, I was unable to get wireless to actually work, especially not with WPA_SUPPLICANT providing access to my WPA2 encrypted network.

Hopefully information for installing the correct drivers for the Mac Mini wireless card can be found reasonably easy, as I can not retrace the steps anymore. My Mini required the b43 drivers, which requires download of the firmware by installing the b43-fwcutter package (sudo aptitude install b43-fwcutter).

So assuming your driver is working, I eventually found WPAHowTo for an old version of Ubuntu that describes most of the steps for configuring WPA2 (I only read the WPA_SUPPLICANT parts of that HowTo). All the newer how-tos seem to assume a graphical user interface and only describe how to use network-manager.

All instructions say to shut down eth0 before trying to start wlan0 (that's how they are called on my system). So I grudgingly connected the Mini to a monitor and a keyboard again to complete the configuration. I also tested wlan without encryption, which worked.

Next install wpa_supplicant if not already done (sudo aptitude install wpasupplicant).

My wlan network uses a preshared key, so I used wpa_passphrase to generate the basis for a config file:

wpa_passphrase NetworkEssid passphrase

(replace NetworkEssid and passphrase according to your network's setttings).

which resulted in output like

network={
ssid="NetworkEssid"
#psk="TextPassphrase"
psk=somerandomnumbersandletters
}

Then create or edit /etc/wpa_supplicant.conf (on my system the file did not exist yet). Since it needs the output of wpa_passphrase, I actually piped the output of wpa_passphrase into a file and copied it to /etc/wpa_supplicant.conf (somehow piping there directly didn't work). (all operations in /etc require root privileges, so sudo accordingly). Also change owner and group of the conf file back to root in case by copying it or creating it it became owned by your "normal" user (chgrp root thefile and chown root thefile).

After some searching around, I found an example wpa_supplicant.conf for a WPA2 WLAN network using a preshared key and CCMP/AES encryption here They say they need a weird "double configuration" for it to work, but actually it also worked for me when I removed the TKIP stuff. So my final wpa_supplicant.conf file looks like this:

network={
ssid="dummy"
proto=WPA2
key_mgmt=WPA-PSK
pairwise=CCMP
group=CCMP
#psk="dummydummy"
psk=somerandomnumbersandletters
}

(Except of course other values for dummy and psk). It is probably save to delete the line with the clear text password, too.

Now the instructions from the WPAHowTo said to test wpa_supplicant like this (already with my parameters, not the ones from the HowTo):

sudo wpa_supplicant -iwlan0 -c/etc/wpa_supplicant.conf -Dwext

(Omitting the -w parameter from the HowTo, doesn't seem to exist anymore)

The problem here was the -D parameter, as here you are supposed to state the correct driver (also, apparently, instead of wlan0 your wlan might have a different device name). At the Homepage of the linux driver for the b43 I found the information that "wext" should be used for wpa_supplicant.

So, again following the old HowTo, I put the following into my /etc/networks/interfaces:

auto lo
iface lo inet loopback
address 127.0.0.1
netmask 255.0.0.0

#auto eth0
iface eth0 inet dhcp

auto wlan0
iface wlan0 inet dhcp
wpa-driver wext
wpa-conf /etc/wpa_supplicant.conf

Now if I power up the server, it automatically connects to my WPA2-encrypted WLAN. I was very happy about this and put the server on the fridge. However, while I started writing up this summary, I experienced several connection losses. Now I feel like giving up on connecting the server via WLAN and try one of those Powerline networking things instead, which enable networking through the electric power lines (like this one).. On the other hand, I just moved the Mac Mini server into my room to connect it to the monitor again, and here WLAN seems to work fine. So maybe it was just the location on top of the fridge that doesn't work - it is closer to the router, but at another angle and with different walls in between. I might try some other places for the server yet.

One candidate might be the bathroom, but I am bit worried about the occasional high humidity.

There are yet more issues to be solved before my home server is ready. Backups, what kind of file systems to share, iTunes server (?) or something else?

One small thing I also haven't yet found a solution for yet: it would be nice if the Mini would shutdown if I press the power button. At the moment the power button simply seems to be ignored by the Ubuntu Server installtion. I could not yet find a solution for this - in the net there are some instructions for making the power button initiate the shutdown sequence, but they are all for normal PCs, not for PowerPC Minis. If anybody knows of a solution, please let me know!

That way, my girl-friend could also power the server on and off without having to learn about ssh and linux shells, and it wouldn't have to run all the time.