User kevin carde - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:17:57Z http://mathoverflow.net/feeds/user/2121 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7004/intuitive-explanation-to-probability-question/7015#7015 Answer by Kevin Carde for Intuitive explanation to Probability question Kevin Carde 2009-11-28T02:35:11Z 2009-11-28T02:35:11Z <p>I really like Vigleik's answer, but I'll throw in yet another way to look at your original problem. P<sub>x</sub> = (P<sub>x-1</sub>+P<sub>x+1</sub>)/2 is an example of a (discrete) harmonic function; i.e., a function whose value is the average of the adjacent values. In this case, P<sub>x</sub> is a harmonic function on a chain graph. For purposes of intuition, we can move from a discrete to a continuous line and think about the criterion for a function of one (real) variable to be harmonic: it is harmonic if and only if its second derivative vanishes; i.e., it's linear. This provides some intuition why your solution just linearly interpolates between 0 and 1.</p> <p>Your general problem of P<sub>x,y,p</sub> is no longer harmonic, so it will not have as easy a solution, as you may be discovering. For notational simplicity, I'll write P<sub>n</sub> for P<sub>n,y,p</sub> (preferring n as the index of a sequence to x). If you write down your new recurrence, you will get equations</p> <p>P<sub>n</sub> = (1-p)P<sub>n-1</sub>+pP<sub>n+1</sub></p> <p>subject to P<sub>0</sub> = 0, P<sub>y</sub> = 1. We can work with this, or we can use a trick. Let k = (1-p)/p (so p = 1/(1+k)). Then you can verify that</p> <p>P<sub>n</sub> = kP<sub>n-1</sub> + 1</p> <p>satisfies the original equation (with the additional freedom to scale all P<sub>n</sub> by a constant factor - we've broken the homogeneity of our original recurrence). [It actually takes some doing to verify this: consider using this new recurrence to write down P<sub>n</sub>-P<sub>n+1</sub>. When you solve that out for P<sub>n</sub>, you retrieve the original recurrence.]</p> <p>This is much easier to handle, with solution</p> <p>$P_n = \frac{k^n-1}{k-1}$.</p> <p>This gives P<sub>0</sub> = 0 as desired, but you'll need to scale down all solutions so that P<sub>y</sub> = 1.</p> http://mathoverflow.net/questions/6929/chances-of-streaks-in-small-bit-streams/6995#6995 Answer by Kevin Carde for Chances of streaks in small bit-streams Kevin Carde 2009-11-27T22:47:11Z 2009-11-27T22:47:11Z <p>I'm going to call your "streams" "strings" instead, because "streams" looks too much like "streaks" to me. This becomes a much easier problem if we translate it into an enumeration problem. Since each of the 2<sup>10</sup> possible bit strings occur with equal probability, it suffices to count the total number of streaks of length k in all these strings (and then as Kristal says just divide by 2<sup>10</sup> for the expected value per string). Let S(k,n) be the number of k-streaks in all strings of length n. For k = 1 we can make a straightforward recursion:</p> <p>$S(1,n) = 2S(1,n-1) + 2^{n-1} - 2^{n-2} = 2S(1,n-1) + 2^{n-2}$</p> <p>since for every n string, we have two copies of every (n-1)-string as a prefix (with their associated 1-streaks), plus half the time we add a new 1-streak at the end (if the bit we add at the end is different from the old last bit). Sometimes, though, we break a 1-streak at the end; this happens if our previous last bit was a 1-stream, so it happens once for each possible n-2 string as a prefix. (Note that this means the recursion requires n > 2!).</p> <p>This recursion is easy to solve; we have S(1,2) = 4 from which it follows $S(1,n) = (n+2)2^{n-2}$.</p> <p>Now there's a bijection between (k-1)-streaks in (n-1)-strings and k-streaks in n-strings (just add / remove another bit to the streak), so S(k-1,n-1) = S(k,n). We conclude</p> <p>$S(k,n) = (n-k+3)2^{n-k-1}$</p> <p>for k &lt; n, and S(n,n) = 2. For n=10, we have the sequence</p> <p>3072, 1408, 640, 288, 128, 56, 24, 10, 4, 2</p> <p>for streaks of length 1, 2, 3, ..., 10 out of the 2<sup>10</sup> = 1024 possible strings, so dividing through should give the expected number in a random string.</p> <p>The sequence S(1,n) is not in Sloane, but the total number of streaks in all n-strings $\sum_{k=1}^n S(k,n)$ is - this sequence starts 2, 6, 16, 40, 96, 224,... and has general form $\sum_{k=1}^n (n-k+3)2^{n-k-1} = (n+1)2^{n-1}$.</p> <p>This sequence <a href="http://www.research.att.com/~njas/sequences/A057711" rel="nofollow">A057711</a> apparently has quite a few combinatorial interpretations.</p>