View unanswered posts  View active topics

Page 1 of 1

[ 35 posts ] 

Author 
Message 
theVDude

Post subject: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 1:35 pm 

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."
Last edited by theVDude on Sun Jul 24, 2011 1:55 pm, edited 1 time in total.


Top 


wwwmwww

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 1:43 pm 

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
_________________ 


Top 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 1:55 pm 

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."


Top 


elijah

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 2:06 pm 

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 offtopic"
"You are actually more off topic than me, you mentioned something on topic in the Off Topic forum."
"You more so for discussing the ontopic "offtopic" topic in the offtopic forum."


Top 


eye2eye

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 2:41 pm 

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 


wwwmwww

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 3:01 pm 

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.
_________________ 
Last edited by wwwmwww on Sun Jul 24, 2011 3:13 pm, edited 1 time in total.


Top 


TomZ

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 3:08 pm 

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 


wwwmwww

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 3:20 pm 

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
_________________ 


Top 


Jared

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 7:49 pm 

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 


gingervergo

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 8:02 pm 

Joined: Fri Mar 06, 2009 9:23 pm


Top 


Brandon Enright

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 8:13 pm 

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 


Allagem

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 8:49 pm 

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 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! 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 XB draws. The probability of all these events happening together is: (X choose B) * (1/N)^B * (1/N) * (N2/N)^(XB) 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 Peace, Matt Galla


Top 


Iranon

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 9:44 pm 

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 


Allagem

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 9:53 pm 

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 


Brandon Enright

Post subject: Re: Fair Lottery Puzzle Posted: Sun Jul 24, 2011 9:54 pm 

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 XB draws. The probability of all these events happening together is: (X choose B) * (1/N)^B * (1/N) * (N2/N)^(XB) 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 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 


chris the cynic

Post subject: Re: Fair Lottery Puzzle Posted: Mon Jul 25, 2011 7:30 am 

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 (N1)*2+1. N includes you, but X is the number of drawings before you win, so there are only N1 possible winners in said drawings.


Top 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Mon Jul 25, 2011 10:19 am 

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 oneinahundredmillion 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."
Last edited by theVDude on Thu Jul 28, 2011 2:53 pm, edited 1 time in total.


Top 


Brandon Enright

Post subject: Re: Fair Lottery Puzzle Posted: Mon Jul 25, 2011 5:20 pm 

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 [ 7.26 KiB  Viewed 3529 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 48bit 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 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Tue Jul 26, 2011 12:58 pm 

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."


Top 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 11:41 am 

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."


Top 


PuzzleMaster6262

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 12:07 pm 

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 


Brandon Enright

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 12:14 pm 

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/MultiplywithcarryJust 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 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 2:49 pm 

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! 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."


Top 


TomZ

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 3:39 pm 

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]=P1, A[1]=A[2]=0, where P is the player count.
Pick a random number R in [0, P1]
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 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 5:51 pm 

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, 09. 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."


Top 


Brandon Enright

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 5:58 pm 

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 redoing 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 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 7:18 pm 

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."


Top 


GuiltyBystander

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 7:27 pm 

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 


schuma

Post subject: Re: Fair Lottery Puzzle Posted: Thu Jul 28, 2011 8:03 pm 

Joined: Thu Jul 23, 2009 5:06 pm Location: Berkeley, CA, USA

My approximation for the probability is: p(n) = integral of (1x^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:
Untitled1.png [ 4.21 KiB  Viewed 3323 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.


Top 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Fri Jul 29, 2011 9:39 am 

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, P1 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."


Top 


TomZ

Post subject: Re: Fair Lottery Puzzle Posted: Fri Jul 29, 2011 9:48 am 

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]=P1, so if R is P1 R<A[0]+A[1]+A[2] will evaluate to false and you will win. If you picked from [0,P] both P and P1 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(P1) would give an integer in [0,P2] so you would need to call Rand(P) to get an integer in [0,P1].
_________________ 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 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Fri Jul 29, 2011 9:57 am 

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."


Top 


theVDude

Post subject: Re: Fair Lottery Puzzle Posted: Fri Jul 29, 2011 10:16 am 

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."


Top 


GuiltyBystander

Post subject: Re: Fair Lottery Puzzle Posted: Fri Jul 29, 2011 1:41 pm 

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]=P1, A[1]=A[2]=0, where P is the player count.
Pick a random number R in [0, P1]
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, P1] 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,n1) # 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%%" % (100100.0*c/((i+1)*n)) )
_________________ Real name: Landon Kryger


Top 


GoombaGeek

Post subject: Re: Fair Lottery Puzzle Posted: Sat Jul 30, 2011 12:07 pm 

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 



Page 1 of 1

[ 35 posts ] 

Who is online 
Users browsing this forum: No registered users and 2 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


