fixedpoint.jp




2018/11/07

「月を入力すると日を返す多項式」と線形代数

"「月を入力すると日を返す多項式」と中国剰余定理"にあるような有理数係数の多項式は、わざわざ中国剰余定理を考える必要はなくラグランジュ補間で直接得られる。実際、SageMathの関数lagrange_polynomialが使える:

sage: R = PolynomialRing(QQ, 'x')
sage: p = R.lagrange_polynomial([(1,31),(2,28),(3,31),(4,30),(5,31),(6,30),(7,31),(8,31),(9,30),(10,31),(11,30),(12,31)])
sage: p
-11/907200*x^11 + 163/181440*x^10 - 37/1260*x^9 + 13481/24192*x^8 - 2055371/302400*x^7 + 240683/4320*x^6 - 28268521/90720*x^5
 + 85774775/72576*x^4 - 446998571/151200*x^3 + 46351537/10080*x^2 - 221017/56*x + 1416
sage: 

一般に、\(n+1\)個の相異なる実数\(x_0, x_1, ..., x_n\)と、\(n+1\)個の実数\(y_0, y_1, ..., y_n\)がそれぞれ任意に与えられたとき、\(n\)次以下の実数係数の1変数多項式\(p(x)\)で、各\(i = 0,1,...,n\)について\(p(x_i) = y_i\)となるものが一意に存在することが証明できる。しかも線形代数の知識で証明できることが、例えば「数学をいかに使うか」の第1章で端的に説明されている。

#permalink

2018/11/04

好き嫌い投票による順位付けと確率

YouTubeなどの動画配信サイトには、各動画について閲覧者が「好き(like)」、または「嫌い(dislike)」を投票する機能がある。この機能でlikeの数とdislikeの数を集計して得られるとして、動画を好ましい順に並べるにはどのようにすれば良いだろうか?

ただし、それぞれの投票は平等に扱うとするが、各動画ごとに投票総数(つまり、likeとdislikeを合わせた数)がまちまちであっても適用できる順位付けにしたい。具体的には、2引数(1つ目の引数がlikeの数、2つ目の引数がdislikeの数)の実数値をとる関数\(r: \mathbb{N}^2 \rightarrow \mathbb{R}\)で、以下のような条件を満たすものを考案する問題と考えることができる:

任意の\(p, p_i, q, q_i \in \mathbb{N}\)について、

つまり、この関数の値が大きいほど好ましさの順位が高いというものである。\(\mathbb{N}\)は0から始まるものとする。

上の条件を満たすような\(r\)の一例として\[r(p, q) =\begin{cases} p & \text{if } q = 0,\\ -q & \text{if } p = 0,\\ \frac{p-q}{p+q} & \text{otherwise.}\end{cases}\]がある。

特に\(p > q > 0\)のとき、Bertrand's ballot theoremから、この\(r(p, q)\)は「最初の投票から直近の投票までのどの時点においてもlikeの数がdislikeの数を上回っていた確率」と同じものである。

#permalink

Archives

2018: Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2017: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2016: Dec / Nov / Sep / Aug / Jul / Mar / Feb / Jan

2015: Dec / Oct / Sep / Jul / May / Mar / Feb

2014: Dec / Nov / Oct / Aug / Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2018 fixedpoint.jp