Bitcoin Forum
December 03, 2016, 11:52:40 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: the three doors problem, increasing the chance of finding the right hash  (Read 3296 times)
forests
Newbie
*
Offline Offline

Activity: 20


View Profile
June 15, 2011, 06:34:02 PM
 #1

Many of you may be familiar with the three doors problem, aka the Monty Hall problem. (info on wikipedia).

Basically it states that you have three doors presented to you, one which holds a car behind it.  You pick one giving you 1/3 of a chance of having the right answer, but then you're presented what's behind one of the doors you didn't pick, and it's not the car. If you switch your pick, your chances of being right increases to 2/3, instead of your original chance of 1/3.

Here's the results of a simulation
http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Monty_problem_monte_carlo.svg/583px-Monty_problem_monte_carlo.svg.png

So what if we give miners the monty hall problem? We could increase the chances of finding the right hash by a nice margin.

So in a pool you could effectively have it so 90% of miners ditch 1/3 of the hashes that need to be tested, and 10% of the miners work on the ditched ones.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
ukbitco.in
Jr. Member
*
Offline Offline

Activity: 30


View Profile
June 15, 2011, 06:58:10 PM
 #2

Who's going to show you there is a goat behind a door?
gigitrix
Sr. Member
****
Offline Offline

Activity: 476


Bitcoins finest!!!


View Profile
June 15, 2011, 07:12:16 PM
 #3

You misinterpret the statistics behind purely random hashing.
tito13kfm
Jr. Member
*
Offline Offline

Activity: 42



View Profile
June 15, 2011, 07:27:22 PM
 #4

In the Monty Hall problem, the host has knowledge that the player does not.  In bitcoins, the pool does not have this knowledge.

Monty Hall does not open one of the 2 remaining doors at random, he shows you one which does not contain a car because he knows which one has the car in it.

If you do what you suggest you would just increase variance by a wide margin which is what pools are looking to reduce.

DamienBlack
Jr. Member
*
Offline Offline

Activity: 56


View Profile
June 15, 2011, 07:38:08 PM
 #5

Indeed, this doesn't work. The "host" needs to know which door to open that doesn't have the right thing. The extra odds comes from the information the host gives you. If miners just discard blocks at random, it does nothing to help your odd.

To show you the truth of this, imagine that the host doesn't know anything about where the car is. You pick a door, he opens one, then you switch. 33% of the time you'll have picked the right door to start, 33% of the time, the host will open the right door (ending the game early) and 33% of the time you will switch and find the right door. As you can see, your odds didn't go up by switching doors.

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
Klestin
Hero Member
*****
Offline Offline

Activity: 494


View Profile
June 15, 2011, 07:41:48 PM
 #6

Who's going to show you there is a goat behind a door?
You sir have hit the nail on the head.

In a weird coincidence, I just explained the monty hall problem to my daughter today.  *Checks for hidden microphones*
tito13kfm
Jr. Member
*
Offline Offline

Activity: 42



View Profile
June 15, 2011, 08:15:56 PM
 #7

Who's going to show you there is a goat behind a door?
You sir have hit the nail on the head.

In a weird coincidence, I just explained the monty hall problem to my daughter today.  *Checks for hidden microphones*

There is a specific term for this kind of phenomenon, but it escapes me at the moment.  I believe the term is Dutch or some other similar language.  It basically states that upon learning new information or discussing something long forgotten the likelihood of hearing about it fairly shortly afterwards is increased.

forests
Newbie
*
Offline Offline

Activity: 20


View Profile
June 15, 2011, 09:59:07 PM
 #8

Indeed, this doesn't work. The "host" needs to know which door to open that doesn't have the right thing. The extra odds comes from the information the host gives you. If miners just discard blocks at random, it does nothing to help your odd.

To show you the truth of this, imagine that the host doesn't know anything about where the car is. You pick a door, he opens one, then you switch. 33% of the time you'll have picked the right door to start, 33% of the time, the host will open the right door (ending the game early) and 33% of the time you will switch and find the right door. As you can see, your odds didn't go up by switching doors.

When the host picks the right door at the start you win. No more need to switch.

When the host picks the wrong door, then what exactly is the situational difference between this and the monty hall problem? In both cases you've gotten one wrong door open, and two doors closed. That gives you 2/3 of a chance if you switch.

I wrote a C implementation, source here http://pastebin.com/PN2k6HZP

Basically it makes a hash from a random number between 0-99,999, then the number is found via two methods, each run 99 times.
The first method is an implementation of the monty hall problem.
The second method is purely random.  Neither ever tests the same number twice.

example output
Quote
results for hashes randomly found with doors
found behind door 1: 46
found behind door 2: 53
average number of tries: 48972.77

results for hashes randomly
average number of tries: 52223.12

Most times I ran it the monty hall implementation ran with the lowest average tries, but when the purely random method won it would usually win by a larger margin than the monty hall problem.
lemonginger
Full Member
***
Offline Offline

Activity: 210


firstbits: 121vnq


View Profile
June 15, 2011, 10:49:15 PM
 #9

Most times I ran it the monty hall implementation ran with the lowest average tries, but when the purely random method won it would usually win by a larger margin than the monty hall problem.

Good, run it a few more hundred thousand times and then run a chi-square analysis.

I think you will find that they are not significantly different in terms of how often they find the hash.

EpicFail
Jr. Member
*
Offline Offline

Activity: 42


View Profile
June 15, 2011, 11:15:18 PM
 #10

In the Monty Hall scenario the host ALWAYS picks the wrong door, and you are using this particular piece of information it to your advantage by switching.

The pool cannot do this (only picks a random door).

Think about it for a moment.

EDIT: By always picking the wrong door he is artificially lengthening the game (the game never ends on round 2), making it a completely different problem/game than the pool.
Rodyland
Hero Member
*****
Offline Offline

Activity: 499


View Profile
June 15, 2011, 11:22:49 PM
 #11

This is awesome!

This is just like the youtube video I saw the other day.

Some dude (solo miner) had noticed that it takes him minimum of about 2 days to solve a block. 

So his "solution" to the "wasted" time was to switch to pooled mining for 2 days each time he solves a block, and then switch back to solo mining.

Huh

Beware the weak hands!
1NcL6Mjm4qeiYYi2rpoCtQopPrH4PyKfUC
GPG ID: E3AA41E3
forests
Newbie
*
Offline Offline

Activity: 20


View Profile
June 15, 2011, 11:41:46 PM
 #12

Most times I ran it the monty hall implementation ran with the lowest average tries, but when the purely random method won it would usually win by a larger margin than the monty hall problem.

Good, run it a few more hundred thousand times and then run a chi-square analysis.

I think you will find that they are not significantly different in terms of how often they find the hash.



thanks, that's an excellent suggestion.  seeing how we're dealing with random numbers and the doors aren't guaranteed to have prizes I don't really doubt that statistically this method is completely unsound.  However I didn't know about chi-square tests and I've got other ideas I'd like to map out using this method.
bitcoinminer
Sr. Member
****
Offline Offline

Activity: 322



View Profile
June 16, 2011, 12:59:35 AM
 #13

Why don't we have The Price is Right have an episode where instead of a car, it's 2,000 BTC, and then this will be a relevant conversation Smiley

Why don't NVIDIA and Intel develop a processor that only does 1 hash per second, but it's always the exact right one?

Be fearful when others are greedy, and greedy when others are fearful.

-Warren Buffett
MoonShadow
Legendary
*
Offline Offline

Activity: 1666



View Profile
June 16, 2011, 01:11:41 AM
 #14

Why don't we have The Price is Right have an episode where instead of a car, it's 2,000 BTC, and then this will be a relevant conversation Smiley

Why don't you make such a suggestion to the show?

"The powers of financial capitalism had another far-reaching aim, nothing less than to create a world system of financial control in private hands able to dominate the political system of each country and the economy of the world as a whole. This system was to be controlled in a feudalist fashion by the central banks of the world acting in concert, by secret agreements arrived at in frequent meetings and conferences. The apex of the systems was to be the Bank for International Settlements in Basel, Switzerland, a private bank owned and controlled by the world's central banks which were themselves private corporations. Each central bank...sought to dominate its government by its ability to control Treasury loans, to manipulate foreign exchanges, to influence the level of economic activity in the country, and to influence cooperative politicians by subsequent economic rewards in the business world."

- Carroll Quigley, CFR member, mentor to Bill Clinton, from 'Tragedy And Hope'
bitcoinminer
Sr. Member
****
Offline Offline

Activity: 322



View Profile
June 16, 2011, 04:57:37 AM
 #15

Why don't we have The Price is Right have an episode where instead of a car, it's 2,000 BTC, and then this will be a relevant conversation Smiley

Why don't you make such a suggestion to the show?

Or maybe the two people who DONT win have to go on a date with Drew Carey!

Be fearful when others are greedy, and greedy when others are fearful.

-Warren Buffett
Klestin
Hero Member
*****
Offline Offline

Activity: 494


View Profile
June 16, 2011, 11:19:38 AM
 #16

Why don't NVIDIA and Intel develop a processor that only does 1 hash per second, but it's always the exact right one?
I wonder if nvidia is aware of their deficiency in hashing speed?  If network growth continues, sooner or later they'll notice the sales being lost to their competitor.
Synaptic
Member
**
Offline Offline

Activity: 84


View Profile
June 16, 2011, 12:28:24 PM
 #17

Why don't NVIDIA and Intel develop a processor that only does 1 hash per second, but it's always the exact right one?
I wonder if nvidia is aware of their deficiency in hashing speed?  If network growth continues, sooner or later they'll notice the sales being lost to their competitor.

Nvidia has made it's mark as a provider of "superior" visualization equipment, especially on the professional side. Bitcoin miners even now are an almost insignificant fraction of AMD's total sales.

AMD doesn't even care about bitcoin miners...

...especially since bitcoin mining is a fad with little future market potential anyhow.
Klestin
Hero Member
*****
Offline Offline

Activity: 494


View Profile
June 16, 2011, 12:55:10 PM
 #18

Why don't NVIDIA and Intel develop a processor that only does 1 hash per second, but it's always the exact right one?
I wonder if nvidia is aware of their deficiency in hashing speed?  If network growth continues, sooner or later they'll notice the sales being lost to their competitor.
Bitcoin miners even now are an almost insignificant fraction of AMD's total sales.

Have you seen how hard it is to get even last-gen AMD hardware?  I'd be surprised if they weren't aware of this phenomenon, and I still say sooner or later, NVidia will notice.  As to the longevity of this "fad", only time will tell.
Synaptic
Member
**
Offline Offline

Activity: 84


View Profile
June 16, 2011, 01:28:45 PM
 #19

Why don't NVIDIA and Intel develop a processor that only does 1 hash per second, but it's always the exact right one?
I wonder if nvidia is aware of their deficiency in hashing speed?  If network growth continues, sooner or later they'll notice the sales being lost to their competitor.
Bitcoin miners even now are an almost insignificant fraction of AMD's total sales.

Have you seen how hard it is to get even last-gen AMD hardware?  I'd be surprised if they weren't aware of this phenomenon, and I still say sooner or later, NVidia will notice.  As to the longevity of this "fad", only time will tell.

I think you need to check your math.

The entire Bitcoin mining network might POSSIBLY contain 30,000 GPUs, assuming a large spread of cards pulling less than 200MH/s.

Even at the most liberal of estimations of GPU's in the network, do you seriously think AMD and ESPECIALLY Nvidia are going to go out of their way to cater to ~30,000 unit sales? Especially into an already saturated market with extremely little potential for future capacity?

Think again kids.  Think long, and hard about it.

EDIT:  Just so you realize the utter futility of your conception, roughly 25 million GPUs are sold....EACH QUARTER.

So, you were saying?
chiropteran
Sr. Member
****
Offline Offline

Activity: 348



View Profile WWW
June 16, 2011, 02:13:52 PM
 #20

I think you need to check your math.

The entire Bitcoin mining network might POSSIBLY contain 30,000 GPUs, assuming a large spread of cards pulling less than 200MH/s.

Even at the most liberal of estimations of GPU's in the network, do you seriously think AMD and ESPECIALLY Nvidia are going to go out of their way to cater to ~30,000 unit sales? Especially into an already saturated market with extremely little potential for future capacity?

Think again kids.  Think long, and hard about it.

EDIT:  Just so you realize the utter futility of your conception, roughly 25 million GPUs are sold....EACH QUARTER.

So, you were saying?


Couple things that you are overlooking.

Majority of GPU sales are cheap integrated crap.  Intel is the #1 GPU manufacturer by volume, simply because of the vast number of systems sold with cheap integrated intel graphics.

30,000 as a number of GPUs might be small, but we are talking about 30,000 GPUs that retail for $100-$300 EACH, some even more.  While the 25 million total GPUs you refer to is mostly $2 integrated junk.  If you look at the numbers as money rather than total units, the stuff sold for mining is not statistically insignificant.

Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!