Sorry. I didn’t mean for these to be “tell me the answers!” questions but rather “i thought these select questions were interesting and I didn’t know how to do it right off the bat, so while I work on it, I thought I’d share with the dope to see if they had insight” questions.
My personal take on this was to change the exponents to their base-10 equivalents, find the sum, then change it back into base-4 which is less grindsome.
Personally, I find that more grindsome. Why bother converting to base ten and back? That’s unnecessary work.
Ok, one from me:
There is a triangular garden with corners ‘A’ , ‘B’ and ‘C’. There is a bird at one of the corners. The bird flies to and instantly reaches another corner selected at random after every minute. If the starts at corner ‘A’, what are the chances of it reaching the same corner after 10 minutes?
Assuming that the bird has to pick a new corner every minute, it’s 171/512. I didn’t do anything clever–just set up the transition matrix of the appropriate Markov chain, and applied it to the appropriate initial distribution.
Correct!!
People who haven’t studied Markov chain (myself included:)) can solve this too. Should give it a try.
If you are at A at any moment, you are guaranteed to not be at A the next minute.
If you are not at A, you have 50-50 odds of being at A or not at A the next minute.
So, letting K be the proportion of birds at A minus half the proportion of birds not at A, we find that K multiplies by -1/2 every minute.
Thus, after 10 minutes, K is = (-1/2)^10 = 1/2^10.
From this, we can solve for the proportion of birds at A: p - (1 - p)/2 = 1/2^10, thus p = (1 + 2/2^10)/3 = (2^9 + 1)/3 * 1/2^9 = 171/512.
(This is in fact ultrafilter’s method, just made more layperson-friendly)
[Also, Jesus, the boards are sluggish right now…]
Put another way: let the proportion of birds at A be 1/3 + 2/3K (and thus the proportion of birds not at A be 2/3 - 2/3K).
After a minute, the birds at A will be half the ones who previously weren’t at A. This makes K multiply by -1/2 every minute, and so the answer is 1/3 + 2/3 * (-1/2)^10.
Good, this explaination is easier to understand than post#66.
I’d thought in following manner:
Let p(n) be the probability of bird being at ‘A’ after n minutes.
=> p(n-1) is the prob. that it was at ‘A’ after (n-1) minutes.
=> 1-p(n-1) : prob. that it wasn’t at ‘A’ after (n-1) minutes.
=> 1/2*(1-p(n-1)) : prob. that it was at ‘B’ after (n-1) minutes.
=> 1/4*(1-p(n-1)) : prob. that it reached ‘A’ via ‘B’ after n minutes.
and likewise, 1/4*(1-p(n-1)) : prob. that it reached ‘A’ via ‘C’ after n minutes.
So,
p(n) = 1/4*(1-p(n-1)) + 1/4*(1-p(n-1)) = 1/2*(1-p(n-1))
p(0) = 1 as bird starts from ‘A’.
Solving the equation above:
p(1) = 0, p(2) = 1/2, p(3) = 1/4, p(4) = 3/8, p(5) = 5/16, p(6) = 11/32, p(7) = 21/64, p(8) = 43/128, p(9) = 85/256, p(10) = 171/512
I’m going to quadruple post, because I still feel like the presentations above made things look like magic (it wasn’t clear why to pick that particular definition of K, except that it worked).
But there’s no such thing as magic. The methodical derivation is like this:
We know that, if p is the proportion of birds at A right now, then in a minute, it will be 1/2(1 - p) = 1/2 - 1/2p.
Thus, we just need to know how to quickly iterate the function f§ = 1/2 - 1/2p.
This function has the convenient property that changing its input by some amount will always change its output by -1/2 times that amount.
And it’s also easy enough to find a value which is left undisturbed by this function (specifically, 1/3).
Thus, we see that this function can be thought of as “Construe the input as 1/3 + delta, and scale the delta up by a factor of -1/2”. From which it’s clear that iterating the function N times amounts to “Construe the input as 1/3 + delta, and scale the delta up by a factor of (-1/2)^N”.
ETA: I originally posted this before I saw truthseeker2’s post #69. Yup, truthseeker2, that’s exactly right, though for large amounts of time, you won’t want to manually iterate through each minute one by one; that’s where the exponentiation trick comes in handy.
One could observe the pattern in numerator and denominator in this case.
For ex., denominator is always 2sup[/sup]
and numerator oscillates alternatively between smallest integer greater than 1/3rd of denominator and greatest integer smaller than 1/3rd of denominator.
therefore, without using the equation,
p(16) = 10923/32768 
One more:
A dice is rolled ‘n’ times. What are the chances of not getting any consecutive even outcomes(2,4,6) in ‘n’ throws?
Let P(n) be the probability of doing so.
If n is at least 2, then one either ends with an odd flip, or one ends with an odd flip followed by an even flip.
Thus, P(n + 2) = P(n + 1)/2 + P(n)/2[sup]2[/sup].
We could solve this recurrence directly, but you are probably more fond of its correspondence to another well-known recurrence relation; it is equivalent to 2[sup]n + 2[/sup] P(n + 2) = 2[sup]n + 1[/sup] P(n + 1) + 2[sup]n[/sup] P(n), and thus, 2[sup]n[/sup] P(n) is a Fibonacci-type sequence.
We also clearly have that P(0) = P(1) = 1. That is, P(0) = 1/2[sup]0[/sup] and P(1) = 2/2[sup]1[/sup].
So P(n) is the nth Fibonacci value divided by 2[sup]n[/sup], where the 0th Fibonacci value is 1 and the 1st Fibonacci value is 2.
Great. You are right, Indistinguishable (as usual).
I had made this question from thisquestion. People can refer to its solution for easier understanding.
I solved it by non-recursive approach. Will wait for people to also try it out through non-recursive approach.
I suppose enough time has passed that probably no one else is going to try it out. What is the non-recursive approach?
That’s another problem that’s solvable by a Markov chain, which counts the length of the current sequence of heads.
The transition matrix is given by
0.5 0.5 0
0.5 0 0.5
0 0 1
and the initial distribution is just (1, 0, 0).
Sure, I thought noone would have been interested.
x odd outcomes will make (x+1) slots for even outcomes. At most 1 even can come in a slot so that there are no consecutive even outcomes.
Example of 4 slots made by 3 odd outcomes:
_ O _ O _ O _
Let {n/2} represent largest integer less than or equal to n/2.
Let [n/2] represent smallest integer greater than or equal to n/2.
Fix the number of odd outcomes to compute the number of ways.
1.For n odd outcomes, 0 even outcomes, there are(n+1) slots for even outcomes. No. of ways such that there are no consecutive even outcomes=1=(n+1)C0
2.For n-1 odd outcomes, 1 even outcomes, there are n slots for even outcomes. No. of ways such that there are no consecutive even outcomes= nC1
3.For n-2 odd outcomes, 2 even outcomes, there are (n-1) slots for even outcomes. No. of ways such that there are no consecutive even outcomes= (n-1)C2
4.For n-3 odd outcomes, 3 even outcomes, there are (n-2) slots for even outcomes. No. of ways such that there are no consecutive even outcomes= (n-2)C3
…and so on till {n/2} odd outcomes.
Each of the above will have to be multiplied by 3^n since each of the n outcomes in every favorable sequence has 3 choices, either 1,3,5(odd) or 2,4,6(even)
Adding all:
Probability of getting no consecutive even outcomes in n dice rolls=
3^n((n+1)C0 + (n)C1 + (n-1)C2 + (n-2)C3…+({n/2}+1)C[n/2] ) / 6^n
where 6^n is total number of possible sequences from n dice rolls.
Cancel out 3^n.
Answer = ((n+1)C0 + (n)C1 + (n-1)C2 + (n-2)C3…+({n/2}+1)C[n/2] ) / 2^n