Kyle Roth's Math 320 blog

I don't see the purpose of an indicator random variable, because I'm not sure what little omega and E represent in the definition for it. In general, I didn't understand the significance of showing that any Bernoulli random variable is the indicator of the function of some event. I'm also having a hard time understanding some of the variables in the equations for the Poisson distribution. But I can see how that distribution is applicable to many real life situations, because many events tend not to occur at the same time but spaced out. I think it will help to go over real life examples of these distributions and discuss what each variable means in that context. Then I'll get a sense of what they mean symbolically in the equations.

The idea of a probability mass function was kind of difficult to grasp, because I didn't see how adding those terms up would be interesting. But then I realized in the example that the sum of the probabilities was 1, meaning that this sum is like a weighted average value for the random variable. The most interesting part to me is how Bernoulli random variables could produce a binomial distribution, like when people first started realizing that successive dice rolls followed the normal curve. I'm sure these random variables are very applicable whenever involved in statistics or any kind of probabilistic modeling. And I can see how being able to apply functions to random variables and calculate the probability mass function for them could be very useful in trying to see how uncertain factors can affect outputs in a system.

Probability has been used for millennia, but not studied until the 16th century. It's funny that it took until Pascal and Fermat looked at probability of future events that they could find a solution for their game problem. It's really cool to see the quick development of probability and statistical theory as people noticed patterns and started applying them. I had no idea, but even the Romans and Greeks didn't look at probabilities at all! Overall, I see a general swing toward belief in order during the Enlightenment, and in the last century a swing back to belief in chaos and unpredictability of systems. I find it interesting that these belief swings occurred across many fields of study, not just mathematics. The speaker went on to discuss sensitive dependence on initial conditions. He discussed the Lorenz attractor, which hearkened back to when I took calculus 3 and differential equations. That was when I was most interested in mathematics for mathematics' sake. ...

The definition of independents for entire sets is eye-opening, because initially I didn't understand why all subcollections needed to be tested. The unexamples made it much clearer, but I got a little confused with the example given about Bernoulli trials. I understand the results (like how P(E_1 intersect E_2) is p^2) but I don't follow the calculations involved in getting there. I had never heard of the prosecutor's fallacy, but it makes total sense and I have totally fallen into it myself. I'll definitely notice from now on when someone makes that fallacy in their arguments. I've usually noticed selection bias in news reports and other information, but now that I know the actual definition and name and it'll be easier to spot and tell my friends. :P

Until now, I hadn't thought about the fact that probability problems become counting problems when all outcomes of length one have equal probability. I had used that fact to solve problems, but didn't realize what I was doing. I'm excited to use probability and statistics to understand machine learning algorithms from a mathematical perspective. In class I'd like to talk about when to use permutations and when to use combinations, when solving these equal-weight probability problems. I feel like it's still not clear to me which is used in what cases.

Today I saw a talk given by a lady who spoke on some research she does with the probability that two random integers are relatively prime. This has a visual representation in thin trees planted on lattice points of the Cartesian plane. There are interesting parallels between this representation and the idea of relative primality. For example, arbitrarily large squares of hidden trees on that graph can be found, and we know this because we can construct arbitrarily large sets of consecutive integers where any collection of elements of these sets (with one element from each set) is relatively prime. This is difficult to prove and has its roots in number theory. She presented everything in an exciting way which made it fun to listen to.

The two algorithms for the knapsack problem were a little difficult to understand, especially when it talked about the difference between pseudo-polynomial and regular polynomial complexity. Also, in  the section I didn't see a straight explanation of what NP-complete meant. I love the xkcd comics. I also thought it was interesting to see the debate among experts in different fields about whether P=NP, because it's so decisive in so many different problems that we are currently trying to solve. (See https://xkcd.com/664/.)

This section was simple to understand, and I think it would be cool to see how binary codes are used on a computer, or over the internet. I imagine there are lots of cases where Huffman encoding is important to the efficiency of many systems. The proof for the optimality of the Huffman algorithm is difficult to follow and a lot longer than I expected given the simplicity of the algorithm. I'd actually like to go over that proof in class (at least in outline form).

I thought the explanations were really good when the book talked about graphs where DFS is better versus graphs where BFS is better. I hadn't thought about it before, but the explanations made sense. I also appreciated the xkcd comics that explained some of the concepts. It was a little difficult to follow the proof for the fact that Dijkstra's algorithm always finds the shortest path. It would be nice to go over that in class to be able to understand it better.

Something that confused me was the difference between an optimal value and an optimizer. Remark 4.1.2 discusses that difference, but I'm at a loss for what those actually are. The example about Fibonacci numbers was really interesting, because I've build Fibonacci number generators in Python and Java but they always take forever for large inputs. But implementing the algorithm with memoization makes it work very quickly! It's a neat idea. In regards to the issue with spatial complexity, I feel like the high memory cost can be mitigated by working iteratively and deleting previous results. Of course, this wouldn't be effective if the program needed to run multiple times and wanted temporal savings after running multiple times. But this way the spatial complexity is constant because it only needs a variable to store the current n-value and two variables for the current Fibonacci number values. Also, the program could store just the results and the previous values (n a...

The proof for the temporal complexity of building a heap was a little difficult to read initially, but it makes sense that the complexity of heapifying should be less than adding nodes one at a time to an empty heap. I initially thought the heap didn't make sense, because there wasn't any order to the nodes. Heaps make a lot of intuitive sense, and they help me understand priority queues better. I'd like to learn how priority queues help solve shortest path problems.

This section is really interesting. I think it'd be need to try to write a program that handles a binary search tree with automatic rebalancing. I wonder why this would be a better representation of sorted data if we can already use a binary search algorithm on a sorted list. What I thought was the most difficult about this section was understanding all the algorithms for rebalancing in the different cases of imbalance. In class it would be nice to go over why we need to understand each of those cases, so we know how to rebalance a BST.

This section was pretty intuitive to understand. I see great value in understanding these different structures, so we can make programs that use these structures much more efficiently. It'll be interesting to see what we do in the lab that reflects these principles. Nothing in this section was particularly challenging, although the propositions at the beginning of the section were not obviously true to me at the onset. The proofs made sense, but I had never thought about those rules being true before.