Answer by Kevin Carde for Intuitive explanation to Probability question

2009-11-28T02:35:11Z

I really like Vigleik's answer, but I'll throw in yet another way to look at your original problem. P_x = (P_x-1+P_x+1)/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_x 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.

Your general problem of P_x,y,p 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_n for P_n,y,p (preferring n as the index of a sequence to x). If you write down your new recurrence, you will get equations

P_n = (1-p)P_n-1+pP_n+1

subject to P₀ = 0, P_y = 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_n = kP_n-1 + 1

satisfies the original equation (with the additional freedom to scale all P_n 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_n-P_n+1. When you solve that out for P_n, you retrieve the original recurrence.]

This is much easier to handle, with solution

$P_n = \frac{k^n-1}{k-1}$.

This gives P₀ = 0 as desired, but you'll need to scale down all solutions so that P_y = 1.

Answer by Kevin Carde for Chances of streaks in small bit-streams

2009-11-27T22:47:11Z

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¹⁰ 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¹⁰ 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:

$S(1,n) = 2S(1,n-1) + 2^{n-1} - 2^{n-2} = 2S(1,n-1) + 2^{n-2}$

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

This recursion is easy to solve; we have S(1,2) = 4 from which it follows $S(1,n) = (n+2)2^{n-2}$.

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

$S(k,n) = (n-k+3)2^{n-k-1}$

for k < n, and S(n,n) = 2. For n=10, we have the sequence

3072, 1408, 640, 288, 128, 56, 24, 10, 4, 2

for streaks of length 1, 2, 3, ..., 10 out of the 2¹⁰ = 1024 possible strings, so dividing through should give the expected number in a random string.

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}$.

This sequence A057711 apparently has quite a few combinatorial interpretations.

User kevin carde - MathOverflow

Answer by Kevin Carde for Intuitive explanation to Probability question

Answer by Kevin Carde for Chances of streaks in small bit-streams