variance in block times --- std deviation

[tspacepilot]

I know that mining difficulty is adjusted from time to time in order to keep the blocks hashing on average at 10 minutes per.  However, from my experience waiting for confirmations here and there, I also know there can be quite a bit of variance in this distribution (the distribution of time-between-blocks).  Has anyone calculated the standard deviation?

[Amph]

it would go all the way up to 20 mins, but no more then 30 for sure(there are exception of 1 hour or more), it is based on a exponential distribution

it would go all the way up to 20 mins, but no more then 30 for sure, it is based on a exponential distribution

You clearly have not actually looked at the history as it has taken over an hour to create a new block in the past.

(of course your post was made because of your ad-sig rather than for any actual "real reason" as you didn't even bother doing the slightest bit of research before posting)

well not, i did some search, it was not made purely because of the sig, i know that it can go to 1 hour or even more, but the average(of rising or falling above 10 min) is what i've wrote

p.s. i didn't include it at first because those(rising to one hour or more) were only isolated cases

[CIYAM]

it would go all the way up to 20 mins, but no more then 30 for sure, it is based on a exponential distribution

You clearly have not actually looked at the history as it has taken over an hour to create a new block in the past.

(of course your post was made because of your ad-sig rather than for any actual "real reason" as you didn't even bother doing the slightest bit of research before posting)

[CIYAM]

it would go all the way up to 20 mins, but no more then 30 for sure, it is based on a exponential distribution

Is what you wrote.

Now - if you want to do the honourable thing then edit your original reply rather than making a new post (which would be the "ad-sig" thing).

[CIYAM]

p.s. i didn't include it at first because those(rising to one hour or more) were only isolated cases

Respect - you didn't make a separate post (sorry but I do tend to get annoyed by ad-sigs) and yes such very long confirmation times are not very often.

What would be more interesting would be a mathematical explanation for the longest possible time one might have to wait for a confirmation (assuming that the network hashing rate hadn't decreased radically).

[cr1776]

Hi,
Here are some discussions about it block times, standard deviations, means, medians, probability densities and distributions.  Instead of re-doing the math, I think these do a reasonable job of explaining it.  But, perhaps they will spawn other questions or not answer it.  ;-)

In regard to the 30 minute comment,  ~95% of the time there is at least one block found every 30 minutes.


http://www.reddit.com/r/Bitcoin/comments/2vocap/what_is_the_standard_deviation_of_time_between/

http://bitcoin.stackexchange.com/questions/25293/probablity-distribution-of-mining

https://bitcointalk.org/index.php?topic=906082.msg9955875#msg9955875

[tspacepilot]

Ok, some kinda sig-ad warfare happened here with CIYAM and someone else.  Anyway, from what I recall from a course taken a long time ago, we calculate variance by doing the sum of square differences from the mean  and divide that by the sample size.  Then maybe the square root of that is std-deviation?  I guess I was hoping that one of the whizzes out there would already have this for me (ie, it's a known) rather than me having to look into it.

@CIYAM I think the longest possible time is infinity.  Since we can never guarantee that the next block will be found (ie, the true distribution of times between blocks should have tails that asymptotically approach infinity (one one side) and zero (on the other)), but I'm not so much intersted in the max and min but in an empirical sampling over which we can calculate variance (I'm sure there's some such sampling being done in order to make the difficulty adjustments).

EDIT: @cr1776: thanks for those links.  Some of them have more info than others.   I'm not sure anyone actuall did the empirical sampling.  But the consensus seems to be that the distribution is asymmetrical and has a std dev of 10 minutes.  I'd consider my question more or less answered, but I'll leave this open in case anyone does the sampling or has something else to add here.

[gmaxwell]

Block finding is just a poisson process; its variance of the intervals well defined-- 1/(lambda)^2; and thus the std dev is the same as the mean.  Observed empirical variance will be slightly different due to shot noise, changes in hashrate, etc... but close enough.

It's important to keep in mind that the variance is a necessary component; without variance the network would never converge again after a fork.

[Cryddit]

Std Deviation is 10 minutes, but it's asymmetric.  Obviously, the odds of the next block arriving before the current one is zero (although timestamps sometimes lie to the contrary), but the odds of a block taking 20 minutes, 30 minutes, etc, are positive. 

It's got what I think of as a "half-life."  I'm not entirely sure how long the half-life is but I think it's something around 7 minutes.  So I'd expect a distribution something like: it's ALWAYS (how long since the last one doesn't matter) got a 50% chance of arriving within the next 7 minutes, 25% chance of arriving between 7 and 14 minutes, 12.5% chance of arriving between 14 and 21 minutes, etc. 

But I'm not entirely sure how long the "half-life" period is.

[teukon]

Std Deviation is 10 minutes, but it's asymmetric.  Obviously, the odds of the next block arriving before the current one is zero (although timestamps sometimes lie to the contrary), but the odds of a block taking 20 minutes, 30 minutes, etc, are positive.  

It's got what I think of as a "half-life."  I'm not entirely sure how long the half-life is but I think it's something around 7 minutes.  So I'd expect a distribution something like: it's ALWAYS (how long since the last one doesn't matter) got a 50% chance of arriving within the next 7 minutes, 25% chance of arriving between 7 and 14 minutes, 12.5% chance of arriving between 14 and 21 minutes, etc.  

But I'm not entirely sure how long the "half-life" period is.

Yes, this is an apt analogy.

Also, good guess!  The corresponding period is

	-log(1 - 50%) * 10 minutes
=	log(2) * 10 minutes
=	6 minutes and 55.89 seconds (2.d.p)

[Peter R]

And a weird property of the Poisson distribution is that it doesn't matter how long you've already been waiting, the expectation time for the next block is always 10 minutes from now. 

[teukon]

And a weird property of the Poisson distribution is that it doesn't matter how long you've already been waiting, the expectation time for the next block is always 10 minutes from now.  

Indeed.  This seems to catch many people out.  Given the information: "there is one block on average every 10 minutes", one would naturally expect the age of the current block to have some bearing on the expected time to the next block.

Oddly, absent knowledge of the most recent blocks, the expected age of the current block is also always 10 minutes.  This paradoxically suggests that the average gap between two consecutive blocks is 20 minutes.

[tspacepilot]

Block finding is just a poisson process; its variance of the intervals well defined-- 1/(lambda)^2; and thus the std dev is the same as the mean.  Observed empirical variance will be slightly different due to shot noise, changes in hashrate, etc... but close enough.

It's important to keep in mind that the variance is a necessary component; without variance the network would never converge again after a fork.

Thanks gmaxwell, this definintely answers my question concretely.  I can look up the poisson process in wikipedia or something to know more.

Std Deviation is 10 minutes, but it's asymmetric.  Obviously, the odds of the next block arriving before the current one is zero (although timestamps sometimes lie to the contrary), but the odds of a block taking 20 minutes, 30 minutes, etc, are positive. 

It's got what I think of as a "half-life."  I'm not entirely sure how long the half-life is but I think it's something around 7 minutes.  So I'd expect a distribution something like: it's ALWAYS (how long since the last one doesn't matter) got a 50% chance of arriving within the next 7 minutes, 25% chance of arriving between 7 and 14 minutes, 12.5% chance of arriving between 14 and 21 minutes, etc. 

But I'm not entirely sure how long the "half-life" period is.

Thanks cryddit, your answer makes it really clear why the tail on th right is so much longer than the one on the left (you hit a wall on the left where the previous block happened and there's no such wall on the right).

Thanks to others as well, I'm going to read some wikipedia articles now and try to get a little smarter.  Cheers!

[Pietjebel]

I have a question complementing this thread.
I have copied a chunk from the whitepaper:

The average work required is exponential in the number
of zero bits required and can be verified by executing a single hash.
For our timestamp network, we implement the proof-of-work by incrementing a nonce in the
block until a value is found that gives the block's hash the required zero bits

Every 2 weeks difficulty is adjusted to keep the 10 minutes avarage in place, but how can this be garanteed since adding or subtracting a nonce will change the difficulty and thus the average exponentialy.
Is there no risk the average will go from lets say 8 minutes to 16 minutes ?

[tspacepilot]

I have a question complementing this thread.
I have copied a chunk from the whitepaper:

The average work required is exponential in the number
of zero bits required and can be verified by executing a single hash.
For our timestamp network, we implement the proof-of-work by incrementing a nonce in the
block until a value is found that gives the block's hash the required zero bits

Every 2 weeks difficulty is adjusted to keep the 10 minutes avarage in place, but how can this be garanteed since adding or subtracting a nonce will change the difficulty and thus the average exponentialy.
Is there no risk the average will go from lets say 8 minutes to 16 minutes ?

I think I understand your question as "how can they always target 10, since adding or removing a requirement for a zero moves the difficulty target exponentially".  I would also like to know the answer to this, but to clarify the quote from the whitepaper, the nonce they're incrementing is just a value added to the block hash in order to make the block hash to the right number of leading zeros.  They keep incrementing the nonce until they find a block hash the satisfies the difficulty requirments.  But the "nonce" is not the same thing as the leading zeros themselves.  I await an answer to your actual question from someone smarter than me

[spin]

We can work out using http://en.wikipedia.org/wiki/Exponential_distribution#Quantiles that:
99% of blocks to be found in 46mins..  Which means 1 in 100 blocks will take longer than that.  This is assuming a stable hash-rate/difficulty.

Might help with the original query.

[tspacepilot]

We can work out using http://en.wikipedia.org/wiki/Exponential_distribution#Quantiles that:
99% of blocks to be found in 46mins..  Which means 1 in 100 blocks will take longer than that.

This is assuming a stable hash-rate/difficulty.

I'm sure I'm missing something, but isn't that equation based on continuous parameters?  Whereas the number of leading zeros is always discreet.  So what happens when, say 2 leading zeros at a given hashrate would lead to 8 min block times but 3 leading zeros would lead to 16 minutes.  You can't require 2.5 zeros.  Sorry for my dumbness.

[DannyHamilton]

- snip -
I think I understand your question as "how can they always target 10, since adding or removing a requirement for a zero moves the difficulty target exponentially".  I would also like to know the answer to this,
- snip -

We don't just add or remove a zero.

Adding or removing a zero was an example in a concept document about how a difficulty could be adjusted.  It does not describe how the difficulty adjustment was actually implemented once the software was written.

Instead, the difficulty target is simply a 256 bit number.  Any hash value that is less than the target is valid regardless of how many zeros there are.

Now in practice, a number that is less than the target will never have LESS leading zeros than the target has, but it might have the exact same number of zeros if the rest of the hash is less than the target difficulty.

[spin]

The other thing with the exponential distribution is it has no maximum value.

So you could potentially have a long wait (but with low probability).

Here are some more probabilities:
min   probability 1 in
10   36.7879%   2.7
20   13.5335%   7.4
30   4.9787%   20.1
40   1.8316%   54.6
50   0.6738%   148.4
60   0.2479%   403.4
70   0.0912%   1096.6
80   0.0335%   2981.0
90   0.0123%   8103.1
100   0.0045%   22026.5
110   0.0017%   59874.1
120   0.0006%   162754.8

So chances of a block taking longer than 2 hours is 0.0006% (or 1 in 162 755 blocks).

Assuming difficulty and hash rate is in perfect balance and stable.

[Pietjebel]

Cheers for that Danny.

Btw, would a realtime difficulty adjustment be feasable in order to garantee a 10-12 min range for instance ? I mean from a architectual perspective ?

I guess not since it would probably be done already. But it would have advantages I take it.