1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Interesting Probability problem and maybe binomial theorem

  1. Sep 13, 2015 #1
    1. The problem statement, all variables and given/known data
    For reference, this is the image setting up the problem.
    "A wireless sensor grid consists of 21×11=231 sensor nodes that are located at points (i,j) in the plane such that i∈{0,1,⋯,20} and j∈{0,1,2,⋯,10} as shown in Figure 2.1. The sensor node located at point (0,0) needs to send a message to a node located at (20,10). The messages are sent to the destination by going from each sensor to a neighboring sensor located above or to the right. That is, we assume that each node located at point (i,j) will only send messages to the nodes located at (i+1,j) or (i,j+1). How many different paths do exist for sending the message from node (0,0) to node (20,10)?"

    Problem 11
    In Problem 10, assume that all the appropriate paths are equally likely. What is the probability that the sensor located at point (10,5) receives the message? That is, what is the probability that a randomly chosen path from(0,0) to (20,10) goes through the point (10,5)?

    Problem 12
    In Problem 10, assume that if a sensor has a choice, it will send the message to the above sensor with probability pa and will send the message to the sensor to the right with probability pr=1−pa. What is the probability that the sensor located at point (10,5) receives the message

    2. Relevant equations
    C(n k) = n! / k!(n-k)!
    P(A) = |A| / |S|
    P(A) = C(n k)(Pan)((1-(Pa))n-k

    3. The attempt at a solution

    This is an extension of a previous homework probleem i did.
    I know that the answer to problem 10 is:

    C(30 20)

    So this is 'given.' The justification by the professor was that you have 30 necessary routes (20 to the right and ten to the top) and so you have to choose 20 of them (or ten of them) and subsequently you will get the remaining segment as well.

    Problem 11 is a simple rendition of this one. I worked it out with my friend and we concluded fairly confidently that if you had 30 routes and needed to know the probability of getting it through the middle then you would have to a separate cardinality of C(15 10). This would grant you all of the possible ways to get to the midddle sensor. Using the probability theorem,

    P(A) = |A|/|S| = C(10 ) / C(30 20) ≈ 9.99e-5

    Problem 12 is the catch. We did not know where to even go with this one. We found some answers that were basically way too large for what we thought we were searching for.
    This was my solution, derived from the binomial theorem where i have n bernoulli trials and k successes, where a success is given by a shift to the right so that my exponents maintained the direction i intended to go:

    P(A) = C(15 10)(0.510)(0.55)

    The point five was to mirror the results from problem 11. I called these bernoulli trials because each sensor was independant of the previous one for k < 20, because obviously once it reaches the edges it no longer has a choice. This yieled an answer different from the result of problem 11, and my friend who REALLY enjoys math could not figure this out. I believe the flaw in my answer is that it's an inappropriate rendition of the bernoulli trials, and thus the binomial theorem does not count. However, my friend began charting out the probability of reaching each sensor independantly and it seemed like that was the right direction to head towards. So I'm at a loss.

    My professor said to study from the book for the exam and that his goal was to make everybody make a 50 on his tests. So something like this showing up on my intro to stats class is very real fear of mine. If anyone could shed some light on this type of counting method, I'd be greatly appreciative.
  2. jcsd
  3. Sep 13, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    It gives your all possible ways to reach the middle sensor. What about the number of ways to go from there to the final target?

    Also, a simple cross-check: you can draw lines of 20-30 sensors where the signal has to reach at least one. The middle one is certainly one with many options. How could just 0.0001 of all paths cross it?

    The answer to problem 12 is right (if you generalize it), the disagreement with (11) mainly comes from the wrong answer there.
    Note that the two problems won't give exactly the same answer. Some nodes will send the signal in a specific direction with probability 1 (because they are at the (edit) upper or right edge), so not all paths will have the same probability.

    Edit: fixed orientation of edges
    Last edited: Sep 13, 2015
  4. Sep 13, 2015 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    For Problem 12, you need to get from (0,0) to (10,5), so need to take 10 steps right and 5 steps up, for a total of 15 steps. Think, instead, of tossing a biased coin 15 independent times, with P(heads) = pr and P(tails) = 1 - pr on each toss. You want the probability of getting 10 heads in 15 tosses. Have you not seen such problems before?

    By the way: even when reaching an edge there is still a choice: from the bottom edge it can still go up or right, and from the left edge it can still go up or right. Where you run into trouble is along the right or top edges, but for paths stopping at (10,5) this is not an issue. Interestingly, though: it would be an issue for paths stopping at (20,10), or even at (n,10) with n < 20 or (20,m) with m < 10.
    Last edited: Sep 13, 2015
  5. Sep 13, 2015 #4
    Thanks! I didn't think that maybe problem 12 would be right and problem 11 would be wrong. I guess that makes sense. I'm still grappling with what "believable" numbers should be.
    As for problem 11, I'm stuck in this regard: If I have C(30 20) combinations of getting to the top right, then theoretically I'd have
    C(15 10) ways to get to the middle one. I justify this by using the same logic we got the 30, 20. We have 10 to the right and 5 upwards for a total of 15, and we're choosing ten as ones of interest. FROM the middle node then, we'd have the same situation: Ten and 5 more to go. This would imply the result to be:
    (C(15 10) C(15 10)) / C(30 20).
    However the answer is way too large now if problem 12's answer is right. .

    That's the analogy I used to get to problem 12! :D I really haven't spent much of any time on statistics or probability since high school, and even then only for a few weeks or so, I'm afraid. My mathematics are very stunted in terms of early education. I've learned most of it since college. So I apologize for my slowness sometimes. I try to connect everything to similarities and metaphors because those are what I used most of my life to explain the world.

    The right and top edges were the ones i thought this would fall apart on. At that point we lose our fair coin and it is constrained by a prior rule. However, in this problem I do not have to calculate that far out i don't think.

    Also, and this isn't quite the problem, I'm having a little difficulty visualizing what combinations mean in this instance. In examples where you draw a hand from a deck of cards and are searching for aces or something, I visualized it as you have 52! decks of cards, you divide out these decks by all of the ways the segment below your hand could be (because you simply don't care) and then you divide out the number of ways you could get your hand. In this case, I can't easily make the visualization. I'm trying to view it from the perspective: k!C(n k) = P(n k). So I'm starting with what a permutation of these sensors would look like and then extrapolate from there.
  6. Sep 13, 2015 #5


    User Avatar
    2017 Award

    Staff: Mentor

    Well, the answers are different for the reason I mentioned.

    You have 30 "steps" in your deck, 20 of them are "to the right", 10 "up".
  7. Sep 13, 2015 #6
    Oh wow. I think I may actually be beginning to understand this stuff. Thank you! That's why we divide twice, because we are not interested in all of the different permutations of heading to the right. We're simply interested in the fact that they do.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted