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章で端的に説明されている。

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}\)について、

• \(r(p, q) = -r(q, p)\) [likeとdislikeの重みは等しく、符号は逆]
• \(p_1 < p_2\)ならば\(r(p_1, q) < r(p_2, q)\) [第一引数について狭義単調増加]
• \(q_1 < q_2\)ならば\(r(p, q_1) > r(p, q_2)\) [第二引数について狭義単調減少]
• \(p_1 p_2 q_1 q_2 \neq 0\)かつ\(p_1 : q_1 = p_2 : q_2\)ならば\(r(p_1, q_1) = r(p_2, q_2)\) [like/dislike比が同じなら同程度に好ましいとする]

つまり、この関数の値が大きいほど好ましさの順位が高いというものである。\(\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の数を上回っていた確率」と同じものである。

Archives