martingale betting system in data compression question
John
Consider a martingale betting system where you bet 1 unit default and
double your previous bet if you lose. If you use this system to bet on
+/- 10^6 random bits (0 or 1) you will end up with more units than you
started with for pretty much any random data source each time you try
it. (You can easily verify this by creating a small computer program
and use a prng.)
Somehow it looks like this system beats the random source. Which made
me wonder how all this relates to datacompression and how such a
system translates to a next byte prediction model. And even though i
know random data can't be predicted with more than 50% accuracy and i
don't see how this system can be implemented in a datacompression
context, i can't shake the feeling there is an edge here that can be
used.
Which for obvious reasons is not a good thing, and i would really
appreciate it if someone could point out where my logic is flawed.
Cheers,
John
David A. Scott
news:kq21b1lntp2b1la8c...@4ax.com:
Martingale betting systems are for losers.
The edge is not there but I arge this with people all the
time. A x friend of mine went to Reno to show me how it
wins he lost. But blamed me for bad luck.
Look at Expected value. Play until you win or three times
which ever comes first you will see it break even. If
you don't see it then your beyond hope so look again.
beat 1 then 2 then 4 beat lets look at 8 cases call a one a win
a zero a lose
000 lost thre times in a row lost 1 2 4 for a total of 7 dollars
001 lost twice but won once so won 1 dollar
010 lost once quit after winnin so won 1 dollar
011 lost once quit after winning so won 1 dollar
100 101 110 111 won so quite on first roll 4 cases fo 4 dollars
Net result ZERO yes 7/8 time win a buck but 1/8 time lost 7 dollars.
Yes change the rules so play until you win a dollar ahead.
Unfortunately you only have a fintite lifespan. Yes you have a good
chance of winning a dollar but the one case of losing it all still
make it a ZERo SUM game. You break even.
Other idiots go to Vegas and Bet block on roulette. Yes Black Red
and Green. First of all its not a 50 50 bet do same match as above
you LOSE. Yes you may win but the big loss will more than make up
for the little you might win.
What you fail to see that a long string can occurr which even would
wipe out Gates if he played it.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
John
<daVvid_...@email.com> wrote:
-8<-
>> Consider a martingale betting system where you bet 1 unit default and
>> double your previous bet if you lose. If you use this system to bet on
>> +/- 10^6 random bits (0 or 1) you will end up with more units than you
>> started with for pretty much any random data source each time you try
>> it. (You can easily verify this by creating a small computer program
>> and use a prng.)
-8<-
> Martingale betting systems are for losers.
>The edge is not there but I arge this with people all the
>time. A x friend of mine went to Reno to show me how it
>wins he lost. But blamed me for bad luck.
>
>Look at Expected value. Play until you win or three times
>which ever comes first you will see it break even. If
>you don't see it then your beyond hope so look again.
-8<-
> What you fail to see that a long string can occurr which even would
>wipe out Gates if he played it.
I agree it won't do you much good in a casino scenario because of the
exponential growth of the bet and the betting limit. But if you use it
in a computer program which doesn't suffer from a limit, and bet
against a fixed amount of prng bits you will see you'll win
+/-(0.5*number of bets) units in 99.999.. percent of the cases.
This struck me as odd, because i kind of suspected it would be a no
win system ending up around zero. And i still fail to see how i can
explain this number as a neutral/"break even" outcome.
Cheers,
John
David A. Scott
news:e3l2b1td6pf1g5h70...@4ax.com:
>
> I agree it won't do you much good in a casino scenario because of the
> exponential growth of the bet and the betting limit. But if you use it
> in a computer program which doesn't suffer from a limit, and bet
> against a fixed amount of prng bits you will see you'll win
> +/-(0.5*number of bets) units in 99.999.. percent of the cases.
>
> This struck me as odd, because i kind of suspected it would be a no
> win system ending up around zero. And i still fail to see how i can
> explain this number as a neutral/"break even" outcome.
>
>
It is a zero sum game even on the computer.
if you win ONE unit is 99.99999999999 % of times
you lose SEVERAL UNITS that .00000000001 % of the time
I see like trying to explain to cops in New York that the
Swiss have a low murder rate because most there have guns
they don't see it. Liberals still think communism or
socalism is the answer to all. Its not. I suspect its
more like trying to argue with one in Black Jack on
if you should take the insurance bet when you have a
Black Jack and dealer has an Ace up. Many people you
included I suspect would take the sure thing and walk
a way with the money. I would look at count and only
take insurance when the count in my favor. Yes I have
won some and lost some. But when with a friend and he
sees you lose you can't convince him you did the correct
thing.
Matt Mahoney
> On Thu, 16 Jun 2005 14:29:46 +0000 (UTC), "David A. Scott"
> <daVvid_...@email.com> wrote:
>
> [snip]
>
> >> I agree it won't do you much good in a casino scenario because of the
> >> exponential growth of the bet and the betting limit. But if you use it
> >> in a computer program which doesn't suffer from a limit, and bet
> >> against a fixed amount of prng bits you will see you'll win
> >> +/-(0.5*number of bets) units in 99.999.. percent of the cases.
> >>
> >> This struck me as odd, because i kind of suspected it would be a no
> >> win system ending up around zero. And i still fail to see how i can
> >> explain this number as a neutral/"break even" outcome.
> >
> > It is a zero sum game even on the computer.
> >if you win ONE unit is 99.99999999999 % of times
> >you lose SEVERAL UNITS that .00000000001 % of the time
>
> up with a win situation. And when i was googling for martingale and
> data compression i found this information:
>
> http://www.cs.umd.edu/users/samir/abstracts/kautz.html
>
> Which i think refers to this paper:
>
> http://eccc.uni-trier.de/eccc-reports/1998/TR98-058/
>
> And these sources seem to suggest that a winning betting game equals
> data compression. Does anybody know what this is all about?
>
> Cheers,
> John
In a martingale system you bet on whether strings in an unknown
language are members of the language. The strings are presented in
standard lexicographical order. Since there is a 1-1 mapping between
strings and positive integers, the problem is equivalent to betting
whether 1, 2, 3,... are members of some unknown set. That set can be
described by an infinite stream of bits, so the problem is also
equivalent to betting on bits in an infinite bit stream. If there is a
strategy where your winnings tend to infinity, then the bit stream is
compressible. However the betting strategy described by the OP is not
a martingale betting system. In a martingale system, you start with a
finite amount of money and cannot bet more than you have.
If the bit stream is generated by a program, then there is always a
winning strategy (guess the program), and the stream is compressible.
This implies that there is no program that can generate random a data
stream (but you knew that).
As for how you guess the program, start with the shortest ones that are
consistent with the data so far. Hutter proved that this is the best
strategy. http://www.idsia.ch/~marcus/ai/aixigentle.htm
Essentially, the proof is that shorter programs must be more likely
because no other probability distribution over an infinite set is
possible. If a program has probability p greater than 0, then there
can only be a finite number of longer programs that are more likely,
out of the infinite set of longer programs.
-- Matt Mahoney