|
I've got another probability question. A bit similar to the last one I asked, but I'm still stumped.
The goal is to get to 0. If you are at some other number, you roll to see what number you to go next. Either you stay at your current number or you move up. You continue rolling until you get to 0.
See the chart below. The first number is the number you are at, and the second number is the number you can potentially go to, followed by the chance of getting there. So for example, if you are at 1 you have a 50% chance of rolling to 0 and stopping after 1 roll, and a 50% chance of staying at 1 and trying again.
1 => 0 (50%)
1 => 1 (50%)
2 => 0 (25%)
2 => 1 (50%)
2 => 2 (25%)
3 => 0 (12.5%)
3 => 1 (37.5%)
3 => 2 (37.5%)
3 => 3 (12.5%)
The question is: What is the expected number of rolls to get to 0 for each number? I already have the answers by simulation: 1 = 2, 2 = 2.667, 3 = 3.144. But I'm stumped as to how to actually calculate that.
Calculating at 1 is easy. Without even having to do any calculations, you can easily see that if you have a 50% chance of winning, you will win on average 2 times.
Calculating 2 is trickier. You have a 25% chance of rolling 0, therefore ending in 1 roll. You have a 50% chance of rolling to 1. Since I already know the expected value at 1 is 2 rolls, that means at 2 you have a 50% chance of winning after 3 rolls. But what is the value if you roll from 2 to 2? There's a convergence there that I'm not sure how to calculate. Any help would be appreciated. Thanks!
|
Edit: Okay Im not typing this, sorry.
Hope you can read my scribbling  Not sure why our results are different for 3.
If you have any questions, please ask and I can elaborate more if needed.
![[image loading]](https://i.imgur.com/FkLyGJw.jpg)
|
Whoops, that should've been 3.14 for 3, not 4.14. Thanks, let me see if I can figure out your hand written notes :D
|
Sounds like a typical get-a-hypothesis-by-juggling-with-numbers-into-proof-by-induction exercise: Basically:
E[W_n]= 1/(n+1)* (E[W_n]+...+E[W_1]+E[W_0]), which means you can calculate E[W_n] if you know all "lower" expected values.
However, now that I read your numbers again, it seems that not every number has the same probability? You should definitely explain what the number of rolling x is when you can roll numbers up to n. Do you mean to say you can only roll 0 or 1 and then subtract the result from n? In any case, you should be able to modify the recursive formula to get get proof by induction/recursion.
Edit: Ok my formula is wrong, take the one from the screenshot it the post above. The idea should still stand.
Edit: Also, 22/7 would round to 3,142 or 3,143 but never 3,144. Is that just a typo?
|
On July 17 2018 05:51 Mafe wrote:You should definitely explain what the number of rolling x is when you can roll numbers up to n. The context is that I'm trying to solve the problem here: https://projecteuler.net/problem=323.
I'm looking at a smaller example, a 4-bit number instead of 32-bit. Take a number from 0 to 2^4-1 and convert it to binary. If in binary a number has one 0 and three 1's, what is the probability that a bit-wise OR against another 4-bit number will yield a number with all four 1's (15)? It's 50%. The chart I provided earlier is the probability of going from a 4-bit number with x 0's to a 4-bit number with y 0's. Since it's a bitwise OR operation, you will never lose 1's.
I'm sure there are better approaches to the problem, but this is the direction I'm trying to solve it from. In fact, it's looking like I should probably try a different approach, as it's quite complicated to determine those probabilities.
Edit: Also, 22/7 would round to 3,142 or 3,143 but never 3,144. Is that just a typo? It was just a guess from the results of my simulation. You're correct mathematically, but my simulated results would vary further than just a rounding error.
|
Aren't the bits completely unrelated in that situation? Meaning you can take the problem as 32 copies of the 1 bit problem and then recombine them later on?
Possible idea for a approach not completely thought through
+ Show Spoiler + A single bit has a probability of P0(n) = 1/2^(n+1) to NOT be a 1 after n operations. And P1(n) is thus 1-(1/2^(n+1))
32 such bits thus have a probability of at least one of them not being a one of 1-(P1(n))^32. Maybe it is possible to somehow get an expected value out of this.
Though i am slightly confused by the "rounded to 10 digits after the decimal point" thingy. That implies some sort of numerical or simulationary approach in my opinion, because why would you want 10 digits if either the result could be described as an exact number in some way (fraction, roots or whatever) or the point is just a mathematical approach.
|
On July 17 2018 06:57 Simberto wrote:
Aren't the bits completely unrelated in that situation? Meaning you can take the problem as 32 copies of the 1 bit problem and then recombine them later on?
yes , at first sight it looks like you could model this problem with i.d.d. random variables , then regard the 1-dim case and multiply your way up from there
|
Yeah I'm pretty sure there are better ways to solve it. This just kinda how I started it, so I wanted to see how far I can get. You guys helped me out, I got exactly what I needed. Thanks!
|
good luck
|
Solved it! ![[image loading]](https://i.imgur.com/lSPO4mg.png)
Thank you all for your help
|
been a while and I am expected to know the answer to these combinatorics problems. I have a couple im pretty unsure about.
#1.) There are 5 circles, 8 squares, 2 triangles, and 7 lines. 4 shapes are chosen at once.
how many ways can we get at most 2 circles?
my answer: count the ways to get 0 circles, 1 circle, and 2 circles
0 = (17 choose 4)
1 = (5 choose 1)*(16 choose 3)
2 = (5 choose 2)*(15 choose 2)
then add those up. is this right?
2.) given a binary string of length 15, 4 of the positions are set to 1 (at random). the rest are zero. how many strings can be made that have no ones next to each other?
-wtf, I have no idea how to do this :/
3.) similar to #2. We have 4 As, 3 Bs, 2 Cs, 1 D, 1 E. We use all the letters to form a word at random (all letters must be used).
How many words contain no Bs next to each other?
i also have no idea how to do this one, it seems very similar.
|
For #1, why is it 16 and 15 instead of 17s?
|
your Country52798 Posts
I know how to do #1 and maybe #2. #3 I thought I had but some smaller examples have convinced me otherwise. I suspect I will be able to get it more easily in the morning - a bit rusty at this.
For #1 I think you're supposed to assume that all similar shapes are the same, so choosing circle #1 results in the same outcome as if you chose circle #2, for example. In that case, you should set up some kind of linear equation that satisfies the condition (picking exactly 4 shapes from 4 types of shapes), include restrictions on the number of circles and triangles you have, and figure out the number of solutions to that equation.
For #2, I think I solved it correctly by assuming that every 1 is either the first digit in the string or preceded by a 0. Therefore, you can break up the problem into 2 cases — one where the first digit is 1, and one where the first digit is 0 — and figure out the number of ways in each case to rearrange the appropriate number of 0s and "01"s. For example, in the first case, the first digit must be 1, after which point you have three "01"s and 8 other 0s.
|
On September 07 2018 13:00 DarkPlasmaBall wrote:
For #1, why is it 16 and 15 instead of 17s?
This. Also a bit rusty, but shouldn't you multiply the second line by 4, and the third line by 6, because the order in which that happens doesn't matter?
For #2, seems like you can solve that with dynamic programming. The chance of having 2 1s next to one another is:
Let c1 be the chance the first digit is 1, and c2 be the chance the 2nd digit is 1, given that the first digit is 1.
double1(total, 1s) = c1 *(c2 + (1-c2)*double1(total -2, 1s -1) + (1 - c1)*double1(total -1, 1s)
double1(_, 0) = 0
double1(1, _) = 0
For any total and 1s, c1 = 1s/total and c2 = (1s -1)/(total - 1)
Your answer is 1 - double1(15, 4).
#3 is identical to 2. Bs are 1s and all other letters are 0s.
|
Concerning #1: I am guessing we do not distinguish the circles, etc. from one another? That'd make for a whole lot more possibilities.
#2: the way these problems are usually handled are that you imagine the 11 zeros side by side and the 4 ones as 'partitioners' which you can place at any of the 12 positions in between the zeros or to either side. Think of it as 11 blue cars parked in a row. You now want to park your 4 red cars. The first one you can put in between two blues (10 spaces) or in front of all or in the back of all, makes a total of 12 possibilities. For the next car you have one less possibility, etc.
If all the red cars were different you would have 12*11*10*9 possibilities. But you cannot distinguish between two red cars so you have to account for that. This leads to 12 over 4 as your end result. (drawing without putting back, without caring for oder, binom coefficient)
|
I wrote it in Python. For my dynamic programming solution, I get:
1 - 0.6373626373626374 = ~36%
Using Kleinmuuhg's method, the probability is (12 over 4)/12⁴ = 0.02387152777
What am I doing wrong?
E: I also just saw that the question is not about the probabilities, but the actual combinations. Either way, there is something wrong somewhere :D
E2: checking it for strings of length 3 and 2 1s, I think it's clear that both kleinmuuhg and my method work, but I fucked up on the total number of possiblities. It isn't 12⁴, it's 15 choose 4. And then it all works.
|
A simple recursive Python solution for #2 that seems to produce reasonable results:
def get_count(zeros, ones):
if ones == 0: # Nothing, or only 0s left
return 1
if ones == 1: # A single 1 can be placed in multiple positions
return zeros + 1
if zeros == 0: # All other combinations require 0s to work
return 0
# The remaining string starts with either 0 or 10
return get_count(zeros - 1, ones) + get_count(zeros - 1, ones - 1)
get_count(11, 4)
Not sure it's correct, but this gives a result of 495.
|
For #1:
+ Show Spoiler +((17/22)*(16/21)*(15/20)*(14/19))
+ ((5/22)*(17/21)*(16/20)*(15/19))
+ ((5/22)*(4/21)*(17/20)*(16/19))
= 0.472544999
Out of 175560 total combinations, that comes to 82960/175560.
For #2:
+ Show Spoiler +This can be solved by means of simple dynamic programming. Basically, the number of ways of selecting x number of 1's from a binary string of length y is the sum of the number of ways of selecting x - 1 number of 1's from a binary string of length y - 2 for all of x. Here's my c# code: private int Solve(int maxSize, int maxCount) {
int[,] data = new int[maxSize + 1, maxCount + 1];
for (int spot = 1; spot <= maxSize; spot++) {
data[spot, 1] = 1 + data[spot - 1, 1];
for (int count = 2; count <= maxCount; count++) {
for (int position = spot; position - 2 >= 1; position--) {
data[spot, count] += data[position - 2, count - 1];
}
}
}
return data[maxSize, maxCount];
}And the results: Solve(15, 4) = 495
Edit: #2 isn't the same as #3, my bad
|
#3 can't be trivially reduced to #2 since "abc" and "cba" are still distinct words even if the only "b" is always second.
The solution should be pretty straightforward with combinatorics. Anyhow, in Python (combined with the solution for #2):
def get_word_count(letter_counts):
if sum(letter_counts.values()) == 1:
return 1 # Only one letter left
def sub_count(letter):
if letter_counts.get(letter) == 0:
return 0 # Invalid letter to continue with
else:
return get_word_count({k: (v - 1 if k == letter else v) for k, v in letter_counts.items()})
return sum([sub_count(letter) for letter in letter_counts.keys()])
get_count(8, 3) # Distinct positions of b
get_word_count({'a': 4, 'c': 2, 'd': 1, 'e': 1}) # Different words "around" b:s
For a result of 70560.
|
On September 08 2018 03:43 BByte wrote:
#3 can't be trivially reduced to #2 since "abc" and "cba" are still distinct words even if the only "b" is always second.
You are correct! I was a little too excited and glossed over that fact.
Curious though, do we know if the problem is asking for how many distinct words? Since my solution finds all the distinct ways of arranging B's so they're never next to each other, then it's just a couple quick calculations based on whether or not the problem is asking for only distinct solutions. Your number is likely right since it's divisible by 84 :D
|
|
|
|
|
|
EPT
