אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

This talk will cover two topics:
First, we suggest a new interpretation of Spearman correlation using k-subset permutations. We characterize the distribution of the Spearman correlation of a permutation that starts with the identity permutation over n elements and is perturbed by uniformly shuffling a random subset of k indices. We present some key aspects of this distribution, including its expected value and variance for every k between 1 and n. We then generalize it to any starting vector.
In the second part of the talk, we define a generalization of the ‘Coupon Collector’ problem dubbed ‘Edge Collector’, where we are given two sets A and B of the same size, and a perfect matching between them. At each step we draw a pair of elements from A, and get their pair of matching elements in B. However, we do not know which element from the first pair corresponds to which element in the second. Using a Markov process, we find a recursive formula and an estimation for the expected number of steps needed to determine all the matchings.