Mixing
what is the probability that a sequence is increasing?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us.
In a casino in Monte Carlo, you play at a very peculiar machine. The machine has $n$ wheels, each with $k$ possible values (not necessarily distinct). The wheels may be different from each other, that is it does not necessarily hold that every wheel has the same $k$ values on it.
When you activate the machine, each wheels lands in one of its $k$ possible values chosen uniformly at random and independently of all other wheels. You win a jackpot if the $n$ chosen values form an increasing sequence $x_1 leq x_2 leq dots leq x_n$ (the sequence does not need to be strictly increasing). You want to compute your chances of winning a jackpot.
My idea would have been to define the events: $A_i = ``x_i-1 leq x_i"$. So I have to calculate $P[A_2 & dots &A_N]$. I'm not sure but $P[A_i]$ must be: $P[A_i] = (k-z)/k * (1/k)$ ($z$ is the number that has been taken in $x_i-1$). But how do I calculate this probability? Does any one also have an idea how to implement it in Java? The master solution uses recursion, but I didn't get that part.
We have been given numbers to solve this problem: For example: we have two wheels and the number of different values each wheel has is 3.
Wheel 1 has the values: 1, 2, 3
Wheel 2 has the values: 1, 2, 3
The probability of an increasing sequence is 2/3
Another Example would be: we have two wheels, $k = 2$
wheel 1 = 1, 2
wheel 2 = 2, 2
probability is 1 :)
Thank you!!
probability algorithms computer-science
edited Jul 31 at 21:14
Clarinetist
10.3k32767
asked Jul 31 at 19:21
scalpula
32
add a comment |Â
up vote
0
down vote
favorite
I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us.
In a casino in Monte Carlo, you play at a very peculiar machine. The machine has $n$ wheels, each with $k$ possible values (not necessarily distinct). The wheels may be different from each other, that is it does not necessarily hold that every wheel has the same $k$ values on it.
When you activate the machine, each wheels lands in one of its $k$ possible values chosen uniformly at random and independently of all other wheels. You win a jackpot if the $n$ chosen values form an increasing sequence $x_1 leq x_2 leq dots leq x_n$ (the sequence does not need to be strictly increasing). You want to compute your chances of winning a jackpot.
My idea would have been to define the events: $A_i = ``x_i-1 leq x_i"$. So I have to calculate $P[A_2 & dots &A_N]$. I'm not sure but $P[A_i]$ must be: $P[A_i] = (k-z)/k * (1/k)$ ($z$ is the number that has been taken in $x_i-1$). But how do I calculate this probability? Does any one also have an idea how to implement it in Java? The master solution uses recursion, but I didn't get that part.
We have been given numbers to solve this problem: For example: we have two wheels and the number of different values each wheel has is 3.
Wheel 1 has the values: 1, 2, 3
Wheel 2 has the values: 1, 2, 3
The probability of an increasing sequence is 2/3
Another Example would be: we have two wheels, $k = 2$
wheel 1 = 1, 2
wheel 2 = 2, 2
probability is 1 :)
Thank you!!
probability algorithms computer-science
edited Jul 31 at 21:14
Clarinetist
10.3k32767
asked Jul 31 at 19:21
scalpula
32
2
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
1
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us.
In a casino in Monte Carlo, you play at a very peculiar machine. The machine has $n$ wheels, each with $k$ possible values (not necessarily distinct). The wheels may be different from each other, that is it does not necessarily hold that every wheel has the same $k$ values on it.
When you activate the machine, each wheels lands in one of its $k$ possible values chosen uniformly at random and independently of all other wheels. You win a jackpot if the $n$ chosen values form an increasing sequence $x_1 leq x_2 leq dots leq x_n$ (the sequence does not need to be strictly increasing). You want to compute your chances of winning a jackpot.
My idea would have been to define the events: $A_i = ``x_i-1 leq x_i"$. So I have to calculate $P[A_2 & dots &A_N]$. I'm not sure but $P[A_i]$ must be: $P[A_i] = (k-z)/k * (1/k)$ ($z$ is the number that has been taken in $x_i-1$). But how do I calculate this probability? Does any one also have an idea how to implement it in Java? The master solution uses recursion, but I didn't get that part.
We have been given numbers to solve this problem: For example: we have two wheels and the number of different values each wheel has is 3.
Wheel 1 has the values: 1, 2, 3
Wheel 2 has the values: 1, 2, 3
The probability of an increasing sequence is 2/3
Another Example would be: we have two wheels, $k = 2$
wheel 1 = 1, 2
wheel 2 = 2, 2
probability is 1 :)
Thank you!!
probability algorithms computer-science
edited Jul 31 at 21:14
Clarinetist
10.3k32767
asked Jul 31 at 19:21
scalpula
32
I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us.
In a casino in Monte Carlo, you play at a very peculiar machine. The machine has $n$ wheels, each with $k$ possible values (not necessarily distinct). The wheels may be different from each other, that is it does not necessarily hold that every wheel has the same $k$ values on it.
When you activate the machine, each wheels lands in one of its $k$ possible values chosen uniformly at random and independently of all other wheels. You win a jackpot if the $n$ chosen values form an increasing sequence $x_1 leq x_2 leq dots leq x_n$ (the sequence does not need to be strictly increasing). You want to compute your chances of winning a jackpot.
My idea would have been to define the events: $A_i = ``x_i-1 leq x_i"$. So I have to calculate $P[A_2 & dots &A_N]$. I'm not sure but $P[A_i]$ must be: $P[A_i] = (k-z)/k * (1/k)$ ($z$ is the number that has been taken in $x_i-1$). But how do I calculate this probability? Does any one also have an idea how to implement it in Java? The master solution uses recursion, but I didn't get that part.
We have been given numbers to solve this problem: For example: we have two wheels and the number of different values each wheel has is 3.
Wheel 1 has the values: 1, 2, 3
Wheel 2 has the values: 1, 2, 3
The probability of an increasing sequence is 2/3
Another Example would be: we have two wheels, $k = 2$
wheel 1 = 1, 2
wheel 2 = 2, 2
probability is 1 :)
Thank you!!
probability algorithms computer-science
edited Jul 31 at 21:14
Clarinetist
10.3k32767
asked Jul 31 at 19:21
scalpula
32
edited Jul 31 at 21:14
Clarinetist
10.3k32767
edited Jul 31 at 21:14
Clarinetist
10.3k32767
edited Jul 31 at 21:14
Clarinetist
10.3k32767
10.3k32767
asked Jul 31 at 19:21
scalpula
32
asked Jul 31 at 19:21
scalpula
32
asked Jul 31 at 19:21
scalpula
32
32
2
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
1
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40
add a comment |Â
2
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
1
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40
2
2
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
1
1
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
accepted
This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.
Suppose we have three wheels with the numbers $1,4,6,2,8, 14,4, 12, 27$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.
This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.
Let's assume that the data are given in an $ntimes k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $ntimes k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.
The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.
answered Jul 31 at 21:07
saulspatz
10.3k21324
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
add a comment |Â
up vote
0
down vote
This looks like a job for dynamic programming.
Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.
Then divide by $k^n$.
answered Jul 31 at 19:42
Henning Makholm
225k16290516
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.
Suppose we have three wheels with the numbers $1,4,6,2,8, 14,4, 12, 27$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.
This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.
Let's assume that the data are given in an $ntimes k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $ntimes k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.
The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.
answered Jul 31 at 21:07
saulspatz
10.3k21324
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
add a comment |Â
up vote
0
down vote
accepted
This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.
Suppose we have three wheels with the numbers $1,4,6,2,8, 14,4, 12, 27$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.
This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.
Let's assume that the data are given in an $ntimes k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $ntimes k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.
The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.
answered Jul 31 at 21:07
saulspatz
10.3k21324
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.
Suppose we have three wheels with the numbers $1,4,6,2,8, 14,4, 12, 27$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.
This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.
Let's assume that the data are given in an $ntimes k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $ntimes k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.
The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.
answered Jul 31 at 21:07
saulspatz
10.3k21324
This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.
Suppose we have three wheels with the numbers $1,4,6,2,8, 14,4, 12, 27$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.
This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.
Let's assume that the data are given in an $ntimes k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $ntimes k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.
The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.
answered Jul 31 at 21:07
saulspatz
10.3k21324
answered Jul 31 at 21:07
saulspatz
10.3k21324
answered Jul 31 at 21:07
saulspatz
10.3k21324
answered Jul 31 at 21:07
saulspatz
10.3k21324
10.3k21324
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
add a comment |Â
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages?
– Emannuel Weg
Jul 31 at 21:31
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example.
– saulspatz
Jul 31 at 21:36
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
Thank you very much! It now makes sense to me :)
– scalpula
Aug 3 at 18:10
It was my pleasure.
– saulspatz
Aug 3 at 18:11
It was my pleasure.
– saulspatz
Aug 3 at 18:11
add a comment |Â
up vote
0
down vote
This looks like a job for dynamic programming.
Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.
Then divide by $k^n$.
answered Jul 31 at 19:42
Henning Makholm
225k16290516
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
add a comment |Â
up vote
0
down vote
This looks like a job for dynamic programming.
Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.
Then divide by $k^n$.
answered Jul 31 at 19:42
Henning Makholm
225k16290516
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This looks like a job for dynamic programming.
Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.
Then divide by $k^n$.
answered Jul 31 at 19:42
Henning Makholm
225k16290516
This looks like a job for dynamic programming.
Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.
Then divide by $k^n$.
answered Jul 31 at 19:42
Henning Makholm
225k16290516
answered Jul 31 at 19:42
Henning Makholm
225k16290516
answered Jul 31 at 19:42
Henning Makholm
225k16290516
answered Jul 31 at 19:42
Henning Makholm
225k16290516
225k16290516
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
add a comment |Â
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :)
– scalpula
Jul 31 at 19:44
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability.
– Emannuel Weg
Jul 31 at 21:28
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868383%2fwhat-is-the-probability-that-a-sequence-is-increasing%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0
– Bram28
Jul 31 at 19:25
I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3
– scalpula
Jul 31 at 19:32
So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way)
– Rolazaro Azeveires
Jul 31 at 19:36
1
@RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers.
– Henning Makholm
Jul 31 at 19:40