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

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:

Despite increasing the maximum bets far in excess of safe levels, SatoshiDice appears to be prospering:

Maybe.  Lotteries usually have really bad house edges (around 50% or so), whereas SatoshiDice only currently takes 1.9%.  So you're less likely to be unlucky at SatoshiDice, mathematically speaking.  But when the flying spaghetti monster is out to get you, mathematical odds don't matter.

I don't have very good luck with lotteries. Does the same carry over into bitcoin? :-P

It's 0 through 65535 inclusive.

So when you play "lessthan 48000" you should win 73.2% of the time, and when you play "lessthan 64000" you should win 97.6% of the time.

I played lessthan 48000 3 times yesterday and only won once (luckily biggest of the 3 bets was the one that won).  But the games are proveably fair - you can get the secret number they used to pick your magic number and validate that they did the maths correctly.

One guy was saying he lost over 60 "lessthan 8000" games in a row the other day, so long losing streaks are definitely possible, just very unlikely.

Tried it a few times last night. Even picked the higher numbers. Lost every time.

What is the pick range of the magic number?

I fixed a bug in the analysis script that was misclassifying some small "lessthan 64000" and "lessthan 48000" wins as refunds.