Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Jul 23, 2014 5:18 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 35 posts ] 
Author Message
 Post subject: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 1:35 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Let's say we have a fair lottery where a hundred million (100,000,000) people get one ticket each, and a winner is drawn at random each day. The winner stays in the pool even after winning. What are the odds that you win it once before someone else (one individual) wins it three times (doesn't have to be in a row)?

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Last edited by theVDude on Sun Jul 24, 2011 1:55 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 1:43 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
theVDude wrote:
What are the odds that you win it once before someone else wins it three times (doesn't have to be in a row)?

Before anyone wins it 3 times? Or someone in particular? Not certain I know how to solve the problem either way but I'm pretty sure that makes a big difference.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 1:55 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Edited to make it more clear.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 2:06 pm 
Offline
User avatar

Joined: Sat Mar 29, 2008 12:55 am
Location: WA, USA
before a specific individual wins it 3 times? Well, their chance of winning 3 times would be 1/ 100,000,000^3, while your chance of winning would be 1/100,000,000 each time...
So... if all are equal... then everyone has an equal chance each time of winning, so each time is completely independent of every other time.
So, you have exactly the same chance of winning as he does every time, it doesn't matter how many times he wins...
However, if it were 3 times in a row, that probability would be dependant and have a different value.

_________________
"This is Pretty off-topic"

"You are actually more off topic than me, you mentioned something on topic in the Off Topic forum."

"You more so for discussing the on-topic "off-topic" topic in the off-topic forum."


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 2:41 pm 
Offline
User avatar

Joined: Thu Oct 16, 2008 9:46 pm
Location: Littleton CO
It would be 1/100,000,000 every time there was a drawing. Because the amount of people always stays the same and it is always fair.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 3:01 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
elijah wrote:
before a specific individual wins it 3 times? Well, their chance of winning 3 times would be 1/ 100,000,000^3,
Need to multiply that by the number of drawings.

But I don't think that is his question... I think he means any of the 100,000,000 individuals have won it 3 times. And I'd bet someone would have won it 3 times before 50% of the people have won once so I'd say your odds are less then 50%. Though at 1 drawing a day odds are you are dead before you win.

More interesting question... what is the most likely age of the first person to win it 3 times assuming the drawings started the day they were born?

Carl

P.S. If I've done the math correctly they should be about 193,595 years old.

_________________
-
Image

Image


Last edited by wwwmwww on Sun Jul 24, 2011 3:13 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 3:08 pm 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Wow, this is really tricky. My guess is the probability (that somebody wins three times before you do) is really quite high. The chance that you win stays very tiny, but the chance that somebody wins twice or trice increases as the number of people that has won once or twice increases. It's a bit like the birthday paradox where in a group of 30 people, the chance that two will have the same birthday is nearly 73%.
I'm currently failing to see a way to do better than a numerical approximation.

Carl's last question (expected age) is very much easier. The expected times you have won after n drawings is n/100.000.000 so the expected age is 300.000.000 drawings.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 3:20 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
TomZ wrote:
Carl's last question (expected age) is very much easier. The expected times you have won after n drawings is n/100.000.000 so the expected age is 300.000.000 drawings.

I'm not after the number of times you need to draw to win 3 times but the number of drawings needed before the odds are 50% that at least someone has won 3 times. Not sure I did the math correctly above but its still a very long time.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 7:49 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Here's how I would do it, although I can't guarantee I'm right:

Ignore everyone else but one other person. The chance you'll be picked before he gets picked:

Once: 1/2
Twice: 1/2 + 1/4
Thrice: 1/2 + 1/4 + 1/8 = 7/8

Now take 7/8 to the 99,999,999th power, since there are that many people besides you. The final result is so small that neither my computer's calculator or Google Calculator can give it, apparently.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 8:02 pm 
Offline
User avatar

Joined: Fri Mar 06, 2009 9:23 pm
I am by no means an expert, but can this be solved with the Bernoulli Distribution?

_________________
--Eric Vergo

My Shapeways shop


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 8:13 pm 
Online
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
theVDude wrote:
Let's say we have a fair lottery where a hundred million (100,000,000) people get one ticket each, and a winner is drawn at random each day. The winner stays in the pool even after winning. What are the odds that you win it once before someone else (one individual) wins it three times (doesn't have to be in a row)?


You wording is still a bit ambiguous. Do you mean you win exactly once before somebody else wins 3 times or at least once?


EDIT: If you allow "at least once" then there is AT LEAST a 1 / 100,000,000 probability that YOU'RE the person to win 3 times. I'm still thinking about how to go about solving this problem.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 8:49 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
The beautiful thing about probability is as long as you are very careful, you can almost always come up with an expression for any theoretical problem. Solving it numerically is an entirely different problem :lol:

Edit: ok, so I read this problem too fast the first time and thought you asked for the probability that you don't win until someone else wins three times. But that's not what you asked is it? No problem, I can write a formula down for this one too! 8-)

I also assume when you say someone else, you have an individual picked out beforehand, like the one guy in the population named Bob. What is the probability you win once before Bob wins three times? right? I will assume so. Clearly if this lottery goes on forever, you will eventually win, so we can rewrite the question as: What is the probability that your first win occurs before Bob has won three times? The simplest expression for this I believe comes when you break it down this way: Bob can either win zero times, once or twice before you in order for the outcome to be favorable.

Let N be the number of people participating in this lottery.
Let X be the number of drawings before you win. (so you win on the x+1st draw)
Let B be the number of times Bob wins during those X draws.

The events that must occur are:
On exactly B of the X draws that you don't win, Bob must win. You must win on the draw immediately after the xth draw. You BOTH must lose the other X-B draws.
The probability of all these events happening together is:

(X choose B) * (1/N)^B * (1/N) * (N-2/N)^(X-B)

Sum this expression over X=0 to X=infinity and sum the resulting expression over B=0 to B=2 and set N= 100 million and you have the answer. Now someone else figure out the numerical answer :wink:

Peace,
Matt Galla


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 9:44 pm 
Offline
User avatar

Joined: Wed Apr 01, 2009 2:59 pm
Allagem wrote:
I also assume when you say someone else, you have an individual picked out beforehand


That wouldn't be a terribly interesting problem. It's hard to phrase unambiguously, but I'm sure he means to just run the lottery over and over and keep track of how many times each of the 100,000,000 people have won thus far. Specify one of those people to be you. Most people will stay at 0 wins for a long time, a few will have 1 win, and a very small number will have 2 wins, and so on. Wait until someone hits 3 wins, and when that happens, how likely is it that you are still sitting on 0 wins?


Edit: this should be pretty manageable do with a binomial distribution and some combinatorics if you asked for, say, the probability that [one person (you) haven't won at all, another person has won 3 times, and the other 999,999,998 people have won either 0, 1, or 2 times] after N winners in total have been chosen. Then take that expression and let N go to infinity, and you've got your answer.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 9:53 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
Iranon wrote:
Allagem wrote:
I also assume when you say someone else, you have an individual picked out beforehand


That wouldn't be a terribly interesting problem. It's hard to phrase unambiguously, but I'm sure he means to just run the lottery over and over and keep track of how many times each of the 100,000,000 people have won thus far. Specify one of those people to be you. Most people will stay at 0 wins for a long time, a few will have 1 win, and a very small number will have 2 wins, and so on. Wait until someone hits 3 wins, and when that happens, how likely is it that you are still sitting on 0 wins?


I agree it's less interesting, but when he changed "someone else" to "someone else (one individual)" it sounded like he was leaning towards the individual picked out beforehand possibility. I think we need some clarification from the author :)

Peace,
Matt Galla


Last edited by Allagem on Sun Jul 24, 2011 10:06 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sun Jul 24, 2011 9:54 pm 
Online
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Allagem wrote:
Let N be the number of people participating in this lottery.
Let X be the number of drawings before you win. (so you win on the x+1st draw)
Let B be the number of times Bob wins during those X draws.

The events that must occur are:
On exactly B of the X draws that you don't win, Bob must win. You must win on the draw immediately after the xth draw. You BOTH must lose the other X-B draws.
The probability of all these events happening together is:

(X choose B) * (1/N)^B * (1/N) * (N-2/N)^(X-B)

Sum this expression over X=0 to X=infinity and sum the resulting expression over B=0 to B=2 and set N= 100 million and you have the answer. Now someone else figure out the numerical answer :wink:

Hi Matt,

The trouble with this solution is that it is basically a simulation in disguise. By needing to sum X from 0 to some bound (I think ((N * 2) + 1), not infinity, right?) you're tackling the problem as in a way that takes the same amount of time as just doing the lottery game.

I have been trying to find a way of approaching the problem that doesn't involve a sum. Can you take a stab at eliminating your sum?

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Mon Jul 25, 2011 7:30 am 
Offline

Joined: Sun Jul 08, 2007 7:15 pm
bmenrigh wrote:
Allagem wrote:
Let N be the number of people participating in this lottery.
Let X be the number of drawings before you win. (so you win on the x+1st draw)

By needing to sum X from 0 to some bound (I think ((N * 2) + 1), not infinity, right?)

The bound would actually be (N-1)*2+1. N includes you, but X is the number of drawings before you win, so there are only N-1 possible winners in said drawings.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Mon Jul 25, 2011 10:19 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Sorry guys, it's just one person, not any specific person, other than it isn't you. Apparently:

notch wrote:
The chance of you winning before someone else wins three times is less than half a percent.

(Based off a Mersenne Twister based Monte Carlo simulation)


and

notch wrote:
(Disclaimer: I'm not an educated mathematician. Feel free to double check my results and tell me if I'm wrong)

So, to explain the lottery question and the very unintuitive answer..

Every time you don't win, someone else wins. The number of people who have won the lottery once will very quickly grow significantly larger than the number of people you are. Since they are more than you, the odds of one of them winning are higher than the odds of you winning, which means that there will eventually be at least one person who has won the lottery twice.
That person has the same chance of winning as you do, so each drawing, you both have a one-in-a-hundred-million chance of winning. If neither do, either someone who has never won will win, or someone who has won once will win, and there will suddenly be twice as many people who have won twice than you are.
Because of the high number of participants, this gets iterated maaaany times before you're likely to win (50 million times on average), and the pool of winners who aren't you has plenty of time to grow.

Even in a lottery of just 1000 people, your odds of winning before someone else wins three times is only about 15%.

The odds of you winning a fair 100 million person lottery before someone else wins TEN times in total is about 50%.

This, my friends, is the power of the pigeon hole principle.


I took this from Notch's (the creator of minecraft, although it seems like jeb does most of the work now) Google+. It intrigued me. D: Should I write a quick program that will simulate this over and over and over and over (starting with a smaller number of people and working up?)

Just sticking up some java I wrote and need to test when I get home. You can ignore it.
Code:
import java.util.Scanner;
import java.util.Random;

public class lottoTest {
   public static void main(String[] args) {
      /*  pc = Player Count
       *  i = iterations
       *  l = lotto number
       *  yw = times you win BEFORE someone else gets 3 wins
       *  yl = times someone wins 3 times before you get a win
       *  ic = just a counter
       *  yW = if you won, add to count of wins
       *  yL = if you lost, add to count of losses
       *  prc = percentage
       */
      int l, yw, yl, ic;
      boolean yW, yL;
      double prc;
      Scanner s = new Scanner(System.in);
      Random r = new Random();
      yw = 0;
      yl = 0;
      ic = 0;
      
      System.out.println("Players?");
      int pc = s.nextInt();
      System.out.println("Iterations?");
      int i = s.nextInt();

      long startTime = System.nanoTime();
      for(int a = 0 ; a < i ; a++){
         int[] p = new int[pc];
         yW = false;
         yL = false;
         
         while(!yW && !yL){
            l = r.nextInt(pc);
            p[l]++;
            if(p[0] > 0){
               yW = true;
            }
            else if(p[l] == 3){
               yL = true;
            }
         }
         if(yW){
            yw++;
         }
         else if(yL){
            yl++;
         }
         ic++;
      }
      
      prc = 100*((double)yw/(double)ic);
      long endTime = System.nanoTime();
      double timeTook = (((double)endTime - (double)startTime)/1000000);
      System.out.println("Took "+ timeTook + " ms");
      System.out.println("You won before someone else won 3 times " + yw + " times out of " + ic + " times. (" + prc + "%)");
      
      }
}

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Last edited by theVDude on Thu Jul 28, 2011 2:53 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Mon Jul 25, 2011 5:20 pm 
Online
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
theVDude wrote:
Sorry guys, it's just one person, not any specific person, other than it isn't you. Apparently:

notch wrote:
The chance of you winning before someone else wins three times is less than half a percent.

(Based off a Mersenne Twister based Monte Carlo simulation)

I coded up a simulation last night too but I couldn't find a satisfactory fit for the curve and then I moved on to other things.

I'm less interested in the answer for 100M and more interested in the function that tells us for any N. Here is my simulation for N in [2, 10000]:
Attachment:
lottery_10k_sim.png
lottery_10k_sim.png [ 7.26 KiB | Viewed 4092 times ]
The X axis is N, the number of people in the lottery, and the Y axis is the probability that you have won at least once when somebody gets 3 wins. Each point is an average of 100 trials for that N.

The green line is my best stab at a function that roughly fits the curve. It clearly isn't the right shape but I can't think of anything that fits that shape better.

Finally, be careful about using Mersenne Twister for choosing array buckets and such, it's Linear. For arrays with many factors more than 623 buckets the selection is detectably biased. You should use something that isn't linear for these sorts of simulations.

EDIT: I see that I miss read your post. Your code uses Java's Random() class which according to the documentation is a 48-bit LCG. LGGs are linear and can't be used for this sort of simulation. If you generate x, y, z points from subsequent calls to an LCG and plots thousands of them in a box you'll see that the points all lay in a bunch of parallel planes. It's really shocking how bad LCGs are -- they will totally throw off your simulation.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Tue Jul 26, 2011 12:58 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
I was just sticking it in there because I wrote it quick. D:

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 11:41 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Sorry for the double post, I've been working on this a bit more and will be doing a lot more simulations at home tonight. Trying to figure out a way to graph it all so I don't have to do as much work, and I'm going to leave running for a WHILE to get a best fit. My plan: Do at least 1000 simulations for N. Average the results of probability of those simulations (So for 1000 N, I'll get something like "You won before someone else won 3 times 171 times out of 1000 times. (17.1%)" then plot out each N for up to 100,000,000. Connect the dots, right? Surely taking the graph further out (instead of 10,000 100,000,000) will let us find a better best fit?

I'll be using true random numbers from random.org if I can get the client library to work, otherwise I'll figure out a better way.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 12:07 pm 
Offline
User avatar

Joined: Sun Jun 13, 2010 1:00 am
Location: Colorado
Wouldn't it work better to do more simulations and less n values? The graph would be shorter but the quality of each point would be a lot better so that if your r2 value isn't almost 1 you know you have the wrong best fit line. Then you could do less simulations and more ns to see if this equation stays good.

_________________
My Shapeways Shop
My YouTube Videos
My Museum Puzzles


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 12:14 pm 
Online
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
theVDude wrote:
Sorry for the double post, I've been working on this a bit more and will be doing a lot more simulations at home tonight. Trying to figure out a way to graph it all so I don't have to do as much work, and I'm going to leave running for a WHILE to get a best fit. My plan: Do at least 1000 simulations for N. Average the results of probability of those simulations (So for 1000 N, I'll get something like "You won before someone else won 3 times 171 times out of 1000 times. (17.1%)" then plot out each N for up to 100,000,000. Connect the dots, right? Surely taking the graph further out (instead of 10,000 100,000,000) will let us find a better best fit?

I'll be using true random numbers from random.org if I can get the client library to work, otherwise I'll figure out a better way.

Yeah taking N over a bigger range will help you fit better. The graph becomes nearly linear though for a best fit you need to bias the smaller N otherwise they wont matter.

You could probably compute every 10th N or so rather than every N to save yourself a lot of time. The curve fit will be the same. Also, if you do the simulation like I did, when N is large (> 10M) you'll be using quite a bit of memory.

I wouldn't recommend random.org or any other such gimmick website. I don't think they can provide you random numbers as fast as you will need them. The site claims it has been in operation since 1998 and has only generated 1 Tbit of entropy. Your simulation will probably need more than this. You don't want to wait a decade to get it.

Just use a good PRNG. For example:

PRNGn[0] = sha1('seed/iv');
PRNGn[N + 1] = sha1(PRNGn[N] + N)

Where '+' is concatenation.

If you don't like this you can use something simple and fast in software like
http://en.wikipedia.org/wiki/Multiply-with-carry

Just don't use something like Mersenne Twister which has some pretty bad statistical properties when you have to pick thousands of consecutive bins/points/coordinates from a single shared space/array.

Also be sure you don't bias your selection of an integer from a particular range like [1,99,999,999] by using something like modulus. A pretty standard way is to turn your random int into a float in [0,1) and then use multiplication and floor().

I'm look forward to seeing your results!

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 2:49 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Got this with the random class as I'm at work, but it's working! :D
Code:
Players?
10000000
Iterations?
10000
Took 374290.892057 ms
You won before someone else won 3 times 92 times out of 10000 times. (0.9199999999999999%)


I'll have to use a multidimensional array, as 100,000,000 is large for a regular array. LOL.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 3:39 pm 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
I don't think you need an array that large. You could do with an array of length 3. Where A[0] is the amount of players who have never won, A[1] is the amount of players who have won once, A[2] is the amount of players who have won twice.

Initialize as A[0]=P-1, A[1]=A[2]=0, where P is the player count.

Pick a random number R in [0, P-1]

If R<A[0] increase A[1] by 1, decrease A[0] by 1
Else If R<A[0]+A[1] increase A[2] by 1, decrease A[1] by 1
Else If R<A[0]+A[1]+A[2] somebody has won three times before you did
Else you won before somebody else won three times

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 5:51 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
I just tried this with pennies and my table and I don't think it works.
P = 10. I used random.org to generate a bunch of random numbers, 0-9.
First number, 6. 6 < 9, so A[0] = 8, A[1] = 1.
Next number, 1. 1 < 8, so A[0] = 7, A[1] = 2.
Next number, 4. 4 < 7, so A[0] = 6, A[1] = 3.
Next number, 8. 8 !< 6, next 8 < 9, so A[0] = 6, A[1] = 2, A[2] = 1.
Next number, 6. 6 !< 6, next 6 < 8, so A[0] = 6, A[1] = 1, A[2] = 2.
Next number, 6. 6 !< 6, next 6 < 7, so A[0] = 6, A[1] = 0, A[2] = 3.

6 was done 3 times, so has won three times, yet we didn't make it to the third if statement. D:

Maybe I'm thinking through it wrong? Any idea?

Heck, if 6 wins three times at the start, and there's 10 players, this won't catch it. 6 < 9, 6 < 8, 6 < 7. D:

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 5:58 pm 
Online
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I worked through Tom's suggestion in my head and it sounded right to me. I was going to map everything into [0,1) and it would no longer be a true sim but it would be statistically correct. I'm in the middle of coding something for work but I'll probably take a stab at re-doing my sim with Tom's suggestion tonight.

By the way, using my sim with N = 10M, I get an expected value of 76.271 out of 10000 trials. That's quite a bit different than your 92. I didn't calculate the stddev or anything like that though so maybe our numbers aren't that far off?

_________________
Prior to using my real name I posted under the account named bmenrigh.


Last edited by Brandon Enright on Fri Jul 29, 2011 11:29 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 7:18 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
I do understand it now. I thought about it in the car while driving out to dinner. I will compare the two when I get home. Then off to model my tabletop.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 7:27 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
theVDude wrote:
6 was done 3 times, so has won three times, yet we didn't make it to the third if statement. D:
Maybe I'm thinking through it wrong? Any idea?
Heck, if 6 wins three times at the start, and there's 10 players, this won't catch it. 6 < 9, 6 < 8, 6 < 7. D:
That's because when you "move" a player from one part of the array to the next, it reorders the players' number. When you first picked player 6 and moved him to the next bucket, he is now player 10.

Nice catch Tom. Reminds me of counting sort.


PuzzleMaster6262 wrote:
Wouldn't it work better to do more simulations and less n values? The graph would be shorter but the quality of each point would be a lot better so that if your r2 value isn't almost 1 you know you have the wrong best fit line. Then you could do less simulations and more ns to see if this equation stays good.
I was thinking along the same lines so here's my results of an exhaustive search for a few small n.
Code:
People with 0 wins   /  Possible people when @ 3 wins = Percent%    n
          8/          64 = 12.5%  n=2
       1296/        6561 = 19.8%  n=3
     259968/     1048576 = 24.8%  n=4
   69860000/   244140625 = 28.6%  n=5
24818425920/ 78364164096 = 31.7%  n=6
Besides the 2nd number of each line, nothing struck me a pattern and nothing came up in the integer sequence database. Doing an exhaustive search takes a long time (the last one took me almost a day), so I decided to try it with when someone wins twice instead of thrice. Here's those results
Code:
          4/         16 = 25.0%  n=2
         90/        243 = 37.0%  n=3
       1824/       4096 = 44.5%  n=4
      38900/      78125 = 49.8%  n=5
     902880/    1679616 = 53.8%  n=6
   22954638/   40353607 = 56.9%  n=7
  638202880/ 1073741824 = 59.4%  n=8
I didn't see any immediate pattern here either. Didn't look too long though.

The only thing of interest is that the gcd of the numerator for 3 wins is 8, while it's only 2 for 2 wins. Oh, and both the numerator and denominator grow exponentially.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Thu Jul 28, 2011 8:03 pm 
Offline
User avatar

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
My approximation for the probability is:

p(n) = integral of (1-x^3*exp(-x)/6)^n*exp(-x), x from 0 to 1,

where n is the number of players. This approximation is good only for large n. I don't know how to evaluate the integral in closed form. I did a numerical integration and it seems to be close to bmenrigh's simulation.
Attachment:
Untitled-1.png
Untitled-1.png [ 4.21 KiB | Viewed 3886 times ]

The good thing to have a formula is that I can provide a value for n = 100,000,000. The probability is about 0.00349.

_________________
Check out some virtual puzzles I created at http://nan.ma


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Fri Jul 29, 2011 9:39 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Just tried out that logic that TomZ came up with. You want a random from 0, P. 0, P-1 makes it come up with 0 wins always. I'm not sure why, but it does.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Fri Jul 29, 2011 9:48 am 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
I don't think that's correct. A[0]+A[1]+A[2]=P-1, so if R is P-1 R<A[0]+A[1]+A[2] will evaluate to false and you will win. If you picked from [0,P] both P and P-1 would result in you winning (resulting in increasing your chance of winning by two).

Are you sure that you're using the random function correctly? In C#, Rand(P-1) would give an integer in [0,P-2] so you would need to call Rand(P) to get an integer in [0,P-1].

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Fri Jul 29, 2011 9:57 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Doh, of course. D: I've been making lots of silly mistakes lately. D: I forgot about that because I stuck a variable in instead of a number.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Fri Jul 29, 2011 10:16 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
Players?
100000000
Iterations?
10000
Took 167788.561786 ms
You won before someone else won 3 times 29 times out of 10000 times. (0.29%)

This is with math.Random, but the other easy options I have don't work well at work. This fits with what schuma said.

Players?
2147483647
Iterations?
10000
Took 1260494.273126 ms
You won before someone else won 3 times 13 times out of 10000 times. (0.13%)

Too lazy to start using longs, so here's 10000 iterations of a maxed int value.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Fri Jul 29, 2011 1:41 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
TomZ wrote:
I don't think you need an array that large. You could do with an array of length 3. Where A[0] is the amount of players who have never won, A[1] is the amount of players who have won once, A[2] is the amount of players who have won twice.

Initialize as A[0]=P-1, A[1]=A[2]=0, where P is the player count.

Pick a random number R in [0, P-1]

If R<A[0] increase A[1] by 1, decrease A[0] by 1
Else If R<A[0]+A[1] increase A[2] by 1, decrease A[1] by 1
Else If R<A[0]+A[1]+A[2] somebody has won three times before you did
Else you won before somebody else won three times
You can optimize this a little so you don't have to do as much math. For the sake of clarity, I'll call my array B so it's less confusing.
Initialize B[0] = B[1] = B[2] = P
This way, relative to Tom's array we have
B[0] = A[0]
B[1] = A[0] + A[1]
B[2] = A[0] + A[1] + A[2]

Pick a random number R in [0, P-1]
Iterate through B[i] until you find a B[i] such that R < B[i]. When you do, --B[i] and stop iterating.
You know when someone has won 3 times when B[2] != P

Here's some python I'm using (to lazy to create a project/whatever in faster language atm)
Code:
towin = 3
n = 1000000
c = 0 # fails
r = 100000 # trials
aa = [n] * towin # cache
for i in range(r):
    a = aa[:] # faster to make a copy than to create it
    while a[-1]==n and a[0]>0:
        j = random.randint(0,n-1) # endpoints are inclusive
        for k in range(towin): #check which bucket it goes in
            if j<a[k]:
                a[k] -= 1 #remove it from bucket
                break
print ( "%7.4f%%" % (100.0*c/((i+1)*n)) ),
print ( "%7.4f%%" % (100-100.0*c/((i+1)*n)) )

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Fair Lottery Puzzle
PostPosted: Sat Jul 30, 2011 12:07 pm 
Offline
User avatar

Joined: Wed Jun 22, 2011 4:57 pm
Location: The land of dreams, coincedentally located in Alberta
See, I'm used to Professor Layton puzzles, where there's always a solution you can find using only logic (not complex math).

Now I visit this forum, and every puzzle's solution involves at least 30 lines of code and one giant graph.

It's taking a while to sink in, I still believe that you can solve the fair lottery puzzle by writing a few things down and thinking about it (that's almost definitely false).

_________________
3x3x3 PB: 38.9 seconds
Well, I accumulated puzzles without even trying this Christmas. Whoops.
(Bermuda 8 planets, Rex Cube, Master Skewb, London Natural History Museum keychain 2x2x2, Impossiball)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 35 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group