Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[da_nang]

(exp(i*360°/n)-1) != 0

For n > 1.

[/nitpicking]

[frostshotgg]

Thanks for the explanations guys, it actually makes a lot of sense.

[ZetaX]

If f(x)=x^n+a_1·x^{n-1}+...+a_n is any monic polynomial, then -a_1 is the sum of its roots and (-1)^n a_n is their product by Vieta (who gives you several more fomrulas for the other coefficients). Use that on f(x) = x^n - a to see that the n-th roots of a sum to zero unless n=1.

[da_nang]

First off, I'm not sure whether to post this here or in the coding thread.

Anyways, onto my little complex problem.

The statement is simple, but execution is far from it AFAIK.
Basically, I want to generate a probability mass function. The probability concerns the following:

Say you have n∈ℕ\{0} events and you want to know what the probability of x events occurring is where 0 <= x <= n. Each event is a binary choice of true and false. The kicker? The probability of it being true follows an arbitrary probability sequence p_k where 1 <= k <= n is the occurrence index. In other words, if we call each event U_k∈{0,1} then P(U_k = 1) = p_k.

So, if X = U₁ + U₂ + ... + U_n, then the probability mass function is f(x) = P(X = x).

Easy to state on paper, but generating the values of f(x) is a pain. Now, if p_k = p where p is a constant probability, then this is a plain old binomial distribution. However,  since it's not constant, then it becomes a lot more complicated.


There are two algorithms I have that work. The first one:

• Generate all unique permutations of x 1s and n-x 0s.
• For each permutation i, generate a value m_i = m_i,n:
  
  • Base case: m_i,0 = 1
  • Recursive case: m_i,j = p_j*m_i,j-1 , when the jth symbol is a 1
    m_i,j = (1-p_j)*m_i,j-1 , when the jth symbol is a 0
• f(x) is thus the sum of all m_i.

The second one:

• Base cases:
  
  • m_n,x,1 = p_n
  • m_n,x,0 = 1-p_n
  • m_n,v,0 = m_n,w,1=  0 where {v,w} != {x,x}
  • m_z,v,0 =  m_z,w,1 = 0 where v > x, w > x, and z < n
• Recursive case:
  
  • m_i,j,0 = (1-p_i)(m_i+1,j,0 + m_i+1,j+1,1)
  • m_i,j,1 = p_i(m_i+1,j,0 + m_i+1,j+1,1)
• f(x) = m_1,0,0 + m_1,1,1

Technically, step 1.4. isn't necessary but it's there to prevent unnecessary backtracking.

In any case, both of these have horrible computational complexities. Just for the first one, the number of permutations is n!/(x!(n-x)!) and each of them needs to be parsed so the minimum complexity is n*n!/(x!(n-x)!) which I believe is O(n*n!). Sure, easy when n is small, but I'm interested when n is around 10-100. For n = 30 I couldn't be arsed to wait any longer. 20 is the maximum I've been willing to wait.

Then to spin it around even further, say I kept x fixed but varied n? What would the probability mass function g(n) be? Is it as simple as generating all the values with f(x) where n is varied and then dividing all values with the total sum?

Is there a way to make this faster? Knowing the structures of the probability mass functions would be nice but I don't necessarily care what the functions f(x) and g(n) look like as long as I can generate the values in a reasonable amount of time.

EDIT:

Alright, I might have a solution using probability generating functions. I'm a bit unfamiliar with this field so if anyone would be willing to chip in, be my guest.

Let U_k be an indicator variable for the kth event such that U_k∈{0,1} and P(U_k = 1) = p_k .
The PGF of U_k is G_Uk(z) = 1 - p_k + p_k z .

Now, let X_n = U₁ + U₂ + U₃ + ... + U_n . Since U_k are independent from each other, G_Xn(z) = G_U1(z)G_U2(z)G_U3(z)...G_Un(z).

And boy do the tests show rapid speed increase!

From there, P(X_n = x) = (d^x/dz^x)G_Xn(z)/x!
which should be easier to manage and give a representation of the probability mass function.

[MagmaMcFry]

As I understand it, your problem is as follows: Given n biased coins, each of which has its own probability p_i to land on heads, what is the probability of landing exactly k heads if you throw all of them once? Math says the following: Let p(n,k) be the probability of throwing k heads with the first n coins. Then p(n,k)=p_n*p(n-1,k-1)+(1-p_n)*p(n-1,k). With a direct recursion, you'll get O(2^n) recursive calls, which you don't want. But if you use memoized recursion, you'll only get O(k(n-k)) calls, which is obviously much better.
The probability mass function approach is actually isomorphic to the memoized recursion, except it can have a little unnecessary overhead (it's O(n^2)) when your k is much smaller or only a little smaller than your n. If k << n, you can throw away all monomials of degree > k when calculating G_Xn. If n-k << n, you can transform the problem by replacing all p_i by 1-p_i and then calculating p(n,n-k) instead of p(n,k), basically you count tails instead of heads.

[da_nang]

I'll have to program that into Matlab tomorrow, then!

Looking closer into the problem, it seems a Poisson Binomial distribution is at work here as the PGFs are identical. Now if only it had a neat closed-form PMF...

[da_nang]

Quick question:

If one shone a flashlight at flat wall at an angle such that an ellipse formed with semimajor and semiminor axes a and b respectively, would the light intensity follow a bivariate normal distribution centered at the center of the ellipse with standard deviations a and b in the x and y directions respectively and truncated to within the elliptical area?

[MagmaMcFry]

Nope. First of all, you're talking about irradiance, not intensity. Second, the closer half of the ellipse would get more light than the further half. Third, flashlights usually have a really weird light distribution (if you shine it directly at a wall, you get rings of brighter and less bright areas).

Here's a formula to help you calculate the irradiance from a point light source onto a specific point on a wall: E_e = I_ecos(α)/r², where E_e is the irradiance, I_e is the radiant intensity (the "brightness" of the torch in that direction), r is the distance, and α is the angle of incidence onto the wall.

[Skyrunner]

Is finding f(t) from this equation:

f'(t) = F/m₀ * 1/sqrt (1-(f(t))²/c²)

possible? O_o

[frostshotgg]

If I understand the way that's written correctly, flip everything over, divide by m0/F, then clean up a bit from there. I think your final answer will come out as +- f(t) because of square roots, but other than that it'll work. That looks vaguely like a physics equation, so you can just apply logic to determine the sign.

[Skyrunner]

But isn't it a differential equation? Don't you need to integrate somewhere?

[frostshotgg]

If you just want to solve for f(t), I don't think so. You'd have to integrate somewhere if the equation had d(whatever) somewhere in it. It's hard to tell in just a single line of text the way things are laid out.

[Skyrunner]

Is that better? Here, F, m₀, and c are all constants. The right side is the derivative of f(t), and the left side has f(t).

[frostshotgg]

Ah. That's much clearer. Yeah, I'm gonna let someone else explain it. If you just want the answer I can give it to you, but I suspect you want a thorough explanation and I'm terrible at explaining that particular part of calculus.

[crazysheep]

That looks like you need to solve a nonlinear differential equation..