Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 2 [All]

Author Topic: A Math/Stats Question  (Read 8789 times)

0 Members and 1 Guest are viewing this topic.

WanderingWinder

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5275
  • ...doesn't really matter to me
  • Respect: +4381
    • View Profile
    • WanderingWinder YouTube Page
A Math/Stats Question
« on: January 30, 2015, 09:38:48 am »
0

I feel like this should be simple, but having spent 15 minutes, I haven't cracked it yet. You guys are who I've come to.

Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?

Probably I need to explain this better. If the first trial is success, obviously we hit (1 of 1 is a majority). If after 3, we have 2+ out of 3, then we hit success, but these would already have been counted by the first one hitting, except for the case 011. etc etc. Probably there's a better way of going about this, but I haven't come up with it yet.

WalrusMcFishSr

  • Minion
  • *****
  • Offline Offline
  • Posts: 642
  • An enormous walrus the size of Antarctica
  • Respect: +1793
    • View Profile
Re: A Math/Stats Question
« Reply #1 on: January 30, 2015, 11:18:46 am »
+6

I'm not an expert in statistics by any means. But is it possible this analysis could apply?

http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf

In particular, section 2 ("The monkey at the cliff"). If the monkey falls off the cliff, that means the majority of steps have been towards the cliff, which is analogous to a majority of trials being successful. If I'm understanding correctly, the odds approach 1 if the odds of success are greater than or equal to the odds of failure. Otherwise, the odds are p/q.
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

Eras

  • Ambassador
  • ***
  • Offline Offline
  • Posts: 30
  • Respect: +3
    • View Profile
Re: A Math/Stats Question
« Reply #2 on: January 30, 2015, 01:56:19 pm »
0

I would look at this using stopping times ( http://en.wikipedia.org/wiki/Stopping_time ). I'll try it this afternoon or tonight if I have some time :-)

Edit : Should've taken the time to read the PDF first, my post is redundant.
« Last Edit: January 30, 2015, 03:13:08 pm by Eras »
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: A Math/Stats Question
« Reply #3 on: January 30, 2015, 02:05:37 pm »
0

ThAt's basically what the pdf does
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: A Math/Stats Question
« Reply #4 on: January 30, 2015, 02:36:41 pm »
+1

I think WalrusMcFishSr's post is better, but here's an argument I thought up. (PPE: I think it's actually the same as the argument in the link, now that I've read the pdf more closely)

Think of it as a random walk, where we either travel +1 or -1 with equal probability. The question becomes P(visit +1 at any point, starting from state 0)

Let that be p. If the first trial is +1, then we've obviously made it, so

P(visit +1 at any point, starting from state 0) = 1/2 + 1/2 * P(visit +1 at any time, starting from -1)

To visit +1 starting from -1, we must first pass through 0, so

P(visit +1 at any time starting at 0) = 1/2 + 1/2 * P(visit 0 at any time starting from -1) * P(visit +1 at any time starting from 0)

The probabilities are the same under translation (we only care about walking right by 1, not where we start from), so this turns into

p = 1/2 + 1/2 * p^2

which has a solution at only p = 1

Edit: yep it for sure is the same argument. I also only solved it for when the random walk chance is 1/2, so you should just look at the pdf instead because that solves it generally.
« Last Edit: January 30, 2015, 02:38:53 pm by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

TheExpressicist

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +203
    • View Profile
Re: A Math/Stats Question
« Reply #5 on: February 04, 2015, 03:12:07 pm »
0

Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?

If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: A Math/Stats Question
« Reply #6 on: February 04, 2015, 03:20:38 pm »
+5

Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?

If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.

A good rule of thumb is that whenever infinity is involved, you need to be very careful on your intuition. From the linked PDF, it turns out that the probability is 1 for p >= 1/2, and p / (1-p) for p < 1/2.

This sounds weird because if we do something an infinite number of times, surely we must have every possibility eventually happen. However, it turns out this isn't generally true. For example, a random walk in 2 dimensions returns to the origin with probability 1, but a random walk in 3 dimensions returns to the origin only around a third of the time. Usually, this comes down to the rate of growth for the two - for example, if the probability of getting a majority at time t+1 is 1/4 the probability of a majority at time t, then the probabilities decrease fast enough to make the sum across all times t not equal to 1.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

TheExpressicist

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +203
    • View Profile
Re: A Math/Stats Question
« Reply #7 on: February 04, 2015, 03:39:23 pm »
0

Given a Bernoulli process (probability of success p), what is the chance that, given an infinite number of trials, after SOME point, the majority of trials have come up with success?

If I understand the question right ("given an infinite number of trials, what is the probability that at any point the number of successes outnumber the number of failures"), the probability is 1 for any p > 0.

A good rule of thumb is that whenever infinity is involved, you need to be very careful on your intuition. From the linked PDF, it turns out that the probability is 1 for p >= 1/2, and p / (1-p) for p < 1/2.

This sounds weird because if we do something an infinite number of times, surely we must have every possibility eventually happen. However, it turns out this isn't generally true. For example, a random walk in 2 dimensions returns to the origin with probability 1, but a random walk in 3 dimensions returns to the origin only around a third of the time. Usually, this comes down to the rate of growth for the two - for example, if the probability of getting a majority at time t+1 is 1/4 the probability of a majority at time t, then the probabilities decrease fast enough to make the sum across all times t not equal to 1.

Yup, I misread the question as asking about an infinite number of random walks, rather than an infinite number of steps in a single random walk.
Logged

Davio

  • 2012 Dutch Champion
  • *
  • Offline Offline
  • Posts: 4787
  • Respect: +3412
    • View Profile
Re: A Math/Stats Question
« Reply #8 on: February 04, 2015, 03:51:05 pm »
0

I consider myself an interested amateur with regards to statistics and probabilities, meaning I understand the simple problems but struggle with harder and counterintuitive ones.
So don't shoot if I'm way off base.

But my question is this: does this have something to do with entropy? I understand that when you keep shuffling a deck of cards, you don't automatically get back to the original order because you're introducing entropy.

But given an infinite number of shuffles don't we just get every ordering as much as any other?

So with the walking in 3d analogy, does taking a step introduce entropy?
Logged

BSG: Cagprezimal Adama
Mage Knight: Arythea

TheExpressicist

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +203
    • View Profile
Re: A Math/Stats Question
« Reply #9 on: February 04, 2015, 04:00:54 pm »
0

But given an infinite number of shuffles don't we just get every ordering as much as any other?

You'll get each ordering in proportion to how probable that ordering is. If you flip two coins a single time, the probabilities look like: 25% two heads, 50% one heads, one tails, 25% two tails. So if you flip two coins X times, you'll have on average .25*X instances of two heads,.5*X instances of one heads one tails, and 25*X instances of two tails.

But you can't assign the value "infinity" to X. You can look at things as X approaches infinity. So no matter what the real value of X is, you'll always have twice as many instances of one-heads-one-tails as you will two-heads.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #10 on: February 04, 2015, 04:03:51 pm »
0

But given an infinite number of shuffles don't we just get every ordering as much as any other?

You'll get each ordering in proportion to how probable that ordering is. If you flip two coins a single time, the probabilities look like: 25% two heads, 50% one heads, one tails, 25% two tails. So if you flip two coins X times, you'll have on average .25*X instances of two heads,.5*X instances of one heads one tails, and 25*X instances of two tails.

But you can't assign the value "infinity" to X. You can look at things as X approaches infinity. So no matter what the real value of X is, you'll always have twice as many instances of one-heads-one-tails as you will two-heads.

If you consider each card to be unique in a deck of cards, each ordering (of the 52 cards) has the same probability, right?  The .5*X instance of one heads one tails comes because you're considering the orderings HT and TH to be the same.
Logged

TheExpressicist

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +203
    • View Profile
Re: A Math/Stats Question
« Reply #11 on: February 04, 2015, 04:06:30 pm »
0

If you consider each card to be unique in a deck of cards, each ordering (of the 52 cards) has the same probability, right?  The .5*X instance of one heads one tails comes because you're considering the orderings HT and TH to be the same.

If we're talking about a deck of unique cards, yes.
Logged

Davio

  • 2012 Dutch Champion
  • *
  • Offline Offline
  • Posts: 4787
  • Respect: +3412
    • View Profile
Re: A Math/Stats Question
« Reply #12 on: February 04, 2015, 04:08:21 pm »
0

That I understand.

But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.

I think amateurs like me often make the mistake of treating infinity as a really big number.

If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.
« Last Edit: February 04, 2015, 04:10:11 pm by Davio »
Logged

BSG: Cagprezimal Adama
Mage Knight: Arythea

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #13 on: February 04, 2015, 04:12:49 pm »
0

That I understand.

But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.

I think amateurs like me often make the mistake of treating infinity as a really big number.

If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.

Well a physical shuffle is not a complete random permutation on the deck order.  In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic.  So, uh.. actually it's not the easiest problem I guess.  For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #14 on: February 04, 2015, 04:14:29 pm »
0

If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.

I like when this play is relevant:

Logged

theory

  • Administrator
  • *****
  • Offline Offline
  • Posts: 3603
  • Respect: +6121
    • View Profile
    • Dominion Strategy
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #16 on: February 04, 2015, 04:32:16 pm »
0

That I understand.

But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.

I think amateurs like me often make the mistake of treating infinity as a really big number.

If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.

Well a physical shuffle is not a complete random permutation on the deck order.  In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic.  So, uh.. actually it's not the easiest problem I guess.  For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.

But actually, after enough* shuffles, the distribution function of the imperfectly shuffled deck is well approximated by the uniform distribution.  And if we assume a uniform selection of a deck ordering, you can calculate how long you can expect to wait to get back to the original ordering.  So take that number and tack on "enough" extra shuffles at the beginning.  I imagine the extra shuffles up front shouldn't matter at all.  I also imagine your hands will get tired.

*Rule of thumb: 7.  I think it's more formally treated in http://projecteuclid.org/download/pdf_1/euclid.aoap/1177005705, though I haven't read through that.. this is just from a few minutes of Googling.
Logged

WanderingWinder

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5275
  • ...doesn't really matter to me
  • Respect: +4381
    • View Profile
    • WanderingWinder YouTube Page
Re: A Math/Stats Question
« Reply #17 on: February 04, 2015, 04:49:11 pm »
+1

That I understand.

But let's say I open up a pack of cards and it's ordered. Now I start shuffling in a physical manner. This is important because I don't just pick 52 numbers one after the other. Will I ever get back to my original order? After 1 shuffle some cards are still close together. They move further apart as I shuffle more.

I think amateurs like me often make the mistake of treating infinity as a really big number.

If I have an infinite amount of monkeys they will reproduce the works of Shakespeare. But it will take them infinitely many years and I'll have to feed them an infinite amount of bananas and we'll all be infinitely dead by the time it's done.

Well a physical shuffle is not a complete random permutation on the deck order.  In fact, when we shuffle we try to shuffle perfectly (a faro shuffle), which is completely deterministic.  So, uh.. actually it's not the easiest problem I guess.  For perfect shuffles it is, but for slight random perturbation of a perfect shuffle, I'm not sure.

But actually, after enough* shuffles, the distribution function of the imperfectly shuffled deck is well approximated by the uniform distribution.  And if we assume a uniform selection of a deck ordering, you can calculate how long you can expect to wait to get back to the original ordering.  So take that number and tack on "enough" extra shuffles at the beginning.  I imagine the extra shuffles up front shouldn't matter at all.  I also imagine your hands will get tired.

*Rule of thumb: 7.  I think it's more formally treated in http://projecteuclid.org/download/pdf_1/euclid.aoap/1177005705, though I haven't read through that.. this is just from a few minutes of Googling.

It really depends on how you shuffle.

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #18 on: February 04, 2015, 04:54:51 pm »
0

Yeah, this is assuming imperfect riffle shuffling.
Logged

WanderingWinder

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5275
  • ...doesn't really matter to me
  • Respect: +4381
    • View Profile
    • WanderingWinder YouTube Page
Re: A Math/Stats Question
« Reply #19 on: February 04, 2015, 04:56:37 pm »
0

Yeah, this is assuming imperfect riffle shuffling.
Yes, but also a particular version of imperfect riffle. Bobby might shuffle that way, but Suzie probably won't, even if she does an imperfect riffle shuffle as well.

Lightning edit: i.e. they will have different measures of 'how imperfect' of a riffle shuffle you are looking at.

WalrusMcFishSr

  • Minion
  • *****
  • Offline Offline
  • Posts: 642
  • An enormous walrus the size of Antarctica
  • Respect: +1793
    • View Profile
Re: A Math/Stats Question
« Reply #20 on: February 04, 2015, 05:22:18 pm »
+1

I was assuming the truffle shuffle.
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

Donald X.

  • Dominion Designer
  • *****
  • Offline Offline
  • Posts: 6357
  • Respect: +25672
    • View Profile
Re: A Math/Stats Question
« Reply #21 on: February 04, 2015, 07:42:04 pm »
0

Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics
Logged

jaketheyak

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 292
  • Respect: +613
    • View Profile
Re: A Math/Stats Question
« Reply #22 on: February 04, 2015, 09:38:55 pm »
0

Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics

Sorry to derail the maths discussion, but am I the only one bothered by the fact that riffle shuffling damages cards?
Dominion isn't blackjack, just give the cards a quick overhand shuffle and get on with your turn!
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: A Math/Stats Question
« Reply #23 on: February 05, 2015, 10:46:37 am »
+2

Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics

Sorry to derail the maths discussion...

Really, this is a forum for derailing Dominion discussion with maths topics, not the other way round!
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: A Math/Stats Question
« Reply #24 on: February 05, 2015, 10:50:48 am »
+2

Some information on riffle shuffling for Dominion from BGG: http://boardgamegeek.com/thread/817695/initial-shuffle-statistics

Sorry to derail the maths discussion, but am I the only one bothered by the fact that riffle shuffling damages cards?
Dominion isn't blackjack, just give the cards a quick overhand shuffle and get on with your turn!

Just come up with a model that measures the degradation of cards as a result of riffle shuffling, the consequence of which can be the extent of your botherment.  That way you're not derailing the math thread.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: A Math/Stats Question
« Reply #25 on: February 05, 2015, 12:06:50 pm »
0

Yeah, this is assuming imperfect riffle shuffling.

But don't you make your own shuffle luck?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: 1 2 [All]
 

Page created in 0.198 seconds with 20 queries.