Topic: Satoshi Dice -- Statistical Analysis - page 75. (Read 192896 times)

I used the pbinom function in R to calculate a binomial CDF, instead of messing with beta functions. You could also use the Gnu Scientific Library, specifically gsl_cdf_binomial_P where the three variables used in the function are the number of wins (q in R, k in gsl), the probability (p in both R and gsl), and the number of trials (size in R, n in gsl).

For my variables I used your data with the integer value in the "Win" column as q, the "Should win" column as p, and the "#Bets" column as size. If you're using R, also use the lower.tail = TRUE arg.

Interesting.

How are you calculating the CDF?

I thought this might be of interest. The last column of the table shows how probable the luck for a given game is. As a simple indicator, consider game with a CDF over 0.95 to be very lucky and any game with a CDF under 0.05 to be very unlucky.

As a measure is's quite useful since the CDF results tends to be counter-intuitive as they are affected by observation size as well as the outcome. For example, the 48000 game has been very lucky so far, even though the fraction of wins (0.73581) is not much larger than the probability (0.73242). The 128 game seems very lucky (0.00224 compared with 0.00195) but the CDF shows us this is not significantly lucky (0.75278). The 32 game seems unlucky (0.00029 cw 0.00049) but isn't unusual  (0.49737).

I was made aware of it by one of Derren Brown's TV shows - possibly this one.  I'd check but I think the storm outside is making my Internet connection too flaky to do anything much at the moment.

The charts are from gnuplot using data generated by a modified version of the extras/sample_armory_code.py script in the armory git repository.

I follow now. Nice clear way to approach the problem when you put it like that.


I hadn't been aware of that, it's an interesting problem. Thanks!

Btw, what are you using for charts?

After all that unpleasant maths back the your regularly scheduled tables of numbers and graphs...




I noticed a sharp drop of 100 BTC or so on the red line about a day ago and looked to see what happened.

This bet is responsible for the loss.  2 BTC on each of lessthan 1500, 2000, 3000, and 4000, with a lucky number of 920 winning all 4 bets.  A 223.90897599 BTC return for an 8 BTC outlay!

Here, for 6 heads in a row.  The expected length of a round is the sum of the probability of each outcome times the length of that outcome:

Outcome	p(Outcome)	len(Outcome)	p(Outcome)*len(Outcome)
T	1/2	1	1/2
HT	1/4	2	1/2
HHT	1/8	3	3/8
HHHT	1/16	4	1/4
HHHHT	1/32	5	5/32
HHHHHT	1/64	6	3/32
HHHHHH	1/64	6	3/32
			-----
			63/32

so 63/32 flips.  The expected number of rounds to get 6 heads is 64, the expected length of each round is 63/32, so the expected number of flips is 64*63/32 = 126.


... and you were, a couple of times...    But only in little ways.

This reminded me of both Penney's game and the discussion around this question, both of which you may find interesting if you didn't see them before.

Tricky one, that. Toss a coin one million times and see how many times you get three heads in a row, right? Not a geometrically distributed random anymore, since the round end is either throwing a tail or or getting three heads in a row.

I'm not sure of your method but you do have the correct answer. In general, the number of coin tosses it takes on average to get n heads in a row is given by:


  Heads in a row   Expect. no. tosses
               1                  2
               2                  6
               3                 14
               4                 30
               5                 62
               6                126
               7                254
               8                510
               9               1022
             10               2046
             11               4094
             12               8190
             13              16382
             14              32766
             15              65534
             16             131070
             17             262142
             18             524286
             19            1048574
             20            2097150

Try this against your method and see if you're right in a few more cases. I'm not saying you're wrong, just that I don't follow how you got your result.

There's a very nice derivation of this (and of a more general solution where the probability of a head or tail varies with each toss) using Markov chains here.


It was fun and I got to learn some new things. Plus you also persevered - I could have been wrong.

You're right.  It seems counter-intuitive to me that flipping three heads in a row (a 1-in-8 shot) takes an expected 14 flips to happen, but it does.

Because the average length of a round which ends when we either flip a tail or get 3 heads:

T : half the time
HT : 1/4 the time
HHT : 1/8 the time
HHH : 1/8 the time

is 1*1/2 + 2*1/4 + 3*1/8 + 3*1/8 = 1.75 tosses - so the expectation is that it takes 1.75*8 = 14 flips.

Thanks for persevering with me!

Then he hasn't finished playing, in terms of the definition of "round" which I gave above. This is equivalent to "75 losses or greater" the probability which is as I described:


except I was wrong - the upper tail CDF is (1-1/p)^(k-1). Ooops! Still, the basic idea remains the same - multiply by the number of expected rounds per game to get the number of plays before 75 losses on a row or more occurs.


Sure. As per the first part of my post, you can find the probability of 10 or more heads by using the upper tail CDF: (1-p)^(k-1). In this case, it's (1-1/2)^9 = 1/512. This probability means that for a round defined as a series of flips ending in a tail, flipping 10 or more heads in a row should occur once every 512 rounds, or once every 1024 plays - as you saw in your simulation.

So going back to the original question - how many times would any one players be expected to play to experience 75 losses or more in a row? The upper tail CDF is (1-8000/65536)^(75-1) = 1/15274.94  and the mean number of plays per round = 8.192, so we would expected a run of 75 losses or greater to occur once every  125132.3 plays. Different from my original answer because I had the upper tail CDF function wrong. You can check with this simulation if you like:


I could be wrong - write your own sim to check and see how it goes!

Is that 'exactly' where we are differing?  The guy didn't have exactly 75 losses and then a win.  He had 75 losses and quit playing.  Who knows how many losses he would have had if he had kept playing.

I think we expect at least 10 heads in a row once every 1024 flips.

(exactly 11 heads is half as likely as exactly 10, exactly 12 is half as likely again,etc.  1/2 + 1/4 + ... = 1.  ie. the chance of seeing exactly 10 is the same as the chance of seeing 11 or more.  I see exactly 10 once every 2048 flips, I see 11 or more once every 2048 flips too.  Combining these 2, I see 10 or more every 1024 flips.

OK, here's how I see it:

The number of times any one player must play before he wins at the 8000/65536 game is a shifted geometrically distributed random variable, p = 8000/65536. Let the term "round" indicate a series of plays ending in a win.

This means the probability of 75 or more plays before a win is given by the upper tail geometric distribution CDF:


So for every round played, there is a 5.747515e-05 chance the round will end after 74 plays. So, on average, we expect one in 17398.82 rounds to last 75 plays or more.

The mean number of plays per round is:


So, converting rounds to plays, we expect a run of 75 or more losses in a row to occur once in 17398.82 * 8.192 = 142531.1 plays.

So I was out by a factor of almost 10.


For you (fair) coin flip example, calling a series of plays ending in a head a "round", 10 heads in a row has a probability of occurring determined by the probability density function, p*(1-p)^(k-1).

In this case, k = 10 and p = 0.5, so the probability of winning exactly 10 heads in a row for a given round is 0.5*(1-0.5)^9 = 1024

There is a mean of 2 flips per game, so we'd expect exactly 10 heads in a row once every 2048 flips.

Here is my code for a coin flip simulation, written in R:


1/0.0004780581 = 2091.796, quite close to the exact 2048.


Edit: If you want to know the probability of exactly 75 losses in a row occurring, use the geometric distribution probability density function: p*(1-p)^(k-1) =  8000/65536*(1- 8000/65536)^(75-1) = 7.99154e-06 or once in 125132.3 rounds. Since one round has a mean number of plays of 8.192, the expected number of plays before a round of exactly 75 losses before one win is 125132.3 * 8.192 = 1025084 plays.

Some more R code for you to try, simulating a game that ends a series of losses with a win, the probability of a win being 8000/65536:


Quite close. The lower p is the greater the variance so you might want to bump the first term in rgeom() up to 1e10 if you machines faster than my work computer.

Here's the simulation code:

I think you might be right - serves me right for posting while trying to leave early for lunch. I'll go over it later and see if I come to the same results as you.

I'm not sure, but I don't think you should multiply by 75.  Maybe add (75-1).

Consider flipping a fair coin.  How many times do you need to flip before it is 'likely' to get 10 heads in a row?

It's a 1-in-1024 chance, so I would say you need to flip 1024 + (10-1) = 1033 coins to have a reasonable chance of 310 heads in a row.

By your (implied) logic would you say you need 1024*10 = 10240 flips to make it likely?

I just ran a simulation.  Flipping coins until getting 10 in a row, and counting how many flips it took.  I tried it 100,000 times.  116 (0.12%) of those times the first 10 coins were all heads.  To have a 1% chance of getting 10 heads in a row I had to flip 29 times.  For 10% I had to flip 221 coins, etc.  Flipping 1033 coins gives a 39.71% chance of getting 10 heads in a row.

But flipping 10239 coins gives a huge 99.34% chance.

I have a feeling this is a binomial distribution thing, so I should be able to work out the maths rather than doing it by simulation.  But I think that after 17399 * 75 plays you're almost guaranteed to have a losing streak of 75 or more.

Oh, and the analysis I'm posting is based on work done by etotheipi - the OP in this thread.  But I'm glad you appreciate it.

Quick comment: It's even unluckier than that, since  it's 1 chance in 17399 of a run of 75 or less bets in a row not winning - so that's going to have required 17399 * 75 =   1304925 or more bets to make it likely to have occurred once.

Enjoying you analysis so far - thanks for your work.

3 new games have been introduced: lessthan 52k, 56k, and 60k: